[백준] 1463 : 1로 만들기 (Python)

출처 : https://www.acmicpc.net/problem/1463  아이디어해당 문제는 3가지 연산이 트리의 간선들로 연결되고 루트 노드가 X로 고정되있으므로, 특수 그래프 트리의 탐색 유형임을 알 수 있다. 이를 바탕으로, 다음 3가지의 알고리즘 탐색 기법을 설계해보았다.BFS + MemoDP - Top Down (DFS+Memo)DP - Bottom-Up (For Loop)일반적으로 시간 효율성은 DP -> BFS이므로, DP의 접근 방식을 선택하였고 이에 대해 자세히 살펴보자. (물론, 해당 문제의 경우는 BFS로도 잘 풀릴 수 있지만, 일반적인 문제들의 경우는 두 기법 모두 접근 방식이 다를 수 있다.) DP가 가능한 이유해당 문제를 시각화하면 다음 사진과 같다.각 노드에 3가지의 서브트..

• format_list_bulleted Problem Solving/Baekjoon
• · 2025. 1. 11.

[백준] 2210 : 숫자판 점프 (Python)

출처 : https://www.acmicpc.net/problem/2210   아이디어이번 문제는 상하좌우로 탐색을 진행해야 하는 그래프 탐색 유형이다. 요구사항 분석을 통해 DFS와 BFS의 탐색 과정을 어떻게 설정해야하는지 확인해보자. '한 번 거쳤던 칸을 다시 거쳐도 된다.'일반적으로는 해당 요구사항은 백트래킹으로 해석할 수 있다. 그러나, 이번 문제에서는 백트래킹이 아니라, '단순히 이전에 방문했던 칸을 다시 탐색해도 된다.'라는 의미를 가진다. 즉, 방문처리를 따로 하지 않고, 온전히 상하좌우 방향을 모두 탐색하는 설계를 세울 수 있다는 뜻이다. 여기서 우리는 다음과 같은 의문점이 생긴다.'방문처리를 하지 않으면, 어떻게 탐색 종료 조건을 넣어야 하는가?'이러한 의문점에 대한 해답인 인사이트는 ..

• format_list_bulleted Problem Solving/Baekjoon
• · 2025. 1. 10.

[백준] 6067 : Guarding the Farm (Python)

출처 : https://www.acmicpc.net/problem/6067 아이디어해당 문제는 상하좌우 칸을 체크하며, 산봉우리에 포함되는 지역인지 확인해야하기 때문에 그래프 탐색 문제 유형으로 해석할 수 있다. 요구사항을 바탕으로, 어떻게 산봉우리 개수를 출력할지 생각해보자. '인접하다'의 정의는 X좌표 차이와 Y좌표 차이가 모두 1이하인 경우상하좌우뿐만 아니라, 대각선도 인접하다는 사실을 알 수 있다. 즉, 인접 칸(노드)들을 탐색하게 되는 간선이 8개가 존재한다. 산봉우리와 인접한 격자는 모두 산봉우리의 높이보다 작아야 한다.산봉우리의 고도는 가장 커야 한다는 의미이다. 이를 통해, 산봉우리는 지역(덩어리)로 구분이 되고, 이에 따른 지역(덩어리) 개수를 출력해야하므로, BFS 탐색을 몇번 하는가를..

• format_list_bulleted Problem Solving/Baekjoon
• · 2025. 1. 9.

[백준] 9184 : 신나는 함수 실행 (Python)

출처 : https://www.acmicpc.net/problem/9184 문제재귀 호출만 생각하면 신이 난다! 아닌가요?다음과 같은 재귀함수 w(a, b, c)가 있다.if a 20 or b > 20 or c > 20, then w(a, b, c) returns: w(20, 20, 20)if a 위의 함수를 구현하는 것은 매우 쉽다. 하지만, 그대로 구현하면 값을 구하는데 매우 오랜 시간이 걸린다. (예를 들면, a=15, b=15, c=15)a, b, c가 주어졌을 때, w(a, b, c)를 출력하는 프로그램을 작성하시오.입력입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제..

• format_list_bulleted Problem Solving/Baekjoon
• · 2025. 1. 8.

[백준] 15900 : 나무탈출 (Python)

출처 : https://www.acmicpc.net/problem/15900 문제평소에 사이가 좋지 않던 성원이와 형석이가 드디어 제대로 한 판 붙으려고 한다. 성원이와 형석이 둘과 모두 똑같이 친한 인섭이가 대결 종목을 정해 가져왔다. 바로 '나무 탈출' 이라는 보드게임이다.'나무 탈출' 은 N개의 정점이 있는 트리 모양으로 생긴 게임판과 몇 개의 게임말로 이루어진다. 트리의 각 정점에는 1번부터 N번까지 번호가 붙어있다. 1번 정점은 '루트 노드' 라고 불리며, 이 루트 노드를 중심으로 정점 간에 부모-자식 관계가 만들어진다. 자식이 없는 노드는 '리프 노드' 라고 불린다.이 게임은 두 사람이 번갈아 가면서 게임판에 놓여있는 게임말을 움직이는 게임이다. 처음에는 트리의 모든 리프 노드에 게임말이 하나..

• format_list_bulleted Problem Solving/Baekjoon
• · 2025. 1. 7.

[백준] 13463 : Brexit (Python)

출처 : https://www.acmicpc.net/problem/13463 문제오래전 은하계에서 아주 먼 옛날, 은하계 전역의 많은 국가로 구성된 대규모 성간 무역 연합이 있었습니다. 최근에 한 국가가 연합을 탈퇴하기로 결정했습니다. 그 결과, 다른 국가도 탈퇴를 고려하고 있는데, 주요 무역 파트너가 없어지면 연합에 참여하는 것이 더 이상 이롭지 않기 때문입니다.당신은 국가 X의 우려하는 시민이며, 당신의 국가가 연합에 남을지 여부를 알고 싶어합니다. 당신은 서로의 무역 파트너인 모든 국가 쌍의 목록을 만들었습니다. 주어진 국가 Y의 무역 파트너의 절반 이상이 연합을 탈퇴하면, 국가 Y도 곧 뒤따를 것입니다. 이 정보를 바탕으로, 당신은 이제 당신의 본국이 연합을 탈퇴할지 여부를 결정하려고 합니다.입력..

• format_list_bulleted Problem Solving/Baekjoon
• · 2025. 1. 6.