목적 요즘은 IT 기업에 개발자로 취업하기 위해서 코딩테스트라는 관문을 통과해야하는 경우가 허다하다. 이러한 기업들의 요구 때문인지 자연스럽게 코딩테스트를 위한 알고리즘 공부를 중요시 하고 있고 심지어 코딩테스트를 대비하기 위한 알고리즘 학원과 300만원이 넘는 방학 집중 코스까지 생겨났다. 나도 알고리즘을 시작하려던 때에 어떻게 하면 알고리즘을 제대로 효율적으로 배울까를 고민하며 알고리즘 공부법에 대한 블로그글, 유투브 영상 등을 찾아다녔고 알고리즘학원에 직접 전화해보기도 했다. 나와 같은 고민을 하는 분들에게 내가 공부했던 비효율적이지만 효율적인 알고리즘 공부법을 소개하고자 한다. 알고리즘 공부법을 찾는 당신에게 공부할까를 정하는 문제는 선택이 필요하고 그에 따른 책임과 리스크가 따르기 때문에 고민이 되기 마련이다. 특히 취업을 위한 코딩테스트를 준비하고 있는 상황이라면 최대한 짧은 시간 내에 좋은 성과를 내야한다는 생각이 고민을 더 어렵게 만든다. 나는 알고리즘을 공부하는…

참고 자료 본 글은 내가 정리하기 위해 따로 해놓은 것으로 나는 갓멍멍님의 글을 참고했다. KMP 알고리즘 KMP 알고리즘은 문자열(텍스트)에서 특정 문자열(패턴)을 효율적으로 찾아내기 위한 방법이다. 문자열(T)에서 패턴(P)를 찾아내는데 필요한 시간이 O(N*M)이라고 할때 이 알고리즘을 사용하면 O(N+M)만에 처리 가능하다! 문자열의 i번째부터 패턴 j번째와 비교할 때 다를 경우에 문자열의 i+1 과 패턴의 0번째 부터 비교를 하는 것이 아니라 이미 같았던 부분 중 패턴을 굳이 처음부터 하지 않아도 되는 경우는 j를 0이 아닌 pi[j]에서 진행하도록 한다. 쓸만한 정보 Pi(접두사와 접미사) 이 알고리즘에서 가장 중요한 부분이 바로 이 검색에 앞서 만들어둔 pi이다. pi[i]는 패턴의 길이가 i일때 접두사와 접미사가 같은 개수를 의미한다. 예를 들어 패턴을 “ABAABAB”라고 할 때 pi는 다음과 같이 표현 할 수 있다. 그 후 pi를 이용해서 문자열을 n만큼만 훑으…

LCA란 LCA란 Lowest Common Ancestor의 약자로 트리 속 두 노드의 가장 가까운 조상 노드를 의미한다. 이것을 BFS나 DFS를 이용해 모든 경로를 훑어봄으로써 두 노드 사이의 같은 조상을 찾을 수도 있겠지만 이를 더욱 빠르게 하기 위해 만든 알고리즘이 LCA 알고리즘이다. LCA 알고리즘 방법은 간단하다. 1.트리를 만들고 각 노드의 조상들을 저장한다. 2.두 노드의 깊이를 같게 깊이가 깊은 노드를 조상으로 업데이트 시켜준다. 3.두 노드를 조상으로 올리면서 가장 가까운 공통조상을 찾아준다. 트리 만들기 알고리즘 트리를 만드는 방법은 두가지가 있다. 자세한 내용은 코드를 보면서 설명하고자 한다. BFS를 이용한 트리 만들기 위 코드에서 build_tree는 트리를 만들어주는 함수이다. 1번 노드를 기준으로 해서 트리를 뻗쳐나가고 그에 따라서 깊이인 level을 저장해주고 parent를 업데이트 시켜준다.(parent에 대한 내용은 좀있다 다시 설명하겠다.) D…

세그먼트 트리란? 세그먼트 트리는 트리의 각 노드에 어레이 부분부분의 연산 결과를 미리 저장해놓으므로써 탐색 시간을 OlogN)으로 감소시켜준다. 주로 부분합, 부분최소, 최대값을 찾는데 사용된다. 세그먼트 트리 구조 세그먼트 트리의 리프 노드와 나머지 노드는 다음과 같은 의미를 가진다. 리프 노드 : 해당 어레이 값 다른 노드 : 오른쪽 자식과 왼쪽 자식을 연산한 결과 값 구조는 아래와 같은 구조를 가지게 된다. 사진 세그먼트 트리 만들기(합 구하기용) 만약 node를 root node로 주고 start, end를 어레이 전체 범위로 잡게 되면 리컬션을 통해 tree가 완성 된다. 세그먼트 트리 탐색(합 구하기용) 만약 어레이 원소가 10개라고 할 때 0-9까지 모든 원소의 합을 찾고 싶다고 하면 아래와 같이 루트 노드만 확인하면 될 것이다. 사진 하지만 만약에 2~4까지 범위의 합을 구하고 싶다고 하면 아래와 같이 두개의 원소를 확인하면 될 것이다. 사진 그래서 만약 노드가 담…

위상 정렬(Topological Sort)이란? 여태까지 정렬 기준이 였다면 **위상정렬의 정렬 기준은 ‘위상’**이다. 여기서 위상이란 incoming edge의 수를 의미한다. 위상 정렬은 Directed Acyclic Graph(DAG)에서만 가능한 정렬방법이다. DAG란 각 edge가 방향을 가지고 있는데 cycle이 발생하지 않는 경우를 말한다. Cycle이 있으면 무한 루프를 발생시킬 것이다!! 보통 일의 순서를 정하는 알고리즘에서 많이 사용된다. Topological Sorting 알고리즘 알고리즘의 과정은 다음과 같다. 각 vertex의 위상(incoming edge의 수)를 저장한다. 정점(위상이 0인 노드)을 다 큐에 넣어준다. 큐에서 노드를 하나씩 꺼내서 위상정렬에 넣어준다. 꺼낸 노드와 연결된 노드의 위상을 하나씩 낮춰주고 엣지를 없애준다. 위상이 0인 노드를 큐에 다시 넣어준다. 3번부터 5번을 큐가 빌 때까지 반복한다. 예시 다음과 같은 그래프에 대해 위상…

링크드 리스트 링크드 리스트는 나의 오랜 숙적이다. 항상 최후의 방법으로 미뤄놓는 방법인데 알고리즘을 하면서 링크드 리스트를 사용하지 않고는 풀기 어려운 문제가 나와서 하는 수 없이 정리를 해본다ㅎㅎ 더블 링크드 리스트란? 보통 링크드 리스트라고 하면 다음 원소가 무엇인지(next)를 포인터로 연결해놓게 된다. 하지만 더블 링크드 리스트는 이전 원소의 값도 알려주는(prev) 포인터가 존재한다. 더블 링크드 리스트는 지금 element 이후와 이전의 원소 정보가 모두 필요할 때 사용한다. ex) 원소 정방향, 역방향으로 출력하기 참고 더블 링크드 리스트 참고 사이트 여기서 tail이 움직일 수 있게 코드를 수정했다. Node 구조체 Node를 추가할 때는 ptr 정보를 같이 받아와서 ptr 바로 뒤에다가 새로 생성된 노드를 연결시켜준다. Double Linked List 구조체 더블 링크드 리스트에서 더미를 head와 tail에 놔둬서 링크드 리스트가 범위를 초과하지 않을 수 있게…

Minimum Spanning Tree란? Minimum Spanning Tree란 Undirected Graph 내에서 Cycle이 발생하지 않는 한도 내에서 모든 vertex가 연결되있는 tree 중 weight의 합이 가장 작은 tree를 의미한다. 그렇기 때문에 무조건 Edge의 갯수는 Vertex 갯수 - 1 개이다. 어떻게 찾지? 일단 edge의 set인 A를 만들자 처음에 A가 빈 상태에서 하나씩 넣은 거다. 여기서 중요한 것은 safe edge만 넣는다. Safe Edge란 A가 MST의 subset이라면 A를 추가해도 MST의 subset을 유지할 때의 Edge를 의미한다. Kruskal 알고리즘의 기본 개념 일단 Edge를 다 weight가 작은 순으로 나열한다. A라는 숲을 유지한 상태에서 safe edge를 찾아서 추가해준다. 즉 이 알고리즘은 GREEDDDY이다!!! Kruskal 알고리즘 스텝 edge을 weight 작은 순으로 sorting한다. 가장 작…

기존 Rank 활용 방법 이전 포스트에서 그림으로 표현했듯이, union과 find를 계속 진행하다보면 worst case에서는 그림과 같이 나오게 된다. 사진 그림과 같이 작은 트리가 큰 트리에 붙는 형식으로 이는 Linked List의 형태를 띄게 된다. 이것의 시간 복잡도는 O(log n) 만큼 걸리게 된다. 이를 union by rank라고 한다. Path Compression 활용 방법 다른 방법이 또 있다면 path compression이다. 이 방법은 find()가 호출될 때 tree를 납짝하게 만드는 것이다. find()가 x에 대해서 호출되면 x로부터 root node를 찾기 시작한다. 찾아서 root node를 반환시켜준다. 그리고 root node에 이어붙이기 때문에 Rank 활용 때처럼 중간에 있는 친구들을 다 search하지 않아도 된다는 장점이 있다. Rank와 Path Compression을 활용하면 기존의 방법보다 훨씬 효율적인 코드를 짤 수 있다! R…

Disjoint-set 구조와 Union-Find 알고리즘이란? Disjoint set 이란 연결이 끊어진 원소들의 집합을 의미 한다. 이 데이터 구조를 위해서 Union-Find 알고리즘이 2가지 주요한 operation을 제공한다. Find : 어떤 원소가 어느 집합에 있는지 찾아준다. 주로 두개의 element가 같은 집합에 있는지 확인하는데 사용된다. Union : 2개의 집합을 하나의 집합으로 합쳐준다. 이 알고리즘은 Cycle을 찾는데 아주 용이하다. Union-Find의 활용 코드 (사이클 찾기) 사진 위와 같은 그래프 일 때 사이클 여부를 Union-find를 이용해서 확인해보자! 주석을 확인하면 훨씬 이해가 빠를 것이다. 헷갈림 주의!! union을 하게 되면 같은 집합에 있는 원소의 child node가 같아지게 된다. 밑에 그림을 참고하자:) 사진 느낀점 내가 bfs로 짰을 때보다 훨씬 효율적인지는 모르겠지만 일단 굉장히 직관적이다. 두개의 집합을 합치는 방법도…

Shortest Path 최단경로를 찾는 문제의 특징은 다음과 같다. Input : directed graph G = (V, E) with weight function w : E -> R S에서 D까지의 minimum weight을 가지는 path를 찾는 문제이다. Weight w(p) of path p : p로 가는 길에 있는 모든 edge weight의 합이다. u부터 v 까지의 shortest-path weight은 다음으로 표현한다 S(u,v) = if path가 있으면 u부터 v까지 오는 path 중의 min . 없으면 무한대 Variants 최단거리를 찾는 문제는 크게 4종류가 있다. Single-source shortest path : 하나의 S에서 모든 vertex까지 최단거리 Single-destinations : 모든 vertex에서 하나의 D까지의 최단거리 Single-pair : 하나의 S로 부터 모든 하나의 D까지의 최단거리 All-pair : 모든 vert…

Branch and Bound? Branch(가지)와 Bound(범위)를 이용한 방법으로 최적의 해를 찾기 위해 어느 정도의 범위를 정해두고 범위를 벗어난 값들을 가지치기 하는 방법을 의미한다. BFS를 이용해 뎁스를 늘려가며 최선의 값을 찾는다고 했을 때 모든 리프까지 가지 않고 어느정도의 바운더리를 정하고 바운더리 밖에 있는 친구들을 제하는 방법을 의미한다. Knapsack에 어떻게 적용해? 각 원소를 넣는 경우와 안 넣는 경우로 두 경우로 가지(Branch)를 쳐가는데 현재 원소의 최대치로 넣었을 때의 경우(bound)가 현재 찾은 최대 가치(max_benefit)을 넘지 못하면 더 이상 볼 가치가 없는 친구이므로 더이상 뻗지 않는다.(queue에서 넣지 않는다.) 여기서 queue를 priority queue로 하면 맥스 근처 값을 더 빨리 찾을 수 있기 때문에 가치가 없는 친구들을 더 많이 걸러낼 수 있다! 가치가 없다고 여기는 경우는 두가지이다. bound <= max_…

Knapsack 문제란? 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제를 말한다. 크게 두가지 종류의 문제로 나뉘는데 물건을 쪼갤 수 있다면 Fractional Knapsack Problem 물건을 쪼갤 수 없다면 0-1 Knapsack Problem 이라고 한다. 모든 문제에서 일단 item이라는 struct를 사용했다. 쪼갤 수 있다면? (Greedy) 만일 쪼갤 수 있다면 말그대로 가치( value/weight )가 제일 높은 애들을 최대한 담고 공간이 부족하다면 하나를 쪼개서 부분적으로 넣고 끝내면 된다. 즉, 제일 좋은 것을 취해가는 Greedy Algorithm을 이용하면 된다. Greedy Algorithm 활용 코드 0-1 Knapsack Problem DP 되나? Subproblem으로 문제를 쪼개서 부분의 답이 전체의 답이 되는지를 먼저 확인해보자 만일…