복습노트 복습노트

Priority Queue(우선순위 큐) 우선순위가 가장 높은 원소부터 pop되는 큐 ex)원소의 값이 클수록 우선순위가 높다 배열로 구현 1) 삽입 : O(N) / 삭제 : O(1) 2) 삽입 : O(1) / 삭제 : O(N) 결국 둘다 O(N^2)이 걸린다. 따라서 힙(Heap)으로 구현 Heap (힙) 완전 이진 트리로 이루어진 자료구조 최솟값 or 최댓값을 빠르게 구하기 위한 자료구조 최대 힙(Max Heap) : 부모 노드의 값이 자식 노드의 값보다 항상 크거나 같은 힙 최소 힙(Min Heap) : 부모 노드의 값이 자식 노드의 값보다 항상 작거나 같은 힙 느슨한 정렬상태(반 정렬 상태) 유지 ex) 최대 힙 (Max Heap) Heap 원소 삽입 (ex : max heap) 시간 복잡도 : ..

문제 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 섬의 개수 n이 주어지고 섬과 섬사이에 무게를 최대로 옮길수 있는 간선의 정보 m개가 주어집니다. 섬과 섬사이에 최대로 옮길 수 있는 무게보다 큰 무게를 옮길 수 없습니다. 그리고 특정섬 a, b 가 주어지면 a와 b사이에 한번에 최대로 옮길 수 있는 무게를 구하면 됩니다. 예를 들어 0번 섬에서 9번섬으로 갈 수 있는 최대 무게는 11입니다. 따라서 11이상인 무게는 항상 옮길 수 있고 11미만인..

1) 정점 v가 속해 있는 그룹은 몇 번 그룹인가? (Find) 2) 정점 u가 속한 그룹과 정점 v가 속한 그룹을 합치면 어떻게 되는가? (Union) 정점 인덱스가 속한 그룹의 정보를 다음과 같은 배열에 저장할 수 있습니다. 만약 0번 그룹과 5번 그룹을 합치고 싶으면 어떻게 해야 할까? 다음과 같이 배열을 수정할 수 있습니다. 시간복잡도 Find : O(1) Union : O(N) 모든 정점을 순회하면서 바꿔야하기 때문 위의 그래프를 조직도 처럼 만들어 보자! 최고 리더는 -1로 해주고 각 노드마다 직속 상사를 배열로 저장하면 다음과 같은 배열이 됩니다. 여기서 0번 그룹이 5번그룹과 합치려면 어떻게 해야될까? 다음과 같이 합치면 됩니다. 시간 복잡도 Find : O(정점 v가 속한 트리의 높이) ..

문제 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 현재 위치 n이 주어지고 도착 지점 k가 주어지면 도착할때 까지 최단시간을 구하는 것입니다. 먼저 현재위치 n은 n+1로 가거나 n-1로 가거나 n*2로 갈 수 있습니다. 예를 들어 n = 5이고 k = 17이면 5 -> 10 -> 9 -> 18 -> 17 이므로 총 4초만에 최소시간으로 도달합니다. 단순히 문제를 봤을 때는 처음에는 dp를 생각하였습니다. 하지만 n이 움직일 수 있는 3가지 경우의 수에 대해서 따로따로 봐야하고 ..

문제 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 행렬의 크기 nm이 주어지면 1이면 벽이고 0이면 갈 수 있는 길입니다. 이때 벽을 한번 부수고 통과할 수 있다고 할때 최단거리를 구하는 문제입니다. 최단 거리이므로 BFS로 이용하면 됩니다. 원래 평소대로라면 bool visited[x][y] : arr[x][y]에 해당하는 부분을 방문하면 true로 바꿔주었지만 벽을 부수는 경우도 생각해줘야 하기때문에 방문기록이 총 3차원으로 생각할 수 있습니다. int dist[x][y][0]..

문제 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net Flood Fill Algorithm : 어떤 칸과 연결된 영역을 찾는 알고리즘 가로 M과 세로 N이 주어지고 배추의 위치 (M(가로), N(세로)) 이 주어 집니다. 다음과 같이 1끼리 인접한 부분(상하좌우)이 몇개인지 출력하는 문제입니다. 위의 그림에서는 5개입니다. 주어지는 위치가 처음에 가로, 세로가 주어지므로 행렬로 생각할 때 주의해야합니다. M은 행이 아닙니다. 열입니다. N은 열이 아닙니다. 행입니다. 즉 행열이 반대로 주어지는 겁니다. 저는 처음에 이것을..

그래프 탐색이란? 그래프의 한 정점으로 부터 출발해서 모든 정점을 1번씩 방문하여 그래프에 대한 정보를 얻는 것 정점 방문 순서에 따라 크게 두 방식으로 나뉨 깊이 우선 탐색(DFS) / 너비 우선 탐색 (BFS) DFS(깊이 우선 탐색) 다음 분기(brunch)로 넘어가기 전에 현재 분기를 완전히 탐색하는 방법 트리의 전위(preorder)탐색이 그래프로 확장된 개념 재귀 함수 or 스택으로 구현 1) 정점 1개를 선택한다. 2) 현재 정점과 이웃한 정점 중 아직 방문하지 않은 정점 중 하나를 방문한다. 3) 더 이상 방문할 수 있는 정점이 없는 경우, 현재 정점의 이전 정점으로 돌아간다. 4) 모든 정점을 방문할 때까지 2~3을 반복한다. 왼쪽의 그래프를 dfs를 통한 순서를 오른쪽 dfs tree로..

Graph? 이산수학에서 사용 특정 집합의 추상화된 원소들에 대하여, 원소들의 일부분이 어떤한 관계로 "연결되어있음"을 나타내는 수학적 구조의 일종 연결 관계가 있는 집합을 나타내는 데에 좋은 자료구조이다. 정점 v의 차수(degree) deg(v) 정점 v와 연결되어있는 정점의 수 ex) deg(1) = 2 경로(path) p 정점의 나열로써, 인접한 정점 사이에 간선이 있는 경우 p = {1, 3, 4, 5, 3} 단순 경로 (simple path) p 경로로써, 중복되는 정점이 없는 경우 p = {1, 3, 4, 5} 순환 (cycle) c 경로로써, 시작점과 끝점이 동일한 경우 c = {1, 3, 4, 5, 3, 1} 단순순환 (simple cycle) c 순환으로써, 시작점과 끝점을 제외한 중복..