알고리즘36 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 스택(Stack) 과 큐(Queue) 스택(Stack) : 접시를 쌓듯이 자료를 쌓아 올린 형태의 자료구조 스택에 저장된 원소는 top으로 정한 곳에서만 접근 가능 top의 위치에서만 원소를 삽입/삭제하기 때문에 먼저 삽입한 원소는 밑에 쌓이고, 나중에 삽입한 원소는 위에 쌓이며 마지막에 삽입한 원소가 가장 먼저 삭제된다. 그래서 후입선출(LIFO , Last In First Out) 구조라고 함 스택의 연산으로는 대표적으로 삽입 연산 : push 삭제 연산 : pop 이 존재하고 조회하는 peek 등 존재함 스택을 응용하는 예시로 시스템 스택이 있음 가장 마지막에 호출된 함수가 가장 먼저 실행을 완료하고 복귀하는 후입선출 구조이므로 스택을 이용하여 수행순서 관리하는 것. 실행 순서를 복기하면, 프로그램이 실행을 시작하면 메인 함수가 실행되.. 미가공 필기(알고리즘) 2021. 6. 24. 210623 알고리즘 자료구조란? 컴퓨터에서 어떤 문제를 해결하기 위해 자료의 특성에 따라서 자료를 분류하여 구성하고 저장해 놓은 것 자료구조의 형태 단순 구조 - 정수, 실수, 문자, 문자열 선형 구조 - 순차 리스트, 연결 리스트, 스택, 큐, 덱 비선형 구조 - 트리, 그래프 파일 구조 - 순차 파일, 색인 파일, 직접 파일 알고리즘이란? 알고리즘은 문제해결 방법을 추상화하여 단계적 절차를 논리적으로 기술한 명세서 알고리즘의 표현 방법 자연어를 이용한 서술적 표현방법 순서도를 이용한 도식화 표현방법 프로그래밍 언어를 이용한 구체화 방법 가상코드를 이용한 추상화 방법 알고리즘과 프로그램의 차이는? 알고리즘은 어떤한 문제에 대한 해결 방법, 프로그래밍 언어, 컴파일러, 시스템에 비의존적 프로그램은 알고리즘을 구현하여 문제를.. 미가공 필기(알고리즘) 2021. 6. 23. 이전 1 2 3 다음 반응형