프로그래밍나무

LIS 개념 증가하는 부분 수열에 대해서 먼저 설명하자면 한 배열에서 어떤 원소들을 지웠을 때 나머지 모든 원소들이 증가하는 형태를 나타내는 것을 말합니다. [1, 3, 2, 4]라는 배열이 있다고 가정하겠습니다. 그럼 증가하는 부분 수열은 [1, 3], [1, 3, 4], [1, 2, 4] 등이 나올 수 있습니다. 이런 부분 수열 중에서 가장 긴 수열을 LIS라고 합니다. LIS 알고리즘 LIS를 구현하는 알고리즘은 다음과 같습니다. 다른 모든 원소들을 비교하는 O(N^2) 알고리즘 이진 탐색으로 원소들을 비교하는 O(NlogN) 알고리즘 N^2 알고리즘 이 알고리즘은 각 원소마다 해당 원소를 마지막 원소로 가진 LIS 길이를 구합니다. 이 길이중에서 가장 긴 길이가 전체 LIS길이가 됩니다. 각 원소..

유클리드 호제법(최대공약수) GCD(A, B)=GCD(B, A% B)이다. 계속하다가 A%B가 0이 될 때 B가 원래 A, B의 최대 공약수가 된다. EX) (6,4)->(4,2)->(2,0) 6,4의 최대 공약수는 2 최소공배수는 A*B/GCD(A, B)이다. 소수 구하기 제일 좋은 방법은 에라토스테네스의 체이다. 시간 복잡도는 N개의 수에 대한 소수를 구할 때 NlglgN이다. 2에서부터 N까지 수에서 제일 작은 수로 나누어지는 수를 삭제한다. 그럼 처음에는 4, 6, 8... 이 없어진다. 다음에는 제일 작은 수인 3으로 나누어지는 수를 삭제한다. 삭제되는 것을 잘 보다 보면 2를 삭제할 때는 삭제되는 처음 수가 2*2이고 3을 삭제할 때는 삭제되는 처음 수가 3*3인 것처럼 처음 삭제되는 수는 i..

정의 인접 행렬은 그래프의 연결 관계를 이차원 배열로 나타내는 방식 인접 리스트는 각각의 정점에 인접한 정점들을 리스트로 표현한 방식 이런 그래프가 있을 때 각각의 방식으로 표현한다면 1 2 3 4 1 0 1 1 1 2 1 0 0 1 3 1 0 0 0 4 1 1 0 0 인접 행렬은 이런 방식으로 표현되고 1: 2, 3, 4 2: 1, 4 3: 1 4: 1, 2 인접 리스트는 이런 방식으로 표현된다. 장단점 인접 행렬 그래프에 간선이 많은 밀집 그래프의 경우 유리하다. 장점 두 정점을 연결하는 간선의 존재여부를 O(1)안에 알 수 있다. 정점의 차수를 O(N) 안에 알 수 있다. 단점 인접 행렬 전체를 검사할때 O(n^2)가 필요하다. 인접 리스트 그래프에 간선이 적은 희소그래프의 경우 유리하다 장점 인접..

힙 정렬 알고리즘 개념 과정 설명 오름차순을 구성하기 위해서는 배열을 최대힙으로 구성 최대 힙의 가장 첫번째 원소(배열에서 가장 큰 원소)를 하나씩 빼면서 정렬 힙의 원소가 하나 남을 때까지 반복 과정 상세 설명 정렬할 요소들을 가지고 배열에 하나씩 요소들을 넣으면서 최대 힙 구성 정렬할 요소 (4, 3, 2, 5, 1, 6) 맨 처음 원소 삽입 과정을 따로 처리할 과정이 없으므로 생략 인덱스 1 2 3 4 5 6 4 3 2 3 삽입 인덱스 2의 부모인 1과 비교, 인덱스 1의 원소가 더 크므로 pass 2 삽입시에도 동일 인덱스 1 2 3 4 5 6 4 3 2 5 ↓ 인덱스 1 2 3 4 5 6 4 5 2 3 ↓ 인덱스 1 2 3 4 5 6 5 4 2 3 5 삽입 인덱스 4의 부모인 인덱스 2의 원소와..

합병 정렬 알고리즘 개념 과정 설명 배열을 길이가 0 또는 1이 될 때까지 두 개의 배열로 나눈다. 각 나눠진 두개의 배열을 정렬하면서 합병 하나의 배열이 될 때까지 계속 합병 과정 상세 설명 정렬되지 않은 배열을 다른 배열에 정렬하면서 합병 4 3 7 1 5 6 2 3 4 1 7 5 6 2 두 개의 원소를 하나의 배열로 묶으면서 정렬한다. ex) (4,3)->(3,4) 3 4 1 7 5 6 2 1 3 4 7 2 5 6 두 개의 원소로 이루어진 배열 두 개를 하나의 배열로 묶으면서 정렬한다. ex) (3,4,1,7)->(1,3,4,7) 1 3 4 7 2 5 6 1 2 3 4 5 6 7 하나의 배열로 묶어서 정리 퀵 정렬 알고리즘 시간복잡도 Best: nlogn Avg: nlogn Worst: nlogn ..

퀵 정렬 알고리즘 개념 과정 설명 배열의 한 원소를 피벗으로 선택 피벗을 기준으로 왼쪽에는 피벗보다 작은 원소를 오른쪽에는 피벗보다 큰 원소를 배치 피벗을 제외한 양쪽의 두 배열을 각각 정렬 배열이 더 이상 나누어지지 않을 때까지 실행 과정 상세 설명 피벗을 제외한 배열의 왼쪽과 오른쪽을 같이 검사한다. 배열의 왼쪽에는 피벗보다 작은 수가 있어야 하므로 왼쪽에서 검사할 때는 피벗보다 큰 수를 찾으면 멈추고 배열의 오른쪽에는 피벗보다 큰 수가 있어야 하므로 오른쪽에서 검사할 때는 피벗보다 작은 수를 찾으면 멈춘다. 양쪽의 검사가 멈추게 되면 그 두 수의 위치를 바꾼다. 4 3 7 1 5 6 2 4를 피벗으로 설정한다. 4 3 7 1 5 6 2 3과 2를 검사한다. 3

KMP(Knuth–Morris–Pratt) 알고리즘은 문자열에서 특정 패턴을 찾아내는 문자열 검색 알고리즘 중 하나입니다. 이 알고리즘은 패턴과 문자열을 비교해나가다가 틀렸을 때 틀렸다는 사실보다는 틀리기 전에 일치하는 부분이 있었다는 사실에 집중하는 것이 특징입니다. 그러기 위해서 패턴을 통해서 pi배열을 만들고 패턴과 문자열을 비교해나가면서 pi배열을 통해 다시 비교하는 횟수를 줄이는 과정을 거치게 됩니다. 이제 과정을 하나씩 설명해 보도록 하겠습니다. 이 설명은 백준1786번 : 찾기 문제를 풀면서 작성하였습니다. https://www.acmicpc.net/problem/1786 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가..