happy coding

버블 정렬이나 삽입 정렬이 수행되는 과정은 '작게' 이웃하는 원소의 자리바꾸기이다. 버블 정렬의 수행 과정은 작은(가벼운) 숫자가 배열의 앞부분으로 매우 느리게 이동하며, 삽입 정렬에서 마지막 원소가 가장 작은 숫자라면 그 숫자가 배열의 맨 앞으로 이동해야 하므로 모든 다른 숫자들이 1칸씩 오른쪽으로 이동해야 한다. 쉘 정렬은 이를 이용한 것이다. 쉘 정렬 쉘 정렬은 삽입 정렬을 이용하여 배열 뒷부분의 작은 숫자를 앞부분으로 '빠르게' 이동시키고, 동시에 앞부분의 큰 숫자는 뒷부분으로 '빠르게' 이동시킨다. 쉘 정렬은 gap 을 이용해 정렬한다. 점점 간격을 작게(마지막으로 1) 해서 타그룹에 속해 서로 비교되지 않은 숫자를 찾는데 여기서 모든 원소를 1개의 그룹으로 여기는 것을 삽입 정렬이라고 볼 수 ..

수업을 듣고 정리한 내용입니다. 삽입 정렬(Insertion Sort) 삽입 정렬이란, 배열을 정렬된 부분(앞 부분)과 정렬이 안된 부분(뒷 부분)으로 나누고, 정렬 안된 부분의 가장 왼쪽 원소를 정렬된 부분의 적절한 위치에 삽입하여 정렬되도록 하는 과정을 반복하여 진행하는 정렬이다. 위와 같은 배열이 있다고 가정하였을 때, 삽입 정렬을 실행하면 아래와 같다. 정렬이 안된 부분의 숫자 하나가 정렬된 부분에 삽입됨으로서, 정렬된 부분의 원소 수가 1개 증가하는 동시에 정렬 안된 부분의 원소 수는 1개 감소한다. 이것을 반복해 수행하면, 마지막엔 정렬아된 부분엔 아무 원소도 남지 않고, 입력이 정렬된다. 정렬은 배열의 첫 번째 우너소만이 정렬된 부분에 있는 상태에서 정렬을 시작하게 된다. //Insertio..

수업을 듣고 정리한 내용입니다. 선택 정렬(Selective sort) 입력 배열 전체에서 최솟값을 선택하여 배열의 0번 원소와 자리를 바꾸고, 다음엔 0번 원소를 제외한 나머지 원소에서 최솟값을 선ㅌ개하여, 배열 1번 원소와 자리를 바꾸는 방식을 통해 마지막에 2개의 원소 중 작은 것을 선택해 자리를 바꾼다. 이렇게 최솟값을 선택해 정렬하는 것을 선택 정렬이라고 한다. //selective sort 입력 : 크기가 n인 배열 출력 : 정렬된 배열 A for i=0 to n-2 min = i for j=i+1 to n-1//A[i] ~ A[n-1]에서 최솟값을 가짐 if A[j] < A[min] min = j A[i] A[min]//min이 최솟값이 있는 원소의 인덱스임 return A 시간복잡도 코드의..

버블 정렬(Bubble Sort) 버블 정렬은 이웃하는 숫자를 비교해 작은 수를 앞쪽으로 이동시키는 과정을 반복해 진행하는 정렬이다. 이 모습이 마치 버블과 같아 그러한 이름이 붙였다. 패스(pass) 버블 정렬에는 입력을 전반적으로 1번 처리하는 것을 패스라고 한다. //Bubble sort 입력 : 크기가 n인 배열 A 출력 : 정렬된 배열 A for pass=1 to n-1 for i=1 to n-pass if(A[i-1] > A[i])//위의 원소가 아래의 원소보다 크다면 A[i-1] A[i]//자리 바꾸기 return A 시간 복잡도 버블 정렬은 for 루프 속에서 for 루프를 수행하게 되는데 pass가 1인 경우 n-1 번 비교하게 되고 따라서 총 비교 횟수는 (n-1) + (n-2) .....

내부 정렬(Internal sort) 내부 정렬이란 입력의 크기가 주기억 장치보다 크지 않은 경우에 수행하는 정렬이다. 예시로서는 버블, 선택, 삽입, 퀵, 힙, 쉘, 기수, 이중 피복 퀵, Tim sort 등이 있다. 외부 정렬(External sort) 내부 정렬과 반대로 외부 정렬은 보조 기억 장치에 있는 입력을 여러 번에 나눠 주기억장치에 읽어들인 후, 정렬해 보조 기억 장치에 다시 저장한다. 외부 정렬에는 다방향 합병(p-way Merge)과 다단계 합병(Polyphase Merge)이 있다.

수업을 듣고 정리한 내용입니다. 동전 거스름돈 문제는 그리디 알고리즘으로 안 풀리는 경우가 있는데, 이때 동적계획 알고리즘은 항상 최적해를 구할 수 있게 해줍니다. 부분 문제 동전 거스름돈 문제에서의 부분 문제를 정의하기 위해 먼저 문제에 주어진 요소인 1. 동전의 종류 2. 거스름돈 에 대해 정리해본다. 동전의 종류를 d1, d2, ... dk 등으로 정하는 경우 d1 > d2 > ... > dk = 1을 만족해야 한다. 거스름돈은 n원이라고 둔다. 배낭 문제의 DP 알고리즘에서는 배낭의 용량을 1kg씩 증가시켜가며 문제를 해결하게 되는데, 이때 1원씩 증가시키고, 거스름돈을 배낭의 용량과 같이 생각해본다면 해결된다. //DPCoinChange 입력 : 거스름돈 n원, k개의 동전의 액면, d1 > d..

수업을 듣고 정리한 내용입니다. 배낭 문제는 0-1 배낭 문제라고 말하기도 하는데, n개의 물건과 각 물건 i의 무게 Wi와 가치 Vi가 주어지고, 배낭 용량이 C일 때, 최대 가지 값을 구하는 알고리즘이다. 단, 배낭에 담은 물건의 무게 합이 C를 초과하지 않으며, 각 물건은 1개씩 넣을 수 있다. 이 알고리즘의 부분문제는 i=1,2,...n이고, w = 1,2, ... c라고 가정한 상황에서 K[i,w] = 물건1 부터 i까지만 고려하고, (임시)배낭의 용량이 w일 때의 최대 가치 로 둔다. 여기서 물건은 행이고, 배낭의 용량은 열이다. Knapsack 입력 : 배낭의 용량은 c, n개의 물건과 각 물건 i의 무게 Wi와 가치 Vi, 단 i=1, 2, ... n 출력 : K[n,C] for i = 0..

수업을 듣고 정리한 내용입니다. 편집거리 문제(edit distance)는 문서 편집기를 사용하는 중에 스트링 S를 수정해 다른 T로 변환하고자 할 때, 삽입(insert), 삭제(delete) 그리고 대체(sutstitude) 연산을 사용하는데 필요한 최소 편집 연산횟수를 계산하는 알고리즘이다. 문자를 편집할 때, 어떤 연산을 어느 문자에 수행하느냐에 따라 편집 연산 횟수가 달라지는데, 이를 부분문제를 정의하여 해결한다. 편집거리 문제에서 부분 문제는 접두부(prefix)를 확인하는 과정으로부터 시작된다. S의 길이를 m 그리고 T의 길이를 n이라 하고, 각각의 문자를 s_i, t_i라고 가정하였을 때, S = s1s2s3 ... sm, T = t1t2t3 ... tn이다. E[i,j]를 S의 처음 i..