이것이 취업을 위한 코딩 테스트다
카테고리: Algorithm
Chapter 03 그리디
03-1 당장 좋은 것만 선택하는 그리디
- 현재 상황에서 지금 당장 좋은 것만 고르는 방법
- 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 가장 큰 순서대로, 가장 작은 순서대로와 같은 기준을 알게 모르게 제시해준다
// 거스름돈
// 시간 복잡도는 O(K)
#include <bits/stdc++.h>
using namespace std;
int n = 1260;
int cnt = 0;
int coinTypes[4] = {500, 100, 50, 10};
int main() {
for (int i = 0; i < 4; i++) {
int coin = coinTypes[i];
cnt += n / coin;
n %= coin;
}
cout << cnt << '\n';
}
- 그리디 알고리즘으로 문제의 해법을 찾았을 때는 그 해법이 정당한지 검토해야 한다
- 그리디 알고리즘으로 해결 방법을 찾을 수 없다면, 그때는 이후의 장에서 다루게 될 다이나믹 프로그래밍이나 그래프 알고리즘 등으로 문제를 해결할 수 있는지를 재차 고민해보자
03-4 1이 될 때까지
// 1이 될 때까지
#include <bits/stdc++.h>
using namespace std;
int n, k;
int result;
int main() {
// N, K를 공백을 기준으로 구분하여 입력 받기
cin >> n >> k;
while (true) {
// N이 K로 나누어 떨어지는 수가 될 때까지만 1씩 빼기
int target = (n / k) * k;
result += (n - target);
n = target;
// N이 K보다 작을 때 (더 이상 나눌 수 없을 때) 반복문 탈출
if (n < k) break;
// K로 나누기
result += 1;
n /= k;
}
// 마지막으로 남은 수에 대하여 1씩 빼기 ( 0이 아닌 1이 될때까지만 빼야하니까 )
result += (n - 1);
cout << result << '\n';
}
Chapter 04 구현
04-1 아이디어를 코드로 바꾸는 구현
- 구현이란 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정
- 구현하기 어려운 문제는 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제, 특정 소수점 자리까지 출력해야 하는 문제, 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는(파싱을 해야하는) 문제, 라이브러리를 사용해야 문제 등이 있다
- 완전 탐색은 모든 경우의 수를 주저 없이 다 계산하는 해결방법을 의미하고, 시뮬레이션은 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제 유형을 의미한다
- int 자료형으로 처리할 수 없을 정도로 큰 수는 어떻게 처리해야 할까? 크기가 8바이트인 long long과 같은 자료형을 사용하자
- 메모리 제한을 염두에 두고 코딩하자 ( 데이터의 개수가 1000만 일때 메모리 사용량은 40MB )
- 시간 제한이 1초이고, 데이터의 개수가 100만 개인 문제가 있다면 일반적으로 시간 복잡도 O(NlogN) 이내의 알고리즘을 이용하여 문제를 풀어야 한다
- 문제를 어느 정도의 시간 복잡도의 알고리즘으로 작성해야 풀 수 있을 것인지 예측할 수 있어야 한다
- 자신만의 라이브러리가 구축되어 있다면 코딩테스트에 유리하다
// 상하좌우
#include <bits/stdc++.h>
using namespace std;
// N을 입력받기
int n;
string plans;
int x = 1, y = 1;
// L, R, U, D에 따른 이동 방향
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
char moveTypes[4] = {'L', 'R', 'U', 'D'};
int main(void) {
cin >> n;
cin.ignore(); // 버퍼 비우기
getline(cin, plans);
// 이동 계획을 하나씩 확인
for (int i = 0; i < plans.size(); i++) {
char plan = plans[i];
// 이동 후 좌표 구하기
int nx = -1, ny = -1;
for (int j = 0; j < 4; j++) {
if (plan == moveTypes[j]) {
nx = x + dx[j];
ny = y + dy[j];
}
}
// 공간을 벗어나는 경우 무시
if (nx < 1 || ny < 1 || nx > n || ny > n) continue;
// 이동 수행
x = nx;
y = ny;
}
cout << x << ' ' << y << '\n';
return 0;
}
// 시각
#include <bits/stdc++.h>
using namespace std;
int h, cnt;
// 특정한 시각 안에 '3'이 포함되어 있는지의 여부
bool check(int h, int m, int s) {
if (h % 10 == 3 || m / 10 == 3 || m % 10 == 3 || s / 10 == 3 || s % 10 == 3)
return true;
return false;
}
int main(void) {
// H를 입력받기
cin >> h;
for (int i = 0; i <= h; i++) {
for (int j = 0; j < 60; j++) {
for (int k = 0; k < 60; k++) {
// 매 시각 안에 '3'이 포함되어 있다면 카운트 증가
if (check(i, j, k)) cnt++;
}
}
}
cout << cnt << '\n';
return 0;
}
04-2 왕실의 나이트
// 왕실의 나이트
#include <bits/stdc++.h>
using namespace std;
string inputData;
// 나이트가 이동할 수 있는 8가지 방향 정의
int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[] = {-1, -2, -2, -1, 1, 2, 2, 1};
int main(void) {
// 현재 나이트의 위치 입력받기
cin >> inputData;
int row = inputData[1] - '0';
int column = inputData[0] - 'a' + 1;
// 8가지 방향에 대하여 각 위치로 이동이 가능한지 확인
int result = 0;
for (int i = 0; i < 8; i++) {
// 이동하고자 하는 위치 확인
int nextRow = row + dx[i];
int nextColumn = column + dy[i];
// 해당 위치로 이동이 가능하다면 카운트 증가
if (nextRow >= 1 && nextRow <= 8 && nextColumn >= 1 && nextColumn <= 8) {
result += 1;
}
}
cout << result << '\n';
return 0;
}
Chapter 05 DFS/BFS
05-1 꼭 필요한 자료구조 기초
- 탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정이다
- 대표적인 탐색 알고리즘은 DFS와 BFS 이다
- DFS와 BFS를 제대로 이해하려면 기본 자료구조인 스택과 큐에 대한 이해가 전제되어야 한다
- 자료구조란 데이터를 표현하고 관리하고 처리하기 위한 구조이다
- 스택은 선입후출(FILO) 구조이며 큐는 선입선출(FIFO) 구조이다
// 스택 예제
#include <bits/stdc++.h>
using namespace std;
stack<int> s;
int main(void) {
// 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
s.push(5);
s.push(2);
s.push(3);
s.push(7);
s.pop();
s.push(1);
s.push(4);
s.pop();
// 스택의 최상단 원소부터 출력
while (!s.empty()) {
cout << s.top() << ' ';
s.pop();
}
}
// 큐 예제
#include <bits/stdc++.h>
using namespace std;
queue<int> q;
int main(void) {
// 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
q.push(5);
q.push(2);
q.push(3);
q.push(7);
q.pop();
q.push(1);
q.push(4);
q.pop();
// 먼저 들어온 원소부터 추출
while (!q.empty()) {
cout << q.front() << ' ';
q.pop();
}
}
- 재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수가 언제 끝날지, 종료 조건을 꼭 명시해야 한다
- 컴퓨터 내부에서 재귀 함수의 수행은 스택 자료구조를 이용한다 함수를 계속 호출했을 때 가장 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료되기 때문이다
// 팩토리얼 예제
#include <bits/stdc++.h>
using namespace std;
// 반복적으로 구현한 n!
int factorialIterative(int n) {
int result = 1;
// 1부터 n까지의 수를 차례대로 곱하기
for (int i = 1; i <= n; i++) {
result *= i;
}
return result;
}
// 재귀적으로 구현한 n!
int factorialRecursive(int n) {
// n이 1 이하인 경우 1을 반환
if (n <= 1) return 1;
// n! = n * (n - 1)!를 그대로 코드로 작성하기
return n * factorialRecursive(n - 1);
}
int main(void) {
// 각각의 방식으로 구현한 n! 출력(n = 5)
cout << "반복적으로 구현:" << factorialIterative(5) << '\n';
cout << "재귀적으로 구현:" << factorialRecursive(5) << '\n';
}
05-2 탐색 알고리즘 DFS/BFS
- DFS는 깊이 우선 탐색이다
- 프로그래밍에서 그래프 표현 방식은 인접 행렬 방식과 인접 리스트 방식이 있다
- 인접 행렬 방식은 모든 관계를 저장하므로 노드 개수가 많을수록 메모리가 불필요하게 낭비된다
- 인접 리스트 방식은 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느리다
- DFS는 탐색을 수행함에 있어서 데이터의 개수가 N개인 경우 O(N)의 시간이 소요된다
- DFS는 스택을 이용하는 알고리즘이기 때문에 실제 구현은 재귀 함수를 이용했을 때 매우 간결하게 구현할 수 있다
// DFS 예제
#include <bits/stdc++.h>
using namespace std;
bool visited[9];
vector<int> graph[9];
// DFS 함수 정의
void dfs(int x) {
// 현재 노드를 방문 처리
visited[x] = true;
cout << x << ' ';
// 현재 노드와 연결된 다른 노드를 재귀적으로 방문
for (int i = 0; i < graph[x].size(); i++) {
int y = graph[x][i];
if (!visited[y]) dfs(y);
}
}
int main(void) {
// 노드 1에 연결된 노드 정보 저장
graph[1].push_back(2);
graph[1].push_back(3);
graph[1].push_back(8);
// 노드 2에 연결된 노드 정보 저장
graph[2].push_back(1);
graph[2].push_back(7);
// 노드 3에 연결된 노드 정보 저장
graph[3].push_back(1);
graph[3].push_back(4);
graph[3].push_back(5);
// 노드 4에 연결된 노드 정보 저장
graph[4].push_back(3);
graph[4].push_back(5);
// 노드 5에 연결된 노드 정보 저장
graph[5].push_back(3);
graph[5].push_back(4);
// 노드 6에 연결된 노드 정보 저장
graph[6].push_back(7);
// 노드 7에 연결된 노드 정보 저장
graph[7].push_back(2);
graph[7].push_back(6);
graph[7].push_back(8);
// 노드 8에 연결된 노드 정보 저장
graph[8].push_back(1);
graph[8].push_back(7);
dfs(1);
}
- BFS는 너비 우선 탐색이다
- BFS는 큐 자료구조를 이용하는 것이 정석이다
- BFS는 탐색을 수행함에 있어 O(N)의 시간이 소요된다
// BFS 예제
#include <bits/stdc++.h>
using namespace std;
bool visited[9];
vector<int> graph[9];
// BFS 함수 정의
void bfs(int start) {
queue<int> q;
q.push(start);
// 현재 노드를 방문 처리
visited[start] = true;
// 큐가 빌 때까지 반복
while(!q.empty()) {
// 큐에서 하나의 원소를 뽑아 출력
int x = q.front();
q.pop();
cout << x << ' ';
// 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
for(int i = 0; i < graph[x].size(); i++) {
int y = graph[x][i];
if(!visited[y]) {
q.push(y);
visited[y] = true;
}
}
}
}
int main(void) {
// 노드 1에 연결된 노드 정보 저장
graph[1].push_back(2);
graph[1].push_back(3);
graph[1].push_back(8);
// 노드 2에 연결된 노드 정보 저장
graph[2].push_back(1);
graph[2].push_back(7);
// 노드 3에 연결된 노드 정보 저장
graph[3].push_back(1);
graph[3].push_back(4);
graph[3].push_back(5);
// 노드 4에 연결된 노드 정보 저장
graph[4].push_back(3);
graph[4].push_back(5);
// 노드 5에 연결된 노드 정보 저장
graph[5].push_back(3);
graph[5].push_back(4);
// 노드 6에 연결된 노드 정보 저장
graph[6].push_back(7);
// 노드 7에 연결된 노드 정보 저장
graph[7].push_back(2);
graph[7].push_back(6);
graph[7].push_back(8);
// 노드 8에 연결된 노드 정보 저장
graph[8].push_back(1);
graph[8].push_back(7);
bfs(1);
}
05-3 음료수 얼려 먹기
// 음료수 얼려 먹기
#include <bits/stdc++.h>
using namespace std;
int n, m;
int graph[1000][1000];
// DFS로 특정 노드를 방문하고 연결된 모든 노드들도 방문
bool dfs(int x, int y) {
// 주어진 범위를 벗어나는 경우에는 즉시 종료
if (x <= -1 || x >=n || y <= -1 || y >= m) {
return false;
}
// 현재 노드를 아직 방문하지 않았다면
if (graph[x][y] == 0) {
// 해당 노드 방문 처리
graph[x][y] = 1;
// 상, 하, 좌, 우의 위치들도 모두 재귀적으로 호출
dfs(x - 1, y);
dfs(x, y - 1);
dfs(x + 1, y);
dfs(x, y + 1);
return true;
}
return false;
}
int main() {
// N, M을 공백을 기준으로 구분하여 입력 받기
cin >> n >> m;
// 2차원 리스트의 맵 정보 입력 받기
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
scanf("%1d", &graph[i][j]);
}
}
// 모든 노드(위치)에 대하여 음료수 채우기
int result = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// 현재 위치에서 DFS 수행
if (dfs(i, j)) {
result += 1;
}
}
}
cout << result << '\n'; // 정답 출력
}
05-4 미로 탈출
// 미로 탈출
#include <bits/stdc++.h>
using namespace std;
int n, m;
int graph[201][201];
// 이동할 네 가지 방향 정의 (상, 하, 좌, 우)
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
int bfs(int x, int y) {
// 큐(Queue) 구현을 위해 queue 라이브러리 사용
queue<pair<int, int> > q;
q.push({x, y});
// 큐가 빌 때까지 반복하기
while(!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
// 현재 위치에서 4가지 방향으로의 위치 확인
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
// 미로 찾기 공간을 벗어난 경우 무시
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
// 벽인 경우 무시
if (graph[nx][ny] == 0) continue;
// 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
if (graph[nx][ny] == 1) {
graph[nx][ny] = graph[x][y] + 1;
q.push({nx, ny});
}
}
}
// 가장 오른쪽 아래까지의 최단 거리 반환
return graph[n - 1][m - 1];
}
int main(void) {
// N, M을 공백을 기준으로 구분하여 입력 받기
cin >> n >> m;
// 2차원 리스트의 맵 정보 입력 받기
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
scanf("%1d", &graph[i][j]);
}
}
// BFS를 수행한 결과 출력
cout << bfs(0, 0) << '\n';
return 0;
}
Chapter 06 정렬
06-1 기준에 따라 데이터를 정렬
- 정렬 알고리즘은 이진 탐색의 전처리 과정이기도 하니 제대로 알고 넘어가자
- 정렬 알고리즘은 굉장히 다양한데 이 중에서 많이 사용하는 선택정렬, 삽입 정렬, 퀵 정렬, 계수 정렬만 이 책에서 언급한다
- 정렬 알고리즘은 면접에서 단골 문제로 출제된다는 점을 기억하자
// 선택 정렬
#include <bits/stdc++.h>
using namespace std;
int n = 10;
int arr[10] = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
int main(void) {
for (int i = 0; i < n; i++) {
int min_index = i; // 가장 작은 원소의 인덱스
for (int j = i + 1; j < n; j++) {
if (arr[min_index] > arr[j]) {
min_index = j;
}
}
swap(arr[i], arr[min_index]); // 스와프
}
for(int i = 0; i < n; i++) {
cout << arr[i] << ' ';
}
}
- 선택 정렬은 매번 가장 작은 것을 선택한다 시간 복잡도는 O(N^2) 이다
- 선택 정렬을 이용하는 경우 데이터의 개수가 10,000개 이상이면 정렬 속도가 급격히 느려진다
- 특정한 리스트에서 가장 작은 데이터를 찾는 일이 코딩 테스트에서 잦으므로 선택 정렬 소스코드 형태에 익숙해질 필요가 있다
- 삽입 정렬은 필요할 때만 위치를 바꾸므로 데이터가 거의 정렬 되어 있을 때 훨씬 효율적이다
- 삽입 정렬은 정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤에, 그 위치에 삽입된다는 점이 특징이다
// 삽입 정렬
#include <bits/stdc++.h>
using namespace std;
int n = 10;
int arr[10] = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
int main(void) {
for (int i = 1; i < n; i++) {
// 인덱스 i부터 1까지 감소하며 반복하는 문법
for (int j = i; j > 0; j--) {
// 한 칸씩 왼쪽으로 이동
if (arr[j] < arr[j - 1]) {
swap(arr[j], arr[j - 1]);
}
// 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
else break;
}
}
for(int i = 0; i < n; i++) {
cout << arr[i] << ' ';
}
}
- 보통은 삽입 정렬이 비효율적이나 정렬이 거의 되어 있는 상황에서는 퀵 정렬 알고리즘보다 더 강력하다
- 퀵 정렬은 지금까지 배운 정렬 알고리즘 중에 가장 많이 사용되는 알고리즘이다
- 퀵 정렬은 정렬 라이브러리의 근간이 되는 알고리즘이다
- 퀵 정렬은 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다
- 퀵 정렬에서는 피벗이 사용되는데 피벗을 설정하고 리스트를 분할하는 방법에 따라서 여러 가지 방식으로 퀵 정렬을 구분할 수 있다 책에서는 가장 대표적인 분할 방식인 호어 분할 방식을 기준으로 퀵 정렬을 설명한다
- 피벗의 왼쪽에는 피벗보다 작은 데이터가 위치하고, 피벗의 오른쪽에는 피벗보다 큰 데이터가 위치하도록 하는 작업을 분할 혹은 파티션 이라고 한다
- 퀵 정렬은 재귀 함수 형태로 작성했을 때 구현이 매우 간결해진다
- 퀵 정렬이 끝나는 조건은 현재 리스트의 데이터 개수가 1개인 경우이다
// 퀵 정렬
#include <bits/stdc++.h>
using namespace std;
int n = 10;
int arr[10] = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
void quickSort(int* arr, int start, int end) {
if (start >= end) return; // 원소가 1개인 경우 종료
int pivot = start; // 피벗은 첫 번째 원소
int left = start + 1;
int right = end;
while (left <= right) {
// 피벗보다 큰 데이터를 찾을 때까지 반복
while (left <= end && arr[left] <= arr[pivot]) left++;
// 피벗보다 작은 데이터를 찾을 때까지 반복
while (right > start && arr[right] >= arr[pivot]) right--;
// 엇갈렸다면 작은 데이터와 피벗을 교체
if (left > right) swap(arr[pivot], arr[right]);
// 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
else swap(arr[left], arr[right]);
}
// 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
quickSort(arr, start, right - 1);
quickSort(arr, right + 1, end);
}
int main(void) {
quickSort(arr, 0, n - 1);
for (int i = 0; i < n; i++) {
cout << arr[i] << ' ';
}
}
- 퀵 정렬의 데이터의 개수가 N개일 때 높이는 약 logN이라고 판단할 수있다 따라서 평균 시간 복잡도는 O(NlogN)이다
- 일반적으로 컴퓨터 과학에서 log의 의미는 밑이 2인 로그를 의미한다
- 퀵 정렬의 시간 복잡도는 최악의 경우 O(N^2)이 될 수 있다 이 경우는 이미 데이터가 정렬되어 있는 경우이다
- 계수 정렬 알고리즘은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용할 수 있다
- 계수 정렬은 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다
- 계수 정렬은 비교 기반의 정렬 알고리즘이 아니다
- 계수 정렬은 일반적으로 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는다는 특징이 있다
// 계수 정렬 소스코드
#include <bits/stdc++.h>
#define MAX_VALUE 9
using namespace std;
int n = 15;
// 모든 원소의 값이 0보다 크거나 같다고 가정
int arr[15] = {7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2};
// 모든 범위를 포함하는 배열 선언(모든 값은 0으로 초기화)
int cnt[MAX_VALUE + 1];
int main(void) {
for (int i = 0; i < n; i++) {
cnt[arr[i]] += 1; // 각 데이터에 해당하는 인덱스의 값 증가
}
for (int i = 0; i <= MAX_VALUE; i++) { // 배열에 기록된 정렬 정보 확인
for (int j = 0; j < cnt[i]; j++) {
cout << i << ' '; // 띄어쓰기를 기준으로 등장한 횟수만큼 인덱스 출력
}
}
}
- 계수 정렬의 시간 복잡도는 모든 데이터가 양의 정수인 상황에서 데이터의 개수를 N, 데이터 중 최대값의 크기를 K라고 할 때, 계수 정렬의 시간 복잡도는 O(N+K)이다 ( p.174 참조 )
- 계수 정렬은 데이터의 크기가 한정 되어 있고, 데이터의 크기가 많이 중복되어 있을수록 유리하며 항상 사용할 수는 없다
- 정렬 알고리즘 문제는 어느 정도 정해진 답이 있는, 즉 외워서 잘 풀어낼 수 있는 문제라고 할 수 있다
- 단순히 정렬해야 하는 상황에서는 기본 정렬 라이브러리를 사용하고, 데이터의 범위가 한정되어 있으며 더 빠르게 동작해야 할 때는 계수 정렬을 사용하자
- 코딩 테스트에서 정렬 알고리즘이 사용되는 경우를 일반적으로 3가지 문제 유형으로 나타낼 수 있다 첫째 정렬 라이브러리로 풀 수 있는 문제, 둘째 정렬 알고리즘의 원리에 대해서 물어보는 문제, 셋째 더 빠른 정렬이 필요한 문제
06-4 두 배열의 원소 교체
// 두 배열의 원소 교체
#include <bits/stdc++.h>
using namespace std;
int n, k;
vector<int> a, b;
bool compare(int x, int y) {
return x > y;
}
int main(void) {
// N과 K를 입력받기
cin >> n >> k;
// 배열 A의 모든 원소를 입력받기
for (int i = 0; i < n; i++) {
int x;
cin >> x;
a.push_back(x);
}
// 배열 B의 모든 원소를 입력받기
for (int i = 0; i < n; i++) {
int x;
cin >> x;
b.push_back(x);
}
// 배열 A는 오름차순 정렬 수행
sort(a.begin(), a.end());
// 배열 B는 내림차순 정렬 수행
sort(b.begin(), b.end(), compare);
// 첫 번째 인덱스부터 확인하며, 두 배열의 원소를 최대 K번 비교
for (int i = 0; i < k; i++) {
// A의 원소가 B의 원소보다 작은 경우
if (a[i] < b[i]) swap(a[i], b[i]); // 두 원소를 교체
// A의 원소가 B의 원소보다 크거나 같을 때, 반복문을 탈출
else break;
}
// 배열 A의 모든 원소의 합을 출력
long long result = 0;
for (int i = 0; i < n; i++) {
result += a[i];
}
cout << result << '\n';
}
Chapter 07 이진 탐색
07-1 범위를 반씩 좁혀가는 탐색
- 순차 탐색은 보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용한다
// 순차 탐색
#include <bits/stdc++.h>
using namespace std;
// 순차 탐색 소스코드 구현
int sequantialSearch(int n, string target, vector<string> arr) {
// 각 원소를 하나씩 확인하며
for (int i = 0; i < n; i++) {
// 현재의 원소가 찾고자 하는 원소와 동일한 경우
if (arr[i] == target) {
return i + 1; // 현재의 위치 반환 (인덱스는 0부터 시작하므로 1 더하기)
}
}
return -1; // 원소를 찾지 못한 경우 -1 반환
}
int n; // 원소의 개수
string target; // 찾고자 하는 문자열
vector<string> arr;
int main(void) {
cout << "생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하세요." << '\n';
cin >> n >> target;
cout << "앞서 적은 원소 개수만큼 문자열을 입력하세요. 구분은 띄어쓰기 한 칸으로 합니다." << '\n';
for (int i = 0; i < n; i++) {
string x;
cin >> x;
arr.push_back(x);
}
// 순차 탐색 수행 결과 출력
cout << sequantialSearch(n, target, arr) << '\n';
}
- 이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다
- 이진 탐색은 위치를 나타내는 변수 3개를 사용하는데 탐색하고자 하는 범위의 시작점, 끝점, 그리고 중간점이다
- 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 게 이진 탐색 과정이다
- 이진 탐색의 시간 복잡도는 O(logN)이다
- 이진 탐색을 구현하는 방법에는 2가지가 있는데 하나는 재귀 함수를 이용하는 방법이고, 다른 하나는 단순하게 반복문을 이용하는 방법이다
// 재귀 함수로 구현한 이진 탐색
#include <bits/stdc++.h>
using namespace std;
// 이진 탐색 소스코드 구현(재귀 함수)
int binarySearch(vector<int>& arr, int target, int start, int end) {
if (start > end) return -1;
int mid = (start + end) / 2;
// 찾은 경우 중간점 인덱스 반환
if (arr[mid] == target) return mid;
// 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
else if (arr[mid] > target) return binarySearch(arr, target, start, mid - 1);
// 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
else return binarySearch(arr, target, mid + 1, end);
}
int n, target;
vector<int> arr;
int main(void) {
// n(원소의 개수)와 target(찾고자 하는 값)을 입력받기
cin >> n >> target;
// 전체 원소 입력받기
for (int i = 0; i < n; i++) {
int x;
cin >> x;
arr.push_back(x);
}
// 이진 탐색 수행 결과 출력
int result = binarySearch(arr, target, 0, n - 1);
if (result == -1) {
cout << "원소가 존재하지 않습니다." << '\n';
}
else {
cout << result + 1 << '\n';
}
}
// 반복문으로 구현한 이진 탐색
#include <bits/stdc++.h>
using namespace std;
// 이진 탐색 소스코드 구현(반복문)
int binarySearch(vector<int>& arr, int target, int start, int end) {
while (start <= end) {
int mid = (start + end) / 2;
// 찾은 경우 중간점 인덱스 반환
if (arr[mid] == target) return mid;
// 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
else if (arr[mid] > target) end = mid - 1;
// 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
else start = mid + 1;
}
return -1;
}
int n, target;
vector<int> arr;
int main(void) {
// n(원소의 개수)와 target(찾고자 하는 값)을 입력 받기
cin >> n >> target;
// 전체 원소 입력 받기
for (int i = 0; i < n; i++) {
int x;
cin >> x;
arr.push_back(x);
}
// 이진 탐색 수행 결과 출력
int result = binarySearch(arr, target, 0, n - 1);
if (result == -1) {
cout << "원소가 존재하지 않습니다." << '\n';
}
else {
cout << result + 1 << '\n';
}
}
- 이진 탐색은 코딩 테스트에서 단골로 나오는 문제이니 가급적 외우자
- 이진 탐색의 원리는 다른 알고리즘에서도 폭넓게 적용되는 원리와 유사하기 때문에 매우 중요하다
- 처리해야 할 데이터의 개수나 값이 1,000만 단위 이상으로 넘어가면 이진 탐색과 같이 O(logN)의 속도를 내야 하는 알고리즘을 떠올려야 문제를 풀 수 있는 경우가 많다는 점을 기억하자
07-3 떡볶이 떡 만들기
- 전형적인 이진 탐색 문자이자, 파라메트릭 서치 유형의 문제이다
- 파라메트릭 서치는 최적화 문제를 결정 문제로 바꾸어 해결하는 기법이다
// 떡볶이 떡 만들기
#include <bits/stdc++.h>
using namespace std;
// 떡의 개수(N)와 요청한 떡의 길이(M)
int n, m;
// 각 떡의 개별 높이 정보
vector<int> arr;
int main(void) {
cin >> n >> m;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
arr.push_back(x);
}
// 이진 탐색을 위한 시작점과 끝점 설정
int start = 0;
int end = 1e9;
// 이진 탐색 수행 (반복적)
int result = 0;
while (start <= end) {
long long int total = 0;
int mid = (start + end) / 2;
for (int i = 0; i < n; i++) {
// 잘랐을 때의 떡의 양 계산
if (arr[i] > mid) total += arr[i] - mid;
}
if (total < m) { // 떡의 양이 부족한 경우 더 많이 자르기(왼쪽 부분 탐색)
end = mid - 1;
}
else { // 떡의 양이 충분한 경우 덜 자르기(오른쪽 부분 탐색)
result = mid; // 최대한 덜 잘랐을 때가 정답이므로, 여기에서 result에 기록
start = mid + 1;
}
}
cout << result << '\n';
}
- 파라메트릭 서치 문제 유형은 이진 탐색을 재귀적으로 구현하지 않고 반복문을 이용해 구현하면 더 간결하게 문제를 풀 수 있다
Chapter 08 다이나믹 프로그래밍
08-1 다이나믹 프로그래밍
- 한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘
- 어떤 문제는 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법이 있다 대표적인 방법이 바로 이번 장에서 다루는 다이나믹 프로그래밍 기법이다
- 다이나믹 프로그래밍은 탑다운 방식과 보텀업 방식이 있다
- 점화식이란 인접한 항들 사이의 관계식을 의미한다
- 프로그래밍에서는 수열을 배열이나 리스트로 표현할 수 있다
// 피보나치 함수
#include <bits/stdc++.h>
using namespace std;
// 피보나치 함수(Fibonacci Function)을 재귀함수로 구현
int fibo(int x) {
if (x == 1 || x == 2) {
return 1;
}
return fibo(x - 1) + fibo(x - 2);
}
int main(void) {
cout << fibo(4) << '\n';
}
- 다이나믹 프로그래밍은 다음 조건을 만족할 때 사용할 수 있다 첫째 큰 문제를 작은 문제로 나눌 수 있다 둘째 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다
- 메모이제이션은 값을 저장하는 방법이므로 캐싱 이라고도 한다
// 피보나치 수열 (재귀적)
#include <bits/stdc++.h>
using namespace std;
// 한 번 계산된 결과를 메모이제이션(Memoization)하기 위한 배열 초기화
long long d[100];
// 피보나치 함수(Fibonacci Function)를 재귀함수로 구현 (탑다운 다이나믹 프로그래밍)
long long fibo(int x) {
// 종료 조건(1 혹은 2일 때 1을 반환)
if (x == 1 || x == 2) {
return 1;
}
// 이미 계산한 적 있는 문제라면 그대로 반환
if (d[x] != 0) {
return d[x];
}
// 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환
d[x] = fibo(x - 1) + fibo(x - 2);
return d[x];
}
int main(void) {
// 결과는 12586269025가 나온다
cout << fibo(50) << '\n';
}
- 다이나믹 프로그래밍과 분할 정복의 차이점은 다이나믹 프로그래밍은 문제들이 서로 영향을 미치고 있다는 것
// 호출되는 함수 확인 ( 6번 강의, 21:00 참고 )
#include <bits/stdc++.h>
using namespace std;
long long d[100];
long long fibo(int x) {
cout << "f(" << x << ") ";
if (x == 1 || x == 2) {
return 1;
}
if (d[x] != 0) {
return d[x];
}
d[x] = fibo(x - 1) + fibo(x - 2);
return d[x];
}
int main(void) {
fibo(6);
}
- 큰 문제를 해결하기 위해 작은 문제를 호출하는 것은 탑다운 방식이며 작은 문제부터 차근차근 답을 도출하는 방식은 보텀업 방식이다
// 피보나치 수열(반복적)
#include <bits/stdc++.h>
using namespace std;
// 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
long long d[100];
int main(void) {
// 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
d[1] = 1;
d[2] = 1;
int n = 50; // 50번째 피보나치 수를 계산
// 피보나치 함수(Fibonacci Function) 반복문으로 구현(보텀업 다이나믹 프로그래밍)
for (int i = 3; i <= n; i++) {
d[i] = d[i - 1] + d[i - 2];
}
cout << d[n] << '\n';
}
- 다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식이다
- 엄밀히 말하면 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념을 의미하므로, 다이나믹 프로그래밍과는 별도의 개념이다
- 코딩 테스트에서의 다이나믹 프로그래밍 문제는 대체로 간단한 형태로 출제된다
- 특정한 문제를 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래 걸리면 다이나믹 프로그래밍을 적용할 수 있는지 해결하고자 하는 부분 문제들의 중복 여부를 확인해보자
08-3 개미 전사
// 개미 전사
#include <bits/stdc++.h>
using namespace std;
// 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
int d[100];
int n;
vector<int> arr;
int main(void) {
// 정수 N을 입력받기
cin >> n;
// 모든 식량 정보 입력받기
for (int i = 0; i < n; i++) {
int x;
cin >> x;
arr.push_back(x);
}
// 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
d[0] = arr[0];
d[1] = max(arr[0], arr[1]);
for (int i = 2; i < n; i++) {
// 식량 창고를 털지 않을 것이냐(d[i-1]) 털 것이냐(d[i-2] + arri[i])
d[i] = max(d[i - 1], d[i - 2] + arr[i]);
}
// 계산된 결과 출력
cout << d[n - 1] << '\n';
}
08-5 효율적인 화폐 구성
// 효율적인 화폐 구성
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> arr;
int main(void) {
// 정수 N, M을 입력받기
cin >> n >> m;
// N개의 화폐 단위 정보를 입력 받기
for (int i = 0; i < n; i++) {
int x;
cin >> x;
arr.push_back(x);
}
// 한 번 계산된 결과를 저장하기 위한 DP 테이블 초기화
vector<int> d(m + 1, 10001);
// 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
d[0] = 0;
for (int i = 0; i < n; i++) {
for (int j = arr[i]; j <= m; j++) {
// (i - k)원을 만드는 방법이 존재하는 경우
if (d[j - arr[i]] != 10001) {
d[j] = min(d[j], d[j - arr[i]] + 1);
}
}
}
// 계산된 결과 출력
if (d[m] == 10001) { // 최종적으로 M원을 만드는 방법이 없는 경우
cout << -1 << '\n';
}
else {
cout << d[m] << '\n';
}
}
Chapter 09 최단 경로
09-1 가장 빠른 길 찾기
- 최단 경로 알고리즘 유형에는 다양한 종류가 있는데 각 종류에 맞는 알고리즘을 알고 있다면 문제를 좀 더 쉽게 풀 수 있다
- 컴퓨터공학과 학부 수준에서 사용하는 최단 거리 알고리즘은 다익스트라 최단 경로 알고리즘, 플로이드 워셜, 벨만 포드 알고리즘 이렇게 3개이다 이 책에서는 이 중에 다익스트라 최단 경로와 플로이드 워셜 알고리즘 유형만 다루려 한다 이 2가지가 코딩 테스트에서 가장 많이 등장하는 유형이기 때문이다
- 다익스트라 알고리즘은 그리디 알고리즘 및 다이나믹 프로그래밍 알고리즘의 한 유형으로 볼 수 있다
- 다익스트라 알고리즘은 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다
- 다익스트라 알고리즘을 정확히 이해하고 구현할 수 있을 때까지 연습하자
// 간단한 다익스트라 알고리즘
#include <bits/stdc++.h>
#define INF 1e9 // 무한을 의미하는 값으로 10억을 설정
using namespace std;
// 노드의 개수(N), 간선의 개수(M), 시작 노드 번호(Start)
// 노드의 개수는 최대 100,000개라고 가정
int n, m, start;
// 각 노드에 연결되어 있는 노드에 대한 정보를 담는 배열
vector<pair<int, int> > graph[100001];
// 방문한 적이 있는지 체크하는 목적의 배열 만들기
bool visited[100001];
// 최단 거리 테이블 만들기
int d[100001];
// 방문하지 않은 노드 중에서, 가장 최단 거리가 짧은 노드의 번호를 반환
int getSmallestNode() {
int min_value = INF;
int index = 0; // 가장 최단 거리가 짧은 노드(인덱스)
for (int i = 1; i <= n; i++) {
if (d[i] < min_value && !visited[i]) {
min_value = d[i];
index = i;
}
}
return index;
}
void dijkstra(int start) {
// 시작 노드에 대해서 초기화
d[start] = 0;
visited[start] = true;
for (int j = 0; j < graph[start].size(); j++) {
d[graph[start][j].first] = graph[start][j].second;
}
// 시작 노드를 제외한 전체 n - 1개의 노드에 대해 반복
for (int i = 0; i < n - 1; i++) {
// 현재 최단 거리가 가장 짧은 노드를 꺼내서, 방문 처리
int now = getSmallestNode();
visited[now] = true;
// 현재 노드와 연결된 다른 노드를 확인
for (int j = 0; j < graph[now].size(); j++) {
int cost = d[now] + graph[now][j].second;
// 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
if (cost < d[graph[now][j].first]) {
d[graph[now][j].first] = cost;
}
}
}
}
int main(void) {
cin >> n >> m >> start;
// 모든 간선 정보를 입력받기
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
// a번 노드에서 b번 노드로 가는 비용이 c라는 의미
graph[a].push_back({ b, c });
}
// 최단 거리 테이블을 모두 무한으로 초기화
fill_n(d, 100001, INF);
// 다익스트라 알고리즘을 수행
dijkstra(start);
// 모든 노드로 가기 위한 최단 거리를 출력
for (int i = 1; i <= n; i++) {
// 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
if (d[i] == INF) {
cout << "INFINITY" << '\n';
}
// 도달할 수 있는 경우 거리를 출력
else {
cout << d[i] << '\n';
}
}
}
- 위의 다익스트라 알고리즘의 시간복잡도는 O(V^2)이다 왜냐하면 총 O(V)번에 걸쳐서 최단 거리가 가장 짧은 노드를 매번 선형 탐색해야 하고, 현재 노드와 연결된 노드를 매번 일일이 확인하기 때문이다 따라서 코딩 테스트의 최단 경로 문제에서 전체 노드의 개수가 5,000개 이하라면 일반적으로 이 코드로 문제를 풀 수 있을 것이다
- 이후 배울 구현 방법을 이용하면 다익스트라 최단 경로 문제를 최악의 경우에도 시간 복잡도 O(ElogV)를 보장하여 해결할 수 있다
- 최단 거리가 가장 짧은 노드를 선형적으로 찾는 것이 아니라 더욱더 빠르게 찾을 수 있다면 어떨까? 개선된 다익스트라 알고리즘에서는 힙 자료구조를 사용한다 힙 자료구조를 이용하게 되면 특정 노드까지의 최단 거리에 대한 정보를 힙에 담아서 처리하므로 출발 노드로 부터 가장 거리가 짧은 노드를 더욱 빠르게 찾을 수 있다
- 힙 자료구조는 우선순위 큐를 구현하기 위하여 사용하는 자료구조 중 하나다
- 힙 자료구조는 완전 이진 트리의 일종이다
- 힙 자료구조는 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다
- 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제 한다는 점이 특징이다
- 데이터를 (가치,데이터)으로 묶어서 우선순위 큐 자료구조에 넣을 수 있다 이후에 우선순위 큐에서 데이터를 꺼내게 되면 항상 가치가 높은 데이터가 먼저 나오게 된다
- 우선순위 큐를 구현할 때는 내부적으로 최소 힙 혹은 최대 힙을 이용한다
- 힙 자료구조는 삽입, 삭제시 O(logN)의 연산을 N번 반복하므로 O(NlogN) 시간 복잡도를 가진다
- 이처럼 힙을 이용하는 경우 모든 원소를 저장한 뒤에 우선순위에 맞게 빠르게 뽑아낼 수 있으므로 힙은 우선순위 큐를 구현하는데 가장 많이 사용된다
- 우리는 이러한 최소 힙을 다익스트라 최단 경로 알고리즘에 적용할 것이다 단순히 우선순위 큐를 이용해서 시작 노드로부터 거리가 짧은 노드 순서대로 큐에서 나올 수 있도록 다익스트라 알고리즘을 작성하면 된다
- 최단 거리를 저장하기 위한 1차원 리스트(최단 거리 테이블)는 아까와 같이 그대로 이용하고, 현재 가장 가까운 노드를 저장하기 위한 목적으로만 우선순위 큐를 추가로 이용한다고 보면 된다
// 개선된 다익스트라 알고리즘
#include <bits/stdc++.h>
#define INF 1e9 // 무한을 의미하는 값으로 10억을 설정
using namespace std;
// 노드의 개수(N), 간선의 개수(M), 시작 노드 번호(Start)
// 노드의 개수는 최대 100,000개라고 가정
int n, m, start;
// 각 노드에 연결되어 있는 노드에 대한 정보를 담는 배열
vector<pair<int, int> > graph[100001];
// 최단 거리 테이블 만들기
int d[100001];
void dijkstra(int start) {
priority_queue<pair<int, int> > pq;
// 시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입
pq.push({ 0, start });
d[start] = 0;
while (!pq.empty()) { // 큐가 비어있지 않다면
// 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
int dist = -pq.top().first; // 현재 노드까지의 비용
int now = pq.top().second; // 현재 노드
pq.pop();
// 현재 노드가 이미 처리된 적이 있는 노드라면 무시
if (d[now] < dist) continue;
// 현재 노드와 연결된 다른 인접한 노드들을 확인
for (int i = 0; i < graph[now].size(); i++) {
int cost = dist + graph[now][i].second;
// 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
if (cost < d[graph[now][i].first]) {
d[graph[now][i].first] = cost;
pq.push(make_pair(-cost, graph[now][i].first));
}
}
}
}
int main(void) {
cin >> n >> m >> start;
// 모든 간선 정보를 입력받기
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
// a번 노드에서 b번 노드로 가는 비용이 c라는 의미
graph[a].push_back({ b, c });
}
// 최단 거리 테이블을 모두 무한으로 초기화
fill(d, d + 100001, INF);
// 다익스트라 알고리즘을 수행
dijkstra(start);
// 모든 노드로 가기 위한 최단 거리를 출력
for (int i = 1; i <= n; i++) {
// 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
if (d[i] == INF) {
cout << "INFINITY" << '\n';
}
// 도달할 수 있는 경우 거리를 출력
else {
cout << d[i] << '\n';
}
}
}
- 개선된 다익스트라 알고리즘은 한번 처리된 노드는 더 이상 처리되지 않는다는 특징이 있다
- 개선된 다익스트라 알고리즘의 시간 복잡도 개념을 제대로 이해하지 못해도 최소한 다익스트라 최단 경로 알고리즘의 소스코드만 잘 기억해두자
- 플로이드 워셜 알고리즘은 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 사용할 수 있는 알고리즘이다
- 플로이드 워셜 알고리즘은 노드의 개수가 N개일 때 알고리즘상으로 N번의 단계를 수행하며, 단계마다 O(N^2)의 연산을 통해 현재 노드를 거쳐 가는 모든 경로를 고려한다 따라서 플로이드 워셜 알고리즘의 총시간 복잡도는 O(N^3)이다
- 플로이드 워셜 알고리즘은 다익스트라 알고리즘과는 다르게 2차원 리스트에 최단 거리 정보를 저장한다는 특징이 있다
- 다익스트라 알고리즘은 그리디 알고리즘인데 플로이드 워셜 알고리즘은 다이나믹 프로그래밍 이라는 특징이 있다
- 각 단계에서는 해당 노드를 거쳐 가는 경우를 고려한다
// 플로이드 워셜 알고리즘
#include <bits/stdc++.h>
#define INF 1e9 // 무한을 의미하는 값으로 10억을 설정
using namespace std;
// 노드의 개수(N), 간선의 개수(M)
// 노드의 개수는 최대 500개라고 가정
int n, m;
// 2차원 배열(그래프 표현)를 만들기
int graph[501][501];
int main(void) {
cin >> n >> m;
// 최단 거리 테이블을 모두 무한으로 초기화
for (int i = 0; i < 501; i++) {
fill(graph[i], graph[i] + 501, INF);
}
// 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
for (int a = 1; a <= n; a++) {
for (int b = 1; b <= n; b++) {
if (a == b) graph[a][b] = 0;
}
}
// 각 간선에 대한 정보를 입력 받아, 그 값으로 초기화
for (int i = 0; i < m; i++) {
// A에서 B로 가는 비용은 C라고 설정
int a, b, c;
cin >> a >> b >> c;
graph[a][b] = c;
}
// 점화식에 따라 플로이드 워셜 알고리즘을 수행
for (int k = 1; k <= n; k++) {
for (int a = 1; a <= n; a++) {
for (int b = 1; b <= n; b++) {
graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b]);
}
}
}
// 수행된 결과를 출력
for (int a = 1; a <= n; a++) {
for (int b = 1; b <= n; b++) {
// 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
if (graph[a][b] == INF) {
cout << "INFINITY" << ' ';
}
// 도달할 수 있는 경우 거리를 출력
else {
cout << graph[a][b] << ' ';
}
}
cout << '\n';
}
}
09-2 미래 도시
// 미래 도시
#include <bits/stdc++.h>
#define INF 1e9 // 무한을 의미하는 값으로 10억을 설정
using namespace std;
// 노드의 개수(N), 간선의 개수(M)
int n, m;
// 2차원 배열(그래프 표현)를 만들기
int graph[101][101];
int main(void) {
cin >> n >> m;
// 최단 거리 테이블을 모두 무한으로 초기화
for (int i = 0; i < 101; i++) {
fill(graph[i], graph[i] + 101, INF);
}
// 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
for (int a = 1; a <= n; a++) {
for (int b = 1; b <= n; b++) {
if (a == b) graph[a][b] = 0;
}
}
// 각 간선에 대한 정보를 입력 받아, 그 값으로 초기화
for (int i = 0; i < m; i++) {
// A와 B가 서로에게 가는 비용은 1이라고 설정
int a, b;
cin >> a >> b;
graph[a][b] = 1;
graph[b][a] = 1;
}
// 거쳐 갈 노드 X와 최종 목적지 노드 K를 입력받기
int x, k;
cin >> x >> k;
// 점화식에 따라 플로이드 워셜 알고리즘을 수행
for (int k = 1; k <= n; k++) {
for (int a = 1; a <= n; a++) {
for (int b = 1; b <= n; b++) {
graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b]);
}
}
}
// 수행된 결과를 출력
int distance = graph[1][k] + graph[k][x];
// 도달할 수 없는 경우, -1을 출력
if (distance >= INF) {
cout << "-1" << '\n';
}
// 도달할 수 있다면, 최단 거리를 출력
else {
cout << distance << '\n';
}
}
09-3 전보
// 전보
#include <bits/stdc++.h>
#define INF 1e9 // 무한을 의미하는 값으로 10억을 설정
using namespace std;
// 노드의 개수(N), 간선의 개수(M), 시작 노드 번호(Start)
int n, m, start;
// 각 노드에 연결되어 있는 노드에 대한 정보를 담는 배열
vector<pair<int, int> > graph[30001];
// 최단 거리 테이블 만들기
int d[30001];
void dijkstra(int start) {
priority_queue<pair<int, int> > pq;
// 시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입
pq.push({0, start});
d[start] = 0;
while (!pq.empty()) { // 큐가 비어있지 않다면
// 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
int dist = -pq.top().first; // 현재 노드까지의 비용
int now = pq.top().second; // 현재 노드
pq.pop();
// 현재 노드가 이미 처리된 적이 있는 노드라면 무시
if (d[now] < dist) continue;
// 현재 노드와 연결된 다른 인접한 노드들을 확인
for (int i = 0; i < graph[now].size(); i++) {
int cost = dist + graph[now][i].second;
// 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
if (cost < d[graph[now][i].first]) {
d[graph[now][i].first] = cost;
pq.push(make_pair(-cost, graph[now][i].first));
}
}
}
}
int main(void) {
cin >> n >> m >> start;
// 모든 간선 정보를 입력받기
for (int i = 0; i < m; i++) {
int x, y, z;
cin >> x >> y >> z;
// X번 노드에서 Y번 노드로 가는 비용이 Z라는 의미
graph[x].push_back({y, z});
}
// 최단 거리 테이블을 모두 무한으로 초기화
fill(d, d + 30001, INF);
// 다익스트라 알고리즘을 수행
dijkstra(start);
// 도달할 수 있는 노드의 개수
int count = 0;
// 도달할 수 있는 노드 중에서, 가장 멀리 있는 노드와의 최단 거리
int maxDistance = 0;
for (int i = 1; i <= n; i++) {
// 도달할 수 있는 노드인 경우
if (d[i] != INF) {
count += 1;
maxDistance = max(maxDistance, d[i]);
}
}
// 시작 노드는 제외해야 하므로 count - 1을 출력
cout << count - 1 << ' ' << maxDistance << '\n';
}
Chapter 10 그래프 이론
10-1 다양한 그래프 알고리즘
- 그래프 알고리즘은 코딩 테스트에서 출제 비중이 낮은 편이지만 꼭 제대로 알아야 하는 알고리즘이다
- 알고리즘 문제를 접했을 때 서로 다른 개체가 연결되어 있다는 이야기를 들으면 가장 먼저 그래프 알고리즘을 떠올려야 한다
- 트리는 전통적인 수학에서는 무방향 그래프로 간주되지만, 컴퓨터공학 분야에서는 보통 방향 그래프라고 간주된다
- 그래프의 구현 방법은 크게 두가지 방식이 존재하는데 첫번째는 인접 행렬 방식이고 두번째는 인접 리스트 방식이다
- 우선순위 큐를 이용하는 다익스트라 최단 경로 알고리즘은 인접 리스트를 이용하는 방식이다
- 플로이드 워셜 알고리즘은 인접 행렬을 이용하는 방식이다
- 서로소 집합 자료구조란 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조라고 할 수 있다
- 스택과 큐가 각각 push와 pop연산으로 이루어졌던 것처럼, 서로소 집합 자료구조는 합집합과 찾기 연산으로 구성된다
- 서로소 집합 자료구조를 구현할 때는 트리 자료구조를 이용한다
// 기본적인 서로소 집합 알고리즘
#include <bits/stdc++.h>
using namespace std;
// 노드의 개수(V)와 간선(Union 연산)의 개수(E)
// 노드의 개수는 최대 100,000개라고 가정
int v, e;
int parent[100001]; // 부모 테이블 초기화하기
// 특정 원소가 속한 집합을 찾기
int findParent(int x) {
// 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
if (x == parent[x]) return x;
return findParent(parent[x]);
}
// 두 원소가 속한 집합을 합치기
void unionParent(int a, int b) {
a = findParent(a);
b = findParent(b);
if (a < b) parent[b] = a;
else parent[a] = b;
}
int main(void) {
cin >> v >> e;
// 부모 테이블상에서, 부모를 자기 자신으로 초기화
for (int i = 1; i <= v; i++) {
parent[i] = i;
}
// Union 연산을 각각 수행
for (int i = 0; i < e; i++) {
int a, b;
cin >> a >> b;
unionParent(a, b);
}
// 각 원소가 속한 집합 출력하기
cout << "각 원소가 속한 집합: ";
for (int i = 1; i <= v; i++) {
cout << findParent(i) << ' ';
}
cout << '\n';
// 부모 테이블 내용 출력하기
cout << "부모 테이블: ";
for (int i = 1; i <= v; i++) {
cout << parent[i] << ' ';
}
cout << '\n';
}
- 위의 알고리즘을 그대로 이용하게 되면 노드의 개수가 V개이고 find 혹은 union 연산의 개수가 M개일 때, 전체 시간 복잡도는 O(VM)이 되어 비효율적이다
- find() 함수는 경로 압축 기법을 적용하면 시간 복잡도를 개선시킬 수 있다
- 경로 압축은 find 함수를 재귀적으로 호출한 뒤에 부모 테이블값을 갱신하는 기법이다
// 개선된 서로소 집합 알고리즘 소스코드
#include <bits/stdc++.h>
using namespace std;
// 노드의 개수(V)와 간선(Union 연산)의 개수(E)
// 노드의 개수는 최대 100,000개라고 가정
int v, e;
int parent[100001]; // 부모 테이블 초기화
// 특정 원소가 속한 집합을 찾기
int findParent(int x) {
// 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
if (x == parent[x]) return x;
return parent[x] = findParent(parent[x]);
}
// 두 원소가 속한 집합을 합치기
void unionParent(int a, int b) {
a = findParent(a);
b = findParent(b);
if (a < b) parent[b] = a;
else parent[a] = b;
}
int main(void) {
cin >> v >> e;
// 부모 테이블상에서, 부모를 자기 자신으로 초기화
for (int i = 1; i <= v; i++) {
parent[i] = i;
}
// Union 연산을 각각 수행
for (int i = 0; i < e; i++) {
int a, b;
cin >> a >> b;
unionParent(a, b);
}
// 각 원소가 속한 집합 출력하기
cout << "각 원소가 속한 집합: ";
for (int i = 1; i <= v; i++) {
cout << findParent(i) << ' ';
}
cout << '\n';
// 부모 테이블 내용 출력하기
cout << "부모 테이블: ";
for (int i = 1; i <= v; i++) {
cout << parent[i] << ' ';
}
cout << '\n';
}
- 서로소 집합은 무방향 그래프 내에서의 사이클 판별할 때 사용할 수 있다는 특징이 있다
// 서로소 집합을 활용한 사이클 판별
#include <bits/stdc++.h>
using namespace std;
// 노드의 개수(V)와 간선(Union 연산)의 개수(E)
// 노드의 개수는 최대 100,000개라고 가정
int v, e;
int parent[100001]; // 부모 테이블 초기화
// 특정 원소가 속한 집합을 찾기
int findParent(int x) {
// 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
if (x == parent[x]) return x;
return parent[x] = findParent(parent[x]);
}
// 두 원소가 속한 집합을 합치기
void unionParent(int a, int b) {
a = findParent(a);
b = findParent(b);
if (a < b) parent[b] = a;
else parent[a] = b;
}
int main(void) {
cin >> v >> e;
// 부모 테이블상에서, 부모를 자기 자신으로 초기화
for (int i = 1; i <= v; i++) {
parent[i] = i;
}
bool cycle = false; // 사이클 발생 여부
for (int i = 0; i < e; i++) {
int a, b;
cin >> a >> b;
// 사이클이 발생한 경우 종료
if (findParent(a) == findParent(b)) {
cycle = true;
break;
}
// 사이클이 발생하지 않았다면 합집합(Union) 연산 수행
else {
unionParent(a, b);
}
}
if (cycle) {
cout << "사이클이 발생했습니다." << '\n';
}
else {
cout << "사이클이 발생하지 않았습니다." << '\n';
}
}
- 신장 트리란 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다
- 크루스칼 알고리즘은 신장 트리 중에서 최소 비용으로 만들 수 있는 신장트리를 찾는 알고리즘인 최소 신장 트리 알고리즘의 대표적인 예이다
- 크루스칼 알고리즘의 핵심 원리는 가장 거리가 짧은 간선부터 차례대로 집합에 추가하면 된다는 것이다 다만 사이클을 발생시키는 간선은 제외하고 연결한다
- 최소 신장 트리에 포함되어 있는 간선의 비용만 모두 더하면, 그 값이 최종 비용에 해당한다
- 크루스칼 알고리즘은 간선의 개수가 E개일 때, O(ElogE)의 시간 복잡도를 가진다 왜냐하면 E개의 데이터를 정렬했을 때의 시간 복잡도는 O(ElogE)이기 때문이다
// 크루스칼 알고리즘
#include <bits/stdc++.h>
using namespace std;
// 노드의 개수(V)와 간선(Union 연산)의 개수(E)
// 노드의 개수는 최대 100,000개라고 가정
int v, e;
int parent[100001]; // 부모 테이블 초기화
// 모든 간선을 담을 리스트와, 최종 비용을 담을 변수
vector<pair<int, pair<int, int> > > edges;
int result = 0;
// 특정 원소가 속한 집합을 찾기
int findParent(int x) {
// 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
if (x == parent[x]) return x;
return parent[x] = findParent(parent[x]);
}
// 두 원소가 속한 집합을 합치기
void unionParent(int a, int b) {
a = findParent(a);
b = findParent(b);
if (a < b) parent[b] = a;
else parent[a] = b;
}
int main(void) {
cin >> v >> e;
// 부모 테이블상에서, 부모를 자기 자신으로 초기화
for (int i = 1; i <= v; i++) {
parent[i] = i;
}
// 모든 간선에 대한 정보를 입력 받기
for (int i = 0; i < e; i++) {
int a, b, cost;
cin >> a >> b >> cost;
// 비용순으로 정렬하기 위해서 튜플의 첫 번째 원소를 비용으로 설정
edges.push_back({cost, {a, b}});
}
// 간선을 비용순으로 정렬
sort(edges.begin(), edges.end());
// 간선을 하나씩 확인하며
for (int i = 0; i < edges.size(); i++) {
int cost = edges[i].first;
int a = edges[i].second.first;
int b = edges[i].second.second;
// 사이클이 발생하지 않는 경우에만 집합에 포함
if (findParent(a) != findParent(b)) {
unionParent(a, b);
result += cost;
}
}
cout << result << '\n';
}
- 위상 정렬이란 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것
- 현실 세계에서 위상 정렬을 수행하게 되는 전형적인 예시로는 선수과목을 고려한 학습 순서 결정을 들 수 있다
- 그래프상에서 선후 관계가 있다면, 위상 정렬을 수행하여 모든 선후 관계를 지키는 전체 순서를 계산할 수 있다
- 위상 정렬 알고리즘을 자세히 살펴보기 전에, 먼저 진입차수를 알아야 한다 진입차수란 특정한 노드로 들어오는 간선의 개수를 의미한다
- 위상 정렬 알고리즘 수행중 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단할 수 있다
- 위상 정렬의 시간 복잡도는 O(V+E)이다 노드와 간선을 모두 확인한다는 측면에서 O(V+E)의 시간이 소요되는 것이다
// 위상 정렬
#include <bits/stdc++.h>
using namespace std;
// 노드의 개수(V)와 간선의 개수(E)
// 노드의 개수는 최대 100,000개라고 가정
int v, e;
// 모든 노드에 대한 진입차수는 0으로 초기화
int indegree[100001];
// 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트 초기화
vector<int> graph[100001];
// 위상 정렬 함수
void topologySort() {
vector<int> result; // 알고리즘 수행 결과를 담을 리스트
queue<int> q; // 큐 라이브러리 사용
// 처음 시작할 때는 진입차수가 0인 노드를 큐에 삽입
for (int i = 1; i <= v; i++) {
if (indegree[i] == 0) {
q.push(i);
}
}
// 큐가 빌 때까지 반복
while (!q.empty()) {
// 큐에서 원소 꺼내기
int now = q.front();
q.pop();
result.push_back(now);
// 해당 원소와 연결된 노드들의 진입차수에서 1 빼기
for (int i = 0; i < graph[now].size(); i++) {
indegree[graph[now][i]] -= 1;
// 새롭게 진입차수가 0이 되는 노드를 큐에 삽입
if (indegree[graph[now][i]] == 0) {
q.push(graph[now][i]);
}
}
}
// 위상 정렬을 수행한 결과 출력
for (int i = 0; i < result.size(); i++) {
cout << result[i] << ' ';
}
}
int main(void) {
cin >> v >> e;
// 방향 그래프의 모든 간선 정보를 입력 받기
for (int i = 0; i < e; i++) {
int a, b;
cin >> a >> b;
graph[a].push_back(b); // 정점 A에서 B로 이동 가능
// 진입 차수를 1 증가
indegree[b] += 1;
}
topologySort();
}
댓글남기기