전체 글

MST와 크루스칼 알고리즘 동작 원리. "최소 비용으로 모두 연결"이라는 키워드에서 어떻게 크루스칼까지 이어지는지, 왜 싼 간선부터 고르면 항상 최솟값이 보장되는지 추적해봤다.1. MST란?핵심 아이디어모든 노드를 사이클 없이 최소 비용으로 연결한 트리MST(Minimum Spanning Tree, 최소 신장 트리)는 알고리즘이 아니라 개념이다. "모든 노드를 연결하는 트리 중 간선 비용의 합이 가장 작은 것"을 의미한다.문제에서 아래 키워드가 보이면 MST를 떠올려야 한다."최소 비용으로 모두 연결""모든 섬/도시/노드를 잇는 최소 비용"그림 1. MST 예시 — 섬 연결하기 1 0 ----- 1 | |2 | | 1 | | 2 3간선 목..

📌 문제 정보섬 연결하기 Level 3플랫폼프로그래머스유형그래프, MST, 크루스칼, 유니온-파인드언어Python 3풀이 시간약 70분풀이 날짜2026.06.09문제 링크바로가기 ↗🧩 문제 요약n개의 섬이 있고, 섬 사이를 잇는 다리를 놓는 비용 목록 costs가 주어질 때, 모든 섬이 연결되도록 다리를 놓는 최소 비용을 구하는 문제.입력 조건:n: 섬의 개수costs: [섬a, 섬b, 비용] 형태의 다리 목록출력 조건:모든 섬을 연결하는 최소 비용 반환💡 나의 접근 방식1단계 - 처음 든 아이디어"최소 비용으로 모든 섬을 연결"이라는 키워드에서 MST(최소 신장 트리) 문제임을 바로 파악했다. 모든 노드를 사이클 없이 최소 비용으로 연결하는 게 MST의 정의이기 때문이다.MST를 구현하는 방법은 ..

유니온-파인드의 동작 원리. find가 왜 재귀로 동작하는지, 경로 압축과 rank 기반 합치기가 실제로 어떻게 일어나는지 추적해봤다.1. 유니온-파인드란?핵심 아이디어독립된 집합들을 합치고, 두 원소가 같은 집합인지 빠르게 확인하는 자료구조여러 개의 독립된 집합이 있을 때 union으로 두 집합을 합치고, find로 두 원소가 같은 집합에 속하는지 확인하는 방식이다. 유니온-파인드 자체가 하나의 독립된 알고리즘이 아니라, find와 union이라는 두 연산으로 구성된 자료구조다.기본 구조def find(parents, x): if parents[x] != x: # 루트가 아니면 parents[x] = find(parents, parents[..

📌 문제 정보입국심사 Level 3플랫폼프로그래머스유형이진탐색, 매개변수 탐색언어Python 3풀이 시간약 70분풀이 날짜2026.06.05문제 링크바로가기 ↗🧩 문제 요약n명의 사람이 입국심사를 기다리고 있고, 각 심사관마다 한 명을 심사하는 데 걸리는 시간이 다를 때, 모든 사람이 심사를 마치는 데 걸리는 최소 시간을 구하는 문제입력 조건:n: 심사를 기다리는 사람 수times: 각 심사관이 한 명을 심사하는 데 걸리는 시간 배열출력 조건:n명 모두가 심사를 받기까지 걸리는 최소 시간 반환💡 나의 접근 방식1단계 - 처음 든 아이디어"최소 시간을 구하라"는 말에 처음엔 그리디하게 접근했다. 매 순간 가장 빨리 비는 심사관에게 다음 사람을 배정하는 시뮬레이션을 떠올렸지만, n과 times의 원소 ..

📌 문제 정보길찾기 게임 Level 3플랫폼프로그래머스유형트리, 이진트리 구성, 순회언어Python 3풀이 시간약 90분풀이 날짜2026.06.01문제 링크바로가기 ↗🧩 문제 요약각 노드의 (x좌표, y좌표)가 주어질 때, 이를 이용해 이진트리를 구성하고 전위순회와 후위순회 결과를 구하는 문제트리 구성 규칙:y좌표가 큰 노드가 위쪽(부모), 작은 노드가 아래쪽(자식)같은 부모를 둔 두 자식 노드 중 x좌표가 작은 노드가 왼쪽 자식한 부모에 대해 자식이 둘 이상인 경우는 없음 (x좌표가 모두 다름)입력 조건:nodeinfo: 노드 번호 순서대로 [x좌표, y좌표]가 담긴 2차원 배열노드 번호는 1번부터 시작출력 조건:[전위순회 결과, 후위순회 결과] 형태의 2차원 배열 반환💡 나의 접근 방식1단계 -..

📌 문제 정보미로탈출 Level 3플랫폼프로그래머스유형BFS, 그래프 탐색언어Python 3풀이 시간약 80분풀이 날짜2026.05.25문제 링크https://school.programmers.co.kr/learn/courses/30/lessons/159993">바로가기 ↗🧩 문제 요약격자 형태의 미로(maps)에서 출발지(S)부터 출구(E)까지 가는 최단 시간을 구하되, 반드시 레버(L)를 거쳐야 하는 문제입력 조건:maps는 문자열 배열, 각 문자열은 미로의 한 행S: 시작 지점, E: 출구, L: 반드시 거쳐야 할 레버, O: 통로, X: 벽상하좌우로만 이동 가능출력 조건:출발지에서 레버를 거쳐 출구까지 도달하는 최단 시간 반환도달 불가능하면 -1 반환💡 나의 접근 방식1단계 - 처음 든 아이..

📌 문제 정보다단계 칫솔 판매 Level 3플랫폼프로그래머스유형트리, 해시, 시뮬레이션언어Python 3풀이 시간약 70분풀이 날짜2026.05.04문제 링크바로가기 ↗🧩 문제 요약다단계 판매 조직(enroll, referral)에서 각 판매원(seller)이 칫솔을 판매(amount)했을 때, 추천인 체인을 따라 10%씩 이익을 분배하며 각 판매원이 최종적으로 가져가는 금액을 구하는 문제핵심 조건:판매원은 본인 판매금의 10%를 자신의 추천인에게 지급추천인도 그 금액의 10%를 자신의 추천인에게 지급 (재귀적으로 반복)분배할 금액이 1원 미만이면 그 윗단계로는 분배하지 않고, 자신이 갖음최상위 조직("-")은 더 이상 분배하지 않고 받기만 함입력 조건:가입한 사람 수: 2 ≤ enroll의 길이 ≤..

📌 문제 정보양과 늑대 Level 3플랫폼프로그래머스유형DFS, BFS, 트리언어Python 3풀이 시간약 90분풀이 날짜2026.05.06문제 링크바로가기 ↗🧩 문제 요약루트가 양인 이진 트리에서, 루트부터 출발해 인접한 노드로 이동하며 늑대에게 잡아먹히지 않는 선에서 모을 수 있는 최대 양의 수를 구하는 문제규칙 조건:루트 노드(0번)는 항상 양이며, 시작 지점이동은 현재까지 방문한 노드와 인접한 모든 노드 중에서 선택 가능 (트리 경로 순서를 그대로 따라가지 않아도 됨)어떤 시점이든 늑대 수 ≥ 양 수가 되는 순간 모든 양이 잡아먹힘 → 그 경로는 더 이상 진행 불가모든 노드를 다 방문할 필요는 없음입력 조건:info: 노드별 양(0)/늑대(1) 정보 배열, 1 ≤ info의 길이 ≤ 17edg..