컴퓨터 과학 개론. 알고리즘

1. 기본 개념 – 컴퓨터 알고리즘이란? → 주어진 문제에 대한 하나 이상의 결과를 생성하기 위해 모호하지 않고 간단하며 컴퓨터가 실행 가능한 일련의 유한개의 명령을 순서적으로 구성한 것•이론적 관점에서 반드시 만족해야 하는 조건: 입출력, 명확성, 유한성, 유효성 및 실용적 관점에서의 추가 조건: 효율성 2. 알고리즘 설계-대표적인 설계 기법 →분할정복방법, 동적 프로그래밍 방법, 욕심쟁이 방법 →분할정복방법 →문제를 더 이상 나눌 수 없게 될 때까지 둘 이상의 작은 문제로 순환하여 각 문제를 해결한 후 각 순환 호출마다 분할, 정복, 결합 3단계를 거친다.• 적용가능한 문제→퀵소트,합병소트,바이너리탐색-동적 프로그래밍 방법→문제의 크기가 가장 작은 소문제부터 해를 구해 테이블에 저장해 두고, 이를 이용하여 입력크기가 더 큰 원래의 문제를 점진적으로 만들어가는 상향식 접근법·적용 가능한 문제→모든 정점간 최단경로를 찾는 플로이드 알고리즘-욕심방법 →해를 구하는 일련의 선택과정마다 전후단계 선택과는 관계없이 각 단계에서 ‘최선’으로 여겨지는 국부적인 최적해를 선택해 나가면 결과로서 전체적인 최적해를 얻을 수 있을 것으로 원하는 방법· 거스름돈이 있을 때에 있다.• 배낭문제(물체를 깰 수 있는 경우) →배낭용량을 초과하지 않는 범위에서 배낭에 들어 있는 물체의 이익 합계가 최대가 되도록 배낭에 물체를 넣는 방법을 찾는 문제 →단위 중량당 이익이 가장 큰 물체부터 통째로 배낭에 넣고, 만약 배낭이 남은 용량보다 물체의 무게가 큰 경우에는 물체를 쪼개서 배낭에 넣는다.4. 알고리즘분석 – 정확성분석 → 유효한 입력이 주어졌을 때 유한시간 내에 정확한 결과를 생성하는지 수학적으로 증명 – 효율성분석 → 알고리즘 수행에 필요한 컴퓨터 리소스, 즉 소요되는 메모리 공간의 크기(“공간 복잡도”)와 실행에 소요되는 시간(“시간 복잡도”)을 측정 – 시간 복잡도 알고리즘 수행시간 → 알고리즘에서 이루어지는 기본 연산 수행횟수의 합·단순히 단위연산 개수가 아닌 입력크기 함수로서 표현·입력데이터 상태에 따라 달라 일반적으로 최악의 수행시간을 사용 – 점근성능 →입력사이즈계수 없이 n의 최고차 항만을 이용하여 표현→수행시간의 개산값이지만 수행시간의 증가세 파악이 용이하여 알고리즘의 우열을 계산할 때 사용·표기법→①’Big-Oh’ 점근적 상한 f(n)=O(g(n)), ②’Big-Omega’ 점근적 하한 f(n)=Ω(n)), ③’Big-Theeta’ 점근적 상하한 f(n)=q(n)) 및 빅오 표기간 연산시간 크기 관계 O(log)<log>나머지는 외부기억장치에 저장한 채 정렬하는 방식 -비교기반 정렬 vs 분포기반 정렬 →데이터의 키값을 직접 비교하여 정렬하는 방식 →선택정렬, 버블정렬, 삽입정렬, 합병정렬 및 분포기반 배열 →데이터의 분포정보를 사전에 얻고 정렬방법 →, 기수정렬 – 선택정렬 주어진 데이터 중 가장 작은 값부터 순서대로 선택하여 나열하는 방식 →①미정렬 부분의 데이터 중에서 가장 작은 값을 선택하고 ②선택된 값과 불일치 부분의 첫 번째 데이터와 교환 및 데이터 입력 상태에 민감하지 않으며 항상 동일한 수행시간 →O(n2)-버블 정렬 역순으로 정렬된 경우에는 최악의 수행시간 O(n2)를 갖는 ·데이터 교환이 많이 발생하여 선택정렬보다 비효율적 – 삽입정렬 · 주어진 데이터를 하나씩 추출한 후 나열된 데이터가 항상 정렬된 형태가 되도록 선택한 데이터를 올바른 위치에 삽입하여 나열하는 방식 → 미정렬 부분의 첫 번째 데이터를 꺼낸 후 정렬된 부분에서 원래 위치로 되돌려서 삽입하는 과정을 반복·주어진 데이터가 이미 정렬되었을 경우에는 최선의 수행시간 O(n)을 가지며, 데이터가 역순으로 정렬되었을 경우에는 최악의 2가지 입력기준을 가진다. 각 부분배열에 대하여 독립적으로 퀵정렬을 순환적으로 적용하는 방법 → 피벗이 소정의 위치에 앉도록 정렬하는 방법 · 분할정복을 적용한 알고리즘 피벗 → 두 부분배열로 분할할 때 기준이 되는 데이터 → 보통배열의 제1원소를 피벗으로 지정 · 분할과정 → 퀵정렬의 가장 핵심부분 → 피봇을 중심으로 두 부분배열로 분할하는 과정 → O(n) · 최선의 수행시간 → 피벗을 중심으로 같은 크기의 두 부분배열로 이루어지는 경우에만 피벗(nlog), 나머지 모든 데이터가 한 부분에 분포된다.배열의 좌단원소를 피벗으로 사용할 경우 →O(n2)•평균수행시간 →O(nlogn) → 피벗선택의 임의성만 확보되면 최악의 수행시간이 아닌 평균수행시간이 보장된다 – 합병정렬 → 같은 크기의 두 부분배열로 분할하고 각 부분배열을 순환적으로 정렬한 후 정렬된 두 부분배열을 합병하여 하나의 정렬된 리스트를 형성하는 방식·분할정복을 적용한 알고리즘·합병과정 → 정렬된 두 부분배열을 입력으로 받아 하나의 정렬된 배열로 만드는 과정·최선/최악수행시간 →On(최악수행시간) 특히 데이터가 정렬되어 있지 않은 경우 적합·O(n)-바이너리 탐색 → 정렬된 입력배열에 대해 주어진 데이터를 절반씩 줄이면서 원하는 데이터를 찾는 방법·분할정복을 적용한 알고리즘·주어진 배열의 중앙데이터 값과 탐색키 비교 → ① ‘탐색키=배열의 중앙값’이면 탐색성공, ② ‘탐색키<배열의 중앙값’이면 주어진 배열의 전반부를 탐색범위로 재지정한 후 이진탐색을 순환호출하고 ③’탐색키>배열의 중간값이면 주어진 배열의 후반부를 탐색범위로 재지정한 후 바이너리 탐색을 호출 → 이진탐색트리 – 각 노드 x 의 좌측 서브트리의 모든 키값은 x 의 키값보다 작으며, 우측 서브트리의 모든 키값은 x 의 키값보다 크다는 조건을 만족하는 이진 트리탐색연산 → 루트노드에서 시작하여 값 크기 관계에 따라 트리경로를 따라 내려가면서 원하는 키값을 갖는 원소 찾기 – 삽입연산 → 삽입할 원소를 탐색한 후 탐색이 실패한 지점의 좌측/우자 노드를 생성하여 추가-삭제연산 → 삭제되는 자노드 개수에 따라 3가지 경우로 구분하여 처리/자노드가 없는 경우가 하나인 경우 →남은 노드의 위치조절이 필요 없음• 자노드가 둘 다 있는 경우: 후속자노드(어떤 노드의 바로 다음 키값을 갖는 노드)를 삭제되는 노드의 위치로 올리고, 후속자노드의 자노드 개수에 따라 다시 삭제연산을 처리-성능/평균탐색시간→O(logn)→리프노드를 제외한 모든 노드의 차수가 2인 경우·최악탐색시간→O(n)→경사이진트리, 즉 리프노드를 제외한 모든 차수가 1인 경우