완전탐색
완전탐색이란문제 유형복잡도 파악 완전탐색이란모든 경우를 탐색하는 방법.부분점수를 얻기 좋으나 시간 복잡도가 일반적으로 높은 편. 완전탐색 문제를 접근할 땐 고를 수 있는 값의 종류 파악 중복을 허용하는지 순서를 중요시 하는지 위 세가지를 파악해자. 문제 유형완전탐색 문제는 크게 4가지로 나눌 수 있다. N개에서 중복 허용해서 M개를 순서 있게 나열하기
Category: Theory
19. 그래프 깊이우선탐색(DFS)
깊이우선탐색(DFS)현재 방문중인 노드와 연결된 이웃 노드 중 아직 방문하지 않은 노드 있으면, 그 노드를 다음에 방문.재귀함수로 작성, 마치 트리의 preorder방식과 비슷. psuedo code 12345678910DFS(v): mark v as visited node pre[v] = curr_time #pre리스트는 해당 노드에 첫 방
16. Backtracking
Backtracking답이 x1, x2, x3… 이런 형식으로 도출되는 문제에서, 유효한 답을 모두 찾는 경우 사용되는 알고리즘 기법 x1부터 차례대로 결정하면서 만약 어느 순간 조건에 맞는 답을 도출 못하는 상황에 마주하면,그 전 단계로 돌아가 다른 선택지로 다시 답을 찾아가는 방법이다. 이 기법은 굳이 더 알아보지 않아도 되는 경우를 확인하지 않도록 설
14. 그리디 알고리즘
그리디 알고리즘현재 상태에서 가장 좋은 선택을 반복해서 해를 구성하는 알고리즘 문제는 이 그리디 알고리즘을 통해 얻은 해가 진짜 최선의 선택으로 얻은 해이냐는 것인데,이를 증명하기 위해서는 귀류법을 통해 증명해봐야 한다. 즉 우리가 찾은 해가 해가 아님을 가정으로 하여 다른 해를 가정하여,그 해를 논리적으로 추론하여 모순을 찾아내면, 우리가 찾은 그리디는
11. 다이나믹 프로그래밍-1
다이나믹 프로그래밍문제를 여러 작은 문제로 나누어 재귀적으로 해결하는 방법. divde and conquer와 차이점은? 큰 문제의 답이 작은 문제의 답들의 식으로 표현되지만,그 답을 얻을 때 재귀적으로 얻는게 아니라 미리 계산하여 기록해 놓은 값을 재귀 식에 따라 계산! 즉 원래 문제의 답을 작은 문제들의 재귀 식으로 표현하는 것이 핵심!!!!점화
10. Merge 정렬 알고리즘
Merge 정렬 알고리즘퀵 소트가 피벗을 어떻게 선택하냐에 따라 속도가 달라지는 단점을 상쇄하는 알고리즘 배열은 반으로 나눠 재귀적으로 정렬하고 정렬된 두 배열을 원소 하나씩 비교해서 병합하는 방식.주어진 배열만큼 새로운 배열을 사용해야 하기 때문에 not in-place 알고리즘이다. 먼저 중간 인덱스를 찾는다. 중간 인덱스를 기준으로 나눠서 두 배
9. Quick 정렬 알고리즘
퀵 정렬 알고리즘이론적으로는 빠르지 않지만(O(n^2)), 실제로는 가장 빠른 정렬 알고리즘quick selection과 비슷한 원리임. not in-place quick sort algorithm 어떤 list A를 퀵 정렬 하려면… 피벗을 A[0]으로 잡고, S,M,L 세가지 배열을 선언함 A에 있는 모든 수들이 피벗보다 크면 L, 작으면 S, 같으
8. 기본 정렬 알고리즘
파이썬에서 제공하는 정렬 123A = [3,1,2,-5]A.sort() #[-5,1,2,3]A.sort(reverse = True) #[3,2,1,-5] 정렬 알고리즘의 두 가지 특성 stable vs unstable만약 [2,5,2,7]을 오름차 정렬했을 때 ,[2,2,5,7]로 정렬이 될 텐데, 이 두 개의 2가 입력 순으로 정렬되면 stable하
7.피보나치
피보나치 수 피보나치 수열이란 F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)로 정의되는 수열! 구현 방법 피보나치수 정의를 그대로 재귀함수로 구현 간단하지만..O(g^n) 지수 시간이 걸림..(g는 황금비율 1.1618…) 이차원 배열을 재귀적으로 곱하기 (1 1)(F(n-1)) (1 0
6.Median of Medians 알고리즘
MoM(Median of Medians) 알고리즘퀵셀렉트는 세가지 영역으로 나누는데, 피벗보다 큰 쪽으로 너무 몰리면 수행시간이 길어졌었다. MoM 알고리즘은 피벗을 적절하게 고르는 알고리즘이다.피벗보다 작은 값의 집합 A, 피벗보다 큰 집합 B 둘 다 n/c보다 작도록 피벗을 설정하는 것이다!! 이런 과정으로 피벗을 고른다고 하면, 재귀 과정에서
5.독특한탐색
특수한 선택 문제다음과 같은 요구 조건을 가지느 문제들은 선택(Selection)문제라고 보면 된다. 입력 : n개의 값과 k(1<=k<=n) 값 출력 : k번째로 작은 입력 값 목표 : 비교 횟수 최소화 상한(upper bound) : 어떤 결과를 찾아내는데 항상 임의 횟수의 연산이면 무조건 찾아낼 수 있다.하한(lower
4.일반적인 탐색
일반적인 선택 문제n개의 값중 k 번째 작은 수 찾기 - QuickSelction 배열 중 임의의 수 p를 고른다.(이 p는 pivot) p보다 작은 값을 A에 따로 모으고, p보다 큰 값을 B에 따로 모으고, p와 같은 값을 M에 따로 모은다. 만약 A의 원소가 k보다 작으면 A의 k번째 작은 값이 전체 데이터의 k번째 작은 값이다. 이제 A에서 k보다
3.재귀 알고리즘
재귀 알고리즘재귀 알고리즘 = 알고리즘 내부에서 한번 이상 자신의 함수를 호출sum(n) = 1+2+..+nsum(n) = sum(n-1)+n 123def sum(n): if n==1 : return 1 return sum(n-1) + n 수행시간T(n) = sum(n)의 수행시간이라 할 때T(n) =
2.분할정복법
분할정복법큰 문제를 작은 문제로 분할해 재귀적으로 해결 a와 n 입력받아 a^n 값 구하는 power1(a,n)을 분할 정복법으로 해보자. power1(a, n) = power1(a, n-1)*a 이다. 123def power1(a, n): if n==1: return a return a*power1(a, n-1) power1의 걸리
1.이진탐색
이진탐색오름차순으로 정렬된 n개의 숫자가 저장된 배열 A에서 어떤 값 x가 배열에 있는지 없는지 O(log n) 비교에 알 수 있는 탐색법. 현재 탐색 범위가 A[i]…A[j]라면 가운데값(A[(i+j)/2]) 비교에 알 수 있는 탐색법. 한 번의 비교로 탐색 범위가 반씩 줄어들어 (log n +1)번 이하의 비교로 x 존재 여부 판별. 주어진