여정의 기록

정렬 주어진 데이터를 값의 크기 순서에 따라 재배치 내부 정렬 : 모든 데이터를 주기억장치에 외부 정렬 : 많은 데이터를 보조기억장치에 두고 필요할 때 주기억장치에서 빼서 사용 비교 기반 알고리즘 O(n^2) 버블 정렬, 선택 정렬, 삽입 정렬, 셸 정렬, O(nlogn) 합병 정렬, 퀵 정렬, 힙 정렬 데이터 분포 기반 알고리즘 O(n) 계수 정렬, 기수 정렬 안정적 정렬 동일한 값을 갖는 데이터가 여러 개 일때 정렬 전의 상대적 순서가 정렬 후에도 그대로 유지 제자리 정렬 입력 데이터를 저장한 공간 이외에 추가적인 저장 공간을 상수개만 필요로 함 (입력 크기 n이 증가함에도 추가 저장공간은 증가하지 않음) 버블 정렬 모든 인접한 두 값을 비교하여 왼쪽 값이 더 큰 경우 자리를 바꾸는 과정을 반복 왼 ..

최단 경로 가중 방향 그래프에서 두 정점을 연결하는 경로 중에서 간선의 가중치의 합이 가장 작은 경로 플로이드 알고리즘 Floyd0 데이크스트라 알고리즘 Dijkstra 모든 정점 간의 경로 특정한 하나의 정점에서 다른 모든 정점으로의 최단 경로 (단일 출발점 최단 경로) 동적 프로그래밍 방법 적용 욕심쟁이 방법 적용 O(|V|^3) O(|V|^2) 가중치의 합이 음수인 사이클이 없다고 가정 음의 가중치를 갖는 간선이 없다고 가정 데이크스트라 알고리즘 거리 d[v] : 출발점에서 현재까지 선택된 정점 집합 S를 경유하여 정점 v에 이르는 최소 경로의 길이 출발점에서 시작하여 거리 d[]가 최소인 정점을 차례로 선택하여 최단 경로를 구하는 방법 초기화 : 출발점 d[s]=0 . 나머지 모든 정점 v의 d[..

해를 구하는 일련의 선택 단계가 전후 단계의 선택과 독립적으로, 무관하게 해당 단계에서 가장 최선으로 여겨지는 국부적인 최적해를 선택하여 전체적인 최적해를 구한다. 동적 프로그래밍 욕심쟁이 방법 최적화 문제 해결에 주로 사용 최적성의 원리가 적용된 방법 소문제의 여러 최적해로부터 다음 크기의 문제에 대한 최적해가 결정 -> 항상 전체적인 최적해를 구함 소문제에서 하나의 최적해만 고려 -> 전체적인 최적해를 구하지 못할 수 있음 욕심쟁이 방법으로 해를 구할 수 없는 문제도 많다. 하지만 풀 수 있는 문제라면 아주 간단히 해를 구할 수 있다. 욕심쟁이 방법으로 해를 못 구할수도 있다. 동전 거스름돈 문제 고객에게 돌려줄 거스름돈이 있을 때 동전의 개수를 최소로 하여 거스름돈을 돌려주는 방법을 찾는 문제 거스..

스트링 편집 거리 두 문자열 X, Y 사이의 편집 거리 n개의 X와 m개의 Y 문자열 X를 Y로 변환하는 데 필요한 전체 편집연산에 대한 최소 비용 (특정 위치에 새 문자를 삽입, 문자 삭제, 다른 문자로 변경하는 연산) 최소 편집 비용 == 편집 거리 최적성의 원리 만족 (X와 Y 사이의 편집 거리는 포함한다 - 부분 문자열 사이의 편집 거리를) X의 마지막 글자가 삭제된 경우 x1 x2 ... xn-1 , y1 y2 ... ym 의 최소 편집 비용 + x의 마지막 글자 xn의 삭제 비용 Y의 마지막 글자가 삽입된 경우 x1 ... xn, y1 ... ym-1 + y의 마지막 글자 ym의 삽입 비용 X의 마지막 글자와 Y의 마지막 글자가 같거나 같도록 변경된 경우 x1 ... xn-1 , y1 ... ..

동적 프로그래밍 방법 Dynamic programming 크기가 작은 문제에 대해 해를 저장하고 이를 이용하여 크기가 큰 문제의 해를 점진적으로 만들어가는 상향식 bottom-up 접근 방법 각각의 소문제는 원래의 문제와 동일하지만 입력의 크기만 줄어듦 입력 크기가 아주 작은 단순한 문제가 되면 해를 구할 수 있고, 이런 소문제의 해는 다시 사용될 수 있으므로 테이블에 저장 해당 소문제의 해가 필요할 때마다 테이블에서 결과를 바로 이용 동적 프로그래밍 혹은 동적 계획법 최적화 문제(min/max 값 구하는)에 적용 분할 정복 방법 동적 프로그래밍 방법 하향식 접근 방법 상향식 접근 방법 상위 레벨의 큰 문제를 순환적으로 부분배열로 분할. 가장 작은 배열을 이용해 해를 구하고 이들의 해를 결합해서 원래 문..

합병 정렬 1. 데이터를 나눌 수 없을 때 까지 나눠준다. 2. 두 가지의 원소를 비교하여 정렬한 후 합병해준다. 각 분할된 배열을 어떻게 합병하는가? 각 분할된 배열의 가장 첫번째 원소를 각자 비교하고 새로운 배열에 하나씩 넣어준다. 합병 함수 Merge() Merge(B[], C[], n, m). //A[n+m-1] 최악 O(n), 평균 O(n) 알고리즘 최솟값을 어떻게 찾는가? 각 데이터를 하나씩 모두 비교하는 방법 n개의 데이터에 대해서 적어도 (n-1)번의 비교가 필요 -> O(n) FindMinimum(A[], n) { min=A[0]; for(i=1;i 2n-3번의 비교 O(n) 방법 2 : 모든 원소를 짝을 지어 비교 3/2n-2 FindMinMax(A[], n, min, max) { if..

분할정복 방법의 원리 순환적으로 문제를 푸는 하향식 접근 방법 - 주어진 문제의 입력을 더 이상 나눌 수 없을 때까지 두 개 이상의 작은 문제로 순환적으로 분할. 각 작은 문제를 해결. 이 해들을 결합해서 원래 문제의 해를 구하는 방식 예시) 피자 한판을 한 번에 먹을 수 없다 -> 피자를 나눈다 -> 나눈 피자를 한 번에 먹을 수 없다 -> 한 입 먹을 수 있을 때 까지 계속 나눈다. 특징 - 분할된 작은 문제는 원래 문제와 동일 - 입력의 크기만 작아짐 - 분할된 작은 문제는 서로 독립적 -> 순환적 분할 및 결과 통합 가능 순환 호출 세 단계 분할 : 주어진 문제를 여러 작은 문제로 분할 정복 : 분할된 작은 문제를 순환적으로 분할. 더 이상 분할 불가하게 작다면 순환호출 없이 해를 구한다. 결합 ..

컴퓨터과학 = 컴퓨터 + 데이터 + 프로그램 프로그램 = 알고리즘 + 입력 언어 컴퓨터과학 == 알고리즘 과학 컴퓨터의 한계는 알고리즘의 존재 여부로 갈린다. 강의의 목적) 알고리즘의 설계 및 분석 방법을 습득하자! -> 컴퓨터 기반 문제 해결 방법에 대해 체계적으로 생각하는 훈련 -> 주어진 문제에 대한 지적 추상화 능력 및 통찰력 향상 문제(데이터) -알고리즘(일련의 단계적인 처리과정, 효율적인) -> 결과(정보) 알고리즘 예시) 퀘닉스버그 다리 문제 = 오일러 경로를 찾는 문제(그래프의 모든 간선을 오직 한 번씩만 지나는 경로) = 한붓 그리기 단일 출발점 최단경로 자료구조란? 컴퓨터에서 데이터 사이의 논리적 관계를 표현하고 조직화하는 방법 프로그램 = 자료구조 + 알고리즘 자료구조와 알고리즘 어느..