레야몬

1. 정당성 증명 알고리즘에서 선택한 최댓값보다 더 최댓값이 존재한다고 가정하자(귀류법). 이 때 만약 이 값이 최댓값이라면 알고리즘이 이 최댓값을 선택하지 않았을 수가 없었음을 증명하면 됨. 2. 시간 복잡도 분석 두 가지로 나눔과 동시 나눈 것을 선형 탐색하므로 O(nlgn)이다. https://www.acmicpc.net/blog/view/12 (이 글에 더 자세하게 나와있다.) 히스토그램에서 가장 큰 직사각형 6549번 문제: 히스토그램에서 가장 큰 직사각형 히스토그램에서 가장 큰 직사각형을 찾는 방법을 알아보겠습니다. 문제 히스토그램에서 모든 막대의 너비는 1이고, 높이는 hi일 때, 가장 넓이가 www.acmicpc.net - *

1. 예제: 병합 정렬과 퀵 정렬 병합 정렬은 둘로 나누는 과정에서 O(1)의 시간 복잡도가, 분할 한 수열을 다시 합 칠 때 O(n)의 고정된 계산을 하므로 시간 복잡도는 O(nlgn)이다. 퀵 정렬은 partition을 기준으로 나누는 과정에서 partition이 가운데가 된다는 것을 가정하면 O(nlgn)인 것이 알려져이다. 책에는 없지만 고정적으로 시간 복잡도가 O(nlgnl)인 병합 정렬을 사용하는 것이 조금 더 안정적이지 않을까 싶다. 2. 예제: 카라츠바의 빠른 곱셈 알고리즘 기본적인 사칙연산으로 곱셈을 구현할 경우 \(O(n^{2})\)의 시간 복잡도를 나타내게 된다. 그러나 이를 분할 정복을 이용한 카라츠바 알고리즘을 사용하면 \(O(n^{lg3})\)으로 계산을 줄일 수 있다. 3. 문..

1. 분할 정복 분할 정복(Divide & Conquer)은 주어진 문제를 둘 이상이 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용하여 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산해 내는 것이다. 분할 정복이 일반적인 재귀 호출과 다른 점은 문제를 한 조각과 나머지 전체로 나누는 대신 거의 같은 크기의 부분 문제로 나누는 것이다. 분할 정복을 사용하는 알고리즘은 대게 3개의 구성 요소를 가지고 있다. 문제를 더 작은 문제로 분할하는 과정(divide) 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정(merge) 더이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제(base case) 2. 시간 복잡도 분석 분할 정복은 동일한 크기의 2개의 묶음으로 ..

1. 최적화 문제 최적화 문제(Optimization problem): 문제의 답이 하나가 아니라 여러 개이고, 그중에서 어떤 기준에 따라 가장 '좋은'답을 찾아내는 문제들을 통칭해 최적화 문제라고 한다. ex) n개의 원소중 r개를 골라서 무게의 합을 최대화 하는 문제 etc 2. 여행하는 외판원 문제 그래프에서 모든 점을 다 거쳐가는 사이클을 구성하는 거리가 최소가 되도록 하는 사이클을 구하기 정점이 9개의 경우 9!=362,880으로 시간 안에 해결할 수 있으므로 재귀 호출을 통해 해결할 수 있다. 3. 문제: 시계 맞추기 (문제 ID: CLOCKSYNC, 난이도: 중) 열여섯 개의 시계가 있다. 이 시계들은 모두 3의 배수 시를 가리키고 있는데 모두 12시로 맞추고자 한다. 9개의 스위치가 있고 ..

1. 재귀 호출(recursion) 재귀 합수(recursive function)은 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수이다. ex) 1부터 n까지의 합 = n + 1부터 n-1까지의 합으로 나타낼 수 있고 1부터 n까지의 합을 구하는 함수만 완성하면 이를 구할 수 있다. 모든 재귀 함수는 '더이상 쪼개지지 않는' 최소한의 작업에 도달했을 때 답을 곧장 반환하는 조건문을 포함해야 하며 이를 재귀 호출의 기저사례(base case)라고 한다. 기저 사례는 존재하는 모든 입력이 항상 기저 사례의 답을 이용해야 한다. 2. 예제: 중첩 반복문 대체하기 집합에서 n개의 원소 중 k개를 고르는 모든 경우를 출력하는 코드를 ..

1. 알고리즘의 정당성 증명 1. 알고리즘의 증명을 공부해야 하는 가장 큰 이유는 많은 경우 증명이 알고리즘을 유도하는 데 결정적인 통찰을 담고 있으며 결정적으로 필요한 깨달음이 증명에 담겨 있는 경우가 많기 때문이다. 2. 알고리즘의 증명을 공부하면 자신이 설계한 알고리즘의 정당성을 더 쉽게 증명할 수 있다. 1. 수학적 귀납법(mathematical induction) 단계 나누기: 증명하고 싶은 사실을 여러 단계로 나눈다. 첫 단계 증명: 첫 단계에서 증명하고 싶은 내용이 성립함을 보인다. 귀납 증명: 한 단계에서 증명하고 싶은 내용이 성립한다면, 다음 단계에서도 성립함을 보인다. 2. 반복문 불변식(loop invariant) 반복문 진입시에 불변식이 성립함을 보인다. 반복문 내용이 불변식을 깨뜨..

1. 주먹구구 법칙 입력의 크기를 시간 복잡도에 대입해서 얻은 반복문 수행 횟수에 대해, 1초당 반복문 수행 횟수가 1억(\(10^{8})\)을 넘어가면 시간 제한을 초과할 가능성이 크다. 그래도 예측한 수행 횟수가 기준의 10%이하인 경우와 기준의 10배를 넘는 경우에만 이 법칙을 적용하는 것이 좋다. (어림짐작이기 때문이다.) 2. 주먹구구 법칙은 주먹구구일 뿐이다. 시간 복잡도가 프로그램의 실제 수행 속도를 반영하지 못하는 경우: O표기법으로 시간 복잡도를 표현할 때 상수나 최고차항 이외의 항들을 모두 지워버리므로 실제 프로그램이 수행하는 반복문의 수는 이 계산의 다섯 배일 수도 있고, 10분의 1배일 수도 있다. 반복문의 내부가 복잡한 경우: 실수 계산이나 파일 입출력과 같은 함수들이 많이 있는 ..

알고리즘의 시간 복잡도 분석 1. 선형 시간 알고리즘: O(N) 대부분의 경우 최적의 알고리즘임. 2. 선형 이하 시간 알고리즘 데이터를 모두 다 확인하지 않아도 될 경우를 포함한다. ex) 이진 탐색 O(lgN) 3. 지수 시간 알고리즘 다항 시간 알고리즘: 반복문의 수행 횟수를 다항식으로 표현할 수 있는 알고리즘. 대부분의 경우 이에 속함 지수 시간 알고리즘: 반복문의 수행 횟수에 지수 함수가 포함되어 있는 경우로 이는 개수가 커짐에 따라 계신량이 늘어나는 속도가 매우 빠르므로 효율적으로 해결할 수 있는 문제와 그렇지 않은 문제로 다항 시간 알고리즘과 경계를 이루고 있다. 소인수 분해의 수행 시간: 소인수 분해의 수행 시간은 O(N)이라고 생각하기 쉽지만 숫자가 커질 수록 저장하는 비트의 수가 하나씩..