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

[백준] 28107 : 회전초밥 (Python)

출처 : https://www.acmicpc.net/problem/28107   아이디어해당 문제는 결론부터 말하자면, 우선순위 큐(heap) 유형으로 구분할 수 있다. 그러한 이유를 자세히 살펴보자. 먼저, 핵심 요구사항들을 파악하는 것부터 시작해보자.'1번 손님부터 순서대로 초밥을 먹는다.'여러 명이 같은 초밥을 시켰을 때, 가장 번호가 낮은 손님이 우선권을 갖는다.'각 손님은 자신의 주문 목록에 적힌 순서와 상관없이, 초밥이 존재하면 반드시 먹는다.'주문 목록에 적힌 순서대로 먹는 것이 아닌, 초밥을 기입했냐 안했냐인 존재 여부만을 따진다.'각 종류의 초밥을 한번만 먹는다.'한 손님이 같은 초밥을 여러 개 시킬 일은 존재하지 않는다. (중복 x) 우선권이라는 인사이트를 파악했다면, 사실 우선순위 큐..

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

[백준] 25556 : 포스택 (Python)

출처 : https://www.acmicpc.net/problem/25556   아이디어이번 문제는 스택 유형이다. 요구사항을 바탕으로 다음과 같은 핵심 연산을 떠올렸다.'순열 A의 현재 원소를 4개의 스택 중 어디에 넣어야 하는가?'이에 대한 해답은 예제 입력 케이스들과 함께 발견할 수 있었다. 함께 자세히 알아보자. 위의 사진은 예제 입력 1번 케이스의 삽입 과정을 시각화한 것이다. 먼저 초록색 원 부분을 살펴보자.만약, 4가 존재하는 1번 스택에 3(현재 순열 A의 원소)을 삽입하게 된다면, 4를 절대로 꺼낼 수 없게 된다. 즉, 스택에 원소가 존재한다면, 넣으려는 수 > stack[i][-1] 일때만, 삽입이 가능하다는 의미이다. 이를 스택 삽입 조건 1로 정리할 수 있다.만약, 삽입 불가능하다면..

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

[백준] 3079 : 입국심사 (Python)

출처 : https://www.acmicpc.net/problem/3079   아이디어해당 문제는 결론부터 말하자면, 이분 탐색 유형이다. 필자의 순차적 사고 과정을 작성하였으므로, 사고의 흐름을 파악하면 문제 접근에 도움이 될 것이다. 완전 탐색 1 : 그래프(BFS)루트 노드를 기점으로, BFS를 통해 모든 경우를 비교하여 정답을 카운팅하는 알고리즘을 처음 생각했다. 상황 그래프이기 때문에, 메모리 공간과 시간은 2의 거듭제곱의 복잡도를 가지므로 해당 알고리즘을 탈락시켰다. 완전 탐색 2 : 그리디(탐욕)갱신되는 각 심사대의 끝 시간을 기준으로, 가장 빨리 다음 손님을 받는 심사대를 탐욕적으로 선택하는 방법을 고안하였다. 1번째 예제입력 케이스를 바탕으로 알고리즘 과정을 설명한다. 다음의 사진을 보자..

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

[백준] 9095 : 123 더하기(Python)

출처 : https://www.acmicpc.net/problem/9095  아이디어정수 n의 자식노드들을 트리로 그려보게 되면 n-1, n-2, n-3임을 알 수 있고, 이를 통해, 다음과 같은 규칙을 발견할 수 있다.n의 합 개수는 자식노드들인 각 n-1, n-2, n-3의 개수를 모두 더한 것이다.자식에 해당되는 트리 깊이의 답들이 부모 깊이에서 재사용된다.중복 노드가 존재할 수 있다.그러므로, DP의 조건에 부합되므로 메모제이션 기법이 적용된 DP로 프로그램을 구현할 수 있다. 필자는 Bottom-Up을 선택하였으므로, 보텀업을 통한 DP테이블 저장 과정을 살펴보자. 저장 연산 일반화 공식n이 4일 때를 가정해보자. 4의 모든 경우의 수는 3,2,1 자식노드들을 모두 더한 것과 같다. 이를 통해 ..

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

[백준] 13565 : 침투 (Python)

출처 : https://www.acmicpc.net/problem/13565  아이디어경로를 찾아나가는 문제이므로, 그래프 탐색 유형임을 알 수 있다.인접한 상하좌우를 통해, Inner에 도달 가능한지에 대한 여부만을 요구사항으로 제시하고 있다. 이를 바탕으로, 2차원 행렬 상에서 다음과 같이 구분할 수 있다.빨간색 : 그래프 탐색 시작점파란색 : 간선Inner에 해당되는 칸들에 도달 가능한가?즉, 우리는 해당 문제의 인사이트를 다음과 같이 해석할 수 있고, 이를 통해 프로그램을 구현하면 문제를 해결할 수 있다.1번째 행의 열들 중에서, 마지막 행에 도달 가능한 경로가 존재하는가?탐색 기법은 도달 가능한지만 묻는 문제이므로, DFS/BFS 모두 사용 가능하다. 필자는 DFS로 구현하였다. 정답 코드더보기..

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