알고리즘
12 posts
나의 비효율적이지만 효율적인 알고리즘 공부법 (코딩테스트를 준비하는 이들에게)

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

December 05, 2019
회고
알고리즘
(알고리즘) KMP 문자 검색 알고리즘 + 백준 1786번 찾기

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

September 16, 2019
알고리즘
(알고리즘) LCA 알고리즘 + C++ 예제코드

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

July 27, 2019
알고리즘
(알고리즘) 세그먼트 트리 알고리즘 + 예제 코드

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

July 13, 2019
알고리즘
(알고리즘) 위상 정렬 Topological Sort + C++ 예제

위상 정렬(Topological Sort)이란? 여태까지 정렬 기준이 였다면 위상정렬의 정렬 기준은 ‘위상’이다. 여기서 위상이란 incoming edge의 수를 의미한다. 위상 정렬은 Directed Acyclic Graph(DAG)에서만 가능한 정렬방법이다. DAG란 각 edge가 방향을 가지고 있는데 cycle이 발생하지 않는 경우를 말한다. Cycle이 있으면 무한 루프를 발생시킬 것이다!! 보통 일의 순서를 정하는 알고리즘에서 많이 사용된다. Topological Sorting 알고리즘 알고리즘의 과정은 다음과 같다. 각 vertex의 위상(incoming edge의 수)를 저장한다. 정점(위상이 0인 노드)…

July 02, 2019
알고리즘
(알고리즘) Double Linked List C++ 구현 알고리즘

링크드 리스트 링크드 리스트는 나의 오랜 숙적이다. 항상 최후의 방법으로 미뤄놓는 방법인데 알고리즘을 하면서 링크드 리스트를 사용하지 않고는 풀기 어려운 문제가 나와서 하는 수 없이 정리를 해본다ㅎㅎ 더블 링크드 리스트란? 보통 링크드 리스트라고 하면 다음 원소가 무엇인지(next)를 포인터로 연결해놓게 된다. 하지만 더블 링크드 리스트는 이전 원소의 값도 알려주는(prev) 포인터가 존재한다. 더블 링크드 리스트는 지금 element 이후와 이전의 원소 정보가 모두 필요할 때 사용한다. ex) 원소 정방향, 역방향으로 출력하기 참고 더블 링크드 리스트 참고 사이트 여기서 tail이 움직일 수 있게 코드를 수정했다. …

June 29, 2019
알고리즘
(알고리즘) Minimum Spanning Tree MST 알고리즘 - Kruskal 알고리즘

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 알고리즘의 기…

May 19, 2019
알고리즘
(알고리즘) Union Find 알고리즘 강화버전 - Rank, Path Compression 사용

기존 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…

May 19, 2019
알고리즘
(알고리즘) Disjoint Set 구조와 Union Find 알고리즘

Disjoint-set 구조와 Union-Find 알고리즘이란? Disjoint set 이란 연결이 끊어진 원소들의 집합을 의미 한다. 이 데이터 구조를 위해서 Union-Find 알고리즘이 2가지 주요한 operation을 제공한다. Find : 어떤 원소가 어느 집합에 있는지 찾아준다. 주로 두개의 element가 같은 집합에 있는지 확인하는데 사용된다. Union : 2개의 집합을 하나의 집합으로 합쳐준다. 이 알고리즘은 Cycle을 찾는데 아주 용이하다. Union-Find의 활용 코드 (사이클 찾기) 사진 위와 같은 그래프 일 때 사이클 여부를 Union-find를 이용해서 확인해보자! 주석을 확인하면 훨씬 …

May 19, 2019
알고리즘
(알고리즘) Shortest Path 찾기 - Bellman-Ford, DAG, Dijkstara 알고리즘

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-sourc…

May 09, 2019
알고리즘
(알고리즘) Knapsack 알고리즘 2 Branch and Bound, Heap + 코드

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

April 20, 2019
알고리즘
(알고리즘) Knapsack 알고리즘 Greedy, DP + 코드

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

April 11, 2019
알고리즘