알고리즘 – Proof Techiques
알고리즘의 증명 방법은 크게 귀류법과 귀납법이 존재한다. 귀류법은 정답이 아니라고 가정하고 모순에 의해 증명하는 방법이다.지금부터 귀류법 증명에 대한 예시 3가지를 보이겠다. 1. […]
Tag: 알고리즘
Data Structure – Topological sorting (위상 정렬)
위상 정렬: 순서가 정해져있는 작업을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용되는 알고리즘 ex) 1->4->0->2->3->5 방향 그래프를 대상으로 위상 정렬을 […]
알고리즘 – 카탈랑 수로 알아보는 DP
동적계획법(DP)은 ‘컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 […]
문제풀이 – 하세 다이어그램 (C)
문제 소개 하세 도형(Hasse圖形, 영어: Hasse diagram)은 부분 순서 집합의 원소들을 표현하기 위해 고안된 표기법으로, 각 원소의 순서 관계를 그래프로 표현한 것이다. 코드 및 해설 주요 […]
Data Structure – AVL Tree (Insert Function)
AVL트리모든 노드에 대해서 왼쪽 부분 트리와 오른쪽 부분 트리의 높이 차가 1 이하인 이진 탐색 트리 트리의 균형 상태: 균형 인수(왼쪽 부분 […]
Data Structure – Binary Search Tree (Algorithm)
이진탐색트리왼쪽 부분트리에 있는 노드 값은 모두 루트의 값보다 작다.오른쪽 부분트리에 있는 노드 값은 모두 루트의 값보다 크다.왼쪽 부분트리와 오른쪽 부분트리는 이진탐색트리이다. 연산 […]
문제풀이 – 버스 탑승 스케줄링 (C)
문제 소개 코드 및 해설 문제 풀이 Tip: m(버스 수)을 가지고 t(최대 대기 시간)를 구하는 문제인데, t를 가지고 m을 구하는 것이 더 […]
알고리즘 – 퀵 정렬 알아보기
평균 시간복잡도가 O(nlogn)을 자랑하는 ‘퀵 정렬’을 알아 봅시다! 퀵 정렬의 아이디어 자체는 간단합니다. 아래 세 가지만 기억하면 됩니다! 리스트에서 원소 하나를 고른다. […]
알고리즘 – 최대 부분 배열 합의 여러가지 풀이
최대 부분 배열 합을 구하는 방법은 여러 가지입니다 1. 시간복잡도가 O(n^3)인 방법2. 시간복잡도가 O(n^2)인 방법3. 시간복잡도가 O(nlogn)인 방법4. 시간복잡도가 O(n)인 방법 위 네 […]
알고리즘 – 시간복잡도 개념
시간복잡도(Time Complexity) : 입력의 개수가 n개일 때 알고리즘의 실행 시간을 n에 대한 함수로 표현한 것, 보통 최악의 경우(가장 연산을 많이 해야 되는 […]