david의 CS Blog

경로 역추적 동적 계획법 문제에서는 단순히 문제의 해를 구하는 것 뿐만 아니라, 그 해를 구하기 위한 과정에서 선택해야 하는 요소들을 출력하는 문제도 존재한다. 이를 해결하기 위해선 동적계획법을 진행할 때, 메모이제이션을 통해 저장해놓은 값들을 활용하여 중간 단계에서 최종 단계까지 도달하기 위해 선택해야할 필수 요소들을 출력해야 한다. 예를 들어 BOJ 12852 1로 만들기 2 와 같은 문제에서는 입력받은 자연수 N을 1로 만들기 위해 수행해야하는 연산의 순서를 출력하는 문제이다. 예를 들어 N이 10이라면 최소 횟수인 4 뿐만 아니라 10 -> 9 -> 3 -> 1의 순서를 출력해야한다. 이 문제의 해를 구하는 과정을 동적계획법으로 구현하면 다음과 같다. 1 2 3 4 5 6 7 8 9 10 11 1..

Algorithm이란? 어떤 문제를 해결하기 위한 방법과 절차 등의 집합체를 말한다. 알고리즘의 어원은 약 9세기 페르시아의 수학자인 무함마드 알콰리즈미의 이름에서 유래되었다고 한다. 문제 해결을 위해서는 여러 알고리즘을 고안하고, 이들의 효율성을 평가한 후 최적의 알고리즘을 사용한다. 알고리즘은 다음과 같은 조건을 가지는데, 이 5가지를 모두 만족해야 알고리즘이라고 할 수 있게 된다. 0개 이상의 입력이 존재 1개 이상의 출력이 존재 각 명령어의 의미가 명확해야함(명백성) 한정된 수의 단계 후에는 반드시 종료(유한성) 각 멍령어가 실행 가능해야함(유효성) 알고리즘의 표기 알고리즘을 표기하는 방법은 크게 자연어, 흐름도, 유사 코드, 프로그래밍 언어가 있다. 자연어는 한국어와 같이 알고리즘을 우리가 사용..

세그먼트 트리란? 구간의 정보를 포함하고 있는 자료구조로 보통 완전 이진 트리의 모양이다. 예를 들어 다음과 같은 문제가 있다. 어떤 $N$개의 수가 주어져 있고 다음과 같은 두 가지 연산을 실행한다. $1.$ $a$번째 수의 값에 $b$만큼 더한다. $2.$ $a$번째 수부터 $b$번째 수까지의 합을 구한다. 연산의 실행 횟수가 최대 $100000$개라고 하자. 이 때 이 두 연산을 구현해보자 for(int i=1; i> num; if(num==1){ int a, b; cin >> a >> b; arr[a]+=b; } if(num==2){ int a, b; cin >> a >> b; int sum=0; for(int j=a; j> idx >> val; update(1, 1, n, idx, val); v..

그리디 알고리즘이란? 욕심쟁이라는 이름에 걸맞게 항상 눈 앞에 있는 가장 큰 이익을 구하는 방법으로 각 단계에서 가장 최선의 선택을 하는 기법이다. 완전 탐색으로 풀기 어려운 문제를 그리디 알고리즘으로 풀면 매우 쉽게 풀 수 있는 매우 강력하면서도 어려운 알고리즘이다. 완전 탐색으론 풀기 어려운 시간 복잡도를 그리디 알고리즘으로 접근하면 보통 $O(N)$ 정도의 시간복잡도로 해결이 가능하게 된다. 하지만 각 단계의 최선의 선택이 최적의 해가 아닐 수 있으므로 그리디 알고리즘을 통해 해결 가능한 문제에만 그리디 알고리즘을 사용하여 풀 수 있다. 예를 들어 동전 문제를 보면 1) 1, 2, 5, 10원, 50원, 100원짜리 동전으로 370원을 만들려면 동전을 몇 개를 사용해야 할까?(단 동전의 개수는 매우..

분할 정복이란? 큰 문제를 작은 문제로 나누고, 그 작은 문제들에 대한 결과를 이용하여 큰 문제의 답을 구하는 방법이다. 재귀적으로 함수를 호출하면서 계산 범위를 조금씩 줄여가는 방식으로 진행된다. 분할: 주어진 문제를 2개 이상의 여러 부분 문제로 나눈다.(문제가 작아지면 풀기 쉬워지는 성질 이용) 정복: 여러 해결된 부분 문제들로 조금 더 큰 문제를 해결하여 최종적으로 답을 풀어내는 것 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net $A$의 $B$제곱을 $C$로 나눈 나머지를 구하는 문제로, 분할 정복의..

Breadth-First-Search DFS에서는 재귀 기반의 탐색 방법을 이용하여 그래프를 분기 별로 탐색했다. BFS는 Queue 기반의 탐색 방법으로, 모든 분기를 일정한 간격으로 탐색하는 방법이다. 즉, 분기가 n개 있다면 1번 분기에서 1개의 노드만큼 탐색하면 그 다음에는 2번 분기에서 1개의 노드만큼, ...을 반복하는 것이다. 다르게 표현하면 임의의 노드에서 시작하여 인접한 노드를 따라 모든 방향으로 조금씩 탐색을 진행한다. 구현은 Array를 이용해서도 가능하지만 선입선출(FIFO)의 Data Structure인 Queue를 이용하여 구현한다.   아래는 BFS가 Queue를 통해 어떻게 진행되는지 확인한다.     방문한 정점은 색을 주황색으로 표시하고, 0번부터 탐색을 시작할 것이다. ..

Depth-First-Search  탐색 공간을 탐색하기 위해 다양한 탐색 방법이 존재한다. Bruteforce, 선형 탐색, Backtracking 등이 그 예시이다. 비선형적인 탐색 공간을 탐색하기 위해서는 재귀 기반 탐색 등이 요구된다. 이는 단순한 순차 탐색으로는 비선형 공간을 탐색하기 어렵다는 것을 의미한다. 비선형 공간 중, 가장 일반적인 형태인 Graph에서의 탐색 방법을 알아보자. 이전의 Backtracking 글에서는 이미 수차례 비선형 탐색 공간에서 재귀 탐색을 시행해왔다. 본 글에서는 그래프 탐색의 종류에 대해 더욱 엄밀하게 이해하고자 한다. 그래프 공간에서의 탐색은 방식(탐색 순서)에 따라 크게 2가지로 나뉜다. DFS, BFS가 그 종류이다. DFS(Depth-First-Searc..

그래프(Graph) 그래프(graph)는 정점(vertex)과 간선(edge)로 구성되어 있는 자료구조로, 원소들간의 연결 관계를 명확하게 나타내기 위해 사용된다. 각 원소들을 나타내는 동그라미 부분이 정점(vertex, 혹은 노드(node)라고도 부른다), 정점들을 이어 연결 여부를 나타내는 선분은 간선(edge)라고 부른다. 정점의 집합은 V={0, 1, 2, 3, 4, 5, 6}로 나타낼 수 있다. 간선의 집합은 양 끝의 정점 쌍으로 표시한다. $E=${($0, 1$), ($0, 2$), ($1, 3$), ($1, 4$), ($2, 5$), ($3, 6$), ($4, 6$)}이다. 그래프의 용어들 차수(degree): 어떤 정점과 이어진 간선의 개수 ex) 0번 정점의 차수는 2이다. 인접하다(ad..

Dynamic Programming  프로그래밍을 통한 문제 해결은 결국 탐색 공간에서 원하는 해를 찾아내는 과정이다. 알고리즘의 측면에서 우리는 어떻게 하면 적은 연산을 통해 해를 도출할 수 있을지 고민하는 것이 중요하다. 동적 계획법 또한 해를 탐색하는 전략의 일종으로 해를 구하는 과정에서 불필요한 연산을 최소화하기 위해 고안된 기법이다. 동적 계획법은 문제를 여러 개의 부분 문제로 나누어 각 부분 문제에 대한 결과를 구한 다음, 그 결과들을 이용해 해결하고자 하는 원래의 문제를 푸는 최적화 기법의 일종이다. 즉, 큰 문제를 여러 부분 문제로 나눈 후, 부분 문제들의 답을 각각 구하고 그 결과값을 바탕으로 큰 문제의 결과값을 구하는 방법이다. 이렇게 말하면 쉽게 와닿지 않을 뿐더러 기법에 대한 정의가..

Sort Algorithm 데이터를 탐색하기 위해서는 데이터 공간을 어떻게 구성하는지도 중요하지만, 데이터가 어떻게 나열되어 있는지에 따라서 해를 구하는 과정이 복잡해질 수도 있고, 간단해질 수도 있다.정렬(Sorting Algorithm)은 데이터이 주어져 있을 때, 일정한 기준으로 오름차순 또는 내림차순으로 순서를 재배열하는 것이다. 정렬이 문제 해결에서 효과적인 기법을 위해 필요하지만, 만약 정렬에서 많은 시간이 소모된다면 아무리 효율적인 문제 해결 알고리즘을 사용하더라도 전체적인 알고리즘의 성능은 떨어질 것이다. 따라서 데이터를 효율적인 시간복잡도로 정렬하는 것이 중요하다. 일반적으로 최악의 경우에 $O(N^2)$의 시간복잡도가 소모되며, 가장 효율적인 Sorting Algorithm이 보통 $O..