david의 CS Blog

큐(Queue)란? 큐는 스택과 달리 먼저 들어온 데이터가 먼저 나가는 자료구조이다. 줄을 서 있는 사람들을 생각하면 편할 것이다. 큐는 스택와 다르게 삽입과 삭제가 같은 곳에서 일어나지 않는다. 삭제연산은 앞(front)에서 일어나고 삽입 연산은 뒤(rear)에서 일어난다. 이 그림에서 원소 $D$를 추가하면 $C$ 뒤에 추가되고 삭제연산을 하면 가장 맨 앞의 $A$가 삭제된다. 이렇게 먼저 들어온 원소가 먼저 나가는 형태를 선입선출(FIFO: First-In-First-Out)이라고 한다. Queue의 기능 $push(x)$: $x$를 큐의 맨 뒤에 추가한다. $pop()$: 큐의 맨 앞의 원소를 삭제한다. $empty()$: 큐가 비어있으면 $1(true)$, 아니면 $0(false)$을 리턴한다...

경로 역추적 동적 계획법 문제에서는 단순히 문제의 해를 구하는 것 뿐만 아니라, 그 해를 구하기 위한 과정에서 선택해야 하는 요소들을 출력하는 문제도 존재한다. 이를 해결하기 위해선 동적계획법을 진행할 때, 메모이제이션을 통해 저장해놓은 값들을 활용하여 중간 단계에서 최종 단계까지 도달하기 위해 선택해야할 필수 요소들을 출력해야 한다. 예를 들어 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..

Longest Common Substring  LCS(Longest Common Substring)은 두 문자열이 있을 때, 두 문자열의 최장 공통 부분 수열(공통되는 문자열 중, 최대 길이의 문자열)을 구하는 문제이다. 예를 들어 두 문자열 ACAYKP와 CAPCAK의 LCS는 ACAYKP, CAPCAK => ACAK임을 알 수 있다.  이는 간단한 dp로 풀 수 있는데, 두 문자열 a, b에 대하여 항 $dp[i][j]$를 '첫 번째 문자열 a의 구간 [ i, 끝 ], 두 번째 문자열 b의 구간 [ j, 끝 ]에 속하는 LCS 길이'라고 정의하면 i) a[i]와 b[j]가 같을 때: $dp(i, j)=dp(i+1, j+1)+1$ii) 같지 않을 때: $dp(i, j)=max( dp(i+1, j), d..

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

Union Find란? Union Find는 상호 배타적 집합을 표현하는 자료구조이다. 전체 집합을 교집합이 없는 부분집합들로 나누어서 저장한다. 상호 배타적: 부분 집합 간의 교집합이 없다.(공통된 원소가 없다), 모든 부분집합의 합집합은 전체 집합이다. 집합을 표현해서 구성 요소 간의 연결 여부 또는 연결성을 가지고 있는지 여부를 따지는 문제에서 많이 사용된다. Union Find의 연산 1. $find$: 해당 원소가 어느 집합에 속해 있는지 찾기 3. $union$: 두 집합을 한 집합으로 합친다. Union Find의 구현 유니온 파인드는 트리 형태의 자료 구조이므로 각 집합을 하나의 트리 모양으로 표현할 것이다. 이와 같은 모양의 집합을 트리로 표현하면 다음과 같이 된다. 이 때 트리의 모양은..

stack이란? 스택은 가장 먼저 입력된 데이터가 맨 아래에 쌓이고 가장 최근에 입력된 데이터가 가장 위에 쌓이는 구조를 가진 LIFO 형태의 자료구조이다. 이 그림처럼 스택은 원소가 들어올 때마다 위에 차곡차곡 쌓이는 형태이다. 이 그림에서 원소 D를 추가하면 원소 C 위에 D가 올라가는 형태가 되고 삭제 연산을 하면 가장 위에 있는 $C$가 삭제된다. 이렇게 나중에 들어온 원소가 가장 먼저 나가게 되는 입출력 형태를 후입선출(LIFO: Last-In-First-Out)이라고 한다. Stack의 기능 push(x) : 원소 x를 스택의 맨 위에 추가한다. pop() : 스택에 원소가 있다면 맨 위에 있는 원소를 삭제하고 리턴한다. empty() : 스택이 비어있으면 1(true), 그렇지 않으면 0(f..

세그먼트 트리란? 구간의 정보를 포함하고 있는 자료구조로 보통 완전 이진 트리의 모양이다. 예를 들어 다음과 같은 문제가 있다. 어떤 $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번부터 탐색을 시작할 것이다. ..