[7급 서울시 알고리즘] 26년 1회차 기출문제 정답·해설 페이지

[7급 서울시 알고리즘] 26년 1회차
    1[7급 서울시 알고리즘] 26년 1회차
    21개의 노드를 가진 그래프가 3개의 트리(tree)로 이루어진 숲(forest)의 형태일 때, 간선(edge)의 총 개수로 가장 옳은 것은?
    1
    18
    2
    19
    3
    20
    4
    21
    해설

    간선의 총 개수는 18개다.

    노드가 nn개인 트리는 간선이 n−1n-1개이므로, 트리 kk개로 된 숲의 간선 수는 노드 수 − 트리 수가 된다.

    21−3=1821-3=18

    • 간선 19개: 트리가 2개인 숲일 때의 값이다.
    • 간선 20개: 전체가 하나의 트리(연결 그래프)일 때의 값이다.
    • 간선 21개: 간선 수가 노드 수와 같으면 반드시 사이클이 생기므로 숲이 될 수 없다.

    오류나 개정된 내용이 보이면 알려주세요

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    2[7급 서울시 알고리즘] 26년 1회차
    서로 다른 8개의 값에서 두 번째로 큰 값을 항상 찾기 위해 최악의 경우 필요한 최소 비교 횟수로 가장 옳은 것은?
    1
    8
    2
    9
    3
    13
    4
    24
    해설

    최악의 경우 필요한 최소 비교 횟수는 n+⌈log⁡2n⌉−2n+\lceil \log_2 n \rceil-2, 즉 9회다.

    토너먼트 방식으로 최댓값을 찾는 데 n−1=7n-1=7회가 들고, 두 번째로 큰 값은 반드시 최댓값에게 직접 진 값 가운데 있다.

    최댓값은 log⁡28=3\log_2 8=3번 비교에 참여했으므로, 그 3개 중 최댓값을 고르는 데 2회가 더 든다.
    7+2=97+2=9

    • 8회: 최댓값을 찾는 7회에 1회만 더한 값으로, 후보 3개를 가리기에 부족하다.
    • 13회: 최댓값을 찾은 뒤 나머지 7개를 순차 비교한 7+67+6회로, 최소 횟수가 아니다.

    오류나 개정된 내용이 보이면 알려주세요

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    3[7급 서울시 알고리즘] 26년 1회차
    순환식 T(n)=T(n/3)+T(2n/3)+n (n>1), T(1)=1\mathrm{T}(n)=\mathrm{T}(n/3)+\mathrm{T}(2n/3)+n\ (n>1),\ \mathrm{T}(1)=1로 표현되는 알고리즘의 점근적 시간 복잡도로 가장 옳은 것은?
    1
    Θ(n)\Theta(n)
    2
    Θ(nlog⁡n)\Theta(n\log n)
    3
    Θ(n1.5)\Theta(n^{1.5})
    4
    Θ(n2)\Theta(n^{2})
    해설

    점근적 시간 복잡도는 Θ(nlog⁡n)\Theta(n\log n)이다.

    재귀 트리로 펼치면 각 레벨의 비용 합이 n/3+2n/3=nn/3+2n/3=n으로 최대 nn이다.

    가장 짧은 가지의 깊이는 log⁡3n\log_3 n, 가장 긴 가지의 깊이는 log⁡3/2n\log_{3/2} n으로 모두 Θ(log⁡n)\Theta(\log n)이므로, 전체 비용은 레벨당 nn × 깊이 log⁡n\log n이 된다.

    • Θ(n)\Theta(n): 비용 nn인 레벨이 로그 개만큼 쌓이므로 선형보다 크다.
    • Θ(n1.5)\Theta(n^{1.5}): 레벨당 비용이 nn을 넘지 않고 깊이도 로그이므로 지나치게 크다.
    • Θ(n2)\Theta(n^{2}): 레벨당 비용 nn이 로그 깊이만큼만 쌓이므로 제곱에 이르지 않는다.

    오류나 개정된 내용이 보이면 알려주세요

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    4[7급 서울시 알고리즘] 26년 1회차
    이진 트리(binary tree)의 전위 순회(preorder traversal)와 중위 순회(inorder traversal) 결과가 <보기>와 같을 때, 이 트리의 후위 순회(postorder traversal) 결과로 가장 옳은 것은?
    <보기>
    전위 순회: A − B − D − E − C − F
    중위 순회: D − B − E − A − C − F
    1
    D − B − E − C − F − A
    2
    D − E − B − C − F − A
    3
    D − E − B − F − C − A
    4
    E − D − B − F − C − A
    해설

    후위 순회 결과는 D − E − B − F − C − A이다.

    전위 순회의 첫 원소 A가 루트이고, 중위 순회에서 A의 왼쪽 D, B, E가 왼쪽 서브트리, 오른쪽 C, F가 오른쪽 서브트리다.

    왼쪽은 전위가 B, D, E이므로 B가 루트이고 D가 왼쪽, E가 오른쪽 자식이다. 오른쪽은 전위·중위가 모두 C, F이므로 C가 루트이고 F는 C의 오른쪽 자식이다.

    • D − B − E − C − F − A: 왼쪽 서브트리를 중위 순서로 적은 것으로, 후위에서는 B가 D, E 뒤에 와야 한다.
    • D − E − B − C − F − A: 오른쪽 서브트리의 루트 C가 자식 F보다 먼저 나와 후위 순서가 아니다.
    • E − D − B − F − C − A: D가 왼쪽 자식이므로 E보다 먼저 방문해야 한다.

    오류나 개정된 내용이 보이면 알려주세요

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    5[7급 서울시 알고리즘] 26년 1회차
    <보기>의 텍스트 문자열 T와 패턴 문자열 P에 대해 KMP(Knuth-Morris-Pratt) 알고리즘을 수행하여 인덱스 5에서 불일치(mismatch)가 발생하였다. 다음에 비교할 패턴 문자열 P의 인덱스로 가장 옳은 것은? (단, 패턴 문자열 P의 인덱스는 0부터 시작한다.)
    <보기>
    012345678910
    Tababadaabcd
    =====≠
    Pababac
    1
    0
    2
    1
    3
    2
    4
    3
    해설

    다음에 비교할 패턴 인덱스는 3이다.

    불일치 직전까지 일치한 P[0..4] = ababa에서 가장 긴 접두사이자 접미사는 aba로, 길이가 3이다.

    따라서 T의 인덱스 5는 그대로 두고 패턴을 밀어 P[3]부터 비교를 이어 간다.

    • 인덱스 0: 실패 함수를 쓰지 않고 패턴 처음부터 다시 비교하는 단순 매칭의 동작이다.
    • 인덱스 1: 길이 1인 a만 고려한 값으로, 더 긴 aba를 놓친다.
    • 인덱스 2: ab는 ababa의 접미사가 아니므로 경계가 될 수 없다.

    오류나 개정된 내용이 보이면 알려주세요

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    6[7급 서울시 알고리즘] 26년 1회차
    <보기>의 이진 검색 트리(binary search tree)에서 노드를 삭제하는 과정에 대한 설명으로 가장 옳지 않은 것은? (단, 노드 명칭과 노드 키 값은 동일하다.)
    <보기>
    문제 이미지
    1
    루트 노드를 삭제하기 위해 오른쪽 서브트리의 최솟값을 갖는 노드로 대체할 수 있고, 이때의 전체 수행시간은 트리의 높이에 비례한다.
    2
    노드 12를 삭제하기 위해 노드 15에서 노드 12를 가리키는 포인터가 노드 5를 가리키도록 변경한다.
    3
    노드 25를 삭제하기 위해 노드 22로 대체하고, 노드 15에서 노드 25를 가리키는 포인터를 NULL로 변경한다.
    4
    노드 5를 삭제하기 위해 노드 12에서 노드 5를 가리키는 포인터를 NULL로 변경한다.
    해설

    노드 25를 노드 22로 대체할 때 노드 15의 포인터를 NULL로 바꾸는 설명이 옳지 않다.

    자식이 둘인 노드 25는 왼쪽 서브트리 최댓값 22(또는 오른쪽 서브트리 최솟값 35)로 키를 대체한 뒤, 원래 22가 있던 자리를 지워야 한다. 즉 노드 20의 오른쪽 포인터를 NULL로 바꿔야 하며, 15에서 25를 가리키는 포인터를 NULL로 하면 20·22·35까지 트리에서 떨어져 나간다.

    • 루트 15 삭제: 오른쪽 서브트리 최솟값 20을 찾아 대체하는 과정은 한쪽 경로만 따라 내려가므로 수행시간이 트리 높이에 비례한다(옳음).
    • 노드 12 삭제: 자식이 5 하나뿐이므로 부모 15의 왼쪽 포인터가 5를 가리키게 하면 된다(옳음).
    • 노드 5 삭제: 단말 노드이므로 부모 12의 왼쪽 포인터를 NULL로 바꾸면 된다(옳음).

    오류나 개정된 내용이 보이면 알려주세요

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    7[7급 서울시 알고리즘] 26년 1회차
    <보기 1>은 입력 초기 배열 (a)와 이를 오름차순으로 정렬하는 도중의 배열 (b)의 상태를 나타낸다. 이러한 중간 상태가 나타날 수 있는 정렬 알고리즘을 <보기 2>에서 모두 고른 것은? (단, 각 알고리즘은 배열의 앞쪽부터 처리하는 표준적인 방식으로 구현되었다. 중간 상태는 원소의 교환 또는 이동이 진행되는 중간이 아닌 하나의 원소에 대한 처리가 완료된 시점 또는 버블 정렬에서 한 번의 순환(cycle)이 완료된 시점의 상태이다.)
    <보기 1>
    (a) 입력 초기 배열: 3, 2, 1, 6, 5, 4
    (b) 정렬 중간 배열: 1, 2, 3, 6, 5, 4
    <보기 2>
    ㄱ. 삽입 정렬(insertion sort)
    ㄴ. 선택 정렬(selection sort)
    ㄷ. 버블 정렬(bubble sort)
    1
    ㄱ, ㄴ
    2
    ㄱ, ㄷ
    3
    ㄴ, ㄷ
    4
    ㄱ, ㄴ, ㄷ
    해설

    (b)가 나타날 수 있는 것은 삽입 정렬과 선택 정렬이다.

    삽입 정렬은 2를 삽입하면 2, 3, 1, 6, 5, 4가 되고, 이어서 1을 삽입하면 1, 2, 3, 6, 5, 4가 된다.

    선택 정렬은 첫 단계에서 최솟값 1을 맨 앞의 3과 교환하므로 곧바로 1, 2, 3, 6, 5, 4가 된다.

    • 버블 정렬: 첫 순환 후 2, 1, 3, 5, 4, 6, 둘째 순환 후 1, 2, 3, 4, 5, 6이 되어 (b)가 나타나지 않는다.

    오류나 개정된 내용이 보이면 알려주세요

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    8[7급 서울시 알고리즘] 26년 1회차
    이진 힙(binary heap)과 이를 이용한 힙 정렬(heap sort)에 대한 설명으로 가장 옳은 것은? (단, nn은 힙에 저장된 원소의 개수이다.)
    1
    최소 힙에서 최댓값은 O(log⁡n)O(\log n) 시간에 찾을 수 있다.
    2
    삽입식 힙 생성 알고리즘은 입력 순서와 무관하게 Θ(nlog⁡n)\Theta(n\log n) 시간이 필요하다.
    3
    힙 정렬은 별도의 배열 없이 제자리(in-place)에서 수행 가능하지만, 안정(stable) 정렬은 아니다.
    4
    힙 정렬은 O(n)O(n) 시간에 수행 가능하다.
    해설

    힙 정렬은 제자리 정렬이지만 안정 정렬은 아니다.

    힙 정렬은 배열 안에서 루트를 마지막 원소와 교환하고 힙을 재구성하므로 추가 배열이 필요 없지만, 멀리 떨어진 원소끼리 교환하기 때문에 같은 키의 상대 순서가 바뀔 수 있다.

    • 최소 힙의 최댓값: 리프 어디에나 있을 수 있어 리프 전체(약 절반의 원소)를 살펴야 하므로 O(n)O(n)이 든다.
    • 삽입식 힙 생성: 이미 힙 순서로 들어오는 입력이면 삽입마다 상향 이동이 없어 O(n)O(n)에 끝나므로 입력 순서와 무관하지 않다.
    • 힙 정렬의 시간: 비교 기반 정렬이라 Ω(nlog⁡n)\Omega(n\log n) 하한을 넘을 수 없으며 O(nlog⁡n)O(n\log n)이 든다.

    오류나 개정된 내용이 보이면 알려주세요

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    9[7급 서울시 알고리즘] 26년 1회차
    <보기>와 같은 간선(edge)을 갖는 방향 그래프에 대하여 가능한 위상 정렬(topological sort) 결과의 개수로 가장 옳은 것은? (단, 정점은 A, B, C, D, E 5개이다.)
    <보기>
    A→B A→C B→E C→E D→E
    1
    4
    2
    6
    3
    8
    4
    12
    해설

    가능한 위상 정렬은 8가지다.

    E는 B, C, D 모두의 뒤에 와야 하고 A는 B, C보다 앞서야 하므로, E는 항상 마지막이다.

    A, B, C는 A 다음에 B, C가 어느 순서로든 올 수 있어 2가지이고, 제약이 없는 D를 네 자리 중 하나에 끼워 넣으면 된다.
    2×4=82\times 4=8

    • 4가지: B와 C의 순서를 하나로 고정하고 센 값이다.

    오류나 개정된 내용이 보이면 알려주세요

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    10[7급 서울시 알고리즘] 26년 1회차
    그래프에서 최단 경로를 구하는 벨만-포드(Bellman-Ford) 알고리즘에 대한 설명으로 가장 옳지 않은 것은? (단, N은 정점(vertex)의 개수, M은 간선(edge)의 개수이다. 각 정점은 1, 2, …, N으로 번호가 매겨져 있고, 1번이 시작점이다.)
    1
    1번 정점에서 도달 가능한 음의 가중치를 갖는 사이클이 그래프에 존재하는지 여부를 판단하는 데 사용할 수 있다.
    2
    총 N-1번의 라운드로 이루어지며, 라운드 K에서는 정점 1부터 정점 K까지의 최단 경로를 구한다.
    3
    시간 복잡도는 O(NM)이다.
    4
    사이클이 없는 그래프에서 알고리즘이 수행되는 동안, 모든 정점에 대한 거리 추정치는 실제 최단 경로의 거리와 같거나 이보다 크다.
    해설

    옳지 않은 설명은 라운드 K에서 정점 1부터 정점 K까지의 최단 경로를 구한다는 것이다.

    벨만-포드의 각 라운드는 모든 간선을 한 번씩 완화하며, K번째 라운드가 끝나면 간선을 K개 이하로 쓰는 최단 경로가 모든 정점에 대해 확정된다. 정점 번호와는 관계가 없다.

    • 음의 사이클 판별: N−1 라운드 뒤 한 번 더 완화해 값이 줄어드는 정점이 있으면 시작점에서 도달 가능한 음의 사이클이 있다.
    • 시간 복잡도: N−1 라운드마다 간선 M개를 완화하므로 O(NM)이다.
    • 거리 추정치: 추정치는 실제로 존재하는 경로의 길이로만 갱신되므로 항상 실제 최단 거리 이상이다.

    오류나 개정된 내용이 보이면 알려주세요

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    11[7급 서울시 알고리즘] 26년 1회차
    <보기 1>의 가중치 방향 그래프 G에 대해 모든 정점 쌍의 최단 경로를 구하는 플로이드-워셜(Floyd-Warshall) 알고리즘을 수행하는 과정에서 <보기 2>의 행렬 D2D_2를 얻었다. 다음 단계에서 얻을 행렬 D3D_3의 2행으로 가장 옳은 것은? (단, Dk[i, j]D_k[i,\ j]는 정점 ii에서 정점 jj로 가는 경로 중 중간 정점이 모두 1번부터 kk번 사이의 정점인 최단 경로의 길이이고, 그러한 경로가 없으면 ∞이다.)
    <보기 1>
    <보기 2>
    12345
    10411012
    2∞0-3∞8
    3590217
    4∞∞∞03
    5∞∞-1∞0
    D2D_2

    문제 이미지
    1
    (∞, 0, -3, ∞, 8)
    2
    (∞, 0, -3, ∞, 2)
    3
    (2, 0, -3, -1, 8)
    4
    (2, 0, -3, -1, 2)
    해설

    D3D_3의 2행은 (2, 0, -3, -1, 8)이다.

    정점 3을 중간 정점으로 새로 허용하므로 D3[2,j]=min⁡(D2[2,j], D2[2,3]+D2[3,j])D_3[2,j]=\min(D_2[2,j],\ D_2[2,3]+D_2[3,j])이고, D2[2,3]=−3D_2[2,3]=-3, D2D_2의 3행은 (5, 9, 0, 2, 17)이다.

    j=1j=1: min⁡(∞, −3+5)=2\min(\infty,\ -3+5)=2
    j=2j=2: min⁡(0, −3+9)=0\min(0,\ -3+9)=0
    j=4j=4: min⁡(∞, −3+2)=−1\min(\infty,\ -3+2)=-1
    j=5j=5: min⁡(8, −3+17)=8\min(8,\ -3+17)=8

    • 1열과 4열을 ∞로 둔 행: 2→3→1, 2→3→4 경로가 생겨 각각 2, -1로 갱신되어야 한다.
    • 5열을 2로 둔 행: 2→3→5는 14로 기존 8보다 크므로 5열은 8 그대로이다(2는 정점 4를 거치는 다음 단계 값).

    오류나 개정된 내용이 보이면 알려주세요

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    12[7급 서울시 알고리즘] 26년 1회차
    <보기>의 그래프에 대해 다익스트라(Dijkstra) 알고리즘을 이용하여 정점 A에서 다른 모든 정점까지의 최단 경로를 찾으려고 한다. 마지막으로 최단 경로를 찾게 되는 정점으로 가장 옳은 것은? (단, 방문할 수 있는 정점이 둘 이상인 경우, 알파벳 순으로 방문한다.)
    <보기>
    문제 이미지
    1
    C
    2
    D
    3
    H
    4
    I
    해설

    마지막으로 최단 경로가 확정되는 정점은 C이다.

    A에서 시작해 거리가 가장 작은 정점부터 확정하면 F(3), G(4), J(4), E(5), I(6), B(7), D(7), H(7), C(11) 순이다. G와 J, B·D·H처럼 거리가 같으면 알파벳 순으로 방문한다.

    C까지의 최단 거리는 A→B→C(7+4)와 A→G→E→C(4+1+6)가 모두 11로, 나머지 정점의 최단 거리(모두 7 이하)보다 크다.

    • D: A→G→E→D(4+1+2)로 거리 7에 확정되어 C보다 먼저 처리된다.
    • H: A→G→H(4+3)로 거리 7이며, 같은 거리의 B·D 다음에 확정된다.
    • I: A→G→E→I(4+1+1)로 거리 6에 일찍 확정된다.

    오류나 개정된 내용이 보이면 알려주세요

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    13[7급 서울시 알고리즘] 26년 1회차
    <보기>와 같이 입력키와 각각의 검색확률이 주어질 때, 최적의 이진 검색 트리(optimal binary search tree)로 가장 옳은 것은? (단, 최상단 노드가 루트 노드이다.)
    <보기>
    입력키ABCD
    검색확률0.30.40.10.2
    1
    2
    3
    4
    해설

    최적 이진 검색 트리는 루트 B, 왼쪽 자식 A, 오른쪽 자식 D, D의 왼쪽 자식 C인 트리이다.

    평균 비교 횟수는 각 키의 (깊이×검색확률) 합이며, 이 트리는 1(0.4)+2(0.3)+2(0.2)+3(0.1)=1.71(0.4)+2(0.3)+2(0.2)+3(0.1)=1.7로 가능한 트리 중 최소이다. 확률이 큰 B·A를 위에, 가장 작은 C를 가장 아래에 둔 결과이다.

    • 루트 C, B·D가 자식이고 A가 B 아래인 트리: 0.1+2(0.4)+2(0.2)+3(0.3)=2.20.1+2(0.4)+2(0.2)+3(0.3)=2.2
    • 루트 B, A·C가 자식이고 D가 C 아래인 트리: 0.4+2(0.3)+2(0.1)+3(0.2)=1.80.4+2(0.3)+2(0.1)+3(0.2)=1.8로, 확률이 더 큰 D가 더 깊어 손해이다.
    • 루트 C, A·D가 자식이고 B가 A 아래인 트리: 0.1+2(0.3)+2(0.2)+3(0.4)=2.30.1+2(0.3)+2(0.2)+3(0.4)=2.3으로 확률이 가장 큰 B가 가장 깊다.

    오류나 개정된 내용이 보이면 알려주세요

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    14[7급 서울시 알고리즘] 26년 1회차
    로봇 청소기가 청소할 지역들을 표현한 n×nn\times n 크기의 행렬 MM이 있다. <보기>는 4 × 4 크기의 행렬 MM에 대한 예시로, 행렬의 각 원소 Mi,jM_{i,j}는 지역 (i, j)(i,\ j)을 청소했을 때 얻을 수 있는 양의 정수인 청소 점수이다. 한편, 로봇 청소기는 오른쪽이나 아래쪽으로만 이동할 수 있으며, 왼쪽, 위쪽, 대각선 이동은 허용하지 않는다. 로봇 청소기가 지역 (1, 1)에서 청소를 시작하여 지역 (n, n)(n,\ n)에 도착할 때까지, 가장 많은 청소 점수를 얻고자 한다. 동적 프로그래밍(dynamic programming)을 이용하여 이 문제를 해결하기 위한 점화식으로 가장 옳은 것은? (단, 테이블 DD는 동적 프로그래밍을 위한 (n+1)×(n+1)(n+1)\times(n+1) 크기의 테이블이고, Di,jD_{i,j}는 지역 (1, 1)에서 지역 (i, j)(i,\ j)까지 이동하면서 얻을 수 있는 최대 청소 점수의 합이다.)
    <보기>
    행렬 MM
    (예: M3,1=4M_{3,1}=4)
    1234
    15321
    21912
    34281
    41137
    1
    Di,j={0if i=0 or j=0,Mi,j+min⁡(Mi,j−1, Mi−1,j)otherwise.D_{i,j}=\begin{cases}0 & \text{if } i=0 \text{ or } j=0,\\ M_{i,j}+\min(M_{i,j-1},\ M_{i-1,j}) & \textit{otherwise.}\end{cases}
    2
    Di,j={0if i=0 or j=0,Mi,j+max⁡(Mi,j−1, Mi−1,j)otherwise.D_{i,j}=\begin{cases}0 & \text{if } i=0 \text{ or } j=0,\\ M_{i,j}+\max(M_{i,j-1},\ M_{i-1,j}) & \textit{otherwise.}\end{cases}
    3
    Di,j={0if i=0 or j=0,Mi,j+min⁡(Di,j−1, Di−1,j)otherwise.D_{i,j}=\begin{cases}0 & \text{if } i=0 \text{ or } j=0,\\ M_{i,j}+\min(D_{i,j-1},\ D_{i-1,j}) & \textit{otherwise.}\end{cases}
    4
    Di,j={0if i=0 or j=0,Mi,j+max⁡(Di,j−1, Di−1,j)otherwise.D_{i,j}=\begin{cases}0 & \text{if } i=0 \text{ or } j=0,\\ M_{i,j}+\max(D_{i,j-1},\ D_{i-1,j}) & \textit{otherwise.}\end{cases}
    해설

    옳은 점화식은 Di,j=Mi,j+max⁡(Di,j−1, Di−1,j)D_{i,j}=M_{i,j}+\max(D_{i,j-1},\ D_{i-1,j})이다.

    지역 (i, j)에는 왼쪽 (i, j−1)이나 위쪽 (i−1, j)에서만 올 수 있으므로, 두 지역까지의 누적 최대 점수 중 큰 쪽에 현재 지역의 점수를 더한다.

    0행·0열을 0으로 두면 첫 행·첫 열도 같은 식으로 처리된다.

    • M의 이웃 값 중 큰 쪽을 더하는 식: 바로 앞 지역 하나의 점수만 보아 출발점부터 누적된 합을 반영하지 못한다.
    • M의 이웃 값 중 작은 쪽을 더하는 식: 누적 합을 쓰지 않을 뿐 아니라 작은 쪽을 고른다.
    • D의 이웃 값 중 작은 쪽을 더하는 식: 누적 합은 쓰지만 최소 점수 경로를 구하게 된다.

    오류나 개정된 내용이 보이면 알려주세요

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    15[7급 서울시 알고리즘] 26년 1회차
    4 × 4 체스판에 서로 공격할 수 없도록 퀸 4개를 놓는 N-Queens 문제를 백트래킹(backtracking)으로 해결하고자 한다. 다음 <보기>의 조건에 따라 탐색을 진행할 때, 가장 먼저 찾게 되는 해로 가장 옳은 것은?
    <보기>
    (조건1) 좌표 체계는 체스판의 가장 왼쪽 위 칸을 (1행, 1열)로 정의한다. 행 번호는 위쪽에서 아래쪽으로 1부터 4까지, 열 번호는 왼쪽에서 오른쪽으로 1부터 4까지 순서대로 부여된다.
    (조건2) 탐색 순서는 1행부터 4행까지 행 번호가 증가하는 순서대로 퀸을 배치한다.
    (조건3) 후보 시도는 각 행 내에서는 1열부터 4열까지 열 번호가 작은 칸부터 순서대로 퀸 배치를 시도한다.
    (조건4) 퀸은 가로, 세로, 대각선 8방향에 대하여 자기 자신이 위치한 칸을 제외한 모든 칸을 공격할 수 있다. 예를 들어, (1행, 1열)에 위치한 퀸은 (1행, 1열)을 제외하고 1행 전체, 1열 전체, (2행, 2열), (3행, 3열), (4행, 4열)을 공격할 수 있다.
    (조건5) 백트래킹 규칙은 어떤 칸에 퀸을 놓았을 때 이미 배치된 다른 퀸에게 공격받는 위치라면 같은 행의 다음 열을 시도한다. 만약 특정 행에서 4개의 열을 모두 시도했음에도 퀸을 놓을 수 없다면, 직전 행으로 되돌아가(backtrack) 해당 행에 배치된 퀸의 위치를 다음 열부터 다시 탐색한다.
    (조건6) 해는 1행, 2행, 3행, 4행에 놓인 퀸의 열 번호를 순서대로 나열하여 표기한다.
    1
    (1, 2, 3, 4)
    2
    (2, 4, 1, 3)
    3
    (2, 4, 3, 1)
    4
    (3, 1, 4, 2)
    해설

    가장 먼저 찾는 해는 (2, 4, 1, 3)이다.

    1행을 1열에 두면 2행 3열 뒤 3행에 놓을 곳이 없고, 2행을 4열로 옮겨도 3행 2열 뒤 4행에 놓을 곳이 없어 1행 1열로는 해가 없다.

    1행을 2열로 옮기면 2행 4열, 3행 1열, 4행 3열이 차례로 놓여 해가 완성된다.

    • (1, 2, 3, 4): 모든 퀸이 한 대각선 위에 있어 서로 공격한다.
    • (2, 4, 3, 1): 2행 4열과 3행 3열이 대각선으로 맞닿는다.
    • (3, 1, 4, 2): 올바른 해이지만 1행 3열은 1행 2열보다 나중에 시도되므로 그다음에 찾게 된다.

    오류나 개정된 내용이 보이면 알려주세요

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    16[7급 서울시 알고리즘] 26년 1회차
    <보기>는 배열 arr에서 k번째로 작은 원소를 찾는 알고리즘이다. (가), (나)에 들어갈 내용으로 가장 옳게 짝지은 것은? (단, partition(arr, p, r) 함수는 탐색 구역의 시작 인덱스 p부터 끝 인덱스 r 사이에서 피벗(pivot)을 기준으로 피벗보다 작은 원소는 왼쪽으로, 큰 원소는 오른쪽으로 재배치하는 분할을 수행한 후, 피벗의 최종 위치 인덱스를 반환한다.)
    <보기>
    select(arr, p, r, k)
        if p == r
            return arr[p]
        q←partition(arr, p, r)
        i←q - p + 1
        if k == i
            return arr[q]
        else if k < i
            return select(arr, p, q-1,  (가) )
        else
            return select(arr, q+1, r,  (나) )
    1
    (가) k (나) k − i
    2
    (가) k (나) k
    3
    (가) k − i (나) k − i
    4
    (가) k − i (나) k
    해설

    (가)에는 k, (나)에는 k − i가 들어간다.

    i는 피벗이 구간 [p, r]에서 몇 번째로 작은지를 나타내며, 왼쪽 구간 [p, q−1]에는 피벗보다 작은 원소 i−1개가 있다.

    k < i이면 찾는 원소가 왼쪽 구간에 있고 순위도 그대로 k번째다. k > i이면 왼쪽 원소와 피벗을 합한 i개를 건너뛰므로 오른쪽 구간에서는 k − i번째가 된다.

    • (나)에 k: 오른쪽 구간에서는 앞선 i개가 빠졌으므로 순위를 그대로 쓰면 다른 원소를 찾는다.
    • (가)에 k − i: 왼쪽 구간은 시작점이 같아 순위가 줄어들지 않는다.

    오류나 개정된 내용이 보이면 알려주세요

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    17[7급 서울시 알고리즘] 26년 1회차
    연결된 무방향 가중 그래프(G)의 모든 간선의 가중치에 동일한 양수 c를 더하여 새로운 그래프(G′)를 만들었다. G와 G′를 비교하였을 때, 최소 신장 트리(minimum spanning tree)의 변화 여부와 모든 두 정점 간 최단 경로의 변화 여부에 대한 설명으로 가장 옳은 것은?
    1
    최소 신장 트리와 최단 경로가 모두 그대로 유지된다.
    2
    최소 신장 트리는 그대로 유지되지만, 최단 경로는 달라질 수 있다.
    3
    최소 신장 트리는 달라질 수 있지만, 최단 경로는 그대로 유지된다.
    4
    최소 신장 트리와 최단 경로가 모두 달라질 수 있다.
    해설

    최소 신장 트리는 그대로 유지되지만 최단 경로는 달라질 수 있다.

    신장 트리는 항상 간선이 V−1개이므로 모든 신장 트리의 가중치가 똑같이 (V−1)c만큼 늘어 순위가 바뀌지 않는다.

    반면 경로는 간선 수가 제각각이라 간선 k개짜리 경로는 kc만큼 늘어난다. 예컨대 A–B 직접 간선이 3이고 A–C, C–B가 각 1이면 원래는 우회 경로(2)가 최단이지만, c=2를 더하면 직접 간선은 5, 우회 경로는 6이 되어 최단 경로가 직접 간선으로 바뀐다.

    • 둘 다 유지된다: 간선 수가 많은 경로가 더 크게 불리해지므로 최단 경로는 유지되지 않을 수 있다.
    • 최소 신장 트리만 달라진다: 모든 신장 트리가 같은 양만큼 늘어나므로 최소 신장 트리는 바뀌지 않는다.
    • 둘 다 달라질 수 있다: 최단 경로는 맞지만 최소 신장 트리는 바뀌지 않는다.

    오류나 개정된 내용이 보이면 알려주세요

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    18[7급 서울시 알고리즘] 26년 1회차
    곱셈 가능한 4개의 연쇄행렬 A1A2A3A4A_1A_2A_3A_4가 주어졌을 때, 동적 프로그래밍(dynamic programming) 방법으로 최소 곱셈 횟수를 갖도록 연쇄행렬 곱셈(matrix-chain multiplication)의 순서를 찾으려 한다. 1≤i≤j≤41\le i\le j\le 4를 만족하는 i, ji,\ j에 대하여, <보기 1>과 같이 s[i, j]s[i,\ j]에 Ai⋯AjA_i\cdots A_j가 최소 곱셈 횟수를 갖도록 Ai⋯AkA_i\cdots A_k와 Ak+1⋯AjA_{k+1}\cdots A_j로 분할하는 위치 kk를 저장할 때, <보기 2>의 알고리즘으로 출력되는 연쇄행렬 곱셈의 순서로 가장 옳은 것은? (예를 들어, s[1, 2]=1s[1,\ 2]=1)
    <보기 1>
    1234
    1111
    222
    33
    4
    테이블 ss
    <보기 2>
    PRINT(s, i, j)
       if i == j
            print “A”i
       else print “(”
            PRINT(s, i, s[i, j])
            PRINT(s, s[i, j]+1, j)
            print “)”
    1
    (((A1A2)A3)A4)(((A_1A_2)A_3)A_4)
    2
    ((A1(A2A3))A4)((A_1(A_2A_3))A_4)
    3
    (A1((A2A3)A4))(A_1((A_2A_3)A_4))
    4
    (A1(A2(A3A4)))(A_1(A_2(A_3A_4)))
    해설

    출력되는 순서는 (A1(A2(A3A4)))(A_1(A_2(A_3A_4)))이다.

    PRINT(s, 1, 4)는 s[1,4]=1s[1,4]=1이므로 A1A_1과 A2⋯A4A_2\cdots A_4로 나눈다.

    PRINT(s, 2, 4)는 s[2,4]=2s[2,4]=2이므로 A2A_2와 A3A4A_3A_4로 나누고, s[3,4]=3s[3,4]=3으로 A3A_3과 A4A_4가 분리된다. 결국 매번 왼쪽 첫 행렬을 떼어내는 괄호가 된다.

    • (((A1A2)A3)A4)(((A_1A_2)A_3)A_4): s[1,4]=3s[1,4]=3, s[1,3]=2s[1,3]=2일 때의 결과다.
    • ((A1(A2A3))A4)((A_1(A_2A_3))A_4): s[1,4]=3s[1,4]=3, s[1,3]=1s[1,3]=1일 때의 결과다.
    • (A1((A2A3)A4))(A_1((A_2A_3)A_4)): s[2,4]=3s[2,4]=3일 때의 결과다.

    오류나 개정된 내용이 보이면 알려주세요

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    19[7급 서울시 알고리즘] 26년 1회차
    <보기>의 최대 구간합 문제를 재귀 전략을 활용하여 해결하는 방법 중, 계산량을 최소화하여 올바른 값을 구하는 방법으로 가장 옳은 것은?
    <보기>
    [최대 구간합 문제]
    Input: 크기가 n인 정수 배열 A (시작 인덱스는 0)
    Output: 배열 A의 부분 배열 구간합 중 최댓값
    예시) 크기가 3인 정수 배열
    -12-3
    의 Output는 2이다.
    * 부분 배열 A[i..j]( 0≤i≤j<n) 구간합: 연속한 부분 배열에 포함된 모든 원소의 합, 즉 A[i]+A[i+1]+…+A[j]를 의미한다.
    * 재귀 전략: 배열 A를 전반부 A[0..m−1]과 후반부 A[m..n−1]로 나누어 해결한다. (m = ⌊n/2⌋\lfloor n/2 \rfloor ) (단, n=1이면, A[0]을 반환한다.)
    1
    전반부의 최대 구간합 a와 후반부의 최대 구간합 b를 재귀적으로 구하고, max(a, b)를 취한다.
    2
    전반부의 최대 구간합 a와 후반부의 최대 구간합 b를 재귀적으로 구하고, max(a, b, a+b)를 취한다.
    3
    전반부의 최대 구간합 a와 후반부의 최대 구간합 b를 재귀적으로 구하고, 시작 위치가 전반부에 있고 끝 위치가 후반부에 있는 모든 부분 배열의 구간합을 각각 계산하여 그중 최댓값 c를 구한 후, max(a, b, c)를 취한다.
    4
    전반부의 최대 구간합 a와 후반부의 최대 구간합 b를 재귀적으로 구하고, 전반부에서 A[m-1]을 마지막 원소로 하는 부분 배열의 최대 구간합 c와 후반부에서 A[m]을 첫 원소로 하는 부분 배열의 최대 구간합 d를 각각 구한 후, max(a, b, c+d)를 취한다.
    해설

    올바르면서 계산량이 가장 적은 방법은 경계를 가로지르는 최대합을 c+d로 구하는 분할 정복이다.

    최대 구간은 전반부 안, 후반부 안, 또는 경계를 가로지르는 경우 중 하나다. 가로지르는 구간은 A[m−1]에서 끝나는 왼쪽 부분과 A[m]에서 시작하는 오른쪽 부분의 합이므로, 각각을 선형 시간에 최대화해 더하면 된다.

    점화식이 T(n)=2T(n/2)+O(n)T(n)=2T(n/2)+O(n)이 되어 O(nlog⁡n)O(n\log n)이다.

    • max(a, b): 경계를 가로지르는 구간을 고려하지 않아 틀린 값이 나올 수 있다.
    • max(a, b, a+b): a와 b의 구간이 붙어 있지 않을 수 있어 a+b는 실제 구간합이 아니다.
    • 가로지르는 모든 부분 배열을 계산: 값은 올바르지만 단계마다 O(n2)O(n^2)이 들어 계산량이 크다.

    오류나 개정된 내용이 보이면 알려주세요

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.
    20[7급 서울시 알고리즘] 26년 1회차
    NP-완비(complete) 이론에 대한 설명으로 가장 옳지 않은 것은?
    1
    문제 A가 어떤 알려진 NP-하드(hard) 문제 B로 다항 시간 내 환원된다면 문제 A는 NP-하드이다.
    2
    N개의 노드, M개의 간선이 있는 그래프의 최소 신장 트리를 찾는 문제는 NP에 속한다.
    3
    NP-complete에 속하는 문제 중 하나를 푸는 다항식 시간 알고리즘이 발견된다면 P=NP가 된다.
    4
    무방향 해밀토니안 사이클(Hamiltonian-cycle) 문제는 NP에 속한다.
    해설

    옳지 않은 설명은 A가 NP-하드 문제 B로 환원되면 A가 NP-하드라는 것이다.

    환원 방향이 반대다. 알려진 NP-하드 문제 B를 A로 다항 시간에 환원할 수 있어야 A가 B만큼 어렵다고 할 수 있으며, A를 B로 환원하는 것은 A가 B보다 어렵지 않다는 뜻일 뿐이다.

    • 최소 신장 트리: 크루스칼·프림 알고리즘으로 다항 시간에 풀리는 P 문제이고, P는 NP에 포함되므로 NP에 속한다.
    • NP-완비 문제의 다항 시간 해법: 모든 NP 문제가 그 문제로 다항 시간 환원되므로 P=NP가 된다.
    • 해밀토니안 사이클: 주어진 정점 순서가 해밀토니안 사이클인지 다항 시간에 검증할 수 있으므로 NP에 속한다.

    오류나 개정된 내용이 보이면 알려주세요

    메모
    아직 메모가 없어요. 위 버튼으로 첫 메모를 남겨보세요.

[7급 서울시 알고리즘] 26년 1회차 시험지 PDF 다운로드·인쇄 →

[7급 서울시 알고리즘] 26년 1회차 정답과 해설은 무료인가요?

이 페이지의 20문항 정답과 해설은 로그인 없이 무료로 볼 수 있습니다. 무제한 풀이·실전 모의고사·PDF 출력·전자책 다운로드는 베이직 플랜에 포함됩니다.

이 회차를 CBT 로 직접 풀어볼 수 있나요?

7급 서울시 알고리즘 기출문제 암기장에서 이 회차를 회차별·랜덤으로 풀고 오답노트에 자동으로 모을 수 있습니다. 7급 서울시 알고리즘 기출문제 풀러 가기 →

시험지 PDF 나 전자책으로도 볼 수 있나요?

이 회차의 인쇄용 시험지 PDF 페이지에서 시험지를 받을 수 있습니다. 시험지 PDF 받기 →

[7급 서울시 알고리즘] 26년 1회차 문항별 상세 페이지 전체 보기