훈동

algorithm

  • Longest Increasing Subsequence (LIS)를 NlogN에 구하기

    최장 증가 수열이라고 불리는 Longest Increasing Subsequence (LIS)라는 문제는 간단하지만 강력한 문제 중 하나이다. 이 문제는 다이나믹 프로그래밍을 활용한 O(N2)O(N^2) 풀이와 이분 탐색을 활용한 O(NlogN)O(NlogN) 풀이가 잘 알려져 있는데, 이분 탐색을 활용한 풀이가 어떻게 최적화되었는지에 대한 설명을 이 글에서 적고자 한다. Naive solution: Bruteforcing 간단하게 생각해보자. 모든 부분 수열에서 오름차순을 이루는지 확인해보면 된다. 모든 원소가 부분 수열에 속하거나 속하지 않는 두 가지 상태를 가진다. 길이 NN의 수열이라면 2N−12^N-1개의 부분 수열이⋯

  • 알고리즘에서의 해시 함수

    해싱이라는 건 알고리즘 문제풀이를 해 봤다면 한 번쯤은 들어 보았을 분류이다. 주로 파이썬의 dict, C++의 unordered_set 등이 해싱을 사용해서 구현되었다. 삼성 동계 DX 알고리즘 특강을 들을 때, 해싱을 직접 구현해서 문제를 풀어야 하는 일이 있었다. 해시 함수를 직접 만든 뒤에, 해시가 가지는 시간상의 이점을 활용해서 문제를 해결한다. 그때 당시에는 문제를 푸는 데 꽤나 고생했다. 시간이 조금 지나서 다시 공부해보고 기록한다. 정리한 글에 오류가 있을 수 있습니다. 댓글로 남겨주시면 반영하겠습니다.방문해주셔서 고맙습니다⋯

  • Minimum Spanning Tree 알고리즘의 증명

    MST를 알고 있고, 크루스칼과 프림을 알고 있지만 그냥 쓰고있지 않은가? 이 글을 통해서 “왜 돼?” 에 대한 해답을 찾을 수 있었으면 좋겠다. 그래프가 주어졌을 때, 모든 노드를 연결하는 트리를 Spanning Tree라고 하고, 이 중에서 가장 간선의 가중치의 합이 낮은 트리를 Minimum spanning tree(이하 MST)라고 한다. MST를 만드는 방법으로는 Prim, Kruskal 알고리즘으로 두 가지가 있으며, 각각 O(ElogV),O(ElogE)O(ElogV), O(ElogE) 가 소요된다. (그래프가 dense할 수록 EE 는 V2V^2 에 가까워지며, $O(ElogE) = O(ElogV^2)⋯

  • 수학적 귀납법을 사용해 재귀를 증명하기

    0. 글을 쓰는 이유와 잡다한 이야기 이번 학기에는 <알고리즘>이라는 과목을 수강한다. 나는 알고리즘을 통한 문제해결(Problem Solving)에 관심이 많아서 혼자 여러 알고리즘들을 공부해왔다. 군대를 다녀오기 전, 새내기 시절에는 동아리 내에서 알고리즘 대회를 열어 문제를 출제하기도 했었다. 코로나의 여파가 가시질 않아 이번 학기도 대부분의 과목들이 비대면으로 진행했고, 알고리즘 또한 그랬다. 1주차 강의밖에 듣지 않았지만, 느낀 게 꽤나 많다. 나의 알고리즘 공부법이 완벽하게 틀렸다고 할 수 있을 정도였다. 여러 알고리즘 유형의 문제들을 풀어왔지만, 문제에⋯

Categories