이 편의 문항은 실제 독학사 기출 문제를 그대로 옮긴 것이 아닙니다. 국가평생교육진흥원이 공개한 4단계 알고리즘 과목 출제기준(평가영역)과 공개·복원된 기출의 유형 분포를 바탕으로, 동일한 출제 의도를 갖도록 새로 재구성한 예상·유사 문항입니다. 실제 시험의 문항 수·배점·시간은 매 회차 공고를 통해 반드시 다시 확인하세요.
문제 14지선다
분할정복(divide and conquer) 기법의 일반적인 구조로 옳은 것은?
문제 24지선다
병합 정렬의 시간 복잡도를 점화식으로 나타내면 T(n) = 2T(n/2) + cn (배열을 반으로 나누는 데 상수, 병합에 O(n))이다. 이 점화식을 재귀 트리로 전개해 복잡도를 유도하는 과정으로 옳은 것은?
문제 34지선다
마스터 정리(master theorem)를 이용해 점화식 T(n) = 4T(n/2) + n의 복잡도를 구하려고 한다. a = 4, b = 2이므로 n^(log_b a) = n^(log_2 4) = n^2이다. f(n) = n을 n^2과 비교했을 때의 결론으로 옳은 것은?
문제 44지선다
분할정복과 동적계획법(DP)의 근본적인 차이에 대한 설명으로 옳은 것은?
문제 54지선다
어떤 문제에 동적계획법을 적용할 수 있는지 판별하는 두 가지 필요조건으로 옳은 것은?
문제 64지선다
0/1 배낭 문제(각 물건을 통째로 넣거나 아예 넣지 않음)를 동적계획법으로 풀 때, 배낭 용량 5, 물건이 (무게 2, 가치 3), (무게 3, 가치 4), (무게 4, 가치 5) 세 개라고 하자. dp[i][w]를 처음 i개의 물건만 고려하고 용량이 w일 때 얻을 수 있는 최대 가치라 정의하고 표를 채운다면, 최종 최대 가치 dp[3][5]로 옳은 것은?
문제 74지선다
두 문자열 ACD와 CAD의 최장 공통 부분수열(LCS)의 길이를 동적계획법으로 구하려고 한다. dp[i][j]를 X의 앞 i글자와 Y의 앞 j글자 사이의 LCS 길이라 하고, X[i] = Y[j]이면 dp[i][j] = dp[i-1][j-1] + 1, 다르면 dp[i][j] = max(dp[i-1][j], dp[i][j-1])로 채운다고 하자. 최종 LCS 길이 dp[3][3]으로 옳은 것은?
문제 84지선다
동전 종류가 1원, 3원, 4원이고 목표 금액이 6원일 때, 최소 동전 개수를 구하는 동적계획법 dp[k] = min(dp[k - c] + 1) (c는 사용 가능한 동전, k - c가 0 이상)를 적용해 dp[0]부터 dp[6]까지 채운다면, dp[6]의 값과 그 근거로 옳은 것은?
문제 94지선다
같은 동전 종류(1원, 3원, 4원)와 목표 금액 6원에 대해, 탐욕(greedy) 알고리즘으로 '가장 큰 액면부터 최대한 사용'하는 방식을 적용하면 4원 하나(남은 금액 2원), 다시 1원 두 개를 써서 총 3개(4+1+1=6)가 된다. 이 결과를 앞 문항의 동적계획법 결과(2개, 3+3=6)와 비교했을 때 알 수 있는 사실로 옳은 것은?
문제 104지선다
탐욕 알고리즘이 항상 최적해를 보장하기 위해 필요한 두 가지 성질로 옳은 것은?
문제 114지선다
활동 선택 문제(activity selection problem)에서 활동 A(시작 1, 종료 4), B(시작 3, 종료 5), C(시작 0, 종료 6), D(시작 5, 종료 7), E(시작 6, 종료 8)가 주어졌다고 하자. 탐욕 알고리즘으로 '종료 시각이 가장 빠른 활동부터, 이미 선택한 활동과 겹치지 않는 것만' 차례로 선택할 때 뽑히는 활동과 그 개수로 옳은 것은?
문제 124지선다
백트래킹(backtracking)에 대한 설명으로 옳은 것은?
문제 134지선다
4-Queens 문제(4×4 체스판에 서로 공격하지 않도록 퀸 4개를 놓기)를 백트래킹으로 풀 때, 1행에 1열, 2행에 4열을 놓았다고 하자(같은 열, 같은 대각선에는 놓을 수 없음). 이어서 3행에 놓을 수 있는 열을 검토하면 1열과 4열은 이미 사용되어 제외되고, 2열과 3열이 후보로 남는다. 2열을 놓아 보면 1행(1열)과는 행 차이 2, 열 차이 1로 대각선이 아니라 안전하고, 2행(4열)과는 행 차이 1, 열 차이 2로 역시 안전해 3행에 2열을 놓을 수 있다. 그런데 이어서 4행을 검토하면 남은 열은 3열뿐인데 3행(2열)과 행 차이 1, 열 차이 1로 대각선 공격이 성립해 놓을 수 없다. 이 상황에서 백트래킹 알고리즘이 다음으로 해야 할 일은?
문제 144지선다
분기한정(branch and bound)과 백트래킹의 차이에 대한 설명으로 옳은 것은?
문제 154지선다
0/1 배낭 문제(용량 5, 물건 (2,3), (3,4), (4,5)는 앞 문항과 동일)를 분기한정으로 풀 때, 가치 대 무게 비율이 큰 순서(물건1: 1.5, 물건2: 약 1.33, 물건3: 1.25)로 물건을 정렬한 뒤 물건을 쪼갤 수 있다고 가정한 분수 배낭 상한을 계산하면, 물건1을 전부(무게2, 가치3) 담고 남은 용량 3에 물건2를 전부(무게3, 가치4) 담아 상한 값 7을 얻는다(용량이 정확히 소진됨). 이 상한값 7의 의미로 옳은 것은?
문제 164지선다
설계 기법을 어떤 문제에 적용할지 판별하는 문제다. '동전을 거슬러 줄 때 사용할 동전 개수를 최소화하되, 어떤 동전 액면 조합이 주어질지 미리 알 수 없어 액면 사이의 특별한 배수 관계를 가정할 수 없는 경우'에 가장 적합한 설계 기법은?
문제 174지선다
다음 중 설계 기법과 그 시간 복잡도상의 특징을 짝지은 것으로 옳지 않은 것은?
문제 184지선다
동적계획법에서 메모이제이션(memoization)과 타뷸레이션(tabulation)의 차이로 옳은 것은?
문제 194지선다
다음 중 '탐욕 알고리즘이 최적해를 보장하는 문제'와 '탐욕 알고리즘이 최적해를 보장하지 못하는 문제'를 옳게 짝지은 것은?
문제 204지선다
다음 중 각 설계 기법에 대한 설명으로 옳지 않은 것은?
참고 자료
Last updated on