알고리즘(algorythm)
a. 주어진 문제에 대한 결과를 생성하기 위해, 단순하며 모호하지 않고 컴퓨터가 수행 가능한 일련의 유형 한개의 명령들을 순서적으로 구성한 것
b. 알고리즘의 만족조건
- 입출력: 외부에서 입력을 받아들여 출력 생성
- 명확성: 각 단계는 단순하고 모호하지 않아야 함
- 유한성: 반드시 종료해야 함
- 유효성: 모든 명령이 수행가능해야 함
- 효율성
c. 알고리즘 생성
- 설계: 상향/하향식
- 표현: 일상언어, 순서도, 의사코드, 프로그래밍 코드
- 검증: 수학적/실용적
- 분석: 공간/시간 복잡도
알고리즘 설계
-
데이터가 주어지는 상태에 따라 알고리즘이 달라질 수 있다
알고리즘 분석
-
정확성
-
효율성:
공간복잡도(space complexity): 필요한 총 메모리의 양
시간복잡도(time complexity): 단위 연산 개수보다 입력크기의 함수로 표현하는 것이 바람직하나, 입력이 항상 최선이라고 가정할 수 없으므로 최악의 수행시간을 취득
점근성능
-
입력 크기 n이 충분히 커짐에 따라 결정되는 성능
-
n이 작은 경우 각각의 개수가 중요하지만, n이 클수록 최고차항이 상대적으로 중요
-
점근성능의 표기법
- Big-O의 효율성에 따른 관계:
O(1) < O(log n) < O(n) < O(nlogn) < O(n2) < O(n3) < ... < O(2n) <.. < O(2n) < O(n!)
순환(재귀, recursive) 알고리즘
- 순환 알고리즘의 수행시간은 점화식으로 표현
정렬 알고리즘
- 안정적(stable): 동일한 키값이 정렬 전후에도 상대적 위치가 불변
- 제자리(in place): 저장공간 이외의 별도 공간을 상수 개만 사용
탐색
탐색
탐색(search): 데이터에서 원하는 원소를 찾는 것
구분
저장장소에 따라
- 내부탐색: 모든 데이터를 주기억장치에 저장한 후 탐색
- 외부탐색: 일부 데이터 외 나머지 데이터는 외부 기억장치에 저장된 채 탐색
저장형태에 따라, 리스트(list), 트리(tree), 그래프(graph), 표(table), 스트링(string)
순차탐색 (sequential search)
이진탐색(binary search)
탐색트리
- 연결리스트 구조에서는 순차|이진 탐색이 어려워, 이를 트리형태로 유지함으로써 추가|삭제|탐색이 용이하도록 개발된 탐색
1) 이진 탐색트리
- 탐색: 한 노드의 왼쪽의 키값은 작고, 오른쪽의 키값은 큰 이진트리이므로, 루트에서부터 원하는 키값을 찾아나간다
- 추가: 추가할 원소를 탐색하다가 비교할 노드가 없으면 그 위치에 추가한다. 이미 존재한다면 종료한다.
- 삭제: 삭제할 원소를 탐색하여 삭제하고 남은 노드들의 위치를 조절한다.
- 자식이 없는 리프노드는 삭제만 한다- 자식이 하나 있다면, 삭제한 노드에 자식노드(를 포함한 부분트리)를 올린다
- 자식이 둘 있다면, 삭제한 위치에 succesor 노드(바로 다음 키값)을 올리고, 그 자식 노드를 successor 위치로 올린다.
- 수행시간: 평균 O(log n), 최악(경사트리) O(n)
2) 2-3-4 트리
-
성질
-
2-노드(키값1개,자식2), 3-노드(키값2개, 자식3), 4-노드(키값3개, 자식4)
-
한 노드의 한 키의 왼쪽의 모든 부분 트리의 키값은 작고, 오른쪽은 크다
-
모든 리프노드의 높이는 동일하다
-
-
탐색
-
추가
- 탐색과정에서 4-노드를 만나게 되면 노드분할(하나의 키를 갖는 3개의 2-노드로 상하좌우 분할)을 행한다
3) 흑적트리
- 추가 후 루트쪽으로 올라가면서 흑적트리의 성질을 만족하도록 구조와 색깔을 조정한다.
a. 삼촌도 적색일 경우, 부모-삼촌을 흑색으로 바꾸고 조부모를 적색으로 바꾼다
b-1. (삼촌이 흑색이고) 현재 키값이 부모-조부모 사이의 키값일 경우, 현재를 기준으로 오른쪽으로 회전(rorate) 시킨다(오른쪽을 내림)
b-2. (삼촌이 흑색이고) 현재 키값보다 부모-조부모의 키값이 크거나 작을 경우, 부모-조부모의 색깔을 바꾸고 부모를 기준으로 왼쪽으로 회전(rorate) 시킨다. (왼쪽을 내림)
