기말 고사
Chapter 3 분할 정복 알고리즘
- 선택 문제 -> 안 나올 것 같음. 손코딩으로 나올 수는 있지만.. 알고리즘 문제로는 안 나온다.
- 최근접 점의 쌍 찾기 -> 프로그래밍으로 나올 것 같음. 손코딩 유력
Chapter 4 그리디 알고리즘
(그리디 알고리즘으로는 결과를 보이기. 그림 그리기 등으로 나올 것 같음.)
- 동전 거스름돈 -> 다이나믹과의 차이는?
- 부분 배낭 문제
- 집합 커버 문제
- 작업 스케줄링 -> 작업들을 주고, (빠른 시간 순으로) 머신이 몇 개 사용? 각 머신은 어떤 작업을 수행하는지 그 리스트는?
- 허프만 압축 -> 허프만 압축을 위한 허프만 트리를 그리시오. 혹은 문자의 빈도수 주고, 각 문자의 허프만 코드 쓰기.
Chapter 5 동적 계획 알고리즘
(중간고사의 다익스트라를 기억하며 그와 비슷한 문제가 나올 것임.)
- 모든 쌍 최단 경로 -> 다익스트라를 문제로 냈던 문제 유형을 기억하면서, 행렬을 각 단계 별로 그려보시오. K=1,2,3 ..일 때 행렬을 표시하시오! 그 결과는?
- 연속 행렬 곱셈 -> 다익스트라를 문제로 냈던 문제 유형을 기억하면서, 각 단계별로 행렬 채워보기. 혹은 간단하게 최소 곱셈 횟수는?
- 편집 거리 문제 -> 행렬 다 그려보시오.
- 배낭 문제 -> 알고리즘 문제로 나올 것 같음. 예제보다 간단하게~ 라고 얘기함.
- 동전 거스름돈 -> 그리디와의 차이는?
Chapter 6 정렬 알고리즘
- 기수 정렬 -> MSD로 LSD로
- 외부 정렬 + k-way merge sort -> 유력 | Selection Tree(여기서 어떻게 원소 뺄 수 있는지~), 보충 자료로 공부해야 함.
Chapter 7 안 나옴
Chapter 8, 9 근사 알고리즘, 해 탐색 알고리즘
- 여행자 문제 -> 유력 | (아마 MST의 순회순서 주고, 중복된 거 지운 거 답하면 되는 그런 거?)
- 정점 커버 문제 -> 그리디에서 다루니 여기서 안 봐도 됨.
- 작업 스케줄링 문제 -> 그리디에서 다루니 여기서 안 봐도 됨.
- 백트래킹 기법 -> 유력 | 예제를 이해하면 답할 수 있을 것.
- 분기 한정 기법
- 알고리즘 문제 : 이해하고 풀기. -중간고사와의 양상이 비슷함. 시간 많이 안 걸림.
중간 시험 이후에 것만 냈고, 챕터 별로 하나 이상으로 냈고, 분할 정복은 알고리즘 문제가 없다. 챕터 3개 중에서 다섯 개가 알고리즘 문제로 나온다. - 단답형으로 5점 5점 10점, 챕터 8, 9 장에서 나온다. 쉬움
- 코딩 문제 : 예제, 수업에서 다룬 것. 각 챕터 예제로 3개 냈다.
시간복잡도에 관해서는 조금 문제로 나올 것 같음! 조금은 숙지하고 있기. 느낌이 하드코딩으로 했을 때, 알고리즘 기법을 사용했을 때, 이런 것을 비교하기 위해서 문제를 냈을 것 같음.
Chapter 3 분할 정복 알고리즘
- 최근접 점의 쌍 찾기 -> 프로그래밍으로 나올 것 같음. 손코딩 유력
코딩 핵심.
if ( i <= 3) return ( 2 또는 3개의 점들 사이의 최근접 쌍)
SL과 SR로 S(원래 집합)으로 분할.
CPL = Closestpair(SL) // 왼쪽 분할에서의 최근접 점 쌍.
CPR = Closestpair(SR) // 오른쪽 분할에서의 최근접 점 쌍.
d = min{dist(CPL),dist(CPR)}
CPC는 중간 영역에 속하는 점들 중 최근접 점 쌍. 찾기.
return (CPL,CPR,CPC 중에서 제일 거리가 짧은 쌍)
중간 영역은 y-좌표 기준으로 정렬. 각각 점들 사이의 거리를 계산.(하드코딩) 그렇게 중간영역의 최근접 점 쌍 찾음.
Chapter 4 그리디 알고리즘
- 동전 거스름돈
가장 단위가 큰 화폐부터 차근 차근 줄여서 돈을 거슬러준다!
- 부분 배낭 문제 O(n*logn)
- 집합 커버 문제 O(n^3)
최대한 많은 점을 커버하는 순서대로(원소 많은 순서대로) 집합을 정렬.
차근 차근 집합을 넣기. 넣어두면서 그 집합들의 합집합이 전체 집합이 될 때까지만!
그래서 넣어둔 집합들이 바로 모든 원소들을 커버하는 집합들!
- 작업 스케줄링 O(n*long) + O(m*n)
작업 들 중에서 가장 빠르게 시작하는 순서대로 작업을 정렬.
이제 시작! 기계들에게 할당하면 끝!
- 허프만 압축 O(n*logn)
문자의 빈도수를 기준으로 우선순위 큐에 넣기!
이제 그 문자들을 이용해서 트리를 만들 거다!
빈도 수가 낮은 애들 2명을 뽑아서 자식 노드들로 만들고 새 노드 만드는데 이제 그 노드는 자식들의 빈도수를 합쳐서 다시 우선순위의 큐를 넣기!
다시 큐에서 빈도 수 낮은 애들 2명 뽑고 자식 노드들로 만들고 새 노드 만들기! 위 과정과 똑같고
큐에는 더 이상 2명을 뽑을 수 없는 1개의 원소만 들어 있을 때까지! 그리고 그 1개의 원소는 루트가 된다!
이제 트리에서 왼쪽 자식으로 가면 0, 오른쪽 자식으로 가면 1로, 허프만 코드를 할당!
Chapter 5 동적 계획 알고리즘
- 모든 쌍 최단 경로 O(n^3)
먼저, 입력은 각 노드들이 직접 다른 노드로 갈 때의 가중치를 행렬에 적어 놓은 대로!
이제 시작, 노드의 개수만큼 반복문을 이제부터 진행! [for문 K에 대하여.]
K는 K 노드를 경유해서 갈 때,
모든 노드들을 확인하는 반복문을 진행! [for문 i에 대하여.] - (i는 i노드에서 j노드로 가는 것!)
i가 가게되는 모든 j노드에 대해서 반복문을 진행! [for문 j에 대하여.]
반복문 i와 j에 대한 것은 모든 노드가 다른 노드로 갈 때의 모든 길을 확인하기 위한 것!
이제 여기서 k노드를 경유할 때 {D[i,k]+D[k,j]}. i에서 j로 가는 짧은 길인가? 아니면 D[i,j] 이전의 길이 더 짧은가? 판단
판단해서 더 짧은 거리를 D[i,j]에 넣어서 최단 경로를 기억하자.
반복문을 모두 종료하면 모든 쌍 최단 경로를 구할 수 있다.
- 연속 행렬 곱셈 O(n^3)
행렬들 각각의 가로 세로를 기억하는 입력이 있다! (뭐 인접 행렬끼리만 결합 법칙이 될테니까 입력이 이상할 수도 있다.)
그래서, 처음 행렬에 입력되는 것은 바로 옆에 있는 행렬과 계산한 값이 들어간다. A * B * C * D 가 있다면, 행렬에 들어가는 값이 A*B와 B* C와 C * D 의 결과값이 들어간다는 것이다! (행렬 2개를 계산하는 횟수) 그 다음에는 이제 (행렬 3개를 계산하는 횟수)를 들어가고, 이제 경우의 수를 확인해서 더 적은 곱셈 횟수를 저장한다.
다음에는 (행렬 4개를 계산하는 횟수)가 들어가고, 마찬가지이다! 이걸 반복하는 것!
마지막에는 (모든 행렬을 계산하는 횟수)가 들어가고, 이전에 계산한 결과값들을 이용해서 가장 적은 횟수를 저장한다.
여기까지 봐야 이해할 수 있다! (행렬 X개 계산하는 가장 적은 횟수)를 기억해서 다음 반복문을 돌 때, (행렬 X+1개의 계산하는 가장 적은 횟수)를 구할 때, 이걸 적용하는 거야! 굳이 다시 곱셈을 다 해보는 게 아니라!
그니까, X개 행렬에서 구한 거에다 행렬 하나를 더 곱을 했을 때, 이미 X개 행렬까지의 계산 결과가 있는데 굳이 다시 계산해서 구할 필요 없잖아?
코드는 지금 당장 이런 요약본으로 공부하기엔 버거워.. 어떻게 했는지만 기억하자.
- 편집 거리 문제 O(m*n)
문자를 타겟 문자로 바꿀 때, (삭제, 삽입, 대체) 연산 횟수는 얼마일까?
차근 차근 문자열의 문자 1개, 2개, 3개가 됐을 때 어떻게 해야 타겟 문자열의 문자 1개, 2개, 3개로 바꿀 수 있는지 그 계산 횟수를 저장하자. (예시. Words - > Wasup 로 변환 할때, 원본 Words에서 W, Wo, Wor를, 타겟의 W, Wa, Was로 변환할 때를 차근차근 보겠다는 거야.)
그러면 다음으로 문자열의 문자를 하나 더 봤을 때의 경우는그 이전까지의 문자열 바꾸기는 내비두고, 문자 하나 더 본 다음의 그 연산을 확인만 하면 되잖아? 이미 이전 문자열까지의 연산을 계산했으니까!
E[i,j-1]+1, E[i-1,j]+1, E[i-1,j-1] + a 이 셋 중에서 적은 연산이 바로 그 다음 E[i,j]의 최소 편집 횟수야!
i는 원본의 문자열 중 i번째까지 봤을때, j는 타겟의 문자열 중 j번째 까지만 봤을 때를 뜻해.
- 배낭 문제 O(n*C)
배낭에 넣는 건데 이번에는 좀 달라.
물건들을 고려하는 순서대로 반복문을 짜. 물건 1번째 까지만 고려, 2번째 까지만 고려, 3번째 까지만 고려. 이렇게!
물건 1번째만 고려해서 가방에 넣어보는 거야. 배낭이 넉넉하고, 그 가치가 넣기 전보다 괜찮으면 넣는거지.
물건 2번째까지만 봤을 때는 물건 1과 물건 2 모두 고려해서 넣어보는 거야. 마찬가지로 가치가 높은 경우의 수를 택해서 넣자.
(물건 1을 빼고, 물건 2를 넣는 게 가치가 높다면 그걸 택해! 아니면 물건 1 넣은 채로 냅두고) (가방 넉넉하면 다 넣을 수도 있겠지.)
물건 3번째까지만 봤을 때, 이번에는 물건 1과 물건3을 넣을지 물건 2와 3을 넣을지 그냥 1, 2를 유지할지 뭐 그런 경우의 수도 있겠지. 가치가 높은 경우의 수를 택해.
- 동전 거스름돈 O(n*k)
화폐 단위가 적은 것부터 시작하자. 그걸로 거스름돈을 줘보고, 그 다음 화폐 단위로 줄 수 있으면 적은 화폐 단위를 그 다음 화폐 단위로 화폐를 교환해줘.
가능하다면 말이지.
그렇게 하면 동전의 개수를 최대한 적게 줄 수 있겠지? 이런 방식을 채택하는 거야.
Chapter 6 정렬 알고리즘
- 기수 정렬
자릿수에 따라서 정렬하는 거야. 물론 그 다음 자릿수를 정렬할 때, 이전의 그 순서가 달라지면 안 돼.다음 자릿수에서는 같은 값일 때, 해당 같은 값을 가진 원소들의 이전 자릿수의 순서가 유지되어야 한다는 거야.
LSD랑 MSD 방식이 있는데 이건 작은 자릿수부터? 아니면 큰 자릿수부터? 정렬할지 순서 차이야.
- 외부 정렬 + k-way merge sort
공부해. Selection Tree 및 그런 걸 활용해.
Chapter 8, 9 근사 알고리즘, 해 탐색 알고리즘
- 여행자 문제 -> 유력 | (아마 MST의 순회순서 주고, 중복된 거 지운 거 답하면 되는 그런 거?)
MST에서 순회 순서에서 차근 차근 따라가다가 이미 갔다온 점을 삭제하는 거야. 중복 점 삭제. 그게 끝.
- 정점 커버 문제 -> 그리디에서 다루니 여기서 안 봐도 됨.
- 작업 스케줄링 문제 -> 그리디에서 다루니 여기서 안 봐도 됨.
- 백트래킹 기법 -> 유력 | 예제를 이해하면 답할 수 있을 것.
작은 값을 찾는 문제라면, 이 알고리즘은 그냥 모든 결과를 확인해보고 이거 해로 하기엔 너무 크네? 해가 이제 제일 작나? 확인해보는 거라 그냥 완벽하게 탐색했다 라고만 생각해.
- 분기 한정 기법
백트래킹처럼 결과를 확인해보는데 이미 계산한 결과를 기준으로 결과를 확인해보는 과정에서 그 기준보다 더 높은 값이 나오네? 그러면 안 볼래. 다음 친구 결과나 보자~ 이렇게 가지 치기를 하는 거야.
예를 들어 재귀를 거치는 과정에서 한 번 끝까지 가봐 그 결과가 19인 걸 확인해!이제 다시 돌아가서 다음 재귀 과정을 거치다가 다 끝까지 재귀를 안 갔는데도 값이 21 이나 나와버렸어!그러면 재귀 그만해! 다음 친구 확인하러 가자! 하는 거야.
'[Computer Science]' 카테고리의 다른 글
| [알고리즘] 11/16 이론 (0) | 2023.11.16 |
|---|---|
| [기초프로젝트랩] 09/26 이론 (0) | 2023.09.26 |
