6.Median of Medians 알고리즘
MoM(Median of Medians) 알고리즘퀵셀렉트는 세가지 영역으로 나누는데, 피벗보다 큰 쪽으로 너무 몰리면 수행시간이 길어졌었다. MoM 알고리즘은 피벗을 적절하게 고르는 알고리즘이다.피벗보다 작은 값의 집합 A, 피벗보다 큰 집합 B 둘 다 n/c보다 작도록 피벗을 설정하는 것이다!! 이런 과정으로 피벗을 고른다고 하면, 재귀 과정에서
Archive: 2021
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 존재 여부 판별. 주어진
1. 연결리스트
a. 연결리스트 기본 개념연결리스트는 노드가 링크에 의해 기차처럼 연결된 순차 자료구조. 노드는 실제 값을 가지고 있는 data 정보와 인접 노드로 향하는 link 정보로 구성된 클래스로 구현한다. 다른 값에 접근하려면 링크에 따라 원하는 노드의 데이터에 접근한다. 다만, 배열처럼 index로 접근할 수 없다. 어떤 값을 찾으려면 처음부터 순차적으로 찾아야