본문 바로가기

분류 전체보기638

다리 만들기 ( 2146 번 ) 2146번: 다리 만들기 🧠 알고리즘 BFS + 다익스트라(Dijkstra)를 활용한 섬 간 최단 다리 길이 탐색 ✔️ 동작 방식문제 핵심 아이디어 각 섬을 서로 다른 번호로 구분한 뒤,각 섬의 가장자리 육지에서 바다를 건너 다른 섬까지의 최소 거리를 다익스트라로 구한다. 섬 라벨링 ( BFS )값이 1인 육지를 BFS로 탐색연결된 육지를 하나의 섬으로 묶고 고유 번호 부여가장자리 육지 판별상하좌우 중 하나라도 바다와 인접한 육지는 섬의 가장자리다익스트라로 다리 길이 탐색시작 섬 번호를 제외한 다른 섬을 만날 떄까지 탐색다른 섬 최초로 만난 순간의 비용이 해당 경로의 다리 길이nonlocal answer 값 갱신현재 비용 >= answer면 탐색 중단( 가지치기 ) 🧾 코드import sys, he.. 2026. 1. 11.
가운데를 말해요 ( 1655 번 ) 1655번: 가운데를 말해요 🧠 알고리즘 힙(Heap)을 활용한 실시간 중앙값(Median) 유지 ✔️ 동작 방식문제 핵심 아이디어최대 힙(l_hq)과 최소 힙(r_hq)을 사용하여 중앙값을 효율적으로 관리한다. 입력 숫자 num을 읽는다.두 힙의 크기를 비교크기가 같으면 최대 힙에 넣음 (중앙값 후보)크기가 다르면 최소 힙에 넣음힙 정리최대 힙의 루트값이 최소 힙의 루트값보다 큰 경우, 두 값을 교환하여 중앙값 유지중앙값 출력항상 최대 힙 루트가 현재까지의 중앙값이 됨 🧾 코드import sys, heapq# 최대 힙, 최소 힙l_hq, r_hq = [], []n = int(sys.stdin.readline().rstrip())for _ in range(n): len_l, len_r = le.. 2026. 1. 11.
N과 M (3) ( 15651 번 ) 15651번: N과 M (3) 🧠 알고리즘백트래킹 (Backtracking) ✔️ 동작 방식문제 핵심 아이디어1부터 N까지의 자연수 중에서 길이가 M인 중복 가능 수열을 모두 생성하는 문제이다.현재 선택된 수열(now_lst)을 기준으로 재귀적으로 탐색한다.재귀 구조현재 수열(now_lst)의 길이가 M이면, 즉시 출력하고 재귀 종료. 아직 길이가 M보다 짧다면, 1부터 N까지 반복num을 수열에 추가(append)_dfs(now_lst) 재귀 호출 (같은 수 포함 가능)재귀 종료 후 pop()으로 수열 상태 복원 (백트래킹)최종 출력길이가 M인 모든 수열을 탐색 과정에서 즉시 출력하며, 반복문이 1→N 순으로 진행되어 사전 순으로 출력됨. 🧾 코드import sys# 필요 파라미터# 1) 현재 배열.. 2026. 1. 4.
N과 M (2) ( 15650 번 ) 15650번: N과 M (2) 🧠 알고리즘백트래킹 (Backtracking) ✔️ 동작 방식문제 핵심 아이디어1부터 N까지의 자연수 중에서 중복 없이 M개를 선택하는 모든 조합을 구하는 문제이다.현재 선택된 수열(now_lst)과 시작 인덱스(start)를 기준으로 재귀적으로 탐색한다.재귀 구조현재 수열(now_lst)의 길이가 M이면 출력하고 재귀 종료.아직 길이가 M보다 짧다면, 시작 인덱스 start부터 N까지 반복:n_lst[idx]를 수열에 추가_dfs(idx + 1, now_lst) 재귀 호출 (다음 수부터 선택)재귀 종료 후 pop()으로 수열 상태 복원 (백트래킹)최종 출력 길이가 M인 모든 조합을 탐색 과정에서 즉시 출력한다. 🧾 코드import sys# 필요한 파라미터# 1) 현재.. 2026. 1. 4.

티스토리툴바