알고리즘 강의 마무리 하며 정리
✅ 이론적으로 문제 해결 관점에서 반드시 만족해야 하는 알고리즘 조건
- 유효성
- 명확성
- 유한성
✅ 선형 리스트의 한 쪽 끝에서만 자료의 삽입과 삭제가 이루어지는 자료구조
- 스택
✅ 길이가 k인 이진트리가 가질 수 있는 노드의 최대 개수
- 2k -1
✅ 높이가 4인 이진트리가 최대 개수의 노드를 갖을 때, 단말 노드의 개수
- 8개
✅ 연결 리스트의 특정 노드에서 선행, 후행 노드 양쪽에 대한 접근이 가능한 것
- 이중 연결 리스트
✅ 그래프 G에서 정점 v1에서 정점 vn 까지 경로란?
- 간선(v1, v2), (v2, v3), ... (vn-1, vn)으로 연결된 정점의 순서 리스트 v1, v2, ..., vn을 의미
✅ 알고리즘의 시간 복잡도는 무엇의 함수일까?
- 입력 데이터의 크기
✅ 알고리즘의 대표적인 설계 기법
- 동적 프로그래밍 방법(DP)
- 욕심쟁이 방법(Greedy)
- 분할정복 방법
✅ 입력 크기 n에 대한 알고리즘 수행시간 f(n) = 5n3 + 10n2+ 8n + 200의 점근 성능
- O(n3)
- 제일 큰 녀석만 쳌
✅ 분할 정복에 대한 설명
- 분할된 작은 문제는 독립적
- 하향식 접근 방법을 사용
- 분할, 정복, 결합의 처리 과정을 거친다
✅ 분할정복 방법을 적용한 알고리즘 중에서 입력 크기 n에 대한 성능이 가장 우수한 것
- 이진 탐색
✅ 분할 정복 방법에서 각 순환 호출시마다 거치는 작업단계
- 정복
- 분할
- 결합
✅ 다음 원소에 퀵 정렬을 한 번 적용한 후 왼쪽 부분배열에 존재하는 데이터의 개수(맨 앞의 원소가 피벗인 경우)
[ 30 45 20 15 40 25 35 10 ]
- 4개
- 피벗을 중심으로 왼쪽 오른쪽 나누는 퀵 정렬
✅ 퀵 정렬에서 최악의 성능이 발생하는 경우
- 피벗이 항상 부분배열에서 최솟값/최댓값 경우
- 입력 데이터가 정렬되어 있는 경우
- 피벗만 제자리 잡고 나머지 모든 원소가 하나의 부분배열이 되는 경우
- 최악의 경우 시간 복잡도 점화식
T(n) = T(n - 1) + Θ(n), T(1) = Θ(1)
✅ 중간값의 중간값을 사용하는 선택 문제에서 각 그룹의 몇 개의 원소로 구성될까?
- 5개
✅ 동적 프로그래밍에 대한 설명
- 모든 정점 간의 최단 경로 문제에 적용
- 스트링 편집 거리 문제에 적용
- 상향식 접근 방법
- 최적성의 원리가 만족되는 문제에 적용
✅ 연쇄 행렬 곱셈 점화식
- C[ i, k ] + C[ k + 1, j ] + d[ i-1 ] x d[ k ] x d[ j ]
✅ 모든 정점 간의 최단 경로 기호
- d(3)42
- 4에서 3을 거쳐서 2로 가겠다는 의미
✅ 동적 프로그래밍으로 푸는 저울 문제
- 추의 무게와 물체의 무게가 정수이어야 한다
✅ 피보나치 수열에서 f(7) 값
- 13
- 0 1 1 2 3 5 8 13
✅ 동적 프로그래밍 적용해서 n개의 행렬에 대한 연쇄적 곱셉을 해결하는 알고리즘의 시간 복잡도
- O(n3)
✅ 플로이드 알고리즘 시간복잡도
- O(n3)
✅ 욕심쟁이 방법으로 최소 신장 트리를 구하는 알고리즘
- 프림 알고리즘
- 크루스칼 알고리즘
✅ 동전 거스름돈 문제
- 동전의 액면가가 큰 것부터 욕심을 부려 최대한 사용한다
- 액면가가 임의로 주어지면 해결할 수 없다
✅ 최소 신장 트리의 가중치 합
- 16
- 모든 지점을 연결하고 가중치가 최소가 되는 트리
✅ 욕심쟁이 방법을 적용한 작업 선택 문제
- 가장 빨리 끝나는 작업을 제일 먼저 할당한다
✅ 작업 스케쥴링(기계 2개 이상)
- 가장 빨리 시작하는 것 할당
✅ 허프만 코딩
- 출현 빈도수 높으면 => 짧은 코드
- 출현 빈도스 낮으면 => 긴 코드
- abcdbcdcdd에서 가장 짧은 코드는 'd'
✅ 버블 정렬, 셸 정렬, 힙 정렬, 계수 정렬 중에 정렬 방식이 다른 정렬 알고리즘
- 계수 정렬
✅ 주어진 원소들 중에서 자신보다 작거나 같은 키 값을 갖는 원소의 개수를 계산해서 정렬 위치를 찾는 방식의 정렬 알고리즘
- 계수 정렬
✅ 안정적인 정렬 알고리즘
- 버블 정렬
- 안정적인 정렬이란 동일한 원소의 자리를 안 바꾸는 것
- 버블 정렬은 왼쪽이 큰 경우만 바꾸기 때문에 안정적
- 합병정렬
✅ [50, 40, 30, 20, 10]을 버블 정렬로 오름차순 정렬할 때 자리바꿈 횟수
- 10번
- 인접한 두 원소 비교, 왼쪽이 크면 바꾼다
✅ 정렬되지 않는 데이터 중에서 가장 작은 값과 미정렬 데이터 부분의 첫 번째 원소와 교환하는 정렬 알고리즘
- 선택 정렬
✅ 선택 정렬에 대한 설명
- 제자리 정렬 알고리즘
- 주어진 데이터 중 가장 작은 값부터 골라서 차례대로 나열
- 안정적이지 않은 정렬 알고리즘
- 언제나 동일산 시간 복잡도를 갖는 비교기반 정렬 알고리즘
✅ 삽입 정렬에 대한 설명
- 입력이 거의 정렬된 경우 빠른 수행 시간 O(n)을 갖는다
- 안정적인 정렬 알고리즘
- 제자리 정렬 알고리즘
- 데이터 하나씩 비교하는 비효율 때문에 셸 정렬이 나왔다
✅ 수행시간이 O(nlogn)이고, 제자리 정렬인 알고리즘
- 퀵 정렬
- 힙 정렬
✅ 제자리 정렬 알고리즘
- 선택 정렬
- 삽입 정렬
- 셸 정렬
- 퀵 정렬
- 힙 정렬
- 버블 정렬
✅ 평균 성능이 O(nlogn)인 안정적인 정렬 알고리즘
- 합병 정렬
✅ 비교 기반 알고리즘 중에 입력 크기에 비례하는 만큼 추가적인 공간이 필요한 알고리즘은?
- 합병 정렬
- 왼쪽 부분, 오른쪽 부분
✅ 합병 정렬과 퀵 정렬의 공통점
- 분할정복 방법이 적용된다
✅ 힙 정렬에서 오름차순 정렬하려고 초기 힙을 구성했을때 루트 노드에 존재하는 데이터는?
- 최댓값
✅ 기수 정렬에 대한 설명
- 입력 원소의 값의 자릿수가 상수일 때 유용하다
- 각 자릿수별로 정렬
✅ 순차 탐색에 대한 설명
- 모든 데이터 리스트에 적용 가능
- n개의 데이터에 대한 최대 비교 횟수는 n번
- 데이터가 많은 경우 적합하지 못한 방법
- 원소가 순서 없이 저장된 경우 적합
- 시간 복잡도가 좋은 녀석은 아니다
✅ 이진 탐색에 대한 설명
- 최악의 경우 탐색 성능 O(nlogn)
- 정렬된 리스트에만 적용 가능
- 삽입과 삭제가 빈번한 경우 부적합
- 연결리스트로 구현 불가능
- 분할정복 방법 적용
✅ 이진 탐색 트리에서 루트 노드 삭제시(리프 노드가 양쪽에 있다는 가정)
- 오른쪽 서브 트리에서 가장 작은 것을 루트로 올린다
✅ 흑적 트리에 대한 설명
- 이진 탐색 트리의 형태를 갖는 균형 탐색 트리
- 어떤 노드가 적색이면 부모 노드는 항상 흑색이다
✅ 모든 리프 노드의 레벨이 동일한 트리
- B-트리
✅ 데이터들이 연속된 위치를 점유해서 클러스터를 형성하고, 점점 커지는 현상으로 인해 평균 탐색 시간의 증가를 초래하는 충동 해결 방법
- 선형 탐사
✅ 충돌 해결 방법
- 이중 해싱
- 이차 탐사
- 선형 탐사
✅ NP-완전 문제의 근사 알고리즘으로 해결할 수 있는 문제
- 외관원 문제
- 무방향 그래프에서 모든 정점을 한 번씩만 지나가는 사이클의 존재 여부 확인
- 정규곱형으로 주어진 논리식을 찹으로 만들 수 있는지 판단
- n개의 양수가 주어졌을 때, 각 집합에 포함된 수의 합이 동일하도록 n개의 정수를 두 개의 집합으로 나눌 수 있는지 판정
✅ 외관원 문제에 적합한 염색체 인코딩 방법
- 순열 인코딩
✅ 유전 알고리즘의 교차 연산
- 부모의 형질을 나누어 갖는 연산
- 다른 최적화 방법과 구별짓는 연산
✅ 2-3-4 트리에 대한 설명
- 경사 트리가 발생하지 않는다
'Computer Science > Algorithm :: 알고리즘' 카테고리의 다른 글
| 알고리즘 12강 :: 순차 탐색, 이진 탐색, 이진 탐색 트리 (0) | 2022.03.31 |
|---|---|
| 알고리즘 11강 :: 합병 정렬, 퀵 정렬, 힙 정렬 (0) | 2022.03.24 |
| 알고리즘 10강 :: 버블정렬, 선택정렬, 삽입정렬, 셸정렬 (0) | 2022.03.17 |
| 알고리즘 9강 :: 알고리즘 목차, 분할정복, 동적프로그래밍, 욕심쟁이 (0) | 2022.03.04 |
| 알고리즘 8강 :: 욕심쟁이, 최단경로, 작업스케쥴, 작업 선택 (0) | 2022.03.03 |