Python

4803 트리

문제 https://www.acmicpc.net/problem/4803 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net 접근 주어진 연결정보에 따라 노드를 분리하고 각 노드 집합에 대해 사이클이 발생하는지 확인하면 트리인지 아닌지 판별할 수 있으므로 유니온 파인드를 이용했다. 만약 사이클이 생긴다면 한 노드에서 다른 노드로 갈 수 있는 경로가 2개 이상이 되므로, 노드 집합의 원소의 개수가 k라고 한다면 노드 집합의 간선의 개수가 k-1보다 크다는 뜻 또한 노드를 연결정보에 따라 분리했으므로..

19641 중첩 집합 모델

문제 https://www.acmicpc.net/problem/19641 19641번: 중첩 집합 모델 S번 노드가 루트 노드일 때, 번호가 가장 낮은 노드부터 오름차순으로 방문해서 중첩 집합을 구성했을 때, 각 노드의 번호 left 필드와 right 필드를 출력한다. 총 N개의 줄에 걸쳐 i번째 줄에 i번 www.acmicpc.net 접근 각 노드에 대해 방문하는 순서가 필요해서 dfs를 이용했다. dfs의 매개변수로 순서를 넘길 경우 같은 레벨에 있는 노드들을 처리하기가 힘들어서 공유변수 order를 이용해서 처리했다. 주의할 점은 노드를 오름차순으로 방문하므로, 연결정보를 입력받은 후 정렬해줘야 한다. 풀이 각 노드를 방문하면 order를 1 증가시키고 left 값을 기록한다. 해당 노드와 연결된 ..

트라이

트라이 (Trie) 각 노드에 문자를 저장하는 트리 기반의 자료구로, 트리를 아래쪽으로 순회하면 단어 하나가 나온다. 트라이는 길이가 K인 문자열이 주어졌을 때 O(K) 시간에 해당 문자열이 유효한 접두사인지 확인할 수 있다. 먄악 트리에서 연관된 접두사를 반복적으로 검색해야 하는 경우, 트리의 현재 노드를 참조값으로 넘긴다면 매번 검색할 때마다 루트에서 시작할 필요없이 자식 여부만 확인하면 된다. 구현 # Node 클래스 # key: 해당 노드의 문자, child: 자식 노드 # data: 문자열이 끝나는 위치를 알려주는 역할 (해당 노드에서 끝나는 문자열이 없으면 None) class Node: def __init__(self, key, data=None): self.key = key self.dat..

힙과 우선순위 큐

힙 (Heap) 힙은 힙의 특성을 만족하는 완전 이진 트리로, 최소 힙 기준으로 각 노드의 원소는 항상 자식 노드의 원소보다 작거나 같아야 한다. 최소 힙의 부모 노드는 항상 자식 노드보다 크거나 같지만, 부모-자식 간의 관계만 정의되어 있을 뿐 좌우 관계에 대한 정의는 하지 않기 때문에 힙은 정렬된 구조는 아니다. 인덱스 완전 이진 트리 형태인 이진 힙은 배열에 빈틈없이 배치가 가능하며, 대개 트리의 배열 표현의 경우 계산의 편의성을 위해 0번째 인덱스는 비워두고 1번째 인덱스부터 사용한다. i번째 노드에 대해 부모 노드의 인덱스는 i // 2, 왼쪽 자식 노드의 인덱스는 2 * i, 오른쪽 자식 노드의 인덱스는 2 * i + 1로 계산된다. 원소 삽입 (Python) 최소 힙에 원소를 삽입할 때는 언..

22871 징검다리 건너기 (large)

문제 https://www.acmicpc.net/problem/22871 22871번: 징검다리 건너기 (large) $N$개의 돌이 일렬로 나열 되어 있다. $N$개의 돌에는 수 $A_{1} A_{2} ... A_{i} ... A_{N}$로 부여되어 있다. 가장 왼쪽에 있는 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너가려고 한다. 항상 오른쪽으 www.acmicpc.net 접근 22869 징검다리 건너기 (small) 문제랑 조건은 똑같고, N번째 돌까지 갈 수 있는 모든 경로 중 K의 최솟값을 찾는 문제이므로 파라메트릭 서치 즉, 이분탐색과 DP로 풀이했다. 풀이 DP 과정은 22869번과 동일하고 lt는 0으로 rt는 10 ** 9으로 초기화한 후 이분탐색으로 적절한 K값중 가장 작은 값을 구했다..

22869 징검다리 건너기 (small)

문제 https://www.acmicpc.net/problem/22869 22869번: 징검다리 건너기 (small) $N$개의 돌이 일렬로 나열 되어 있다. $N$개의 돌에는 수 $A_{1} A_{2} ... A_{i} ... A_{N}$로 부여되어 있다. 가장 왼쪽에 있는 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너가려고 한다. 항상 오른쪽으 www.acmicpc.net 접근 1번째 돌에서 N번째 돌까지의 돌들에 대해, 돌을 한번 건너갈 때마다 쓸 수 있는 힘이 K를 넘지 않는 경로가 존재하기만 하면 되는 문제 따라서 i번째 돌까지 이동하는 데 필요한 힘의 최댓값의 최솟값을 저장할 배열을 만들고 DP로 풀이했다. 풀이 d[i]를 i번째 돌까지 이동하는 데 필요한 힘의 최댓값의 최솟값으로 정의했을 때..

트리의 종류와 트리 순회

트리 (Tree) 트리는 사이클을 갖지 않는 하나의 연결 그래프로, 부모-자식의 계층적 관계를 표현하는 자료구조이다. 하나의 루트 노드는 0개 이상의 자식 노드를 가지고, 또 그 자식 노드 또한 0개 이상의 자식 노드를 갖는다. 즉, 트리는 재귀로 정의된 자기 참조 자료구조로 서브트리로 구성된다. 트리는 특수한 형태의 그래프의 일종으로 그래프에 포함되지만, 그래프와 달리 두 노드 간의 경로는 유일하다. 그래프와 트리 모두 비선형 자료구조로 그래프는 단방향과 양방향 모두 표현 가능하지만 트리는 부모 노드에서 자식 노드로의 단방향만 표현 가능하다. 이진 트리 각 노드가 최대 두 개의 자식 노드를 갖는 트리로, 대표적으로 다음과 같은 3가지 유형이 있다. 정 이진 트리 (Full Binary Tree) 모든 ..

1863 스카이라인 쉬운거

문제 https://www.acmicpc.net/problem/1863 1863번: 스카이라인 쉬운거 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 50,000) 다음 n개의 줄에는 왼쪽부터 스카이라인을 보아 갈 때 스카이라인의 고도가 바뀌는 지점의 좌표 x와 y가 주어진다. (1 ≤ x ≤ 1,000,000. 0 ≤ y ≤ 500,000) 첫 www.acmicpc.net 접근 건물 겉넓이, 빗물 트래핑, 주식 매매 같은 문제랑 비슷한 거 같아서 스택으로 풀이했다. 풀이 입력받은 y에 대해 스택에는 y보다 낮은 높이의 건물만 있도록 pop하면서 ans에 1씩 더한다. y가 스택에 있는 마지막 요소랑 같거나 0인 경우에는 스킵하고, 더 작은 경우 append한다. 모든 입력을 처리한 후 스택에 남아있는 원소들..

최단 경로 알고리즘

최단 경로 문제 최단 경로 문제는 각 간선의 가중치 합이 최소가 되는 두 정점 사이의 경로를 찾는 문제이다. 이때 가중치는 거리나 시간과 같은 이동 비용에 해당한다. BFS 간선의 가중치가 모두 1인 두 노드 사이의 최단 경로를 찾는데 사용한다. 인접 리스트로 구현 시 시간 복잡도는 O(V+E)이고, 인접 행렬로 구현 시 시간 복잡도는 O(V^2)이다. 구현 (경로 추적 포함) from collections import deque import sys sys.setrecursionlimit(200000) n, k = map(int, input().split()) time = [-1] * 200001 time[n] = 0 path = [-1] * 200001 path[n] = n q = deque() q.a..