PS
BOJ 1328 - 고층 빌딩
www.acmicpc.net/problem/1328 1328번: 고층 빌딩 상근이가 살고있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼 www.acmicpc.net 이 문제는 DP 를 이용해야 풀 수 있는 문제이다. DP[i][j][k] = w : 지은 건물이 i 개 이며, 왼쪽에서 j 개의 건물이 보이고, 오른쪽에서 k 개의 건물이 보일때, 가능한 총 경우의 수가 w 이다. 건물을 지을때, 가장 높이가 높은거 부터 가장 높이가 작은 1인 건물을 제일 마지막에 짓는다고 가정할때, 3개의 경우의 수가 생긴다 1) 가장 왼쪽에 건물을 짓는다. (DP[i - 1][j - 1][..
BOJ 5719 - 거의 최단 경로
www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 이 문제는 두번째 최단 경로를 구해야 하는 문제이다. 다익스트라 알고리즘을 사용하면, 가장 짧은 경로를 구할 수 있다. 그러나 이 문제는 그 다음번으로 짧은 경로를 찾아내야 한다. 이를 위해서, 다익스트라 알고리즘을 두 번 사용하되, 첫번째 다익스트라 알고리즘 수행하면서, 찾아낸 최단 경로들을 그래프 상에서 제거해야한다. 이를 위해 BFS 를 사용해서 최단경로에 해당하는 부분을 -..
BOJ 10217 - KCM Travel
www.acmicpc.net/problem/10217 10217번: KCM Travel 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세 www.acmicpc.net 이 문제는 다익스트라 알고리즘에 DP 방식을 도입해야 풀 수 있는 문제이다. 다익스트라 자체로는 최소시간을 구할 순 있지만, 이 문제는 소요시간과 비용까지 계산을 해야 되기 때문에, 기본 다익스트라 알고리즘으로는 풀 수 없다. DP 배열을 다음과 같이 세워준다 DP[i][j] = k : i 번 노드까지 j 의 비용으로 갔을때 소요되는 최소시간 k 최소 시간을 찾아내기위해서는..
BOJ 2812 - 크게 만들기
www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 이 문제는 적절한 자료구조를 잘 선택해야 풀 수 있는 문제이다. 이 문제에선 스택을 사용해서 문자들을 하나씩 처리해주는게 좋다 입력으로 들어오는 숫자가 최대 50만 자릿수를 가지므로 문자열로 만들어주고 문자를 앞에서부터 끝까지 돌면서, 지워야할 갯수 k 가 0 보다 큰경우, 스택이 비어있지 않은경우, 스택의 맨 윗값이 현재 문자보다 작은 경우를 동시에 만족하는 경우, 스택에서 하나씩 빼내면서 k 를 줄인다. 그리고 난 후 문자를 하나씩 추가해서 스택에 넣는다. for (int i = 0;..
BOJ 8983 - 사냥꾼
www.acmicpc.net/problem/8983 8983번: 사냥꾼 KOI 사냥터에는 N 마리의 동물들이 각각 특정한 위치에 살고 있다. 사냥터에 온 사냥꾼은 일직선 상에 위치한 M 개의 사대(총을 쏘는 장소)에서만 사격이 가능하다. 편의상, 일직선을 x-축이라 가 www.acmicpc.net 이 문제는 이분탐색을 써야 풀 수 있다. 최댓값이 십만이기 때문에 사대의 위치와 동물의 위치를 이중 포문으로 탐색하면 시간초과가 나기 때문이다. 사대의 위치를 기준으로 탐색하기보다는, 동물의 위치를 기준으로 해당 동물과 가까운 사대를 찾는 방식으로 풀어야 더 수월하게 풀 수 있다. 사대의 위치를 먼저 배열에 다 받아둔뒤, 오름차순으로 정렬시키고, 동물의 좌표를 받을때 마다 이분탐색을 수행한다. 동물과 사대가 사..
BOJ 11657 - 타임머신
www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 이 문제는 벨만 포드 알고리즘을 이용하여 노드간 최단 거리를 구하는 문제이다. - 참고 : blog.naver.com/kks227/220796963742 벨만 포드 알고리즘(Bellman-Ford Algorithm) (수정: 2020-07-10) 이어서 소개해드릴 것은 또다른 최단경로 알고리즘입니다.벨만 포드 알고리즘(Bellman-Ford algor..
BOJ 10165 - 버스 노선
www.acmicpc.net/problem/10165 10165번: 버스 노선 첫 번째 줄에는 버스 정류소의 개수 N(3 ≤ N ≤ 1,000,000,000)이 주어지고 두 번째 줄에는 버스 노선의 수 M(2 ≤ M ≤ 500,000)이 주어진다. 각 버스 노선은 1부터 M까지의 번호로 구분된다. 그 다음 M개 www.acmicpc.net 이 문제는 그리디로 풀어야 하는 문제이다. 이 문제의 가장 핵심 부분은 버스의 노선 [start, end] 가 start > end 일때 어떻게 처리하느냐 이다. 만약 모든 입력이 [start, end] (start < end) 이라면, 입력 값들을 정렬할때, start 가 작은 순대로 앞으로 오게 하고, start 가 만약 같은 경우라면, end 가 큰게 앞으로 오도..
BOJ 17136 - 색종이 붙이기
www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 이 문제는 백트래킹을 써야 풀 수 있는 문제이다. 먼저 10 * 10 크기의 이차원 배열을 (0, 0) 부터 하나씩 순회하면서, 값이 1인 부분을 찾아내고, 값이 1인 (i, j) 좌표에 5개의 색종이 중 어떤 것을 붙일 수 있는지 판별한다 어떤 k 번째 색종이를 붙일 수 있다면, 그 색종이를 붙이고 다음 가지수를 찾기 위해 백트래킹을 써준다. 이때 순회를 하기 위한 재귀함수의 종료조건은 1. 10 *..