알고리즘 문제 풀이/백준
-
[백준] 토마토 - 7576알고리즘 문제 풀이/백준 2021. 4. 16. 09:13
문제설명 www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 기본아이디어 정말 정석적인 BFS 탐색 문제입니다. 익은 토마토를 찾아서 주변 네방향으로 안익은 토마토를 찾으면 익은 상태로 만들고 다음에 새로 익은 토마토 기준으로 반복하면 된다. 구현코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40..
-
[백준] 달이 차오른다, 가자. - 1194알고리즘 문제 풀이/백준 2021. 4. 14. 15:09
문제설명 www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 기본아이디어 일단 문제 자체는 최단경로로 도착지점에 도착하는 거리를 구하는 문제이다. BFS 탐색을 쓰면 되겠다는 생각을 가지고 열쇠를 어떻게 처리를 해야하나 고민을 했다. 방문처리 방식을 추가하기로 했다. 자세하게 설명하면 BFS탐색을 할 때 한번 지나간 곳은 Boolean 배열로 방문했다는 정보를 남기고 진행을 한다. 이렇게 되면 지나온 곳을 다시 돌아가지도 않고 후에..
-
[백준] 카드 구매하기 - 11052알고리즘 문제 풀이/백준 2021. 4. 14. 14:53
문제설명 www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 기본아이디어 N개의 카드를 구매하기 위해 지불해야 하는 금액의 최댓값을 구해라. 문제를 읽고 N의 최대값을 구하려면 어떤 값들과 비교 해야하는지를 고민해 보았다. 동적계획법으로 카드를 N개 구하기 이전에 카드를 N-1개 고르는 값이 최대값으로 다 구해져있다고 가정을 한다면 N개를 뽑는 경우의 수(비교해야되는 수는) C(1) + C(N-1), C(2) + C(N-2), C(3) + C(N-3) , ... , C..
-
[백준] 경비원 - 2564알고리즘 문제 풀이/백준 2021. 4. 13. 23:15
문제설명 www.acmicpc.net/problem/2564 2564번: 경비원 첫째 줄에 블록의 가로의 길이와 세로의 길이가 차례로 주어진다. 둘째 줄에 상점의 개수가 주어진다. 블록의 가로의 길이와 세로의 길이, 상점의 개수는 모두 100이하의 자연수이다. 이어 한 줄 www.acmicpc.net 기본아이디어 일단 먼저 든 생각은 오른쪽으로 갈지 왼쪽으로 갈지는 한 곳을 구한 뒤에 전체에서 빼면 다른 한쪽으로 가는 거리를 구할 수 있다는 것이었다. 그리고 두번째 든 생각은 case로 다 나눠서 풀면 풀리겠다고 생각이 들었다. 동근이의 현재 위치와 상점의 현재 위치를 비교하면서 진행하면 풀 수 있다고 확신이 들었다. 그리고 두번째 풀이, 어차피 모든 위치는 한 지점, 예를들어 제일 위, 왼쪽의 점을 (..
-
[백준] 게리맨더링 - 17471알고리즘 문제 풀이/백준 2021. 4. 13. 16:40
문제설명 www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 기본아이디어 주어진 지점들을 두 분류로 나누고, 각 지점들의 값들의 합의 차이 중 최소값을 찾는 문제이다. 여기서 중요한 점은 두 분류로 나눴을 때 각각의 점들이 다 이어져 있어야 합니다. 주어지는 N값이 작기 때문에 dfs, bfs 탐색으로 해도 된다는 생각이 들었고, 그래서 조합으로 가능한 경우를 다 만든 다음에 bfs탐색으로 연결이 되어있는지 확인하는 방법을 사용했습니다. PS. 너무 많이 틀려서 반례를 많이 찾아봤는..
-
[백준] 퇴사 - 14501번알고리즘 문제 풀이/백준 2021. 4. 12. 22:44
문제설명 www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 기본아이디어 동적계획법 문제입니다. 결국 N+1, 퇴사일에 받을 수 있는 최대한의 금액을 구하는 문제입니다. 1번째 날, 2번째 날, ~~~ , N+1번째 날 순으로 받을 수 있는 금액의 최댓값을 구하면 구할 수 있습니다. 여기서 상담에 걸리는 시간이라는게 주어졌으므로 상담을 하는 경우 그만큼 지난 날에 가서 최댓값을 갱신시켜주면 됩니다. 구현코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 public class 퇴사14501 { static BufferedR..
-
[백준] 소수 구하기 - 1929번알고리즘 문제 풀이/백준 2021. 3. 11. 19:34
문제설명 www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 기본아이디어 M과 N 범위 안에 있는 소수 구하기. N, M이 크지 않기 때문에 간단하게 boolean형 배열을 만들고 2 ~ N 까지 값을 증가시키면서 소수인 값은 자신의 배수에 해당하는 위치를 true로 만들어 줬습니다. M ~ N 까지 값을 소수인지 판별할 수 도 있었지만 최악의 경우를 따졌을 때 (M:1, N:1,000,000) 성능면에서 크게 차이나지 않는것 같아 이렇게 풀었습니다. 풀고 나서 보니까 예전에 풀었던 문제였습니..
-
[백준] DFS와 BFS - 1260번알고리즘 문제 풀이/백준 2021. 3. 11. 19:24
문제설명 www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 기본아이디어 DFS와 BFS 구현 문제이다. 어렵지 않은 문제이지만, DFS와 BFS를 잘 모르는 사람에게는 필요할 거 같아서 올려놓았다. 특히 DFS는 완전탐색, 깊이 우선 탐색으로 많이 알고 있지만 BFS, 넓이 우선 탐색은 생소한 사람들은 코드를 보면 쉽게 알 수 있을 것이다. BFS 코드에 관해서는 DFS와 달리 재귀로 풀지 않고 탐색해야하는 곳을 Queue..