Algorithm/Algorithm for Beginner 썸네일형 리스트형 19. 투 포인터, 슬라이딩 윈도우 (2) 앞서 투 포인터의 개념에 대해 설명을 하였습니다. 이번에는 슬라이딩 윈도우에 대해 설명해보도록 하겠습니다. 때에 따라서 투 포인터와 슬라이딩 윈도우를 구분없이 이야기하거나 개념이 혼동되는 경우가 꽤 있을 정도로 둘은 유사한 접근 방식을 갖고 있는 알고리즘입니다. 투 포인터는 앞에서 언급한 대로 연속적인 데이터가 주어졌을 때 두 개의 포인터를 이용하여 범위를 정해주고 그 범위에 포함된 데이터의 합 등 연산을 한뒤 그것이 원하는 값인지 검증을 하고 조건에 맞지 않는다면 조건에 맞출 수 있도록 end pointer나 start pointer를 적절하게 이동시켜주면서 모든 데이터를 확인하는 방식의 알고리즘이었습니다. 슬라이딩 윈도우는 투 포인터와 유사하게 접근하되 투 포인터처럼 범위의 크기가 줄었다 늘었다 하는.. 18. 최소 공통 조상 (LCA: Lowest Common Ancestor) 2 앞에서 최소 공통 조상(이하 LCA) 알고리즘을 통해 트리 내 두 노드의 공통 조상을 찾는 방법을 설명드린 적이 있었습니다. 트리 내 두 노드의 가장 가까운 조상을 찾는 LCA 알고리즘을 통하여 노드가 공유하는 조상 노드 중 가장 깊은 노드를 찾는 방법을 알게 되었습니다. 가장 원초적 형태의 LCA 알고리즘도 물론 강력한 기능을 갖고 있는 알고리즘이지만 이를 강화시킨 버전의 LCA 알고리즘을 이번 챕터에서 말씀드리려고 합니다. 크기가 그렇게 크지 않은 트리에서는 특정 노드에서 조상을 찾기 위해 올라가는 과정이 그렇게 멀지 않습니다. 두 노드를 비교하여 깊이가 더 깊은 노드의 깊이를 상대적으로 깊이가 얕은 노드에 맞춰주고, 부모로 올라가는 과정을 몇 번 거치면 쉽게 LCA를 구할 수 있었습니다. 문제가 되.. 17. 투 포인터, 슬라이딩 윈도우 (1) 투 포인터와 슬라이딩 윈도우는 비교적 간단한 알고리즘이지만 강력한 알고리즘이기도 합니다. 직관적으로 보았을 때 O(N^2) 이상으로 해결해야하는 문제를 선형시간(O(N))으로 해결해주기 때문입니다. 투 포인터와 슬라이딩 윈도우가 완벽히 일치하는 알고리즘은 아니지만 설계적 측면에서 궤를 같이 한다고 할 수 있습니다. 투 포인터는 간단히 말해서 연속되는 value들을 이용하여 특정 목표에 맞는 값을 찾아주는 알고리즘이라고 할 수 있습니다. 여기서 주의해야할 것은 어디까지나 연속된 값들을 이용하여 풀어나가는 문제에 한정적으로 사용해야한다는 것입니다. 만일 주어진 값들의 연속성이 선행조건으로 주어지지 않는 경우에는 투 포인터를 사용할 수 없습니다. 그런 면에서 문제에서 주어진 값들을 그대로 활용해야하는 경우나 .. 16. 퀵 정렬(Quick Sort)과 병합 정렬(Merge Sort) 정렬을 구현하는데 있어 가장 간편하고 직관적인 알고리즘은 버블 정렬과 선택 정렬일 것입니다. 하지만 O(n^2)의 시간 복잡도를 갖고 있어 빠른 정렬에는 적합하지 않다는 단점을 갖고 있습니다. 자료가 많을 때 빠른 정렬을 하기 위해서는 일반적으로 퀵 정렬이나 병합 정렬을 사용합니다. 퀵 정렬과 병합 정렬은 모두 평균적으로 O(nlogn)의 시간 복잡도를 갖고 있는 정렬 알고리즘입니다. 이러한 시간 복잡도가 가능한 것은 두 알고리즘 모두 재귀적으로 범위를 분할하면서 정렬하기 때문입니다. 퀵 정렬 - 위키백과https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC 합병 정렬 - 위키백과https://ko.wikipedia.org/wiki/%ED%95%A9%EB.. 15. 위상정렬 (Topological Sorting) 위상 정렬(topological sorting)은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미합니다. 위상정렬 - 위키백과https://ko.wikipedia.org/wiki/%EC%9C%84%EC%83%81%EC%A0%95%EB%A0%AC 정의를 보아서는 쉽게 와닫지 않을듯하여 예시를 들어 설명하도록 하겠습니다. 스타크래프트를 플레이한다고 가정해보겠습니다. 게임에서 승리하기 위해서는 유닛을 생산하고 상대방을 공격하여 상대방의 모든 건물을 부숴야합니다. 유닛을 생산할 때에 더 높은 파워를 가진 고급 유닛을 생산하기 위해서는 고급 유닛을 생산할 수 있는 건물을 지어야하는데 단순히 원한다고 지을 수가 있는게 아니라 사전에 지어야하는 여러 건물들이 있습니다. 기초 건.. 14. 인덱스 트리(Indexed Tree) 인덱스 트리는 순서를 갖는 정보들이 주었을 때, 구간의 대표값이나 연산 결과를 빠르게 얻을 수 있는 자료구조입니다. 구간의 정보를 빠르게 파악할 수 있는 이유는 정보들을 2진 트리로 구성하여 두 개 노드의 부모노드에 대표값이나 연산결과를 저장했다가 구간이 주어졌을 때 최대한 커버가 가능한 구간 정보부터 압축적으로 정보를 추출하기 때문입니다. 아래와 같이 8개의 정보를 갖고 있는 배열이 주어졌다고 해봅시다. 1 ~ 8자리까지 각 배열의 자리에는 랜덤한 숫자가 주어져 있고 우리는 구간이 주어졌을 때 그 구간의 합이 얼마인지 알고 싶습니다. 1 2 3 4 5 6 7 8 3 2 8 1 2 3 5 6 만일 구간의 합을 구한다고 했을 때 단순하게 계산한다고 하면 매번 그 범위 내에서 for문을 이용하여 합을 구해야.. 13. 이분 탐색 (Binary Search) 이진 탐색이라고도 부르는 이분 탐색은 간단하면서도 강력한 알고리즘입니다. 기본적인 알고리즘의 아이디어는 이미 정렬이 되어 있는 자료구조에서 특정 값을 찾을 때에 탐색 범위를 절반씩 나눠가면서 해당 값을 찾아가는 것입니다. 절반씩 나눠가면서 탐색하는 것에서 이분 탐색이라는 이름이 나왔다는 것을 알 수 있습니다. 이진 탐색 - 나무위키https://namu.wiki/w/%EC%9D%B4%EC%A7%84%20%ED%83%90%EC%83%89 예를 들어 설명해보도록 하겠습니다.아래와 같이 배열이 하나 주어졌다고 해봅시다. 0 1 2 3 4 5 6 7 8 9 2 5 6 10 12 13 15 17 19 23 여기서 우리가 알고 있는 것은 이 배열이 작은 수부터 큰 수까지 오름차순으로 정렬이 되어 있다는 것 뿐이고,.. 12. 최소 공통 조상 (LCA: Lowest Common Ancestor) 최소 공통 조상은 트리구조에서 특정 두 노드의 가장 가까운 공통 조상을 찾는 알고리즘입니다. 트리구조라는 용어 자체가 생소하신 분들은 나무위키의 트리(그래프) 항목을 참고하시기 바랍니다. 트리(그래프) - 나무위키https://namu.wiki/w/%ED%8A%B8%EB%A6%AC(%EA%B7%B8%EB%9E%98%ED%94%84) LCA(Lowest Common Ancestor) 알고리즘은 일반적으로 앞에서 이야기한 정의에 따라 가장 가까운 위치의 공통 조상을 찾는데 쓰이지만 이는 또한 두 노드의 가장 가까운 거리를 찾는다는 의미도 있기 때문에 노드간 거리를 구할 때도 사용됩니다. LCA 알고리즘은 단순하게 loop를 이용하여 공통조상을 찾는 방식과 DP나 세그먼트 트리를 이용하여 찾는 방식이 있습니다.. 이전 1 2 3 다음
