나그네

1932번: 정수 삼각형 문제 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 풀이 삼각형의 가장 위에서 아래로 차례대로 더해 최댓값을 구하는 문제. dp를 사용해 풀었다. 삼각형의 어느 위치에서 합의 최댓값이 되려면 그 윗 층의 인접한 두 위치까지의 합 중 더 큰 곳에 해당 위치의 값을 더한 값이 된다. 이를 구현하면 끝인 문제다. 코드 #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); int n; cin >>..

11779번: 최소비용 구하기 2 문제 https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 풀이 최소비용 구하기(1916번) 문제에서 확장된 문제다. 풀이는 아래 링크 참고. https://khyunx.tistory.com/71 [백준 / BOJ] C++ 1916 최소비용 구하기 1916번: 최소비용 구하기 문제 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에..

1916번: 최소비용 구하기 문제 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 풀이 다익스트라 알고리즘으로 쉽게 풀 수 있는 문제다. 다익스트라 설명은 아래 링크를 참고하면 된다. [다익스트라 알고리즘 알아보기] 코드 #include using namespace std; #define INF 2147483647 int main() { ios::sync_with_stdio(false); cin.tie(NULL..

1504번: 특정한 최단 경로 문제 https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 풀이 정점 1에서 출발해 특정한 두 정점 v1, v2를 지나 정점 N에 도착하는 최단 거리를 출력하는 문제다. 다익스트라 알고리즘을 사용해 풀 수 있으며 양방향 그래프임을 기억하고 풀어야 하며 경로가 없는 경우 예외 처리 하는 게 힘들었다. 다익스트라 알고리즘에 대해 잘 모른다면 아래 링크를 참고하자. [다익스트라 알..

1238번: 파티 문제 https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 풀이 1부터 N까지 각 마을에 사는 학생이 X번째 마을에 갔다가 돌아오는 최단 거리가 가장 오래 걸리는 학생의 이동 거리를 구하는 문제다. 다익스트라 알고리즘을 이용하면 해결할 수 있다. 다익스트라 알고리즘에 대해 잘 모른다면 아래 링크를 참고하자. [다익스트라 알고리즘 알아보기] 이 문제는 유향인 그래프이고 i 정점부터 출발해 X 정점까지 가..

다익스트라 알고리즘(Dijkstra's Algorithm) 다익스트라 알고리즘은 시작 정점에서 모든 나머지 정점까지의 최단거리(cost)를 구하는 알고리즘 중 하나다. 주로 주어진 두 노드 사이의 최단거리(cost)를 구하는 데 유용하게 사용된다. 다익스트라 알고리즘 특징 정점의 개수가 V, 간선의 개수를 E일 때 O(ElogV)의 시간복잡도를 가진다. 모든 거리(cost)가 음수가 아닐 때만 사용할 수 있다. 우선순위 큐(최소 힙)를 사용한다. 다익스트라 알고리즘 작동 방식 아직 방문하지 않은 정점들 중 거리(cost)가 가장 작은 정점을 하나 선택해 방문한다. 해당 정점에 인접하고 아직 방문하지 않은 정점들의 거리를 갱신한다. 모든 정점을 방문하면 종료한다. 1번 과정을 위해 우선순위 큐(최소 힙)가..

1753번: 최단경로 문제 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 풀이 한 정점에서 다른 모든 정점까지 가는 최단 경로, 즉 최소 비용을 구하면 되는 문제다. 최소 비용을 구하는 알고리즘은 다익스트라 알고리즘과 벨만포드 알고리즘이 있는데 이 문제에선 음의 가중치가 없기 때문에 다익스트라 알고리즘을 사용해 풀 수 있다. 다익스트라 알고리즘에 대한 설명은 아래 링크를 참고하길 바란다. [다익스트라 알고..

2579번: 계단 오르기 문제 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 풀이 계단은 1칸 또는 2칸 이동가능하며 연속된 3개의 계단을 오를 수는 없다. 그리고 마지막 계단은 반드시 밟아야 한다. 얻을 수 있는 포인트의 최댓값을 구하는 문제. dp로 해결가능하다. dp[i]는 i번째 계단까지 가는 경우의 포인트의 최댓값이며 v[i]는 i번째 계단을 밟았을 때 얻는 포인트다. 1번째 계단까지의 최댓값은 dp[1] = v[1] 이다. 2번째 계단까지 가는..

4839번: 소진법 문제 https://www.acmicpc.net/problem/4839 4839번: 소진법 각 테스트 케이스에 대해서, 입력으로 주어진 수, 공백, 등호, 공백을 출력하고 문제 설명에 나온 것 같이 소진법으로 나타내 출력한다. www.acmicpc.net 풀이 소수의 곱을 이용하는 문제. 다만 수의 범위가 int 범위 안이기 때문에 29까지 곱하게 되면 범위를 벗어나서 23까지의 곱만 구하면 된다. 그래서 누적곱(?) 배열을 만들어줬다. 가장 큰 누적곱부터 비교하며 N이 누적곱보다 같거나 크다면 N을 누적곱으로 나눈 몫과 누적곱까지의 소수 곱을 출력 형식에 맞는 문자열 형태로 만들어 배열에 추가해 줬다. 그리고 N을 누적곱으로 나눈 나머지로 업데이트해 준다. 만약 누적곱 배열을 모두 ..

6500번: 랜덤 숫자 만들기 문제 https://www.acmicpc.net/problem/6500 6500번: 랜덤 숫자 만들기 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, a0을 포함하고 있다. (0 < a0 < 10000) 숫자가 네 자리가 아닌 경우에는, 앞에 0을 추가해 네 자리로 만들어져 있다. www.acmicpc.net 풀이 a0을 입력받고 a0 * a0을 앞에 0을 추가해 8자리 숫자로 바꿔준 다음 가운데 4자리를 a1으로 한다. 이를 반복해 가며 가능한 ai의 수를 구하는 문제. 숫자 N을 입력받고 N*N의 가운데 4자리를 다시 N으로 하며 모든 N을 계속 배열에 넣었다. 그러다 N이 이미 배열 안에 있을 경우 반복문을 탈출한다. 배열의 크기를 출..