본문 바로가기

CS/알고리즘

 (27)
Chap 6-1. 버블 정렬(Bubble Sort) 6.1 버블 정렬 = 인접한 2개의 레코드를 비교하여 순서대로 되어 있지 않으면 서로 교환한다. 즉, 두 개씩 비교해서 둘 중에 큰 숫자가 한 칸씩 뒤로 간다. – 작은 수는 배열의 앞부분으로 이동하는데, 배열을 좌우가 아니라 상하로 그려보면 정렬하는 과정에서 작은 수가 마치 거품처럼 위로 올라가는 것을 연상케 한다. [패스(pass)란? ] = 배열 전체를 근접한 2개씩 비교하여 큰 것이 뒤로 가게 하는 과정을 반복한다. 1 패스는 = 한 번 입력을 처음부터 끝까지 연속된 두 수를 비교하는 것을 말한다. 1 패스를 수행한 결과는 = 제일 큰 값이 제일 끝에 위치하게 된다. 1패스를 수행하여 제일 큰 값을 정렬하는 데 성공한 것이다. → 그러므로 제일 큰 수를 제외하고 나머지들끼리 다시 위의 과정을 반복..
Chap 6. 정렬 알고리즘(sort) [ 정렬이란? ] 정렬은 물건을 크기 순으로 오름차순이나 내림차순으로 나열하는 것이다. 방대한 양의 데이터를 쉽고 빠르게 정보를 찾기 위해 컴퓨터를 사용한다 이를 위한 기본적이고 중요한 알고리즘이 정렬이라고 할수 있다. [ 정렬의 기준 ] 정렬은 여러 가지 기준으로 나눌 수 있다. (1) “효율적이지만 구현이 어려움 vs 비효율적이지만 구현 쉬움” 예를 들어, 퀵 정렬은 효율적이고 빠르지만 구현이 어렵다. 반면, 버블 정렬은 구현이 쉽지만 비효율적인 방법이고 느리다. (2) “안정성을 보장하는가” 안정성은 중복된 key값이 있다면 상대적인 순서가 보장되는 것이다. 예를 들어, 버블 정렬은 같은 "5"라는 숫자도 상대적인 순서를 구분해준다. 즉, 앞에 있는 5와 뒤에 있는 5를 구별한다. 하지만, 삽입정렬..
Chap 5-3. 편집거리 (Edit Distance) [편집거리 (Edit Distance)] = 삽입 (insert), 삭제 (delete), 대체 (substitute) 연산을 사용하여 스트링(문자열) S를 수정하여 다른 스트링 T로 변환하고자 할 때 필요한 최소의 편집 연산 횟수 즉, 3개의 연산(삽입, 삭제, 대체)을 통해 다른 문자열로 변환이 가능하다. [예시 strong -> stone] strong을 stone으로 바꿔보자 2가지 방법이 가능하다. 방법 1 ) 순서대로 s, t는 그대로 두고 o를 삽입하고 r, o를 삭제한다. n은 그대로 두고 g를 e로 바꾼다. ⇒ 총 4회의 편집 연산을 했다. 방법 2) ‘s’와 ‘t’는 그대로 사용한 후, ‘r’을 삭제하고, ‘o’와 ‘n’을 그대로 사용한 후, ‘g’를 ‘e’로 대체하여, 총 2회의 편집..
Chap 5-2.연속 행렬 곱셈 연속 행렬 곱셈(Chained Matrix Multiplication) 문제 = 연속된 행렬들의 곱셈에 필요한 원소 간의 최소 곱셈 횟수를 찾는 문제 행렬 곱셈 (1) 두 행렬의 곱셈이란? 두 행렬 A, B가 있다. A = 10 x 20 B = 20 x 5 라면 총 곱셈의 횟수 = 10 * 20 * 5 = 1000이다. (2) 3개의 행렬 곱셈 A = 10 x 20 B = 20 x 5 C = 5 x 15 행렬의 곱셈은 결합법칙 성립하므로 (A* B) * C , A * ( B * C) 이 둘 다 성립한다. 하지만 둘의 결과값는 같지만 곱셈의 횟수는 전자가 더 적다.(과정이 다르다) [ 행렬 곱셈의 주의점 ] 주어진 행렬의 순서를 지켜서 “반드시 이웃하는 행렬끼리” 곱해야 한다. 동적 알고리즘 적용 (1) ..
Chap 5-1. 0-1 배낭 문제 0, 1 배낭 문제 조건 4kg을 담을 수 있는 배낭 넣을 수 있는 물건 A, B, C가 있다. B의 무게 = 4, 가치 = 30 C의 무게 = 3, 가치 = 20 A의 무게 = 1, 가치 = 15 가장 단순한 방법은 모든 물건의 조합을 시도를 해서 총 가치를 구한 다음에 가장 가치가 높은 경우를 선택하는 것이다. 이렇게 한다면 지수 시간의 시간 복잡도를 갖는 문제이다. 2^n의 경우의 수이다. 이 문제를 (1) 재귀 방법으로 풀 수 있고 (2) DP방법으로도 풀어볼 수 있다. (1) 재귀 방법 #include #define MAX(a, b) ((a) > (b) ? (a) : (b)) int knapSack(int W[], int V[], int n, int c) { if(n 다음 물건으로 넘어감, 배낭..
Chap 5. 동적 계획 알고리즘 Dynamic Programming(DP) 알고리즘 -입력 크기가 작은 부분 문제들을 해결한 후에 -그 해들을 이용하여 보다 큰 크기의 부분 문제들을 해결해어 -최종적으로 원래 주어진 입력의 문제를 해결 [문제] n개의 원소를 갖는 문제 같은 형태로 문제를 해결해나가지만 n개보다 작은 값으로 (작은 문제로 ) 만들어서 푸는 방법 (1) 최적의 하위구조 특성 k < n 인 k개의 원소를 갖는 문제를 정의하고 문제를 풀었더니 그것이 최적의 풀이법이고 점점점 작은 문제들을 결합해서 최종 풀이법이 완성되어지는 형태의 특성을 갖는 문제를 “최적의 하위구조 특성을 갖는 문제”라고 부른다. 예시) 두 도시를 자동차로 갈 수 있는 최단 경로 A도시 B도시 C도시가 있는데 A에서 C로 가기 위해서는 A-B의 최단 경로를..
Chap 4-7. 허프만 압축 파일을 저장할 때 최대한 작게 저장하는 것이 효율적일 것이다. 데이터 압축 문제는 데이터를 코드화하는 효율적인 방법을 찾는 것이다. (1) 허프만 코드라고 하는 코드화 방식 (2) 주어진 파일을 허프만 코드화하는 탐욕적인 알고리즘 파일은 기본적으로 이진코드를 사용해서 표현한다. 코드화 방식에서 각각의 문자는 코드워드라고 하는 유일한 이진 문자열로 각 문자를 표현한다. 이 중 길이가 고정된 이진 코드는 각각의 문자를 표현하는 bps가 일정하다. 예를 들어 a, b, c를 코드화한다. a : 00, b: 01, c:11 ababcbbbc ⇒ 000100011101010111 (18비트가 필요함) 그러나 길이가 변하는 이진 코드를 사용하면 좀 더 효율적인 코드화 방식을 사용할 수 있다. → 각 문자를 다른 길..
Chap4-6. 작업스케줄링(Job scheduling) 작업 스케줄링 문제 작업의 수행 시간이 중복되지 않도록 모든 작업을 가장 적은 수의 기계(프로세서)에 배정하는 문제 *여기서 기계는 프로세서이며 문제마다 다르다. 하지만 이를 가장 적게 사용하는 방법을 고안하는 것이다. 학술대회에서 발표자들을 강의실에 배정하는 문제와 같다. 발표 = ‘작업’, 강의실 = ‘기계’ 작업 스케줄링 문제에 주어진 문제 요소 1. 작업의 수 입력의 크기이므로 알고리즘을 고안하기 위해 고려되어야하는 직접적인 요소는 아니다. 2. 각 작업의 시작시간과 종료 시간 3. 작업의 길이 - 작업의 시작 시간과 종료시간은 정해져 있으므로 작업의 길이도 주어진 것 - 주어지는 조건에 따라서 작업 스케줄링 문제가 다양하다. - 여러 가지 작업들이 있고 그 작업들마다 시작시간과 종료 시간이 다 ..
Chap4-2. 최소 신장 트리 4.2 최소 신장 트리 그리디 알고리즘을 통해 항상 정답을 도출할 수 있는 알고리즘 최소 신장 트리 (1) 최소 신장 트리란 ? 최소 신장 트리 = 신장트리 + 가중치의 합이 최소 -트리는 그래프의 한 종류이다, 정점과 간선으로 된 그래프이다. -신장트리는 연결 그래프의 부분 그래프로서 그 그래프의 모든 정점과 간선의 부분 집합으로 구성되는 트리 모든 노드는 적어도 하나의 간선에 연결되어 있어야 한다. (노드 = n개 , 간선 = n-1개 ) 트리에 간선을 하나 추가 시키면 반드시 사이클이 만들어진다. 하지만 그래프에 사이클이 형성이 되면 안된다. [크러스컬 알고리즘] 1) 특정한 정점에서 시작되는 것이 아니라 전체 가중치 그래프에서 가중치 가장 작은 간선을 선택한다 2) 먼저 가중치를 기준으로 정렬 후..
Chap4-1. 동전 찾기 문제 4.1 동전 거스름돈 문제 동전 거스름돈 문제를 해결하는 가장 간단한 효율적인 방법 남은 액수를 초과하지 않는 조건하에 ‘욕심내어' 가장 큰 액면의 동전을 취하는 것 동전 거스름돈 문제의 최소 동전 수를 찾는 그리디 알고리즘 동전의 액면은 500원, 100원, 50원, 1원 coinChange(N) 입력 = 거스름돈 액수 W 출력 = 거스름돈 액수에 대한 최소 동전 수 1. D = {10, 50, 100, 500 } //거슬러줄 수 있는 거스름돈 단위의 집합 2. S = { } //답이라고 한다면 3. value = N 4. while(value != 0) x = D에서 x < value 인 가장 큰 값 if 조건에 만족하는 항목이 없으면(D에 해당하는 값이 없을 때) return S = S (합집합) ..

티스토리툴바