"이 두 원소가 같은 그룹에 속하는가." 이 질문 하나만 빠르게 답하면 되는 문제가 생각보다 많다. 네트워크에서 두 컴퓨터가 연결돼 있는지, 격자에서 두 칸이 같은 덩어리인지, 간선을 하나 더 놓으면 사이클이 생기는지 — 전부 같은 질문이다.서로소 집합(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)의 분리 집합..

배열은 아무 자리에나 넣고 뺄 수 있다. 그게 장점 같지만, 알고리즘 문제를 풀다 보면 일부러 그 자유를 버리는 자료구조를 계속 만나게 된다. 스택은 한쪽 끝에서만 넣고 빼고, 큐는 넣는 곳과 빼는 곳을 반대로 갈라놓는다. 스택은 "가장 최근 것"을 늘 알고 있고, 큐는 "가장 오래된 것"을 늘 알고 있다. 이 글은 스택 → 큐 → 원형 큐 → 연결 리스트 순으로 간다. 제한의 방향이 자료구조를 가른다스택과 큐의 차이는 딱 하나다. 넣는 곳과 빼는 곳이 같은가, 반대인가. 스택큐삽입한쪽 끝(top)뒤(rear)삭제같은 쪽 끝(top)반대쪽 끝(front)순서후입선출 LIFO선입선출 FIFO공짜로 아는 것가장 최근 원소가장 오래된 원소대표 응용괄호 검사, 함수 호출, 후위 계산, DFS버퍼, 대기 행렬,..

순열과 조합은 고등학교 확률과 통계에서 이미 배운 내용이다. 그런데 알고리즘에서 다시 배우는 이유는 개수를 세기 위해서가 아니라 실제로 만들어 내기 위해서다."경우의 수는 몇 가지인가"와 "그 경우들을 하나씩 만들어 확인하라"는 완전히 다른 요구다. 앞의 것은 공식 한 줄이면 되지만 뒤의 것은 코드가 필요하고, 그 코드가 언제까지 버티는지도 알아야 한다.이 글은 순열·조합·중복 순열·중복 조합 네 가지가 재귀에 넘기는 슬라이스 한 줄 차이로 전부 나온다는 것을 보이고, itertools 와 비트마스크까지 정리한다. 앞 글 재귀와 완전 탐색 에서 다룬 부분집합 재귀 트리를 알고 있으면 훨씬 잘 읽힌다.같은 데이터, 세 가지 질문학습 자료는 도시 여섯 개가 서로 다 연결된 그래프 하나를 놓고 질문만 세 번 ..