📖 문제[백준] #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 이하의 자연수이며, 잠기지 않는 경우도 고려해야 한다.🔍 문제 접근💡 문제 분석물에 잠기지 않는 안전한 영역이란, 인접한 지점들이 연결된 덩어리로 존..

📖 문제[프로그래머스] [2021 카카오 채용연계형 인턴십] 거리두기 확인하기 (파이썬/Python)난이도: Level 2유형: 완전탐색, BFS 문제 요약개발자를 희망하는 죠르디가 카카오에 면접을 보러 왔다. 코로나 바이러스 감염 예방을 위해, 응시자들은 대기실에서 일정한 거리를 두고 앉아야 한다. 각 대기실은 5x5 크기로, 총 5개의 대기실이 주어진다. 규칙 요약:응시자끼리는 맨해튼 거리 2 이하로 앉으면 안 된다.단, 거리 2 이내라도 파티션(X) 으로 막혀 있다면 예외적으로 허용한다. 문자 의미:`P`: 사람이 앉아있는 자리`O`: 빈 테이블`X`: 파티션 문제 요구사항:5개의 대기실이 2차원 문자열 배열 형태로 주어진다.각 대기실에 대해 거리두기를 지키고 있다면 `1`, 위반한 사람이 단 한..

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

📖 문제[프로그래머스] 게임 맵 최단거리 (파이썬/Python) (자바/Java)난이도: Level 2유형: BFS풀이 시간: 28분문제 요약캐릭터가 `(1,1)`에서 시작해 상대 팀 진영 `(n,m)`까지 이동해야 한다.이동할 수 있는 곳은 1, 이동할 수 없는 벽은 0으로 표시된다.최소 칸 수로 상대 진영에 도착하는 경우의 칸 수를 반환하라.도달할 수 없다면 -1을 반환한다.캐릭터는 상하좌우 네 방향으로 한 칸씩 이동 가능하다.맵 밖으로 나갈 수 없고, 벽(0)은 통과할 수 없다.🔍 문제 접근💡 문제 분석핵심 키워드: 최단거리, 동서남북으로 이동 ⇒ BFS 유형!동서남북으로 인접한 칸만 탐색할 수 있다.`maps`에는 0이 벽을 의미하고 1이 벽이 없는 자리를 의미한다.즉, 매번 이동할 때마다 ..

📖 문제[백준] #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가 감시할 수 있는 방법:🔍 문제 접근💡 문제 분석일단 문제의 ‘방향’ 이미지를 보고 그래프 탐색..