[컴퓨터알고리즘] 추가

 

 

 

 

해보기!

 

 

 

 

해보기

 

 

 

과제

 

 

 

 

 

[중간고사] - 만점목표로!

시험범위 : 1-5장

 

• 1,2장 : 알고리즘 정의,특징, 분류 정리 + 알고리즘 문제 사례 방법 훑기
• 2장 : 알고리즘 정의 특징 분류, 시간복잡도(알고리즘 효율성) : 마지막 연습문제처럼, 문제#1 - 시간복잡도 함수가 주어지고 이를 증명하라는 문제 or 문제 #2 - 알고리즘의 부분코드(수업시간에 봤었던 코드가 나올수도 있음) : 주어진 코드의 복잡도 빅O표기로 나타내시오
• 3~5장 : 각 알고리즘 다 알아야 한다. 공통방법, 아이디어 기술 가능해야 한다. ex) 분할정복 VS 동적계획알고리즘 비교설명해주세요. gridy 알고리즘 vs 동적계획알고리즘 비교설명해주세요. >> 해당 알고리즘 정의 + 어떤 특징이 있는지 가지고 비교설명할 수 있어야 함. 각 알고리즘 방법 정확히 파악해야 한다. 알고리즘 - 코드 빈칸x,  과제에서 했던 것처럼 각 알고리즘별 수행과정, 적용과정 보일 수 있어야 한다. 각 알고리즘별 시간복잡도 설명할 수 있어야 한다.
• 3,4,5장에 알고리즘 너무 많지만... 다 시험범위 포함
• 코드가 별도로 나가지 않는데, 정확하게 파악해야 할 것들이 있었음
  • union find - parent 관계 , 허프만코딩 - 0-1, 알파벳과 숫자가 나타날때 고려대상이 있으면 작은거에서 큰 순서대로
  • 동적계획알고리즘 - 코드까지는 아니지만 부분문제간의 함축적 순서(다음크기의 문제를 해결하기 위해 이전에 미리 해결했던 값을 갖고 옴) 와 같은 의미로 각각의 알고리즘에서 어떤 값을 참조해서 만들어가는지에 대한 인덱스(수식)정도는 알고 있어야 한다. (D[i,k]+D[k,j], D[i,j])  + 분할정복알고리즘 비교 파악해야함. 
    • 내가 비교하거나 계산할 때 고려하는 대상, 부분문제간의 함축적 순서를 반영할 수 있는 각각의 값을 파악할 수 있어야 한다.
  • 연속행렬곱셈 - 이전에 누구의 값을 갖고 비교하는지에 대한, 주요 식이 되는 근거 (ex. edit distance 볼 때도 왼쪽, 위, 대각선 왼쪽 위 이렇게 세가지를 보는데, 표를 볼때가 아니라 수식으로 이야기할때는 해당 인덱스 명시해서 구분할 수 있어야 함.   --->  C[i,k] + C[k+1, j] + d_(i-1) * d_k * d_j) 
• 시험시간 1시간.