[백준] 14248 : 점프점프 (Python)

출처 : https://www.acmicpc.net/problem/14248  아이디어해당 문제는 그래프 탐색 유형으로 분류할 수 있으며, '점프를 해나가는 과정'의 의미를 파악하면 쉽게 해결할 수 있다. 예제를 통해, 그 의미를 살펴보자.예제 입력 1번 케이스를 기준으로, 3번돌의 다음 방문 돌을 오른쪽으로 간다고 가정해보자. 이 때, 돌의 방문 순서는 다음과 같다.3번돌 -> 5번돌 -> 4번돌 -> 2번돌 -> 방문불가(범위초과)이는 함수로써 다음과 같이도 쓸 수 있다.f(3) -> f(f(3)) -> f(f(f(3))) -> f(f(f(f(3)))) -> 방문 불가즉, '점프를 해나가는 과정'은 '재귀 함수'와 동일하다. 이를 토대로, 우리는 그래프로 다음과 같이 시각화할 수 있다.그래프 정의는 ..

• format_list_bulleted Problem Solving/Baekjoon
• · 2025. 2. 28.

[백준] 17141 : 연구소2 (Python)

출처 : https://www.acmicpc.net/problem/17141  아이디어'상하좌우로 인접한 모든 빈칸으로 동시에 복제'해당 요구사항을 통해, 동시에 인접한 칸들로 복제되므로 BFS 그래프 탐색 유형임을 알 수 있다. 그렇다면, 이를 토대로 구현에 필요한 핵심 인사이트들을 파악해보자. 바이러스가 모든 빈 칸들에 복제되었는지 어떻게 판단할까?모든 빈 칸들이 복제되었는지에 대한 여부를 판단해야하므로, 빈 칸 카운팅이 필요하다는 것을 알 수 있다. 즉, BFS 탐색 전의 빈칸들 상태와 탐색 후 빈칸들 상태를 같은지 비교하면 된다.이를 위해 다음 2가지 카운팅 변수를 설정해야 한다.Total_blank : 초기 연수소의 빈칸(0)의 개수들을 카운팅 + 바이러스 후보 칸들(2)State_blank :..

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

[백준] 12869 : 뮤탈리스크 (Python)

출처 : https://www.acmicpc.net/problem/12869  아이디어'한 번에 3개의 scv를 공격할 수 있다.'해당 요구사항을 바탕으로, '어떤 scv에 제일 높은 공격을 진행할 것인가'에 대한 인사이트가 이번 문제의 핵심이다. scv수가 3개인 상황을 예시로 경우의 수가 어떻게 나뉘는지 살펴보자.먼저, 3개의 scv를 공격하는 방법은 순열이라는 것을 알 수 있다. 즉, 6가지 경우의 수가 존재한다는 것이고, 이는 그래프 상에서 분기되는 간선(자식 서브트리)에 해당된다. 이러한 그래프와 scv 공격과의 관계를 바탕으로 다음과 같은 해석을 진행할 수 있다.큰 문제(초기 scv의 공격 최소 횟수)는 작은 문제(서브트리의 scv의 공격 최소 횟수)로 분할 가능하다.작은 문제의 답을 큰 문제..

• format_list_bulleted Problem Solving/Baekjoon
• · 2025. 2. 3.

[백준] 16294 : Bee Problem (Python)

출처 : https://www.acmicpc.net/problem/16294  아이디어'특정 셀에 꿀을 흘리면, 인접한 빈칸들에 퍼져나간다.'해당 요구사항을 통해, 그래프 탐색 유형으로 해석 가능하며 DFS/BFS 모두 사용 가능하다. 주어지는 2차원 행렬은 공백이 포함되있기 때문에 다음의 사진을 바탕으로, 행렬의 범위와 탐색 방향을 계산할 수 있다. 한 번의 탐색은 빈칸들의 덩어리를 찾게 되므로, 한 덩어리(그룹)의 빈칸 개수를 찾아내고 이 수를 이용하여, 벌의 최소 작업량을 구할 수 있다. 정답 코드더보기# https://www.acmicpc.net/problem/16294# Bee Problem# 그래프탐색,BFS,DFSinput=__import__('sys').stdin.readlinedeque=..

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

[백준] 1003 : 피보나치 함수 (Python)

출처 : https://www.acmicpc.net/problem/1003  아이디어해당 문제는 대표적인 그래프 탐색 유형의 문제이며, '중복 연산'에 대한 핵심 인사이트를 개념으로 설명하는 문제이다. 다만, 피보나치 값을 물어보는 것이 아닌, 단말노드인 0과 1을 몇 번 탐색하느냐를 요구사항으로 제시한다.먼저, 일반적인 피보나치 수열에 대한 그래프와 이에 따른 0과 1 단말노드 관점을 시각화하여 살펴보자.왼쪽 그래프에서 Fibo(4), Fibo(3), Fibo(2)과 중복으로 연산된다는 사실을 알 수 있으며, 다음의 DP 조건을 만족하므로, 알고리즘으로 DP를 선택할 수 있다.큰 문제를 작은 문제로 나눌 수 있는가작은 문제의 답이 큰 문제에서 일부분으로 사용되는가이 과정에서 중복되는 연산이 있는가즉, ..

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

[백준] 1068 : 트리 (Python)

출처 : https://www.acmicpc.net/problem/1068  아이디어이번 문제는 특수 그래프 중 하나인 트리라는 것을 직접적으로 알려줬으므로, 그래프 탐색 유형임을 알 수 있다. 트리 순회를 물어보는 요구사항을 바탕으로, DFS BFS 중에서 아무거나 선택해서 사용하면 된다. 필자는 DFS를 선택하였다.그렇다면, 해당 요구사항을 바탕으로 프로그램 설계 시, 어떤 자료구조와 핵심 연산 중 하나인 삭제를 어떤 식으로 진행해야 하는지 살펴보자. 인접행렬 vs 인접리스트예제 입력 1번 케이스를 바탕으로 인사이트를 파악할 수 있다.n : 5-1 0 0 1 1삭제 대상 노드 번호 : 2양방향 트리로써 간선이 2개가 존재한다. 이를 바탕으로, 인접행렬은 대칭성을 띄게 된다. 0의 개수가 많으므로, 희..

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