Eunbi

강한 북서풍이 불고 있다. 이 뜻은 동쪽과 남쪽 사이의 모든 방향으로 항해할 수 있다는 뜻이다. 북쪽이나 서쪽으로 항해하는 것은 불가능하다. → 조건1. 내가 갈 수 있는 섬의 x좌표는 나보다 크거나 같다. 조건2. 조건1을 만족할 때, 내가 갈 수 있는 섬의 y좌표는 나보다 작거나 같다. ==> (입력받을 때 y에 -1를 곱한다면) 조건1. 내가 갈 수 있는 섬의 x좌표는 나보다 크거나 같다. 조건2. 조건1을 만족할 때, 내가 갈 수 있는 섬의 y좌표는 나보다 크거나 같다. x, y 좌표를 오름차순으로 정렬했을 때, 하나씩 탐색하면 x 조건은 자동으로 성립한다. → 따라서 정렬하면 x 좌표값이 필요없게 됨. y 좌표만 보고 y 조건이 성립하는지 판단하는 문제로 변함. 하나씩 탐색을 했을 때 해당 y..

최단경로 문제 가중치가 있는 그래프에서, 가중치의 합이 최소가 되는 경로를 찾는 것. 종류 단일 출발 / 출발지1, 도착지n : 하나의 노드에서 출발해, 여러 도착지를 방문할 때 어느 노드까지 가는 경로가 최단인지 찾는 문제 단일 도착 / 출발지n, 도착지1 : 여러개의 노드에서 출발해, 하나의 도착지를 방문할 때 어느 노드부터 출발해야 경로가 최단인지 찾는 문제. 출발지1, 도착지n의 위 경우의 간선 방향을 뒤집어서 똑같이 해결한다. 출발지n, 도착지n' : 여러개의 노드에서 출발해, 여러 도착지를 방문할 때 최단 경로를 찾는 문제. 가상의 출발 노드 하나를 만들어 (진짜 출발노드와 가상 출발노드를 잇는 간선이 필요한데 이때 간선의 가중치는 0임) 해결한다. 전체 쌍 / 출발지n, 도착지n : 모든 노..

LCA (Lowest Common Ancestor) 노드 A, B의 최소 공통 조상을 찾는 것. DFS/BFS를 수행해 트리의 각 노드 깊이와 부모 노드에 대해 저장한다. 노드 A, B의 부모를 따라 하나씩 올라가 (depth를 맞춘 상태로 시작) 최소 공통 조상을 찾는다. ===> 이는 $O(N)$만큼 걸림. 보다 빠르게 LCA를 수행하는 방법. parent[K][V]=parent[k-1][parent[k-1][V]] : V 노드의 $2^K$번째 조상 노드 (K, V의 순서에 따라 속도가 매우 달라짐. (2차원 배열의 구현특성 때문에)) 가로로 -> 이 방향으로 순회하는 것이 더 빠름. 우리가 갖고있는 정보. 한 노드의 바로 위의 부모 노드는 무엇인지 알고 있음. (parent[0][x]) 이때 par..

그래프 무향 간선 : 방향이 존재하지 않는 간선 유향 간선 : 방향이 존재하는 간선 인접 Adjacent : 정점A, B를 바로 잇는 간선이 존재한다면 A, B는 인접하다. 차수 Degree : 정점에 존재하는 간선의 수 in-degree : 정점에 들어오는 간선의 수 out-degree : 정점에서 나가는 간선의 수 그래프의 종류 무향 그래프 : 무항 간선으로 이루어진 그래프 유향 그래프 : 유향 간선으로 이루어진 그래프 가중치 그래프 : 가중치를 갖는 간선으로 이루어진 그래프 완전 그래프 : 임의의 두 정점에 대해 이를 잇는 간선이 존재하는 그래프 (모든 노드가 연결되어있고, 인접해있음) 연결 그래프 : 임의의 두 정점에 대해 이를 잇는 경로path가 존재하는 그래프 트리 그래프 : 순환(사이클)을 ..