반응형 알고리즘80 [Python] Baekjoon - 1976. 여행 가자 백준 1976번 여행 가자 문제는 도시의 연결 정보와 여행 계획 리스트가 주어졌을 때 여행할 수 있는지를 구하는 문제다. 도시의 연결 정보를 그래프로 표현할 수 있으며 여행 계획대로 탐색할 수 있는지 확인해야 하므로 그래프 탐색 알고리즘을 이용해서 해결할 수 있다. 백준 1976번 여행 가자 문제 정보 알고리즘 분류 - 그래프 탐색 난이도 - 골드 4 여행 가자 문제 요약 N개의 도시의 연결 정보가 주어지고, 여행 계획(M개의 도시 리스트 - 중복 가능)이 주어졌을 때, 여행 가능한지 구하는 문제다. A, B, C 도시에 대해 A-B, B-C가 연결되어있고 여행 계획이 A-C라면, A-B-C로 이동하면 A와 C 순서로 여행을 갈 수 있으므로 여행 가능한 경우이다. 문제 풀이 과정 무방향 그래프가 있고, .. 2021. 7. 21. [Python] Baekjoon - 2193. 이친수 백준 2193번 이친수 문제는 N 자리 이진수 중 맨 앞자리 수가 0이 아니면서 1이 연속해서 등장하지 않는 이친수의 개수를 구하는 문제다. 다이나믹 프로그래밍을 이용해서 해결할 수 있는 문제인데, 점화식을 세워서 정리하면 결국 피보나치수열의 N 번째 수를 구하는 문제다. 백준 2193번 이친수 문제 정보 알고리즘 분류 - 다이나믹 프로그래밍 난이도 - 실버 3 이친수 문제 요약 N자리 이진수 중 맨 앞이 0이 아니고 1이 연속해서 등장하지 않는 이친수의 개수를 구하는 문제다. 문제 풀이 과정 N-1자리 이친수 중 마지막이 0인 수의 뒤에는 0과 1이 붙을 수 있고, 마지막이 1인 수의 뒤에는 0만 붙을 수 있다. P[n] = zero[n] + one[n] zero[n] = zero[n-1] + one[.. 2021. 7. 21. [Python] Baekjoon - 4179. 불! 백준 4179번 불! 문제는 미로 속 지훈이가 불에 타기 전에 미로를 빠져나오는 최소 이동 횟수를 구하는 문제다. 최소 이동 횟수를 구하는 문제이므로 그래프 탐색 알고리즘 중 BFS를 이용해 해결할 수 있다. 난이도는 골드 4이다. 백준 4179번 불! 문제 정보 알고리즘 분류 - 그래프 탐색 난이도 - 골드 4 불! 문제 요약 벽과 빈칸으로 구성된 미로 속에 지훈이가 있는데, 미로 속 한 곳에 불이 붙었다. 지훈이가 불에 타기 전에 미로를 빠져나올 수 있다면 최소 이동 횟수를 구하는 문제다. 문제 풀이 과정 미로를 빠져나가기까지 최소 이동 횟수를 구해야 하므로 BFS를 이용한다. 지훈이가 한 칸 움직일 때마다 불도 상하좌우로 한 칸씩 번진다. 빈칸만 이동할 수 있는 지훈이가 미로를 빠져나가거나 더 이상.. 2021. 7. 20. [Python] Baekjoon - 15664. N과 M (10) 백준의 N과 M 시리즈는 N개의 숫자가 포함된 수열에서 M개를 고르는 문제이다. 매번 조건이나 규칙이 변경되어 총 12개의 문제가 있다. 이번 문제는 비 내림차순으로 출력하는 문제이며 백트래킹을 이용하여 풀 수 있다. 난이도는 실버 2이다. 백준 15664번 N과 M (10) 문제 정보 알고리즘 분류 - 백트래킹 난이도 - 실버 2 N과 M (10) 문제 요약 N개의 중복 수열 중 M개를 뽑아 비 내림차순 수열로 만드는 경우의 수를 모두 출력하는 문제다. 문제 풀이 과정 수열에 포함된 숫자들의 중복을 제거하고 정렬하여 가지고 있는 리스트와, 각 숫자의 등장 횟수를 저장하는 리스트를 준비한다. dfs를 이용해 작은 숫자부터 방문하거나/방문하지 않으면서 M개의 숫자를 선택한다. 이때, 선택되는 숫자의 등장 .. 2021. 7. 20. 이전 1 ··· 13 14 15 16 17 18 19 20 다음 반응형
