포시코딩

개요 여러 개의 문자열 중 특정 문자열을 찾을 때 효과적인 트라이(Trie) 자료구조에 대해 알아보자 먼저, 이름은 retrieval(검색) tree에서 따왔다 정도의 유래가 있는듯하다. 위에서 말한바와 같이 여러 개의 문자열 중 특정 문자열을 찾을 때 하나하나 확인한다면 O(n) (n은 list의 길이)의 시간복잡도를 가지거나 정렬 후 이진 탐색을 사용한다면 O(nlog n)의 시간복잡도를 가지는 반면, 트라이의 경우 최선일 경우 O(1), 최악일 경우에도 O(m) (m은 문자열의 길이) 안에 할 수 있다고 한다. 따라서, 문자열이 아주 길거나 자동 완성 및 검색어 추천 기능 등에서 Trie 자료구조를 통해 효과를 볼 수 있다. 형태 문자열 집합 {'rebro', 'replay', 'hi', 'high..

특정 좌표에서 동서남북 등의 방향으로 나아갈 때 BFS를 사용할텐데 이미 이동했던 곳으로 이동하지 않기 위해 queue 대신 set 자료구조를 사용하면 메모리 사용량을 줄일 수 있다.

전위 순회(pre-order) 루트 -> 왼쪽 자식 -> 오른쪽 자식 중위 순회(in-order) 왼쪽 자식 -> 루트 -> 오른쪽 자식 x축 기준 왼쪽부터 출력 후위 순회(post-order) 왼쪽 자식 -> 오른쪽 자식 -> 루트 연습 문제 https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 코드 위에서 설명한 각 순회별 루트, 왼쪽 노드, 오른쪽 노드 방문 순서를 생각해 재귀를 통해 구현해내면 아주 쉽게 구현할 수 있다. class..

프림 알고리즘(Prim's algorithm) Kruskal's algorithm과 함께 대표적인 최소 신장 트리(Minimum Spanning Tree) 알고리즘 중 하나 Kruskal's algorithm보다 다소 복잡도가 올라간 알고리즘이다. 시작 정점을 선택한 후, 정점에 인접한 간선 중 최소 간선으로 연결된 정점을 선택하고, 해당 정점에서 다시 최소 간선으로 연결된 정점을 선택하는 방식으로 최소 신장 트리를 확장해가는 방식 Kruskal's algorithm과 Prim's algorithm 비교 둘 다 탐욕 알고리즘을 기초로 하고 있음(당장 눈 앞의 최소 비용을 선택해서, 결과적으로 최적의 솔루션을 찾음) Kruskal's algorithm은 가장 가중치가 작은 간선부터 선택하면서 MST를 구한..

Union-Find 개요 집합에는 두가지 종류의 연산이 필요 membership 연산: 집합에 포함된 값인지 합집합(Union), 교집합(Intersection), 차집합(Difference) 파이썬에서는 Set을 통해 집합을 표현할 수 있다. Dict도 가능하지만 중복 key에 대한 처리를 해줘야 함으로 Set이 더 효과적 집합의 함수 집합에는 다음과 같은 함수들이 필요하다. make-set(x) -> x만으로 구성된 집합을 정의(make) find(x): membership fn -> x가 속한 집합의 대표값 리턴 ex) 두 집합 S, T가 있을 때, find(5)라고 한 경우 T에 5가 포함되어 있다면 T를 대표하는 값을 리턴 union(x, y) -> 두 key 값 x, y를 하나의 집합으로 합침..

알고리즘에서 logN의 밑은 2이므로 만약 N이 10억이라고 할 때, N = 10억 = 10^9 log2N = log2(10^9)가 된다. 이건 다시 9log2(10)이 되는데 log2(10)은 3.3정도로 생각하면 되므로 9*3.3 = 약 30이라는 결과를 얻을 수 있다. 만약 문제가 MlogN의 시간복잡도를 요구하는데 M이 200,000이었을 경우 MlogN = 20만 * 30 = 6,000,000이 된다. 메모리 사용량은 1000 = 1KB. 1,000,000 = 1MB가 되므로 MlogN의 메모리 사용량은 약 6MB가 된다는 것을 알 수 있다.

개요 https://4sii.tistory.com/517 그래프 - DFS 구현 DFS 알고리즘 구현 스택, 큐 자료구조 활용 need_visit stack visited queue * BFS 자료구조는 두 개의 큐를 활용하는데 반해, DFS는 스택과 큐를 활용한다는 차이가 있다. 개념 위 그래프에 대해 DFS를 구현한 4sii.tistory.com 위 내용과 이어진다. 이전에는 알파벳으로 된 노드들로 DFS하는 방법을 알아봤는데 이번엔 숫자로 이루어진 DFS 알고리즘을 알아볼 것이다. 특히, 각 노드들에 대해 작은 순서부터 진행한다는 큰 특징이 있는데 코딩테스트에서 DFS를 번호가 낮은 순서부터 처리하도록 명시하는 경우가 종종 있기 때문에 해당 방법에 대해 알고 있는 것은 중요하다고 볼 수 있다. 코드..

계수 정렬 특정 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다. '데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때'만 사용 가능하다. 다른 정렬 알고리즘처럼 비교 후 위치를 변경하는 방식이 아니다. * 파이썬의 sort()나 sorted() 정렬 라이브러리는 퀵 정렬보다도 더 효과적이므로 별도의 요구 없이 단순 정렬하는 상황이라면 정렬 라이브러리를 쓰는게 더 좋다. 다만, 데이터의 범위가 한정되어 있으며 빠르게 동작해야 할 때 계수 정렬을 사용하는걸 추천 구현 arr = [4, 2, 3, 1]이 있을 때 arr에서 제일 큰 숫자 + 1 만큼의 길이를 가진 리스트를 하나 준비한다. (이유는 아래에서 설명) count = [0] * (max(arr)+1) arr을 돌며 값 ..

투 포인터 알고리즘 리스트에 순차적으로 접근해야 할 때 2개의 점의 위치를 기록하면서 처리하는 알고리즘 연속된 40개의 숫자 중 2, 3, 4, 5, 6, 7을 지목해야 할 때 번호로 하나씩 부르기보다 '2부터 7까지'라고 부르는 방법 위 방법처럼 리스트에 담긴 데이터에 순차적으로 접근해야 할 때 '시작점'과 '끝점' 2개의 점으로 접근할 데이터의 범위를 표현할 수 있다. 예시 문제 문제 1. 특정한 합을 가지는 부분 연속 수열 찾기 예를 들어 arr = [1, 2, 3, 2, 5]의 리스트와 M = 5의 값이 주어졌을 때 부분 연속 수열 중 M의 값을 가지는 수열의 개수를 구하라 [1, 2, 3, 2, 5]에서 합이 5인 부분 연속 수열의 조합은 [2, 3], [3, 2], [5]와 같다. Pseudo..

개요 지금껏 시간복잡도에 대해선 무엇인지, 어떻게 구하는지에 대해서만 알았지 구체적으로 어떤 상황에 쓰이는지는 적절한 상황이 없었는데 코딩테스트를 준비하며 시간 제한, 메모리 제한 등과 함께 같이 제시된 조건들을 기준으로 시간복잡도를 생각해 어떤 알고리즘을 사용할 수 있을지 유추하기도 한다는 정보를 알게 되었다. 시간복잡도 O(1) 상수 시간(Constant time) O(log N) 로그 시간(Log time) O(N) 선형 시간 O(N log N) 로그 선형 시간 O(N^2) 이차 시간 O(N^3) 삼차 시간 O(2^n) 지수 시간 위는 자주 사용되는 시간복잡도로, 위쪽일수록 빠르다. 컴퓨터 과학에서 특정 알고리즘의 시간복잡도가 O(N^k)일 때, 이를 '다항 시간에 동작하는 알고리즘' 이라고 말한다..