CS/알고리즘

유클리드 호제법 (Euclidean-algorithm)

0. 글을 시작하며 우리가 문제해결을 하다보면 최대 공약수를 구해야하는 경우가 있습니다. 우선 가장 쉽게 생각해볼 수 있는 것은 초등학교 때 배우는 두 수를 모두 소인수 분해 후 공약수를 찾아 모두 곱하는 방식입니다. 예를 들어 우리가 27과 45의 최대공약수를 구한다고 할 때 보통 이런 그림을 그려서 최대 공약수를 구하곤 합니다. 그래서 우리가 두 자연수의 최대 공약수를 구해야하는 문제를 코드로 작성해서 해결해야할 때 가장 먼저 쉽게 떠올리고 접근하게 되는 방식이 바로 위의 방식일 것 입니다. 이를 코드로 다음과 같이 옮겨서 문제해결을 할 수 있지만 이 방식에는 한 가지 문제점이 있습니다 (여기서는 numberA가 numberB보다 크거나 같은 수임을 전제로 합니다). private static int..

Greedy Algorithm

안녕하세요. 이번 포스팅에서는 Greedy Algorithm에 대해서 다뤄보도록 하겠습니다. 코딩테스트를 준비하는 입장에서 Greedy 알고리즘은 가장 기본이 되는 유형으로 여겨집니다. 난이도가 상대적으로 낮은 유형에 해당하며, 그렇기 때문에 가장 먼저 시작할 수 있는 유형으로 많이 추천됩니다. 하지만 가장 기본이 되는 유형이라고 해서 결코 쉬운 문제들만 있는 것은 아닙니다. 실제로 여러 문제들을 살펴보면 Greedy 유형이더라도 많이 어려운 문제들도 있습니다. 즉, 결코 만만하게 볼 유형은 아닙니다. 그렇다면 지금부터 Greedy 알고리즘이 무엇인지에 대해서 알아보도록 하겠습니다. Greedy Algorithm? 탐욕 알고리즘? 우선 알고리즘의 이름에 사용되는 "Greedy" 라는 단어의 사전적 정의를..

Graph 에 대한 개념정리 - 4

주제 : Activity Network Graph의 응용에서는 'activity network'라는 구조가 존재하는 데 이에 대해서 알아보는 시간을 가지도록 하겠다. Activity Network은 다음과 같이 크게 두 종류로 나눠볼 수 있다. 1. AOV (= Active On Vertex) 2. AOE (= Active On Edge) 1. AOV (= Activity On Vertex) Network 1. A directed graph 2. vertex : 어떤 task나 activity를 의미 3. edge : activity 간의 선후관계(precedence relation)를 의미 2. AOE (= Activity On Edge) Network 1. Edge가 Activity를 의미하며, ve..

Graph에 대한 개념정리 - 3

이번 정리에서는 Graph의 응용문제에 대해서 다뤄보도록 하겠다. Shortest Path Weighted Graph의 특정 vertex에서 다른 모든 vertex에 이르는 최단거리 path를 구하는 문제 (single source all destination) 이 문제 또한 graph 관련 알고리즘을 적용함으로서 해결할 수 있다. 그렇다면 이에 대해서 알아보도록 하겠다. Shortest Path Algorithm 1. Adjacency Matrix에서 기준 vertex에 해당하는 행(row)을 초기값으로 설정 2. 다음을 (n-2)회 반복 - 아직 방문하지 않은 vertex 중에서 가장 가까운 vertex를 선택 - 해당 vertex를 거쳐서 가는 path가 현재 알려진 path보다 짧으면 수정한다. ..

Graph에 대한 개념정리 - 2

Spanning Tree 하나의 graph를 G라고 표현할 때, 우리는 Spanning Tree를 아래와 같이 정의할 수 있다. G가 가지는 모든 Vertex를 연결하는 Cycle이 없는 Subgraph 사실 Cycle이 존재하지 않는 Graph는 Tree로 볼 수도 있다. 그래서 이와 같이 graph를 다루고 있지만 Spanning Tree 라는 용어가 사용되는 것이다. 그래서 우리는 이 Spanning Tree에 약간의 제약조건을 부여함으로써 또 다른 이론이 만들어지기도 한다. 그래서 중복되는 edge가 없이 모든 vertex에 대해서 cycle 없이 연결이 이뤄져야 하기 때문에 n-1개의 edge를 가지게 된다. BFS / DFS Spanning Trees Spanning Tree의 종류에 대해서 ..

Graph에 대한 개념정리 - 1

Graph graph는 다음 두 가지 요소로 이루어진다. 1. Vertex의 집합 2. Edge의 집합 여기서 Vertex는 "어떤 대상의 객체"를 의미하고, Edge는 "Vertex간의 관계"를 뜻한다. Graph와 관련된 용어정리 Graph와 관련되서 알고 있어야할 용어의 종류는 다음과 같다. 1. Vertex 2. Edge 3. Adjacent 4. Path 5. Length of a path 6. Connected 7. Connected Components 8. Cycle Vertex 실세계에서의 어떤 대상을 표현하는 객체 문헌에 따라서 Vertex를 "node"라고 표현하기도 함. Edge Vertex 간의 관계 두 Vertex간에 관계가 존재하는 경우 Edge가 존재한다. 문헌에 따라서 Edg..