알고리즘 – 이분 그래프
이분 그래프 (Bipartite Graph) 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로인접하지 않도록 분할할 수 있는 그래프 인접한 정점끼리 서로 다른 […]
Category: Algorithm
알고리즘 설계
알고리즘 – quickSelect와 MoM
quickSelect는 리스트에서 k번째로 작은 원소를 반환하는 로직(k-selection) 중 하나이다.k-selection 중에서는 가장 빠르다고 알려져있다. 다음은 quickSelect 알고리즘이다. (quickSort와 유사함) 1. p(pivot)를 고른다. (배열의 […]
알고리즘 – 분할 정복과 마스터 정리
분할 정복은 문제를 a개의 더 작은 부분 문제로 나누고(divide), 각각을 재귀적으로 해결한 다음(conquer), a개의 부분 해를 합하여(merge) 전체 문제의 하나의 해로 만들어 […]
알고리즘 – 구간 그래프
구간 그래프 구간을 정점, 구간이 겹치는 것을 엣지로 표현한 그래프 구간 그래프 관련 용어 독립 집합: 그래프에서 서로 인접하지 않은 정점들의 집합 […]
알고리즘 – Proof Techiques
알고리즘의 증명 방법은 크게 귀류법과 귀납법이 존재한다. 귀류법은 정답이 아니라고 가정하고 모순에 의해 증명하는 방법이다.지금부터 귀류법 증명에 대한 예시 3가지를 보이겠다. 1. […]
알고리즘 – 카탈랑 수로 알아보는 DP
동적계획법(DP)은 ‘컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 […]
알고리즘 – 합병 정렬 알아보기
항상 시간복잡도가 O(nlogn)을 만족하는 ‘합병 정렬’을 알아 봅시다! 합병 정렬은 다음의 단계들로 이루어 집니다. 1. 분할(Divide): 입력 배열을 2개의 부분 배열로 분할한다.2. 정복(Conquer): […]
알고리즘 – 퀵 정렬 알아보기
평균 시간복잡도가 O(nlogn)을 자랑하는 ‘퀵 정렬’을 알아 봅시다! 퀵 정렬의 아이디어 자체는 간단합니다. 아래 세 가지만 기억하면 됩니다! 리스트에서 원소 하나를 고른다. […]
알고리즘 – 최대 부분 배열 합의 여러가지 풀이
최대 부분 배열 합을 구하는 방법은 여러 가지입니다 1. 시간복잡도가 O(n^3)인 방법2. 시간복잡도가 O(n^2)인 방법3. 시간복잡도가 O(nlogn)인 방법4. 시간복잡도가 O(n)인 방법 위 네 […]
알고리즘 – 시간복잡도 개념
시간복잡도(Time Complexity) : 입력의 개수가 n개일 때 알고리즘의 실행 시간을 n에 대한 함수로 표현한 것, 보통 최악의 경우(가장 연산을 많이 해야 되는 […]