알고리즘 기출문제

1. 알고리즘의 정의와 구조를 설명하시오.

알고리즘이란
특정 문제를 해결하기 위한 일련의 순서적인 계산/풀이 절차

알고리즘의 조건
입력: '0개 이상의 외부입력 데이터' 가 존재해야 함.
출력: '하나 이상의 결과' 가 나와야 함.
명확성: 모든 명령들은 모호하지 않고, '단순 명확' 할 것
유효성: 모든 명령은 '실행가능' 할 것
유한성: 한정된 수의 단계 후에 '반드시 종료' 할 것

3가지 형태의 구조
Sequence: 명령 구조
Decision: 결정 구조
Repetition: 루프 구조

 

2. Recursive 방식 2진 탐색 알고리즘에 대해 설명하시오.

재귀적 이진탐색 알고리즘: 배열의 중간 값을 확인하여, 중간값보다 작으면 작은쪽(왼쪽)을 크면 큰쪽(오른쪽)에서
다시 이진탐색을 수행하는 탐색방법이다.
이진탐색의 시간복잡도는 

이다.

 

3. 이진 트리의 순회개념과 이진트리 순회방식 3가지를 설명하시오.
이진트리는 v(부모) / left (왼쪽 자식) / right (오른쪽 자식) 로 구성되어 있으며,
이진트리 탐색은 분할정복 탐색알고리즘으로 빠른속도로 탐색이 가능하다는 장점이 있다.

또한 탐색 순위방식에 따라 3가지로 나뉜다. 
전위 pre-order VLR (v - left - right)  
중위 in-order LVR (left - v - right)
후위 post-order LRV (left - right - v)
Level-order: 레벨이 낮은 순서부터 순회

4. Dynamic Programming Algorithm과 Greedy Algorithm에 대해 설명하시오.(99, 103기)
동적 계획법은 전체 문제를 여러 개 하위 문제로 나누고, 하위 문제들의 해결 방법을 결합해 최종 문제를 해결하는 방식
분할정복알고리즘을 예를 들 수 있다.

그리디 알고리즘은 문제를 해결하는 과정에서 순간마다 최적이라는 해만 결정하기 때문에
미래의 값은 알지 못한다. 전체문제의 최적의 답을 보장하지 못하지만 계산속도가 빠르다는 장점이 있다.

5. 알고리즘의 정확도 평가에 대해 설명하시오.(101, 102, 104 107기)

Loop 중 불변의 부분을 찾는 것으로 정확도를 증명하는데 Loop invariant란 루프를 돌 동안 유지되어야 하는 statement이다. Loop invariant를 통해 Loop가 완성적인지 아닌지 체크해 볼 수 있으므로, 루프를 이용한 알고리즘을 짤 때 로직 점검에 아주 탁월한 방법이다. Loop invariant를 증명해 보이려면 세가지 성질을 만족해야 한다.

1) 초기조건 (initialization): 루프에 처음 들어갈 때 변수의 변화 및 statement(조건)의 변화가 맞는지 판단해서, 루프에 정확하게 들어가는지 확인한다.

2) 유지조건 (maintenance): 루프가 시작하기 전부터 해서, 다음 루프로 넘어가기 전까지 만족해야 되는 조건으로 이 조건이 알고리즘의 목적에 부합하는지를 판단한다.

3) 종료조건 (termination): 루프가 끝났을 때, 우리는 사용가능하고 유용한 결과를 얻어야 하며, 이것이 문제해결(알고리즘의 목표)에 도움이 되는 결과가 나오는지 확인한다.

 

6. 점화식(99, 103, 104 107기)

점화식을 해결하는 4가지 방법
1) Repeated Substitution method: 반복적 치환을 이용 (원시적 방법)

- 더 작은 문제에 대한 함수로 반복해서 대치하는 방법

2) Substitution method: 치환 방법

- 결론을 추정하고 수학적 귀납법을 이용해 치환하는 방법

3) The Master method: 특별한 조건을 만족할 때 사용 

- 형식에 맞는 점화식의 복잡도를 이용해서 해결 하는 방법으로 특별한 조건이 맞을 때 사용

4) The Recursion Tree method

- 노드의 재귀적 방법을 통해 해결 (레벨의 수가 몇 개 인지, 몇 레벨에서 base case에 도달되는 지가 포인트

 

7. 함수증가에 따른 시간복잡도 표기법

세타(Theta)

빅오(Big-O)

빅오메가(Big-Omega)

 

8. 병합 정렬(Merge sort)알고리즘에 대해 설명하시오.
9. 후위 표기식(Postfix notation)의 개념을 설명하고 알고리즘을 설명하시오.
10. 랜덤화된 알고리즘 (Randomized Algorithm)의 동작과 방식에 대해 예를 들어 설명하시오(101,

102기)

11. 알고리즘 분석 기준 요소 5가지와, 최적 알고리즘을 찾기 위한 과정에 대해 설명하시오. 12. 퀵정렬(Quick Sort) 알고리즘에 대해서 설명하시오(107)
13. 후위 표현식 스택으로 표현(108)
14. 루프 불변성 개념 설명과 퀵소트 증명(108) 

 프린트  스크랩  잠금