Leta Learns

Segment Tree : 사용자가 요청한 쿼리에 대해서 더 빠르게 응답하기 위해 만들어진 자료구조. 특정 기준으로 트리를 전처리하여 연산 속도를 높이게 된다. 이진 트리 구조. 구간 트리라고도 불림. 배열로 구현 가능. 세그먼트 트리를 이루는 각 노드의 왼쪽 자식과 오른쪽 자식이 각각 해당 구간의 왼쪽 반과 오른쪽 반을 표현. => 이진 트리 구조 Segment Tree를 사용하는 이유 배열 arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 이 있는 경우. arr[4] + arr[5] + arr[6] 의 부분합을 구하는 쿼리와 arr[4]의 값을 바꾸는 쿼리가 있다고 하면 보통의 방식에서 부분합을 구하는 쿼리는 O(N), 값을 바꾸는 쿼리는 O(1)의 시간복잡도를 요구한다. 이처럼 수..

문제 https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 타임머신 문제와 비슷한 유형이다. 다른 점이라면 bf 함수에서 세번째 for문 안에 있는 if문을 돌릴 때, 타임머신에서는 아래의 if문을 사용하여 시작점과 연결된 경로가 있는지 확인해야 했고, if dist[a] != float('inf') and dist[next] > dist[a] + time: 웜홀 문제에서는 시작점이 주어지지 않으므로 이에 대한 확인 없이 negative..

문제 https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 벨만포드 코드에 문제가 있는데 모르겠어서 친구랑 스터디할 때 상의했다. for문을 세 번 돌려야 하는데 난 두 번만 돌려서 문제가 생겼다. for i in range(1, n+1) : 간선 탐색을 위한 for문 (아래 for문을 n번 반복) for a in range(1, n+1) : 노드 탐색을 위한 for문 (모든 엣지에 대해서..

문제 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 어제 푼 다익스트라 코드 이용해서 조금만 손 봤더니 그냥 풀렸다.. 다익스트라 코드 외우면 이 문제 저 문제 풀기 수월하겠네. 외워야겠다. 시작점, 도착점만 입력 받아서 다익스트라 이용해서 dist 배열 구하고 변수(cost) 에 저장한 다음, 해당 배열의 도착점 인덱스 값을 출력해주면 된다. (cost[end]) import sys import heapq ..

문제 https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 다익스트라.. 아무 생각 없이 시도했다가... 피 봤다.... heapq 쓰는 방법 어려워서 고민하다가 다익스트라 예제 코드 구글링해서 참고했다. 이 문제에서 포인트는 파티를 여는 마을(x)로 갈 때 dijkstra 한 번, 파티가 끝나고 집에 갈 때 dijkstra 한 번. 총 두 번 dijkstra 함수를 호출해야 한다는 것이다. dijkstra 함수 내부에..

LCA (Lowest Common Ancestor) 알고리즘 : 최소 공통 조상을 찾는 알고리즘 즉, 두 노드에서 가장 가까운 공통 조상을 찾는 알고리즘 Segment Tree를 사용한 방법, DP를 사용한 방법이 존재하는데 DP 사용법에 대해서 공부하였다. 9와 6의 최소 공통 조상 : 2 4와 10의 최소 공통 조상 : 8 2와 15의 최소 공통 조상 : 1 LCA 접근법 최소 공통 조상 찾는 방법 : 각 노드에서 부모를 타고 올라가서 같은 부모를 찾는다. 이때, 양 노드의 레벨이 같아야 함. => 각 노드의 부모와 레벨을 알아야 하고, 트리가 있어야 함 각 노드의 부모 노드, 레벨 저장하는 법 => DFS 사용 재귀를 한 번씩 돌 때 마다 레벨 += 1, 부모 노드 또한 저장 가능. ex) 6과 1..

최단 경로 알고리즘 (Shortest Path) 그래프에는 어떤 정점에서 다른 정점으로의 사이를 잇는 최단 경로를 구하는 알고리즘이 존재한다. ( != MST ) MST : N-1개의 간선으로 최소 가중치 트리 만듦 그래프 내의 모든 간선의 가중치가 0 이상인 경우 => Dijkstra 알고리즘을 이용한다. 그래프가 음수 가중치 간선을 포함하는 경우 => Bellman-Ford 알고리즘을 이용한다. Dijkstra 알고리즘 출발 정점으로부터 가장 가까운 아직 방문하지 않은 정점을 찾고, 다른 모든 정점까지의 거리에 대해서 선택된 정점을 지나서 가는 경우와, 직접 가는 경우 중 최솟값으로 최단 거리를 갱신해가면서 가장 가까운 정점을 하나씩 방문한 정점 집합에 추가하는 방식으로 최단 경로를 갱신. (음의 간..

문제 https://www.acmicpc.net/problem/1949 1949번: 우수 마을 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, www.acmicpc.net 스터디 할 때 트리 DP 예제 코드를 받아놔서 그거 보고 좀 고치면서 풀었더니 골드1 치고는 엄청 빨리 풀었다. 사실 두 시간 만에 푼 거라 난이도 떠나서도 내 기준 엄청 빨리 푼 편에 속한다. 문제 이해부터 쉽지 않았는데, 문제에서 중요한 바는 각 노드에서 나아갈 수 있는 방향은 '우수마을' or 'not 우수마을' 이렇게 두 가지 경우. 루트 노드가 우수 마을이면 하위 노드는 우..

Bellman-Ford Algorithm : 한 노드에서 다른 노드까지의 최단 거리를 구하는 알고리즘 가중치가 음수일 때도 사용 가능 다익스트라 알고리즘에 비해 느리므로 가중치가 모두 양수인 경우 굳이 벨만포드 사용할 필요 x. 다익스트라 쓰면 됨. Bellman-Ford 알고리즘의 특징 음수 가중치가 있는 그래프의 시작 정점에서 다른 정점까지의 최단 거리를 구할 수 있다. 음수 사이클 존재 여부를 알 수 있다. => 그래프 정점 개수를 v라고 할 때 인접 간선을 검사하고 거리 값을 갱신 (갱신 과정은 v-1번으로 제한) => 그래프의 시작 정점에서 특정 정점까지 도달하기 위해 거치는 최대 간선 수: v-1개 => v번째 간선이 추가되면 사이클이라고 판단 Bellman-Ford 과정 1. 시작 정점 결정..

문제 https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 이번 주 MST 스터디에서 1197번은 프림으로, 1922번은 크루스칼로 풀 생각이었는데 보통 문제 풀 때는 거의 다 크루스칼로 푸니까 둘 다 크루스칼로 풀기로 스터디원이랑 협의했다. 그랬더니.. 1197번이랑 입력 부분 빼고 코드가 전부 똑같다. 이번 주는 크루스칼에 익숙해지는 주간.. import sys input = sys.stdin.readline def find(a): if a == parent[a]: return a parent[a] = find(parent[a]) re..