💡 Map map은 각 노드가 key-value 쌍으로 이루어진 트리이며, 키의 중복을 허용하지 않는다는 점이 특징이다. map은 pair객체로 저장이 되고, first↔key, second↔value 이다. C++에서 map은 탐색, 삽입, 삭제가 모두 O(logN)에 이루어질 수 있는 레드블랙트리로 구현되어 있다. Map의 기본 형태 map m; Map의 정렬 map은 자료를 저장할 때 내부적으로 자동으로 정렬하는 특징을 가지고 있다. 이 때 기준은 key값이 되고 오름차순으로 정렬하게 된다. 내림차순으로 정렬하고 싶은경우 2가지 방법으로 할 수 있다. map map1; 처럼 선언할 때 세 번째 인자로 greater를 추가하는 방법 int데이터를 저장할 경우에만 해당되는 것인데 데이터를 음수화하여 저..
💡 Intro 코딩테스트를 C++로 준비하면서 익숙하지 않은 STL들의 사용법을 정리하려고 한다. 이번에는 string 문자열을 거꾸로 돌려주는 std::resverse 함수에 대해 알아보려고 한다. 💡 std::reverse std::reverse 함수 선언 template void reverse(const _BidIt _First, const _BidIt _Last) reverse elements in [_First, _Last) 와 같은 주석도 함께 달려있는데 first부터 last바로 전 인덱스까지의 요소들을 거꾸로 뒤집는 역할을 한다고 볼 수 있다. std::reverse 함수 정의 에서 중요한 부분을 떼오면 다음과 같다. void reverse(const _BidIt _First, const ..
🐥 Counting Sort counting sort는 정렬 알고리즘 중 가장 간단한 알고리즘으로 볼 수 있다. 그냥 각 수가 나오는 횟수를 세고, 그 횟수만큼 출력해주면 되기 때문이다. 아래 그림을 보면 더 잘 이해가 될 것이다. 위와 같은 리스트가 있다고 가정하자. 리스트에서 값이 1부터 6까지 나오기 때문에 해당 값이 몇번 나왔는지 배열에 저장하고 오름차순으로 횟수만큼 출력해주면 정렬이 되는 것을 볼 수 있다. 💥 단점 counting sort를 사용하기 위해서는 각 수가 나온 횟수를 저장해줘야 한다. 이는 미리 큰 테이블을 만들어두고 대응되는 원소의 값을 증가시키는 방식으로 구현이 가능하다. 예를들어 만약 나오는 수가 1부터 999까지라고 하면 int freq[1000] 와 같이 선언하여 사용하면..
🐥 Quick Sort Quick Sort는 거의 모든 정렬 알고리즘보다 빠른 특징을 가지고 있기 때문에 라이브러리에서의 정렬은 대부분 Quick Sort를 바탕으로 만들어져있다. Quick Sort는 매번 Pivot이라는 원소를 하나 선택하고 Pivot을 제자리로 보내는 작업을 반복한다. Pivot을 제자리로 보낸다는 말의 의미는 Pivot의 왼쪽에는 Pivot보다 작은 원소들을, Pivot의 오른쪽에는 Pivot보다 큰 원소들을 위치시킨다는 것이다. 가장 왼쪽에 있는 원소인 5를 Pivot으로 잡는다면 Pivot의 제자리는 위와 같다. Pivot을 기준으로 왼쪽은 Pivot보다 작은 원소들이, 오른쪽은 Pivot보다 큰 원소들이 있는 것을 볼 수 있다. 자세한 동작과정을 살펴보면 다음과 같다. Piv..
🐥 Merge Sort Merge Sort는 재귀적으로 수열을 나눠 정렬한 후 합치는 정렬 알고리즘이다. 시간복잡도를 먼저 말하면 Merge Sort는 O(NlogN) 에 동작하는 빠른 알고리즘이다. Merge Sort를 이해하기 위해서 먼저 길이가 N, M인 정렬된 두 리스트를 합쳐서 길이가 N+M인 리스트를 만드는 방법을 알아야 한다. 위와 같은 정렬된 리스트 2개를 정렬하는 방법은 간단하다. 두 리스트의 가장 앞 원소를 확인하여 작은 것부터 채워 넣어주면 된다. 이미 두 리스트가 정렬되어 있는 상태이기 때문에 가장 작은 원소는 각 리스트의 가장 앞에 위치해 있을 것이고 두 개의 원소를 비교하면 두 리스트 중 가장 작은 원소를 찾을 수 있게 되는 것이다. 두 원소를 비교하는데 걸리는 시간은 O(1)이..
📌 Intro 크루스칼 알고리즘은 그래프에서 모든 정점들을 가장 적은 비용으로 연결하는 방법을 찾는 알고리즘이다. 다르게 말하면 최소 신장 트리를 찾는 알고리즘이다. 신장트리는 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 말하고, 최소 신장트리는 이러한 신장 트리들 중 비용이 가장 적은 신장 트리를 말한다. 📌 크루스칼 알고리즘 앞에서 말한 것처럼 크루스칼 알고리즘을 사용하면 그래프 내에서 가장 적은 비용으로 모든 노드를 연결하는 방법을 찾을 수 있다. 크루스칼 알고리즘은 모든 간선에 대해 정렬을 수행한 뒤 가장 거리가 짧은 간선부터 집합에 포함시키면서 진행을 하기 때문에 그리디 알고리즘으로 분류된다. 구체적인 알고리즘은 다음과 같다. 간선 데이터를 비용에 따라 오름차순..
📌 Intro 0-1 BFS란 가중치가 0과 1로만 주어진 그래프에서 최단 경로를 찾는 알고리즘인데, 이에 대해 자세하게 알아보도록 하자. 📌 0-1 BFS 보통 최단 경로를 이야기할 때는 다익스트라 알고리즘이 가장 빠르게 동작한다고 알고 있을 것이다. 하지만 가중치가 0과 1로만 주어진 그래프에서는 다익스트라 알고리즘보다 0-1 BFS가 더빠르게 동작한다. 다익스트라 알고리즘의 시간 복잡도는 O(ElogV)이지만 0-1 BFS는 O(V+E)의 시간 복잡도를 가지기 때문이다. 먼저 0-1 BFS의 동작 원리를 살펴보면 다음과 같다. deque front에서 현재 노드를 꺼낸다. 인접 노드를 체크한다. 현재 노드까지의 비용 + 인접 노드로의 비용 < 인접 노드까지 소요된 비용 의 경우 인접 노드로의 비용을..
📌 Intro 데이터를 탐색하는 알고리즘 중 가장 기본적인 알고리즘은 순차 탐색이다. 하지만 순차 탐색은 최악의 경우 O(N) 시간 복잡도를 가지고 있기 때문에 상당히 느리다. 이보다 조금 더 빠르게 탐색하는 방법인 이진 탐색 알고리즘에 대해서 알아보도록 하자. 📌 이진 탐색(Binary Search) 이진 탐색은 데이터가 정렬되어 있는 경우에만 사용할 수 있는 탐색 방법이다. 탐색 범위를 절반씩 줄여가면서 탐색을 진행한다. 이진 탐색은 위치를 나타내는 변수 3개를 사용하는데 탐색하고자 하는 범위의 시작점, 끝점, 중간점 이다. 찾으려는 데이터와 중간점의 데이터를 반복적으로 비교하여 탐색의 범위를 줄여나가고 원하는 데이터를 찾는 것이 이진 탐색 과정이다. STEP 0 이미 정렬된 10개의 데이터 중 값이..
