[전산직(데이터) 공무원 대비] 알고리즘 기초부터 파헤치기 2

본격적인 알고리즘(정렬, 탐색 등)으로 들어가기 전에, 이미 알고 있겠지만 살짝 훑어보는 느낌으로 선형 자료구조를 정리하고 넘어가려 한다. (비선형 자료구조는 뒤에 정리)

 

시험에는 "이 상황에서 어떤 자료구조를 쓰는 게 효율적인가?"를 묻거나, 스택/큐의 연산 순서를 추적하는 문제가 출제된다.

1. 선형 자료구조 (배열 vs 연결 리스트)

자료구조의 가장 기본인 배열(Array)과 연결 리스트(Linked List)를 비교해보자.

핵심 이론: 한 눈에 비교

특징	배열 (Array)	연결 리스트 (Linked List)
메모리 구조	연속된 공간에 할당 (밀집)	흩어진 공간을 포인터로 연결 (분산)
메모리 효율	공간 낭비 적음 (데이터만 저장)	공간 낭비 있음 (포인터 별도 저장 공간 필요)
접근 속도	$O(1)$ (인덱스로 즉시 접근)	$O(n)$ (첫 노드부터 순차 탐색)
삽입/삭제	$O(n)$ (데이터를 밀거나 당겨야 함)	$O(1)$ (링크만 끊고 연결하면 됨, 위치 아는 경우)
크기	고정적 (생성 후 변경 불가)	동적 (필요할 때마다 늘림)
활용	데이터 조회가 많고 데이 크기가 고정될 때	데이터 삽입/삭제가 빈번할 때

 

1-1. 최신 기출 맛보기

문제 1. 선형 자료구조 비교

단일 연결 리스트(Singly Linked List)와 비교할 때, 배열(Array)의 장점에 해당하는 것만 모두 고른 것은?

ㄱ. $i$번째 원소에 접근하는 시간이 빠르다.

ㄴ. 원소의 삽입과 삭제가 번거롭지 않고 빠르다.

ㄷ. 연속된 메모리 공간을 사용하므로 공간 지역성(Locality)이 좋다.

ㄹ. 메모리를 동적으로 할당하여 낭비가 없다.

1. ㄱ, ㄷ
2. ㄱ, ㄹ
3. ㄴ, ㄷ
4. ㄴ, ㄹ

정답: 1번

 

• ㄱ (O): 배열은 인덱스를 알면 $O(1)$만에 즉시 접근(Random Access) 가능
• ㄷ (O): 메모리 상에 데이터가 붙어 있어 캐시 적중률(Cache Hit Ratio)이 높음 (공간 지역성)
• ㄴ (X): 배열 중간에 삽입/삭제하려면 뒤의 데이터를 모두 밀거나 당겨야 해서 $O(n)$이 걸림 (연결 리스트가 $O(1)$로 유리)
• ㄹ (X): 배열은 선언 시 크기가 고정되는 '정적 할당' (꽉 차면 더 못 넣음) 반면, 연결리스트는 '동적 할당' (필요할 때 생성하기 때문에 메모리 낭비 적음)

 

 

2. 선형 자료구조의 응용 스택(Stack)과 큐(Queue)

데이터의 입출력 순서나 포인터(Top, Front, Rear)의 이동을 묻는 문제가 주로 나온다.

(1) 스택 (Stack): LIFO (Last-In, First-Out)

• 개념: "나중에 들어간 놈이 먼저 나온다." (후입선출)
• 비유: 프링글스 통, 쌓여있는 종이컵
• 구조: 한쪽 끝(Top)에서만 삽입과 삭제 발생
• 핵심 연산 ($O(1)$):
  • Push(x): Top 위에 데이터 쌓기
  • Pop(): Top에 있는 데이터 꺼내기
• 활용:
  • 재귀 함수(Recursion)의 호출 관리
  • 웹 브라우저 '뒤로 가기'
  • 괄호 검사 (()()) (짝 맞추기)
  • 후위 표기식(Postfix) 계산
• 주의: 꽉 찼는데 더 넣으면 Overflow, 비었는데 꺼내면 Underflow.

 

(2) 큐 (Queue): FIFO (First-In, First-Out)

• 개념:  "먼저 들어간 놈이 먼저 나온다." (선입선출)
• 비유: 식당 대기 줄, 프린터 인쇄 대기열
• 구조: 뒤(Rear)로 들어와서 앞(Front)으로 나갑니다.
• 핵심 연산 ($O(1)$):
  • Enqueue(x): 줄 맨 뒤에 세움 ($\text{Rear} = \text{Rear} + 1$)
  • Dequeue(): 줄 맨 앞 사람을 내보냄 ($\text{Front} = \text{Front} + 1$)

• 활용:
  • 운영체제의 프로세스 스케줄링
  • BFS (너비 우선 탐색) 알고리즘
  • 버퍼(Buffer)

 

(3) 원형 큐 (Circular Queue)🚨

공무원 시험에 나오는 큐는 90%가 '원형 큐'라고 한다.

선형 큐는 데이터를 꺼내면 앞쪽 공간이 비어서 낭비되는데, 이를 해결하기 위해 배열의 끝과 시작을 이어 붙인 형태이다.

• 인덱스 계산 공식 (암기 필수!)
  • 초기 상태: Front = Rear = 0
  • 인덱스 계산: 다음 위치 = (현재위치 + 1) % 배열크기 (나머지 연산 MOD 사용)
  • 데이터 삽입 (Enqueue): Rear = (Rear + 1) % N 하고 저장
  • 데이터 삭제 (Dequeue): Front = (Front + 1) % N 하고 삭제
  • 포화(Full) 상태: (Rear + 1) % size == Front
  • 공백(Empty) 상태: Front == Rear

 

2-1. 최신 기출 맛보기

문제 1. 스택과 큐 동작

크기가 충분한 스택(S)과 큐(Q)가 있다. 다음 연산을 순서대로 수행했을 때, 최종적으로 출력되는 값의 순서는?

1. S.push(A)
2. S.push(B)
3. Q.enqueue(C)
4. Q.enqueue(D)
5. S.pop() -> 출력
6. Q.enqueue(S.pop())
7. Q.dequeue() -> 출력
8. Q.dequeue() -> 출력

 

1. B, C, A
2. B, C, D
3. A, C, D
4. B, D, A

정답: 2번

• 4번까지의 스택과 큐 상태: S: [A, B] / Q: [C, D]
• 5번: S.pop() → B 출력 (S: [A])
• 6번: S.pop() → A 반환, Q에 삽입 → S: [] / Q: [C, D, A]
• 7번: Q.deq() → C 출력 (Q: [D, A])
• 8번: Q.deq() → D 출력 (Q: [A])

 

문제 2. 원형 큐 인덱스 계산

크기가 5인 배열 Q[0...4]를 사용하는 원형 큐가 있다. 초기에 Front = 0, Rear = 0인 상태에서 다음 연산을 수행했을 때, 최종적인 Front와 Rear의 값은?

연산 순서:

1. Enqueue(A)
2. Enqueue(B)
3. Dequeue()
4. Enqueue(C)
5. Enqueue(D)
6. Dequeue()
7. Enqueue(E)

1. Front: 1, Rear: 3
2. Front: 2, Rear: 0
3. Front: 2, Rear: 4
4. Front: 3, Rear: 1

(힌트) 배열 크기가 5이므로 인덱스는 4를 넘어가면 다시 0이 된다.

 

정답: 2번

1. 초기 상태: F=0, R=0
2. Enq(A): R이 1 증가 $\rightarrow$ R=1
3. Enq(B): R이 1 증가 $\rightarrow$ R=2
4. Deq(): F가 1 증가 $\rightarrow$ F=1 (A 삭제)
5. Enq(C): R이 1 증가 $\rightarrow$ R=3
6. Enq(D): R이 1 증가 $\rightarrow$ R=4 (배열 끝 도달!)
7. Deq(): F가 1 증가 $\rightarrow$ F=2 (B 삭제)
8. Enq(E): R이 1 증가해야 하는데, (4 + 1) % 5 = 0이 되므로 $\rightarrow$ R=0 (뱅글 돌아감)

$\therefore$ 최종 결과: Front: 2, Rear: 0

 

[나의 오답노트]

R은 항상 다음 값이 들어올 자리에 가있다는 것을 잊지 말기!

새로운 값을 입력하고 옆자리로 R이 이동하는 것까지 마무리해야 한다.

 

문제 3. 수식 표기법 변환 (중위 -> 후위)

다음 중위 표기식을 후위 표기식으로 바르게 변환한 것은?

$$A * (B + C) - D$$

1. $A B C + * D -$
2. $A B + C * D -$
3. $A B C * + D -$
4. $A * B C + D -$

(힌트) 우선순위: 괄호 > 곱셈/나눗셈 > 덧셈/뺄셈. 스택에는 연산자가 들어가고, 피연산자는 바로 출력한다.

 

정답: 1번

$A * (B + C) - D$의 변환 과정 추적
우선순위: 괄호 > * > + , -

읽은 문자	스택 상태 (Top은 오른쪽)	출력(결과)	설명
A		A	피연산자는 바로 출력
*	*	A	스택이 비었으니 Push
(	* (	A	괄호 시작은 무조건 Push
B	* (	A B	피연산자 출력
+	* ( +	A B	괄호 안에서 + Push
C	* ( +	A B C	피연산자 출력
)	*	A B C +	괄호 끝! ( 만날 때까지 팝(Pop)
-	-	A B C + *	-가 들어가려는데, Top(*)이 더 셈. 강한 놈(*) 먼저 내보내고(Pop) 입장.
D	-	A B C + * D	피연산자 출력
끝		A B C + * D -	남은 - 팝

 

다음 포스팅에서는 정렬(Sorting)과 검색(Searching)을 정리해 보겠다.