알고리즘 (60) 썸네일형 리스트형 BOJ 11437 LCA www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net LCA 문제이다. (Lowest Common Ancestor ) 사실 이 문제에 대한 최적화 방안은 한창 알고리즘을 공부할 때 같이 스터디를 하는 형한테서 들었지만, 따로 구현은 해보지 않았었다. 처음 이 문제를 접한다면 다들 똑같은 생각을 할 것이다. (물론 나도 처음에는 같은 생각을 했었다.) "시작 node들로부터 depth가 같은 ancestor 까지 탐색을 진행 한 뒤, 방금 구한 ancestor.. BOJ 4386 별자리 만들기 www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 보자마자 greedy하게 짧은 간선들을 선택하면 어떨까 생각을 하였고, 이게 정답을 항상 낸다는 보장이 있나 생각하던 찰나에 이와 완전히 같은 크루스칼 알고리즘이 생각났다. 크루스칼 알고리즘 증명은 위키에도 있지만, 추후에 정리해보도록 하자. ko.wikipedia.org/wiki/%ED%81%AC%EB%9F%AC%EC%8A%A4%EC%BB%AC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98#.. BOJ 1806 부분합 www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 처음 보고 생각난 Naive한 방법은 모든 경우의 수를 계산해보는 방법이었다. 합 배열을 만드는데 O(N), 시작점-끝점 경우의 수가 N^2/2 이므로, 해당 방법은 O(N^2 + N) 으로 시간내에 풀이가 불가능했다. 문제 조건을 잘 보니 "수열의 값은 자연수"임을 확인할 수 있었다. 그렇다면 arr [ i : j ] 의 합을 구한 상태에서 arr [ j ] 을 더한다면 항상 arr [ i : .. BOJ 2467 용액 www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 처음 생각한 방법은 모든 숫자쌍을 비교하는 것이였다. 하지만, 시간복잡도가 O(n^2) 였기 때문에 해당 문제를 시간 내에 푸는 것은 불가능 했다. 문제를 보면서 곰곰히 생각해보니, 두 숫자의 합의 절대값이 작은 경우들만 추려서 확인하면 될 것 같다는 생각이 들었다. 그렇게 하기 위해서는 배열을 정렬한 뒤, 양 끝에서부터 중앙으로 다가오는 포인터를 두어 포인터가 가리키는 두 정수의 절대값을 비교하면서 인덱.. 이전 1 ··· 5 6 7 8 다음