[백준] 11399 : ATM (Python)

출처 : https://www.acmicpc.net/problem/11399  아이디어해당 문제는 1차원 배열의 가능한 경우의 수들을 통해, 최소값을 찾는 문제이다. 다시 말해, 그래프, 이분탐색, 그리디, DP 등으로 접근을 할 수 있다.경우의 수가 조합을 따르기에 그래프(BFS)는 시간 초과의 가능성 있기 때문에, 나머지 3가지의 알고리즘을 통해 문제를 해결할 수 있다. 필자는 그리디로 먼저 접근하였으므로, 그리디로 푸는 과정을 살펴보자. 누적 합이 최소인 순서를 골라야 한다.경우의 수들이 트리 상에서 어떻게 되는지 시각적으로 한번 보자.루트 노드부터 선택할 수 있는 5가지 경우가 존재하므로, 전체 트리가 5개가 존재할 것이다. 그 중에서 누적 합의 의미는 다음과 같다.깊이 1부터 깊이 i까지의 노드..

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

[백준] 16120 : PPAP (Python)

출처 : https://www.acmicpc.net/problem/16120  아이디어해당 문제는 스택의 대표적인 유형 문제인 괄호 넣기와 유사하다. 문자열 내의 특정 문자열을 대체하는 유형이다. 즉, 역과정을 통해 PPAP 문자열인지 검토하는 방법을 통해 문제의 알고리즘을 설계할 수 있다.다시 말해, 'PPAP' 문자열을 'P'로 대체 및 반복하여, 마지막에 'PPAP' 및 'P'가 남으면, PPAP 문자열이라고 정답 처리를 할 수 있다. 대체하고 반복한다는 의미를 다음의 예제를 통해 파악할 수 있다.문자열 내의 PPAP를 찾아 P로 대체하는 과정을 시각화하였고, 대체된 전체 문자열을 다시 이용하여 다음 PPAP를 찾는 것이다. 이런 과정을 거치면 초기 문자열의 길이보다 줄어들게 되고, PPAP 문자열..

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

[백준] 2343 : 기타 레슨 (Python)

출처 : https://www.acmicpc.net/problem/2343  아이디어먼저, 다음 3가지의 요구사항을 통해, 해당 문제는 이분 탐색 유형임을 알 수 있다.강의의 순서가 바뀌면 안된다.블루레이의 크기를 최소로 하려고 한다.M개의 블루레이는 모두 같은 크기여야 한다.순서가 일정하고 랜덤한 크기를 선택하여 최소를 찾는 것이므로, 이분 탐색 조건에 알맞는다. 이 부분이 이해가 되지 않는다면, 특정 k를 1~N까지의 숫자 중에서 빠르게 찾는 문제를 곰곰히 생각해보면 된다.1~N은 순서가 변하지 않으며(순서 일정), 이 중에서 특정한 수를 콕 집어서(랜덤 선택) 그 수보다 큰지 작은지를 바탕으로, 다음 탐색의 범위를 좁히는 것이 키포인트이다.아래에 후술하겠지만, 방금 설명한 예시와 해당 문제 세팅 과..

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

[백준] 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.

[백준] 14271 : 그리드 게임 (Python)

출처 : https://www.acmicpc.net/problem/14271  아이디어해당 문제는 상하좌우 근접 칸을 탐색해야 하는 문제이므로, 그래프 탐색 유형이다. 먼저, 그리드의 칸이 변하는 규칙을 바탕으로, 요구사항이 어떤 의미를 가지는지 파악해보자.요구사항 파악'크기가 무한대이고, 단위 정사각형으로 나누어져 있는 그리드'해당 사진을 통해 알 수 있듯이, 2 by 2 행렬이 4 by 4로 점점 확장되는 모습을 확인해볼 수 있다. 만약, 확장되는 형식으로 그래프를 탐색해야 한다면 완전 탐색이 될 수 밖에 없으므로 O(n**2) 시간 복잡도를 가지게 된다.완전 탐색을 피하기 위해서는 '행렬의 크기가 진짜 무한대인가'를 따져봐야 한다. 커지는 규칙이 존재하는데 그것이 K이다. 얼마나 커지는지는 후술하도..

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