가중치가 전부 같으면 BFS 가 최단 경로다. 가중치가 달라지는 순간 그 보장이 깨지고, 그때 꺼내는 이름이 셋이다 — 다익스트라, 벨만-포드, 플로이드-워셜. 이름이 셋이라 알고리즘도 셋인 것처럼 보이는데, 코드를 놓고 보면 세 개가 전부 같은 한 줄을 돌린다.if dist[u] + w u 까지 온 거리에 간선 하나를 붙이면 v 가 더 가까워지는가. 그렇다면 v 의 거리를 줄인다. 이것을 완화(relax) 라 부르고, 세 알고리즘의 차이는 어떤 간선을 어떤 순서로 완화하느냐 뿐이다. 가장 가까운 정점부터(다익스트라), 모든 간선을 V-1 번(벨만-포드), 경유 정점을 하나씩 늘리며 모든 쌍(플로이드-워셜). 그 순서의 차이가 음수 가중치를 견디는지, 모든 쌍을 구하는지, 파이썬에서 어디서 무너지는지를 ..

도시 일곱 개를 도로로 전부 잇는데 공사비를 가장 적게 쓰고 싶다. 후보 도로는 열한 개, 각각 비용이 다르다. 어느 여섯 개를 고르는가 — 이것이 최소 신장 트리(MST, Minimum Spanning Tree) 문제다.네트워크 배선, 배관, 클러스터링, 그리고 코딩 테스트의 단골이다. 푸는 방법은 둘이다.크루스칼은 도로를 싼 순서로 늘어놓고 "이걸 놓으면 빙 도는 길이 생기는가"만 보며 고른다.프림은 도시 하나에서 출발해 "지금까지 연결된 동네에서 가장 싸게 닿는 새 도시"를 하나씩 붙인다. 고르는 순서가 완전히 다른데 같은 트리에 도착한다. 이 글은 그 두 알고리즘을 원본 자료의 코드로 한 단계씩 따라가고, "왜 둘 다 정답인가"를 컷 속성 하나로 묶은 뒤, 파이썬에서 실제로 재 본 숫자를 얹는다...

"이 두 원소가 같은 그룹에 속하는가." 이 질문 하나만 빠르게 답하면 되는 문제가 생각보다 많다. 네트워크에서 두 컴퓨터가 연결돼 있는지, 격자에서 두 칸이 같은 덩어리인지, 간선을 하나 더 놓으면 사이클이 생기는지 — 전부 같은 질문이다.서로소 집합(Disjoint-set) 은 이 한 가지 질문에 특화된 자료구조다. 집합마다 대표자 를 한 명 뽑아 두고, 질문을 "두 원소의 대표자가 같은가"로 바꾼다. 구현은 정수 배열 하나면 끝난다.이 글의 절반은 그 배열 위에 얹는 최적화 두 개 이야기다. 코드로는 세 줄 남짓인데, 안 켜면 어떻게 되는지 실제로 재 봤더니 이런 숫자가 나왔다.원소 100,000개에 무작위 union 200,000회 + 연결 질의 200,000회최적화 없음 : 489,594.6 m..

거스름돈을 큰 동전부터 주면 개수가 최소가 된다. 회의를 일찍 끝나는 것부터 잡으면 최대한 많이 넣을 수 있다. 둘 다 맞는 말인데, 앞의 것은 동전 집합을 조금만 바꾸면 틀리고 뒤의 것은 어떤 데이터를 넣어도 틀리지 않는다. 똑같이 "당장 제일 좋아 보이는 것을 고른다"인데 결과가 갈린다.그래서 이 글은 탐욕 알고리즘을 기법이 아니라 가설로 다룬다. "그리디로 풀린다"는 것은 코드를 짜는 방식이 아니라 문제가 만족해야 하는 성질이고, 매번 증명하거나 반증해야 한다.말로만 하면 안 와닿아서 전부 돌려 봤다. 미리 숫자 세 개만 적어 둔다.실제 한국 동전으로는 1원부터 3000원까지 전 금액에서 그리디가 최적이다. 여기에 400원짜리 하나를 끼우면 30.0% 에서 틀린다0-1 배낭 문제에서 가장 그럴듯해 ..

"가장 큰 값 하나"를 반복해서 꺼내야 하는 상황이 있다. 작업 스케줄러, 다익스트라, 중앙값 유지,로그에서 상위 K개 뽑기 같은 것들이다. 리스트로 하면 꺼낼 때마다 전부 훑어야 하고, 매번 정렬해두면 넣을 때마다 원소를 밀어야 한다. 한쪽을 빠르게 하면 다른 쪽이 느려진다. 힙은 그 사이의 절충이다. 전체를 정렬하지 않고 루트 하나만 맞춘다. 덜 하기 때문에 싸다.이 글의 후반부는 백트래킹인데, 여기서는 개념이 아니라 "가지치기가 실제로 얼마나 줄이는가" 를 숫자로 본다. 힙은 무엇을 포기해서 빨라지는가힙(heap) 은 완전 이진 트리에 있는 노드 중에서 키 값이 가장 큰 노드나 가장 작은 노드를 찾기위해서 만든 자료구조다.최대 힙(max heap) — 부모 노드의 키 값 > 자식 노드의 키 값...

난이도 D4.스택과 큐 파트에 있던 문제인데 스택도 큐를 안쓰고 풀었다. 사다리타기라 시뮬레이션만 하면 되는데, 어느 쪽에서 시작할지가 이 문제의 핵심 포인트였다. [문제]100 x 100 배열에 사다리가 그려져 있다. 세로 막대는 1이 세로로 이어진 것이고, 가로선도 1로 그려져 있다. 나머지는 0이다. 바닥 어딘가에 2로 표시된 도착점이 있다.사다리를 타는 규칙은 아는 그대로다. 아래로 내려가다가 좌우에 가로선이 나타나면 그쪽으로 꺾고, 옆 막대로 옮긴 뒤에는 다시 아래로만 간다. 바닥에 닿으면 끝이다.2에 도착하려면 맨 윗줄 어느 x에서 출발해야 하는지를 구하면 된다. 테스트 케이스는 10개 고정이고, 한 막대에서 출발한 가로선이 다른 막대를 가로질러 이어지는 경우는 없다.[내 풀이]처음엔 그냥 0..

스택과 큐 파트에 있던 문제.괄호 문자열 하나 받아서 세기만 하면 되는 거라 만만해 보였는데, 처음 짠 게 시간 초과가 나서 다시 짰다.[문제]쇠막대기 여러 개를 겹쳐 놓고 레이저로 자른다.막대기는 자기보다 긴 막대기 위에만, 완전히 포함되게 놓이고 끝점은 안 겹친다. 이 배치를 괄호로 적는다.막대기의 왼쪽 끝은 (, 오른쪽 끝은 )인접한 () 는 무조건 레이저다레이저는 어떤 막대기의 끝점과도 안 겹친다잘린 조각의 총 개수를 구하면 된다. 괄호는 최대 100,000개.입력 출력2()(((()())(())()))(()) #1 17(((()(()()))(())()))(()()) #2 24[내 ..

앞 글에서 스택과 큐를 만들었다. 그런데 스택과 큐 자체가 목적인 문제는 많지 않다. 그것들은 비선형 자료구조를 훑기 위한 도구였고, 이 글이 그 대상을 다룬다. 트리와 그래프는 "원소들 사이의 관계"를 표현한다. 리스트가 1:1 관계라면 트리는 1:N, 그래프는 N:M이다. 관계가 복잡해질수록 어떻게 저장할 것인가가 성능을 결정하고, 그래서 이 글의 절반은 표현 방식 이야기다. 마지막엔 이진 탐색 트리(BST)를 다룬다. 트리 — 정의부터 재귀적이다성질비선형 구조원소들 간에 1:N 관계를 가지는 자료구조원소들 간에 계층 관계를 가지는 계층형 자료구조정의한 개 이상의 노드로 이루어진 유한 집합이며 다음을 만족한다.노드 중 최상위 노드를 루트(root) 라 한다나머지 노드들은 n개(n ≥ 0)의 분리 집합..