알고리즘 썸네일형 리스트형 백준 3176 도로 네트워크 LCA를 활용하는 문제이다. 두 도시를 연결하는 경로는 LCA를 통해 구할 수 있다. 두 노드 u, v에서 LCA까지 이르는 경로를 합치면 두 도시를 있는 최소 경로가 된다. LCA 2 에서는 parents[] 배열에 2^K 번째 부모 노드들을 저장했었는데, 이것을 응용해 2^K 번째 부모 노드까지의 경로에서 에지의 최소값을 저장하는 배열과 최대값을 저장하는 배열을 만들기만 하면 문제를 해결할 수 있다. LCA 2에서 달라질것은, pathMax[] 배열과 pathMin[] 배열을 새로 만든것과, Parents[] 배열을 초기화하거나 갱신할때 새로 만든 두 배열도 값을 넣어준다는 것, 두 노드의 높이를 맞춰주거나 맞춘 후 위로 탐색할때 u와 v가 움직이는것에 맞춰 탐색되는 경로 상 최대/최소값을 찾아준다는.. 더보기 백준 11438 LCA 2 트리를 입력받은 뒤, 공통 조상 중 가장 가까운(높이가 낮은) 노드를 찾는 문제이다. LCA 1이 있고 LCA 2가 있는데, LCA 1은 나이브하게 공통 조상을 밑에서부터 같이 찾아 올라가도 정답 처리가 되지 않을까 싶다. 그 문제는 골드3이고 이 문제는 플레 5이므로 난이도 차이가 꽤 난다. 문제의 접근은 DP-Like 하다. DP도 제대로 본건 아니지만, 연산 과정을 배열에 저장한다는 관점에선 비슷하다고 볼 수 있지 않을까? DP를 좀 더 많이 해보고 차이점을 더 잘 알게 된다면 이 글을 수정해야겠다. 그럼 여기서 DP-Like 하게 연산과정을 저장한다고 했는데, 무엇을 저장하는가? 바로 어떤 노드의 2^K번째 조상을 저장한다. 100000개의 노드가 있을 때, Worst Case일 경우 높이는 10.. 더보기 [나만 몰랐던 알고리즘] MST 구하기 - Kruskal's Algorithm Minimun Spanning Tree는 모든 노드를 잇는 사이클이 없는 그래프 중 간선(edge)의 가중치 합이 최소가 되는 트리(그래프)이다. 글로 봤을땐 저게 뭔가 싶은데 그림으로 한번 보자 위 사진과 같은 그래프에서, 모든 노드를 포함하는 부분 그래프를 신장 부분 그래프라고 한다. 여기서 간선이 어떻게 연결되는지에 따라 여러개의 신장 부분 그래프를 만들 수 있는데, 이 중 간선의 합이 최소가 되는 신장 부분 그래프를 MST라고 하고, 오늘 정리할 알고리즘은 이 MST를 찾는 Kruskal 알고리즘이다. 알고리즘을 크게 정리하면, 모든 에지를 Cost 순으로 정렬되는 Priority Queue에 넣는다. PQ에서 하나를 뽑는다 -> 이 에지의 출발점과 도착점이 연결되어 있지 않다면 트리에 추가한다... 더보기 [나만 몰랐던 알고리즘] Union-Find Union-Find 는 알고리즘이라고 하기에는 다른 알고리즘에서 많이 쓰이는 부품같은 존재다. 원소 N개가 있을때, 이 원소들을 합집합하는 연산(union)과 특정 원소가 어디 속했는지 구하는 연산(find) 이 두개로 이루어져서 이름도 Union-find 이다. 초기화 원소가 N개 있다고 했을때, size = N인 int array parents를 만든다. 이 배열은 해당 인덱스 원소의 부모를 내용으로 가진다. 초기에는 각 원소가 각각의 집합에 속해있다고 가정하므로, parents[i] = i 로 초기화 한다. int parent[10]; for (int i = 0;i 더보기 [나만 몰랐던 알고리즘] 최소 공통 조상, LCA 트리 구조에서 조상은 현재 노드 위에 있는 노드들이다. LCA(최소 공통 조상)은 말 그대로 공통 조상 중에서 가장 낮은(높이가 최소인) 조상을 말한다. 트리를 보면, 루트 노트 1은 깊이 0을 가지고, 9번 노드는 깊이 3을 가지는 것을 볼 수 있다. 여기서 10과 5의 공통 조상은 1, 3이 있고 최소 공통 조상은 3이다. LCA를 구하는 방법은, 나이브하게 접근하면 매번 트리를 타고 올라가면서 확인하는 방법이 있다. 가장 확실하지만 시간이 아주 오래 걸릴 수도 있다. 트리가 꼭 균형이 맞는다는 보장이 없으므로 심한 경우에는 노드 갯수만큼의 비교와 count가 필요하다. 따라서 많은 문제에서 LCA는 다른 방법으로 구하게 된다. LCA에서 가장 핵심이 되는 것은 배열 하나의 추가이다. DP와 비슷하다.. 더보기 백준 2042 구간 합 구하기 진짜 제곧내 문제 이다. 입력받은 N개의 수에서 두 인덱스 사이의 부분합을 구하거나, 특정 인덱스의 수를 변경하는 두 가지의 연산을 하면 된다. 엄청 나이브하게 접근해서 작동만 하는것을 짰을때는 진짜 말그대로 배열에서 하나씩 탐색하며 부분합을 더했고, 변경도 배열에서 직접 변경하도록 했다. 시간초과인걸로 기억한다. 이런 구간 합 문제에서 투 포인터 알고리즘을 사용할 수도 있었다. 하지만 검색을 해보니 세그먼트 트리로 접근해야 한다고 해서 관련된 내용을 찾아보고 작성했다. 세그먼트 트리에 대한 내용은 따로 작성한 포스팅이 있다. 세그먼트 트리는 각 노드가 자신이 포함하고 있는 노드들의 합을 저장하는 트리라고 할 수 있다. 코드 전에 각 함수의 로직을 간략히 보면, init() leaf node나오기 전까지.. 더보기 이전 1 2 3 4 다음
