#알고리즘 14

• PS 2019-07-07

  비트마스킹 (Bitmasking) 정리

  비트마스킹 집합의 상태를 정수의 각 비트로 표현하는 기법. 원소가 N개인 집합을 N비트 정수 하나로 나타낸다. (i번 비트가 1이면 i번 원소가 집합에 있음) 집합 연산이 비트 연산 한 번으로 끝나 빠르고, 무엇보다 상태를 정수 하나

• PS 2019-05-12

  최소 신장 트리 (MST) 정리

  최소 신장 트리 (MST) 연결된 가중치 그래프에서, 모든 정점을 잇되 사이클 없이(즉 트리로) 연결하는 부분 그래프 중에서 간선 가중치의 합이 최소 인 것. 정점이 V개면 간선은 정확히 V-1개를 쓴다. "모든 도시를 최소 비용으로

• PS 2019-03-10

  위상 정렬 (Topological Sort) 정리

  위상 정렬 방향 그래프에서 선후 관계(A 다음에 B)를 어기지 않도록 정점들을 한 줄로 나열하는 것. "선수 과목을 다 들어야 다음 과목을 듣는다", "이 작업이 끝나야 저 작업을 시작한다" 같은 순서 제약을 만족하는 순서를 구할 때

• PS 2019-01-13

  유니온 파인드 (Union-Find) 정리

  유니온 파인드 (서로소 집합) 여러 원소가 어떤 집합에 속하는지를 관리하면서, 두 연산을 빠르게 처리하는 자료구조. - find(x) : x가 속한 집합의 대표(루트)를 찾는다. - union(a, b) : a가 속한 집합과 b가 속

• PS 2018-11-18

  분할 정복 (Divide and Conquer) 정리

  분할 정복 큰 문제를 같은 형태의 작은 부분 문제로 나눠서(divide) 각각 풀고(conquer), 그 결과를 합쳐(combine) 원래 문제의 답을 만드는 설계 기법. DP와 헷갈리기 쉬운데, 분할 정복은 보통 부분 문제들이 겹치

• PS 2018-10-14

  누적 합 (Prefix Sum) 정리

  누적 합 배열의 앞에서부터의 합을 미리 구해 두어, 임의 구간의 합을 O(1) 에 답하는 기법. 매번 구간을 직접 더하면 질의 1번에 O(N) , 질의가 많으면 O(NQ) 로 터진다. 누적 합을 한 번 O(N) 에 만들어 두면 그 뒤

• PS 2018-09-09

  백트래킹 (Backtracking) 정리

  백트래킹 가능한 모든 경우를 DFS로 하나씩 만들어 보되, 더 진행해도 답이 될 수 없다고 판단되는 순간 그 가지를 포기하고 되돌아가는 방법. 완전 탐색(brute force)과 뼈대는 같지만, "여기서 더 가봐야 소용없다"를 미리

• PS 2018-08-12

  이분 탐색 (Binary Search) 정리

  이분 탐색 정렬된 배열에서 탐색 범위를 절반씩 줄여 가며 원하는 값을 찾는 방법. 매번 후보가 반으로 줄어드니 O(log N) . 핵심 전제는 단조성(monotonicity) 이다. "어떤 기준값 이전은 전부 참, 이후는 전부 거짓"

• PS 2018-07-08

  다익스트라 (Dijkstra) 정리

  다익스트라 어떤 그래프 G와 시작 정점 st가 주어질 때, st로부터 다른 모든 정점으로의 최단 경로 길이를 구하는 알고리즘. 이러한 특징으로 시작점 고정 최단거리 알고리즘 이라고도 한다. 다익스트라 알고리즘은 매 단계마다 도달할 수

• PS 2018-06-10

  다이나믹 프로그래밍 (DP) 정리

  다이나믹 프로그래밍 정의 복잡한 큰 문제를 재귀적인 방식(재귀적인 방식이지 재귀 함수로 구현해야 하는것은 아니다)으로 간단한 하위 문제로 나누어 최종 큰 문제까지 해결할 수 있는 알고리즘 설계 기법, 주로 모든 경우의 수를 일일이 다

• PS 2018-05-20

  투 포인터 (Two Pointer) 정리

  Two Pointer 일반적으로 어떤 수열 $A = {1,2,3,4,5,6...}$ 에서 각각 다른 원소를 가르키고 있는 두개의 포인터를 움직이며 투포인터 없이는 $O(N^2)$ 만에 수행 할 수 있는 연산을 $O(N)$ 만에 해결하

• PS 2018-05-13

  너비 우선 탐색 (BFS) 정리

  BFS (너비 우선 탐색) 시작 정점에서 가까운 정점부터 차례대로, 레벨 단위로 퍼져 나가며 탐색하는 방법. 큐(Queue)를 사용한다. DFS가 한 갈래를 끝까지 파고드는 것과 반대로, BFS는 시작점에서 거리 1인 정점들을 모두

• PS 2018-05-06

  깊이 우선 탐색 (DFS) 정리

  DFS (깊이 우선 탐색) 그래프나 트리에서 한 정점을 시작으로, 갈 수 있는 곳까지 최대한 깊이 들어갔다가 더 갈 곳이 없으면 직전 갈림길로 되돌아와 다른 길을 탐색하는 방법. 되돌아오는(backtrack) 동작이 핵심이라, 재귀

• PS 2018-05-05

  그리디 (Greedy) 정리

  Greedy 1. 앞에 놓인 선택지들 중 바로 보이는 것을 딱! 고르면 그게 항상 최선이 될 수 있도록 문제의 구성요소를 변형 및 접근하여 해결하는 방법 - 선택한것은 순간적으로는 최적해가 될 수 있지만, 그 선택들이 모여 전체적으로