본문 바로가기

Algorithm

알고리즘과 자료구조 알고리즘을 공부하는 사람이 자료구조를 이해하지 못한다는 것은 어불성설이라고 생각합니다. 그만큼 알고리즘을 학습하는 사람에게 자료구조는 기본소양과 같습니다. 하지만 일반적으로 구현되어 있는 라이브러리를 이용하는 경우가 대부분이기 때문에 직접 구현해보라는 요구를 받게 되었을 때, 실제 구현하지 못하는 경우가 상당히 많습니다. 자료구조를 정확히 이해하지 못한다면, 어떤 알고리즘을 풀이할 때 어떤 자료구조를 사용하는 것이 옳은가에 대한 판단도 스스로 내리지 못하고 특정 알고리즘을 풀 때는 이 자료구조를 사용해야한다고 기계적으로 암기해버리는 경우가 많습니다. 이러한 문제가 발생하는 원인은 자료구조의 원리를 제대로 이해하지 못하고 있으며, 어떤 방식으로 구현되어 있는지를 이해하지 못하고 있기 때문입니다. 제대로 자..
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들을 이용하여 특정 목표에 맞는 값을 찾아주는 알고리즘이라고 할 수 있습니다. 여기서 주의해야할 것은 어디까지나 연속된 값들을 이용하여 풀어나가는 문제에 한정적으로 사용해야한다는 것입니다. 만일 주어진 값들의 연속성이 선행조건으로 주어지지 않는 경우에는 투 포인터를 사용할 수 없습니다. 그런 면에서 문제에서 주어진 값들을 그대로 활용해야하는 경우나 ..
에라스토테네스의 체 (소수 구하기) 소수 구하기 알고리즘은 간단하지만 확실하게 정리해두지 않으면 헷갈리기 좋은 문제라고 생각한다. 하지만 다른 알고리즘들과 마찬가지로 한번만 확실하게 이해해두면 바로바로 구할 수 있기 때문에 한번정도는 정리해두는 것이 좋다. 소수는 정규 교육과정을 거친 사람은 누구나 이해하고 있을만큼 간단한 개념이다. 1을 제외하고 자기 자신으로만 나누어 떨어지는 수. 이것이 소수의 정의이다. 소수에는 많은 수학적 이론과 증명이 배경에 있겠지만 과감히 생략하고 이 정의에 입각하여 알고리즘적으로 소수를 판가름 하는 코드를 작성해보겠다. 소수에 대해서는 아래의 링크를 참고하자. 소수(수론) - 나무위키https://namu.wiki/w/%EC%86%8C%EC%88%98(%EC%88%98%EB%A1%A0) 소수는 1과 자기 자신..
트라이(Trie) 문자열 관련 알고리즘은 정말 다루기 힘든편에 속한다. 하지만 그중에도 잘만 이해하면 유용하게 사용할 수 있는 알고리즘이 몇있다. 그중에서 트라이(Trie)에 대해서 얘기해보고자 한다. 트라이 - 나무위키https://namu.wiki/w/%ED%8A%B8%EB%9D%BC%EC%9D%B4 트라이 알고리즘은 여러 단어들이 주어진 경우, 특정 단어가 예시로 주어진 단어들 중에 포함되는가를 빠르게 파악할 수 있는 알고리즘이다. 예를들어 n개의 단어가 주어져있고, 각 문자열의 길이가 m인 경우 단순하게 이 단어들중에 특정 단어가 포함되어있는지 확인하려면 최대 O(nm)의 시간 복잡도를 갖게된다. 하지만 트라이를 사용하면 시간복잡도가 O(m)으로 압도적으로 단축되게 된다. 어떻게 이렇게 시간이 줄어들 수 있는지 생..
트리의 순회 트리 구조를 순회하는 방법은 일반적으로 전위, 중위, 후위 순회 세가지 방법이 있다. 방법이 복잡하지는 않지만 정리해두지 않으면 헷갈리니 기회가 되면 한번 정리해보고 직접 코드로 구현해보는 것이 좋을 것같다. 전위 순회는 루트 노드부터 시작해서 왼쪽 서브트리를 타기 전에 노드의 자료를 확인하고 그다음 왼쪽 서브트리로 이동해서 마찬가지로 전위 순회를 하게 되어있고, 왼쪽 서브트리에 대한 전위 순회를 마친 후 우측 서브트리의 전위 순회가 일어난다. 중위 순회는 루트 노드에서 시작해서 좌측 서브트리에 대한 중위 순회가 먼저 일어나고, 중위 순회가 더이상 일어날 수 없는 지점에서 노드의 자료를 확인하면서 좌측 서브트리의 중위 순회를 종료시킨다. 그다음 우측 서브트리의 중위 순회가 일어나게 된다. 후위 순회는 루..
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..

티스토리툴바