전체 글171 210707 그리디 알고리즘(Greedy, 탐욕) 동적 프로그래밍(DP) 을 사용할 때 너무 많은 작업을 하는 경우가 발생하기에 보완하는 목적으로 생김 차이점 : 그리디 알고리즘은 미래를 생각하지 않고 각 단계에서 최선의 선택을 하는 방법 활동 선택 문제 (Activity Selection Problem) 활동 선택 문제란, 한번에 하나의 활동만 처리할 수 있는 하나의 방에서 주어진 활동들에서 최대한 많은 활동을 처리할 수 있는 스케줄을 짜는 문제입니다. 문제를 해결하는 아이디어로는 보통 평범하게는 활동시간이 짧은 순으로 정렬하여 짧은 것부터 선택하는 등의 방법들을 생각할 수 있지만, 최적의 방법은 끝나는 시간순으로 선택하면 됩니다. 허프만 부호화 (Huffman Coding) 문자의 빈도나 확률 정보 등을 이용하여 통계적으로 압축하는 방법 압축할 문자.. 미가공 필기(알고리즘) 2021. 7. 8. 210706 동적 계획법(DP) 2- LCS ,OBST LCS ( Longest Common Subsequence) - 최장 공통 부분수열, 문자열 를 DP로 해결 LCS의 예시) 목표: 부분수열이기에 중간에 맞지 않다면 문자 사이를 건너뛰어 공통되면서 가장 긴 문자열을 찾는 것 해결법 : 를 다시 정리하면 문자열 X, 문자열 Y의 한 글자씩 비교 두 문자가 같다면 LCS[i - 1][ j - 1 ] +1 두 문자가 다르다면 LCS[i - 1][ j ] 와 LCS[ i ][ j - 1 ] 중 큰 값 표시 1 ~ 3 번 과정 반복 앞서 예로 들었던 malestrom 과 becalm 으로 과정을 보이면 한 단어를 기준으로 잡고 한 글자씩 잡고 위의 점화식대로 테이블을 채워나간다 예를 들어 b를 기준으로 잡고 m,a,l,e....m 까지 검사 이 경우 문자가 같은.. 미가공 필기(알고리즘) 2021. 7. 7. 210705 동적 계획법(Dynamic Programming, DP) 동적 계획법(Dynamic Programming, DP) vs 분할 정복법(Divide and Conquer) 문제를 분할하여 작은 문제로 만들어 해결한 후 합쳐서 문제 해결하는 것은 동일 동적 계획법은 서브 문제들 간의 관계가 존재하여 overlapping (작은 문제들이 중복되는 일) 발생 => 작은 문제들의 결과 저장하여 다시 계산하는 일 생략 서브 문제들간의 overlapping 없음 최적 부분구조(Optimal Substructure) 전체 문제가 최적(optimal)구조가 되려면 그 서브 문제들도 최적화 된 솔루션으로 해결가능 해야 함. => 문제를 해결할 때 서브 문제들을 해결하여 그 결과들을 이용하여 최종적인 답 구함 이러한 구조를 가진 문제로 대표적인 예가 최단 경로 문제 피보나치 210.. 미가공 필기(알고리즘) 2021. 7. 6. 210701 레드 블랙 트리(Red-Black Tree) 레드 블랙 트리(Red-Black Tree) 모든 노드는 블랙 노드이거나 레드노드이다 루트는 블랙노드이다 모든 리프 노드는 블랙노드이다 (*리프 노드 : child가 없는 노드) 레드 노드의 child들은 모두 블랙 노드이다 임의의 노드에 대해 그 노드부터 후손 리프 노드까지의 경로에는 같은 수의 블랙노드가 있다 균형 이진 탐색 트리 => 탐색시간 O(log n) 키의 개수 n, 리프의 개수 L 이라고 하였을 때, 전체 노드의 수 = n + L = 전체 edge 수 +1 = 2n +1 L= n+1 레드 블랙 트리 평균 높이 : 원래 트리의 높이를 h, 새로운 트리의 높이를 h' 라 하면 h' >= h/2 검색 연산들은 이진검색 트리와 동일. 삽입, 삭제는 Rotation을 이용하여 수행하다 회전(Rota.. 미가공 필기(알고리즘) 2021. 7. 5. 210630 해싱(Hashing ) 해시 테이블(Hash Table) 찾고자 하는 원소의 키값을 해시함수를 통해 해시 값을 계산하여 그 원소가 저장된 장소를 찾아내는 방법 해시 함수(Hash Function) 모든 가능한 키 값의 집합이 U 라 하고 해시 슬롯의 갯수가 m인 경우 충돌(Collision) : 두 키값의 해시 값이 같을 때 => 충돌 발생시 해결 방법이 효율성을 좌우함 충돌 해결법 연결리스트를 이용한 방법 (Chaining) 오픈 어드레싱(Open addressing) 연결리스트를 이용한 방법 (Chaining) 평균적인 경우 : Simple uniform hashing을 가정시 (각각의 키값이 특정 슬롯에 할당될 확률이 다른 키의 할당에 상관없이 동일하다는 가정) n을 키값의 갯수라고 하고 m을 슬롯의 갯수라고 할 때, 각.. 미가공 필기(알고리즘) 2021. 7. 2. 210629 기수 정렬(Radix Sort) & 카운팅 정렬(Counting Sort) 비교 기반 정렬 알고리즘의 최대 효율 결국엔 숫자열의 모든 가능한 수열 중 하나를 찾아 내는 문제 모든 가능한 순열의 수 : n! 이를 Decistion Tree 를 통해 나타내면 이러한 과정을 통해 비교 기반 정렬 알고리즘의 최대 효율이 O(nlog n) 임을 알 수 있다 그렇다면 비료를 사용하지 않는 정렬 알고리즘은 어떤가? 제한적이지만 O(n)으로 수행가능한 방법들이 존재한다 카운팅 정렬(Counting Sort) 가장 큰 데이터에 따라 효율이 좌우됨 특정 데이터의 개수들을 저장해두고 순서대로 저장된 횟수대로 뱉어내어 정렬하는 방법 위와 같은 방법인데 파란색으로 표시한 1000 이 들어온 경우를 보면 왜 가장 큰 데이터에 효율이 좌우되는지 알 것이다. 가장 큰 데이터가 1000이기에 n이 8 밖에 .. 미가공 필기(알고리즘) 2021. 6. 30. 210629 힙 정렬(heap sort) 우선 힙(heap) 이라는 구조에 대해서 먼저 이야기하면, 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안됨 Complete(or left - complete) binary tree 로 표현 가능 * 가장 낮은 레벨 제외하고 full, 가장 낮은 레벨은 왼쪽부터 채워진 트리 * 우선 순위 큐(Priority Queue)를 구현할 수 있는 자료구조 A가 B의 부모 노드이면, A의 키(Key) 값과 B의 키(Key) 값 사이에는 대소 관계 성립 즉 루트에서 임의의 리프노드( 자식이 없는 노드) 까지 경로는 항상 정렬되어 있다 이진트리는 일반적으로 포인터 사용하여 저장 but left - complete라 배열 사용 가능 두가지 종류 부모 노드의 키 값이 자식 노드의 것 보다 항상 크면 = 최대 힙.. 미가공 필기(알고리즘) 2021. 6. 30. 210628 합병 정렬(merge sort) & 퀵 정렬(quick sort) 합병 정렬(merge sort) : 안정적, 분할 정복 알고리즘(문제를 작은 문제로 분리하고 각각 해결하여 합쳐서 문제를 해결하는 방법) 중 하나 리스트의 길이 0 또는 1이면 정렬된 것으로 취급, 아닌 경우는 비슷한 크기로 잘라 두 개의 리스트로 만듬 각 부분 리스트 재귀적으로 합병 정렬을 통해 정렬함 두 부분 리스트 합병 반복함 단: 만약 배열로 구성한다면 임시 배열 필요 , 제자리 정렬 아님 데이터의 크기가 큰 경우에는 이동 횟수가 많아 매우 비효율적 장 : 안정적인 정렬 방법, 데이터의 분포에 영향 덜 받음, 입력 데이터에 영향 덜 받음 레코드를 연결 리스트로 구성하면, 링크 인덱스만 바꾸면 되기에 데이터의 이동은 무시할 수 있을 정도로 작아짐, 제자리정렬로 구현 가능 큰 데이터 다를 때 연결 리.. 미가공 필기(알고리즘) 2021. 6. 28. 210628 버블 정렬 (bubble sort) & 삽입 정렬 (insertion sort) 버블 정렬(bubble sort) : 인접한 두 원소를 비교하여 정렬하는 알고리즘 n 크기의 배열을 정렬한다고 가정하면 1번째 원소와 2번째 원소를 비교 후 정렬 2번째 원소와 3번째 원소를 비교후 정렬... 반복 n-1번째 원소와 n번째 원소를 비교후 정렬 이것이 한 사이클, 이 사이클을 반복하는데 맨 마지막의 원소는 제외한 범위에서 반복한다 why? 한 사이클을 수행하면 가장 큰 자료가 맨 뒤로 이동하기 때문이다 장 : 구현이 매우 간단하다. 단: 하나의 원소가 가장 왼쪽에서 오른쪽으로 이동하기 위해서는 배열의 모든 다른 요소들과 교환되어야 함, 특정 원소가 최종적인 위치에 이미 있는 경우에도 이동되는 경우 발생함 시간복잡도 비교 횟수 : n-1, n-2,.... 1번 (Best, Worst 일 때 .. 미가공 필기(알고리즘) 2021. 6. 28. 210628 선택 정렬(selection sort) 선택 정렬 (selection sort) : 제자리 정렬 알고리즘 중 하나 입력 배열 외의 다른 추가 메모리 필요 없음 주어진 배열에서 최솟값 찾음 그 값을 맨 앞의 값과 교환함 맨 처음 위치를 제외한 배열 범위에서 1~2번 반복 즉 1,2 번이 하나의 사이클로 한번 할때 마다 배열 내의 가장 작은 원소를 맨 앞으로 땡겨오는 작업을 n번하여 정렬하는 방법이다. 장 : 자료의 이동 횟수가 예상 가능함 단 : 불안정함, 값이 같은 레코드가 있는 경우에 상대적 위치가 변경될 수 있음 시간복잡도 배열의 크기 n 이라 하였을 때 비교 횟수 : n-1, n-2, n-1, .... 2, 1 번 교환 횟수 : 한 번 교환할 떄( swap 함수) 3번 => 최대 3(n-1) 번 그러므로 Best (모두 정렬되어 있는 상.. 미가공 필기(알고리즘) 2021. 6. 28. 210625 시간복잡도와 공간복잡도 성능 평가 성능 분석(performance analysis) - 실행하는 환경에 영향 안 받음 (이론적인 이야기) 성능 측정(performance measurement) - 실행하는 환경에 영향 받음 공간 복잡도(space complexity) : 프로그램 실행하여 완료하는데 까지 필요한 메모리 공간의 양 고정 공간(fixed space) : 프로그램의 입출력에 상관없는 메모리 공간 , 알고리즘과 무관한 공간 ex) 코드 저장 공간단순 변수, 고정된 크기의 배열, 상수 등 가변 공간(variable space) : 프로그램의 입출력에 상관있는 메모리 공간, 알고리즘과 상관있음 ex) 동적 배열 등 총 필요 저장 공간 = 고정공간 + 가변 공간 // S(P) = c + Sp(n) 고정 공간은 상수이므로 공.. 미가공 필기(알고리즘) 2021. 6. 25. 210624 그래프(Graph) 그래프(Graph) : 연결되어 있는 개체간의 관계를 표현하는 자료 구조 트리도 그래프의 일종이라고 볼 수 있다. 그래프의 용어 그래프는 ( V , E ) 으로 표시됨 V는 정점(vertices)들의 집합 E는 간선(edge)들의 집합 정점과 간선은 모두 관련되는 데이터를 가질 수 있음 ( ex - 정점은 도시의 이름 간선은 도로의 길이 등 ) 인접 정점(adjacent vertex) : 간선에 의해 직접 연결된 정점 정점의 차수(degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수 진입 차수(in - degree) : 방향 그래프에서 외부에서 오는 간선의 수 진출 차수(out - degree) : 방향 그래프에서 외부로 향하는 간선의 수 단순 경로(simple path) : 경로 중에서 .. 미가공 필기(알고리즘) 2021. 6. 24. 이전 1 ··· 11 12 13 14 15 다음 반응형