프로그래밍/알고리즘
BOJ 1504 · 특정한 최단 경로
알고리즘 분류 : 다익스트라 1부터 출발해서 정점 X와 Y를 모두 거쳐서 N에 도착하는 최단 거리를 구하는 문제다. 이동 거리가 1 이상의 값을 가지므로, 다익스트라를 이용해야 한다. 정점 두 군데를 모두 거쳐야 하므로, 다익스트라를 여러 번 호출해야 한다. 다익스트라를 여러 번 호출해야 하므로, dist 배열을 매번 INF로 초기화해야 하는 것에 유의한다. 방향성이 없는 그래프이므로, 입력받을 때 양방향으로 저장한다.X, Y를 모두 거쳐서 도착하는 방법은 2가지가 존재한다. 1 → X → Y → N 와 1 → Y → X → N 이다.1 → X, X → Y, Y → N으로 가는 방법을 경로 1이라 하고, 그 이동 거리를 저장한다.1 → Y, Y → X, X → N으로 가는 방법을 경로 2라 하고, 그 이..
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, ..