📜 알고리즘/BOJ(백준)_Python

안녕하세요! 이번 포스트에서는 백준 1766번 문제 “문제집”을 함께 풀어보겠습니다. 이 문제는 문제를 풀기 위한 순서를 정하는 문제로, 위상 정렬을 활용하여 해결할 수 있습니다. 문제를 분석하고 접근 방법을 정리한 후, 최종적인 정답 코드를 확인해 보겠습니다. 문제 URL: https://www.acmicpc.net/problem/1766 1. 문제 설명“문제집” 문제는 문제를 풀기 위한 순서를 정하는 문제입니다. 문제를 풀기 위해 다음 규칙을 따라야 합니다:  1. 어떤 문제를 풀기 위해 다른 문제를 먼저 풀어야 하는 경우가 있습니다. 2. 이러한 문제들 간의 우선순위를 고려하여 모든 문제를 풀 수 있는 순서를 찾아야 합니다. 3. 여러 방법이 존재할 경우, 문제 번호가 더 작은 문제를 우선 풀어야 ..

이 문제는 주어진 계단을 오를 때 얻을 수 있는 최대 점수를 구하는 문제입니다. 계단은 특정 규칙에 따라 올라야 하며, 동적 계획법(Dynamic Programming)을 사용하여 해결할 수 있습니다. 문제를 분석하고 접근 방법을 정리한 후, 최종적인 정답 코드를 확인해 보겠습니다. 1. 문제 설명백준 2579번 문제 “계단 오르기”는 주어진 계단을 오르면서 얻을 수 있는 최대 점수를 구하는 문제입니다. 계단을 오를 때 다음 규칙을 따라야 합니다:  1) 계단은 한 번에 한 계단 또는 두 계단씩 오를 수 있습니다. 2) 연속된 세 개의 계단을 모두 밟아서는 안 됩니다. 3) 마지막 계단은 반드시 밟아야 합니다. 2. 문제 접근법이 문제를 해결하기 위해 동적 계획법을 사용합니다. 핵심 아이디어는 각 계단에..

백준 1463번 문제인 “1로 만들기” 문제를 해결하는 방법에 대해 작성해 보겠습니다. 이 문제는 주어진 정수 N을 1로 만들기 위해 필요한 최소한의 연산 횟수를 찾는 문제로, 동적 계획법(Dynamic Programming)을 사용하여 해결할 수 있습니다. 문제를 분석하고 접근 방법을 정리한 후, 최종적인 정답 코드를 확인해 보겠습니다. 문제 URL: https://www.acmicpc.net/problem/1463 1. 문제 설명백준 1463번 문제 “1로 만들기”는 주어진 정수 N을 1로 만들기 위해 최소한의 연산을 사용하는 문제입니다. 가능한 연산은 다음과 같습니다:  1. N이 3으로 나누어 떨어지면, 3으로 나누기. 2. N이 2로 나누어 떨어지면, 2로 나누기. 3. 1을 빼기. 각각의 연산..

백준 4179번 문제인 “불!” 문제를 해결하는 방법에 대해 작성해 보겠습니다. 이 문제는 미로에서 불과 지훈(Jihoon)이 이동할 수 있는 최단 경로를 찾는 문제로, BFS(너비 우선 탐색)를 사용하여 해결할 수 있습니다. 문제를 분석하고 접근 방법을 정리한 후, 최종적인 정답 코드를 확인해 보겠습니다.문제 URL : https://www.acmicpc.net/problem/41791. 문제 설명1) 문제 개요주어진 미로에서 불과 지훈의 위치가 주어지며, 지훈이 미로를 탈출할 수 있는지 여부와 탈출할 수 있다면 그 시간을 구하는 문제입니다. 미로는 벽('#'), 통로('.'), 지훈의 초기 위치('J'), 불의 초기 위치('F')로 이루어져 있습니다.2) 입력• 첫 번째 줄: 미로의 행의 수  R  ..

이번 글에서는 백준 1753번 문제인 “최단경로” 문제를 함께 해결해 보겠습니다. 이 문제는 그래프에서 특정 시작 정점으로부터 다른 모든 정점까지의 최단 경로를 찾는 문제로, 다익스트라 알고리즘을 사용하여 해결할 수 있습니다. 문제를 분석하고, 접근 방법을 정리한 후, 최종적인 정답 코드를 확인해 보겠습니다. 문제 URL: https://www.acmicpc.net/problem/1753 1. 문제 설명 1) 문제 개요주어진 그래프에서 특정 시작 정점에서 다른 모든 정점으로의 최단 경로를 찾는 문제입니다. 그래프는 방향성과 가중치를 가진 간선들로 이루어져 있으며, 시작 정점으로부터 각 정점까지의 최단 거리를 계산해야 합니다. 2) 입력 • 첫 번째 줄: 정점의 수 V (1 ≤ V ≤ 20,000)와 간선..