Algorithm | Data structure/Theory
-
Sorting(선택정렬, 삽입정렬, 퀵정렬, 계수정렬)Algorithm | Data structure/Theory 2023. 5. 10. 02:17
Sorting ✅ 정렬이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것 ✅ 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용된다. 데이터의 개수가 적을 때, 혹은 데이터의 개수가 많지만 특정 범위로 한정되어 있을 때, 이미 데이터가 정렬되어 있을 때 등 선택정렬(Selection sort) 알고리즘 ✅ 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복한다. 첫 번째 요소를 가장 작은 값이라고 가정하고 저장한다. 더 작은 수를 찾을 때까지 가장 작은 값(가정)을 값을 비교하지 않은 나머지 배열의 요소들과 비교한다. 더 작은 숫자가 발견되면 더 작은 숫자를 새로운 "최소값"으로 저장하고 배열이 끝날 때 까지 이 과정을 반복한다. 배열의 끝..
-
QueueAlgorithm | Data structure/Theory 2023. 4. 26. 20:53
Queue 큐란? 스택의 반대 개념이다. 데이터 접근 방법은 선입 선출(FIFO, First In First Out)이다. 이러한 구조이기 때문에 마지막에 삽입한 요소를 삭제하기 위해서는 앞의 모든 요소가 삭제되어야 한다. 주로 순서를 보장하기 위한 처리가 필요할 때 사용되는 자료구조이다. 시간복잡도 삽입과 삭제는 큐는 선입 선출 구조이기 때문에 O(1)의 시간 복잡도를 가진다. 검색은 큐 안의 데이터를 찾을 때 까지 진행되기 때문에 O(n)의 시간복잡도를 가진다. 큐 예시 네트워크 연결 상태 Check setInterval(() => { if (!checkNetwork()) { // 네트워크 끊어짐 }; }, 1000); function checkNetwork() { if (네트워크 연결 되었음) { ..
-
StackAlgorithm | Data structure/Theory 2023. 4. 26. 20:52
Stack 스택이란? 데이터를 순서대로 쌓는 자료구조 입력과 출력이 하나의 방향으로 이루어져 접근이 제한적 입력과 출력은 후입 선출(LIFO, Last Input First Out) 방식이다. 아래가 막혀있고 위가 뚫려있는 구조로, 데이터가 차곡차곡 쌓이는 구조 이러한 구조 때문에, 마지막에 삽입된 요소만을 삭제할 수 있다. Stack에서 삽입은 push, 삭제는 pop이라는 용어를 사용한다. 시간복잡도 삽입과 삭제는 스택은 후입 선출 구조이기 때문에 O(1)의 시간 복잡도를 가진다. 검색은 스택 안의 데이터를 찾을 때 까지 진행되기 때문에 O(n)의 시간복잡도를 가진다. 스택 예시 Javascript call stack(호출 스택) 자바스크립트는 단일 스레드 프로그래밍 언어이므로 단일 호출 스택을 사용..
-
DFS(Depth-First Search)Algorithm | Data structure/Theory 2023. 4. 11. 14:27
DFS(Depth-First Search) DFS는 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 DFS는 스택 자료구조(혹은 재귀함수)를 이용하며, 구체적인 동작과 과정은 다음과 같다. 탐색 시작 노드를 스택에 삽입하고 방문 처리 스택의 최상단 노드에 방문하지 않은 인접 노드가 하나라도 있으면 그 노드를 스택에 쌓고 방문 처리. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 더 이상 2번의 과정을 수행할 수 없을 때 까지 반복 DFS 동작 예시 function dfs(graph, idx, visited) { // 현재 노드를 방문 처리 visited[idx] = true; console.log(idx); // 현재 노드와 연결된 다른 노드를 재귀적..
-
Stack / Queue / Recursive functionAlgorithm | Data structure/Theory 2023. 4. 11. 02:04
Stack / Queue / Recursive function 탐색(Search)이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말한다. 대표적인 그래프 탐색 알고리즘으로는 DFS와 BFS가 있다. DFS/BFS는 코딩 테스트에서 매우 자주 등장하는 유형!! DFS : https://growth-msleeffice.tistory.com/137 BFS : 준비중 DFS/BFS 알고리즘을 학습하기 전 반드시 알아야 할 개념으로 스택, 큐 자료구조와 재귀함수가 있다. 스택 먼저 들어온 데이터가 나중에 나가는 형식(선입후출)의 자료구조 데이터를 집어 넣는 push, 데이터를 추출하는 pop, 가장 나중에 삽입된 데이터를 확인하는 peek등의 작업을 할 수 있다. 함수 실행 콘텍스트들이 쌓이는 Call..
-
구현 : 시뮬레이션과 완전 탐색Algorithm | Data structure/Theory 2023. 4. 7. 16:12
구현 : 시뮬레이션과 완전 탐색 구현이란 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. 흔히 알고리즘 대회에서 구현유형의 문제란 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제이다. 구현 유형의 예시 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제 적절한 라이브러리를 찾아서 사용해야 하는 문제 이런 구현 문제는 다양한 풀이 경험이 필요하다. 일반적으로 알고리즘 문제에서의 2차원 공간은 행렬의 의미로 사용한다. 시뮬레이션 및 완전 탐색 문제에서는 2차원 공간에서의 방향 벡터가 자주 활용된다. // 동, 북, 서, 남 const dx = [0, -1, 0, 1]; co..
-
GreedyAlgorithm | Data structure/Theory 2023. 4. 5. 19:00
Greedy 그리디 알고리즘(탐욕법)은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다. 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다. 그리디 해법은 그 정당성 분석이 중요하다. 정당성 분석 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토하는 과정이 필요하다. 위 예의 경우, 최적의 해는 5->7->9이다. 그런데, 단순히 매 상황에서 가장 큰 값만 고른다면, 5->10->4 가 해가 되어 최적의 해인 21보다 낮은 값이 된다. 그리디 알고리즘은 이처럼 단순히 매 상황에서 큰 값만 고르는 방식이라고 할 수 있다. 따라서 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다. 하지만 코딩..
-
[자료구조] 자료구조를 배우는 이유Algorithm | Data structure/Theory 2023. 1. 19. 15:03
1. 자료구조를 배우는 이유 데이터를 체계적으로 저장하고 효율적으로 활용하기 위해 자료구조를 사용 대부분의 자료구조는 특정 상황에 놓인 문제를 해결하는 데 특화 많은 자료구조를 알아두면 특정 문제 상황에 적합한 자료구조로 데이터를 정리, 문제를 빠르고 정확하게 해결할 수 있음 따라서, 문제 해결 능력을 필요로하는 알고리즘과 연관성이 있음 2. 자료구조란? 자료구조란 데이터의 묶음을 저장하고 사용하는 방법을 정의한 것이다. 그렇다면, 데이터란 무엇일까? 데이터는 문자, 숫자, 소리, 그림, 영상 등 실생활을 구성하고 있는 모든 값이다. 데이터는 그 자체만으로 어떤 의미를 갖는 정보인지 알 수 없다. 예를 들어 20이라는 숫자는 사람의 나이일 수도 있고 단순히 기간을 의미하는 20년일 수도 있다. 데이터는 ..
-
[자료구조] 해시(hash), 해시 함수, 해시 테이블Algorithm | Data structure/Theory 2023. 1. 17. 16:53
1. 개요 해시 : Key:Value의 구조를 갖는 자료구조를 의미한다. ex) 전화번호부 / 이름=key, 전화번호=value Key : 매핑 전 원래 데이터의 값 Hash value : 매핑 후 데이터의 값(해쉬 테이블의 index) Hash table : (Index, value)의 집합 Hashing : 매핑하는 과정 2. 해시함수 해시함수는 임의의 길이를 갖는 임의의 데이터에 대해 고정된 길이의 데이터로 매핑하는 함수를 말한다. 같은 입력 값(key)에 대해서는 같은 출력 값(index)가 출력 된다. 해시함수는 입력 값의 범위보다 출력 값의 범위가 좁은 경우가 많기 때문에 입력 값이 다르더라도 동일한 값이 출력될 수도 있다. 이러한 경우를 ‘충돌(collision)’이라고 하는데, 위 사진 예..