알고리즘 풀이16 [백준][C++] 4485번: 녹색 옷 입은 애가 젤다지? 풀이 https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net (0,0)에서 출발해 (N-1,N-1)까지 갈 수 있는 경로 중 최소 비용을 구하는 문제이다. 모든 경로를 탐색해야 하기도 하고 최대 크기가 125X125으로 다 도는데 얼마 안 걸리겠다 싶어 완전 탐색으로 풀어보았다. 먼저 필요한 자료구조로는 1. 동굴을 저장할 2차원 배열 2. 각 좌표로 갈 수 있는 최소 비용을 저장할 2차원 배열 3. 좌표를 넣을 큐 풀이로직으로는 1. (.. 2024. 3. 21. [백준][C++] 1446번: 지름길 풀이 https://www.acmicpc.net/problem/1446 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이 www.acmicpc.net 지나야하는 고속도로에서 지름길이 있을 때 운전해야 하는 거리의 최솟값을 구하는 문제이다. 최소 거리를 구해야 하므로 먼저 다익스트라 알고리즘이 생각났다. 다익스트라에 대해서는 아래 블로그로 공부하였다. https://blog.naver.com/ndb796/221234424646 23. 다익스트라(Dijkstra) 알고리즘 다익스트라(Dijkstra) 알고리즘은 다이나믹 프로그래밍을 활용.. 2024. 3. 19. [백준][C++] 2630번: 색종이 만들기 풀이 https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 전체 종이가 같은 색이 아니면 4구역으로 잘라서 전체 구역이 같은 색이 되거나 종이의 크기가 1일 때까지 자른다. 이 때 잘라진 하얀색, 파란색 색종이의 개수를 구하는 문제이다. 나눠서 해결한 결과를 합치므로 분할과 정복 풀이 방법이 떠올랐다. 풀이 로직으로는 1. 전체 종이가 같은 색인지 판단 2. 같은 색이 아니면 4구역으로 분할 후 재귀적으로 1번 수행 3. 같은 .. 2024. 3. 19. [백준][C++] 9663번: N-Queen 풀이 https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net N값이 주어졌을 때 퀸 N개가 N X N에서 서로 공격할 수 없도록 배치하는 경우의 수를 구하는 문제이다. 일단 느낌이 올 때까지 N이 1일 때부터 그림을 그려가며 서로 공격할 수 없는 경우의 수를 구해봤다. N이 4일 때 서로 공격할 수 없는 배치들을 그릴 때 살짝 감이 왔는데 같은 행과 열에는 퀸이 하나만 있다는 것을 알았다. 쉽게 생각해 퀸의 공격 방향을 보면 어느 좌표에 퀸이 있다면 같은 행, 열, 그리고.. 2024. 3. 18. 이전 1 2 3 4 다음
