BOJ
BOJ 1238 · 파티
알고리즘 분류 : 다익스트라 각 학생이 각자 자신의 마을에서 출발하고, X 마을에서 파티를 하고, 다시 자신의 마을로 돌아오는 시간을 맞추는 문제다. 마을 간의 이동은 1 이상의 소요 시간이 걸리므로, 다익스트라 알고리즘을 이용해야 한다. 이 문제는 다익스트라 알고리즘을 두 번만 호출해서 해결할 수 있다.출발의 기준을 i (1 n >> m >> x; vector a[n], b[n]; int dist[n][2]; while (m--) { int u, v, w; cin >> u >> v >> w; a[u-1].push_back({v-1, w}); b[v-1].push_back({u-1, w}); } fill(&dist[0][0], &dist[n][0], INF); dijkstra(a, dist, 0); di..
BOJ 1916 · 최소비용 구하기
알고리즘 분류 : 다익스트라 A 도시에서 B 도시까지 가는 최단 경로를 구하는 문제다. 도시 간에 비용이 0 이상의 양수 값을 지니므로, 다익스트라 알고리즘을 이용해야 한다.BOJ 1753번 '최단경로'와 유사한 문제다. 다음 글을 참조. C++ 소스코드 #include #include #include #include using namespace std; struct bus { int city, cost; bool operator t.cost; } }; int n, m; int depart, arrive; const int INF = 1e9; void dijkstra(vector a[], int dist[]) { priority_queue pq; pq.push({depart, 0}); dist[depar..
BOJ 1753 · 최단경로
알고리즘 분류 : 다익스트라 한 개의 정점에서 다른 모든 정점으로 가는 최단 경로를 구해야 한다. 이 문제는 다익스트라 알고리즘을 이용하는 대표적인 문제다. 다익스트라 알고리즘을 활용하기 위해서 최소 힙(Min-heap)을 이용하면 편하다. C++은 STL에 있는 우선순위 큐(Priority Queue)를 이용하여 최소 힙을 사용하면 된다. 단, Priority Queue가 기본적으로 최대 힙(Max-heap)이므로, 비용(cost)에 -1을 곱해서 사용하거나, 연산자 오버로딩을 통해 순서를 바꿔서 사용하면 된다.Python은 Heapq를 이용하면 된다.정점은 1~N이고, 인덱스는 0~N-1이다. 따라서, 입력받을 때 정점에 -1을 해주거나, 리스트를 N+1 길이로 선언하여 이용해야 한다. C++ 소스코..
BOJ 15658 · 연산자 끼워넣기 (2)
알고리즘 분류 : 브루트 포스 BOJ 14888번 '연산자 끼워넣기'와 거의 동일한 문제이다. 바뀐 점은 연산자의 사용 가능 횟수가 증가했다는 점이다. 구현 방법은 이전 문제를 참조. 이전 문제는 연산자의 개수가 최대 N-1개였지만, 이번 문제는 연산자의 개수가 최소 N-1개, 최대 4N개이다.연산자가 최대로 있는 경우, 연산자를 사용할 때 4개의 연산자 중에서 하나를 선택할 수 있다.따라서 N-1개의 연산자 자리에 연산자 4개 중 하나를 사용하는 경우이므로, 경우의 수는 4^(N-1) 개이다.N의 최댓값은 11이므로, 최대 경우의 수는 4^10 (약 100만)이다.따라서 이 문제는 이전 문제와 동일한 코드로 해결할 수 있다. C++ 소스코드 #include int n; int a[11], op[4]; ..
BOJ 14888 · 연산자 끼워넣기
알고리즘 분류 : 브루트 포스 재귀 함수를 이용하여 수식 연산의 최댓값과 최솟값을 구하는 문제다.주어진 연산자를 모두 사용해서 수식을 만들고, 그 수식의 연산 결과를 출력하면 된다. 재귀 함수 종료 조건 : 인덱스가 범위를 넘어선 경우 (index >= N)연산은 각 연산자의 잔여횟수가 1 이상인 경우에 수행한다. 0이면 연산을 수행하지 않는다.연산을 수행한 후, 사용한 연산자의 잔여횟수를 1회 감소시킨다. C++ 소스코드 #include int n; int a[11], op[4]; int mx = -1e9, mn = 1e9; void solve(int index, int ans, int add, int sub, int mul, int div) { if (index == n) { if (ans > mx)..
BOJ 14501 · 퇴사
알고리즘 분류 : 브루트 포스 재귀 함수를 이용하여 최대 수익을 구할 수 있는 문제다. 이 문제는 다이나믹 프로그래밍 방식으로도 해결할 수 있다. 수익 계산 종료 조건 : 날짜가 N+1 일이 된 경우 (day == N+1)재귀 함수 종료 조건 : 날짜가 N+1 일을 넘은 경우 (day > N+1)day 번째 일에 상담을 하는 경우 : solve(day+t[day], profit+p[day])day 번째 일에 상담을 하지 않는 경우 : solve(day+1, profit) C++ 소스코드 #include int n, ans; int t[16], p[16]; void solve(int day, int profit) { if (day == n+1) { if (ans n+1) return; solve(day+t..
BOJ 1182 · 부분집합의 합
알고리즘 분류 : 브루트 포스 재귀 함수를 이용하여 구현할 수 있는 문제다.집합의 원소가 N 개 있을 때, 모든 부분집합의 개수는 2^N 개이다. N의 제한이 최대 20이므로, 가능한 경우의 수는 2^20 (약 100만)이다. 따라서 모든 부분 집합을 구한 후, 그 집합의 합이 S 인지 판별해보면 된다. 재귀 함수 종료 조건 : 인덱스가 범위를 벗어난 경우 (index >= N)정답을 찾은 경우 : 부분집합의 총합이 S인 경우 (sum == S)원소를 포함하는 경우 : solve(index+1, sum+a[index])원소를 포함하지 않는 경우 : solve(index+1, sum)공집합을 포함하지 않으므로, S가 0인 경우 1개를 정답에서 빼야 한다. C++ 소스코드 #include int n, s, ..
BOJ 5427 · 불
알고리즘 분류 : BFS BFS를 통해 최소 이동거리를 구하는 문제이다. BOJ 3055번 '탈출'과 유사한 문제이다.사람(상근)은 건물 밖으로 탈출해야 하고, 불은 인접한 상하좌우로 번진다. 사람은 불이 번진 곳과 불이 다음에 번질 곳으로 이동할 수 없으므로, 불의 위치를 먼저 Queue에 넣고, 이후에 사람의 위치를 Queue에 넣어야 한다. Queue에 불의 위치와 사람의 위치가 모두 들어가므로, 불과 사람을 구분할 flag를 둔다.빌딩 밖으로 탈출하는 것은, 다음 위치가 주어진 맵의 범위를 벗어나는지 아닌지로 판별하면 된다.다음 위치가 맵의 범위를 벗어나는지 확인하고, 벗어나면 현재까지 이동한 거리를 답으로 낸다.다음 위치가 맵의 범위를 벗어나지만, 불이 벗어난 것이라면 무시한다.이동 거리를 통해..