포시코딩

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

문제 https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 풀이 문제를 풀 때 항상 헷갈리는 문제 중 하나인 이진 탐색을 쉽게 푸는 방법에 대해 소개해보고자 한다. 위 문제를 예로 설명하겠음 문제 정리 문제를 요약하면 다음과 같다. 강의의 수 = N, 블루레이 개수 = M, 강의 길이 배열 = arr M개의 블루레이에 강의를 나눠 담을 때 블루레이 크기의 최소값 구하기 = 정답 블루레이 크기를 평균값을 통해 유추하며 줄여나가 조건에 부합하는 최소값을 되기에..

문제 https://www.acmicpc.net/problem/11497 11497번: 통나무 건너뛰기 남규는 통나무를 세워 놓고 건너뛰기를 좋아한다. 그래서 N개의 통나무를 원형으로 세워 놓고 뛰어놀려고 한다. 남규는 원형으로 인접한 옆 통나무로 건너뛰는데, 이때 각 인접한 통나무의 높이 www.acmicpc.net 문제 풀이 방식이 독특해 포스팅하게 되었다. 이 문제는 기본적으로 정규 분포 형태를 띄게 가운데에 제일 높은 수를, 그 이후 양쪽에 낮은 숫자들을 배치해가면 차이가 최소인 형태를 얻을 수 있는걸 이용해서 풀 수 있다. 풀이 import sys input = sys.stdin.readline for _ in range(int(input())): N = int(input()) arr = lis..

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

https://www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net

01 타일(피보나치 수열) https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 배낭 문제 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmic..

위상 정렬이란? 순서가 정해져 있는 작업을 차례로 수행해야 할 때, 순서를 결정해주는 알고리즘 최소힙인 heapq를 통해 위상 정렬 알고리즘을 구현할 수 있다. 시간복잡도 O(V+E) V: 노드(=Vertex) E: 간선(=Edge) 문제 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 코드 import heapq N, M = map(int, input().split()) arr = [[] for _ in rang..

https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net https://www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net

전위 순회(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를 구한..