📖 문제[백준] #28066. 타노스는 요세푸스가 밉다 (파이썬/Python)난이도: 실버2유형: 구현, 자료구조, 덱📌 문제 요약1번부터 N번까지 청설모가 원을 이루어 앉아 있다.첫 번째 청설모부터 시계 방향으로 K마리를 선택했을 때, 첫 번째 청설모만 살아남고 나머지는 제거된다.만약 남아 있는 청설모가 K마리보다 적다면, 첫 번째 청설모를 제외한 전부 제거된다.제거 이후 청설모가 2마리 이상 남아있다면, 첫 번째 청설모의 오른쪽 청설모가 새로운 첫 번째 청설모가 되고 과정을 반복한다.청설모가 1마리만 남을 때까지 이 과정을 반복했을 때, 마지막으로 살아남는 청설모의 번호를 구하면 된다.🔍 문제 접근💡 문제 분석기본적으로 원형 자료구조 시뮬레이션 문제이다.단순 리스트를 이용해 삭제를 반복하면 시..

📖 문제[백준] #1158. 요세푸스 문제 (파이썬/Python)난이도: 실버4유형: 구현, 큐, 자료구조📌 문제 요약1번부터 `N`번까지의 사람들이 원형으로 앉아있다.양의 정수 `K`가 주어졌을 때, 순서대로 `K`번째 사람을 제거한다.제거된 사람을 제외하고 남은 사람들로 다시 원을 이루어 같은 과정을 반복한다.이 과정을 통해 제거되는 순서를 `(N, K)-요세푸스 순열`이라고 한다.예시:(7, 3)-요세푸스 순열 ⇢ ``즉, `N`과 `K`가 주어졌을 때, 사람들이 제거되는 순서를 출력하는 문제이다.🔍 문제 접근💡 문제 분석사람들을 원형으로 관리해야 한다.매번 K번째 사람을 제거해야 하므로, 큐(Queue) 구조를 활용하는 것이 적절하다.파이썬에서 `list`의 `pop(0)`은 시간 복잡도가..

📖 문제[백준] #2644. 촌수계산 (DFS/BFS) (파이썬/Python)난이도: 실버2문제 유형: DFS/BFS📌 문제 요약`a`, `b`의 촌수를 계산하는 문제이다. 그래프로 따지면 `a`노드와 `b`노드 사이의 간선의 개수를 구하면 된다.만약 그래프가 연결되어 있지 않다면 `-1`을 출력한다.🔍 문제 접근💡 문제 분석DFS와 BFS 모두 풀이 가능하다.이 문제에서는 노드 a와 b 사이의 간선 개수를 구하는 게 목적이기 때문에 깊이 우선 탐색을 사용하는 DFS가 더 적합하다고 판단했다. 또한, 이 문제는 경로를 탐색하면서 불필요한 경로는 제외하는 백트래킹 기법이 더 적합하다. 백트래킹을 통해 불필요한 경로를 가지치기하면서 효율적으로 두 노드 간의 촌수를 계산할 수 있다. 💡 백트래킹백트래..

📖 문제[백준] #5014. 스타트링크 (파이썬/Python)난이도: 실버1유형: BFS📌 문제 요약강호는 스타트업 스타트링크 면접에 늦게 도착해, 건물의 엘리베이터를 타고 이동하려 한다.건물은 총 `F`층이며, 강호는 현재 `S`층에 있다. 면접장은 `G`층이다.엘리베이터에는 버튼이 두 개뿐이다.`U` 버튼: 위로 `U`층 이동`D` 버튼: 아래로 `D`층 이동강호가 `G`층에 도착하려면 버튼을 최소 몇 번 눌러야 하는지 구해야 한다.만약 도착할 수 없다면 `"use the stairs"`를 출력한다.🔍 문제 접근💡 문제 분석“최소 버튼 클릭 횟수” → 최단 거리 문제이다.따라서 BFS(너비 우선 탐색)으로 접근한다.F층: 사무실의 총 층수G층: 스타트링크가 있는 곳의 위치 S층: 강호가 지금 ..

📖 문제[백준] #2468. 안전 영역 (파이썬/Python)난이도: 실버1유형: DFS, BFS📌 문제 요약장마철을 대비해 지역의 높이 정보를 기반으로 비가 내렸을 때 물에 잠기지 않는 안전한 영역의 최대 개수를 계산해야 한다.지역은 N x N 크기의 2차원 배열로 주어진다.비가 많이 오면 특정 높이 이하의 지점들은 잠긴다.이때 상하좌우로 인접해 있는 잠기지 않은 지점들을 하나의 안전한 영역으로 간주한다.비의 양에 따라 잠기는 범위가 달라지므로, 모든 비의 양에 대해 안전 영역의 개수를 구하고, 그 중 최대값을 출력해야 한다.높이는 1 이상 100 이하의 자연수이며, 잠기지 않는 경우도 고려해야 한다.🔍 문제 접근💡 문제 분석물에 잠기지 않는 안전한 영역이란, 인접한 지점들이 연결된 덩어리로 존..

📖 문제[백준] # 16987. 계란으로 계란치기(파이썬/Python)난이도: 골드3유형: 백트래킹문제 요약인범이는 식사 준비를 위해 계란을 깨야 하는데, 손에 힘이 너무 세서 부엌 대리석으로 깨면 늘 산산조각이 나 뒷정리가 어렵다. 이에 친구 유현이가 알려준 팁은, 바로 계란으로 계란을 치는 것. 이를 통해 "얼마나 많은 계란을 깨뜨릴 수 있는지"를 계산하는 것이 문제의 핵심이다.각 계란은 내구도(`S`)와 무게(`W`)가 있으며, 계란으로 계란을 치면 다음과 같은 일이 일어난다:계란 A가 계란 B를 칠 경우, A의 내구도는 B의 무게만큼 깎이고B의 내구도는 A의 무게만큼 깎인다.내구도가 0 이하가 되는 계란은 깨진 것으로 간주한다.예시)계란 1: 내구도 7, 무게 5계란 2: 내구도 3, 무게 4➡..

📖 문제[백준] #15683. 감시 (파이썬/Python)난이도: 골드3유형: 구현, 백트래킹문제 요약N×M 사무실에 설치된 다양한 종류의 CCTV가 있다.각 CCTV의 감시 방향을 적절히 정해, 감시할 수 없는 영역(사각지대)의 최소 크기를 구해야 한다.CCTV는 각기 다른 방향으로 감시가 가능하며, 벽(6)은 감시할 수 없다. CCTV는 회전이 가능하고, 다른 CCTV는 통과할 수 있다.지도 정보:0: 빈칸6: 벽1~5: CCTV 번호조건:벽은 통과할 수 없다.CCTV 는 90도 방향으로 회전할 수 있다.CCTV는 CCTV를 토과할 수 있다.제한 조건:1 ≤ N, M ≤ 8CCTV 개수 ≤ 8CCTV가 감시할 수 있는 방법:🔍 문제 접근💡 문제 분석일단 문제의 ‘방향’ 이미지를 보고 그래프 탐색..

📖 문제[백준] #13549. 숨바꼭질 3 (파이썬/Python)난이도: 골드5유형: BFS문제 요약수빈이는 현재 위치 `N`에 있고, 동생은 `K`에 있다.수빈이는 다음 3가지 방법으로 이동할 수 있다.`X - 1` (1초 소요)`X + 1` (1초 소요)`2 * X` (0초 소요)목표는 동생에게 도달하는 데 걸리는 최소 시간(초)을 구하는 것이다.(숨바꼭질 시리즈)🔍 문제 접근💡 문제 분석처음에 틀린 이유를 찾을 수가 없어서 GPT의 도움을 받았다.이 문제는 가중치가 0 또는 1인 그래프에서의 최단 거리 문제이다.`X → 2X`는 이동 시간 0 → 가중치 0`X → X±1`은 이동 시간 1 → 가중치 1이처럼 간선 가중치가 0 또는 1일 경우, 일반 BFS가 아닌 0-1 BFS 기법을 사용해야 ..

📖 문제[백준] #14226. 이모티콘 (파이썬/Python)난이도: 골드4유형: BFS문제 요약현재 화면에는 😃 이모티콘 1개가 있다.목표: S개의 이모티콘을 화면에 만들기 위한 최소 시간을 구해야 한다.사용할 수 있는 연산은 다음 3가지이다. (모두 1초 소요)연산 설명1. 복사화면에 있는 이모티콘 전부를 클립보드에 복사2. 붙여넣기클립보드 내용을 화면에 붙여넣기3. 삭제화면에서 이모티콘 하나 삭제※ 클립보드가 비어있으면 붙여넣기를 할 수 없다.※ 클립보드, 화면 모두 "일부 선택"은 불가능하며 전량 복사/붙여넣기/삭제만 가능하다.🔍 문제 접근💡 문제 분석"최소 시간" → BFS로 탐색해야 한다.일반적인 BFS와 달리, 상태를 구성하는 요소가 2가지이다.현재 화면 이모티콘 수현재 클립보드 이모..