0. 사전 조사(자료구조)
자료구조는 데이터를 효율적으로 관리하고 처리하기 위한 방법이다.
- 자료구조의 종류
단순 자료구조: int, float, char 등 프로그래밍 언어에서 통상적으로 제공되는 기본 데이터 형식이다.
선형 자료구조
배열(Array): 동일한 타입의 데이터를 연속적으로 저장하는 자료구조로, 인덱스를 통해 빠르게 접근할 수 있다.
연결 리스트(Linked List): 각 노드가 데이터와 다음 노드를 가리키는 포인터로 구성된 자료구조로, 메모리를 효율적으로 사용할 수 있다.
스택(Stack): 후입선출(LIFO) 방식으로 데이터를 저장하고 처리하는 자료구조이다.
큐(Queue): 선입선출(FIFO) 방식으로 데이터를 저장하고 처리하는 자료구조이다.
비선형 자료구조
트리(Tree): 계층적 구조로 데이터를 표현하는 자료구조로, 이진 트리와 일반 트리로 나뉜다.
그래프(Graph): 노드와 간선으로 구성되어 데이터 간의 관계를 표현하는 자료구조이다.
정적 자료구조
배열(Array)과 같이 크기가 고정된 자료구조이다.
동적 자료구조
연결 리스트(Linked List)와 같이 크기가 동적으로 변경될 수 있는 자료구조이다.
세부 설명
- 선형 자료구조
배열(Array): 동일한 타입의 데이터를 연속적으로 저장하는 자료구조로, 인덱스를 통해 빠르게 접근할 수 있다. 크기가 고정되어 있어 동적으로 변경하기 어렵다.
연결 리스트(Linked List): 각 노드가 데이터와 다음 노드를 가리키는 포인터로 구성된 자료구조로, 메모리를 효율적으로 사용할 수 있다. 크기가 동적으로 변경될 수 있다.
스택(Stack): 후입선출(LIFO) 방식으로 데이터를 저장하고 처리하는 자료구조이다. 데이터를 추가하고 삭제하는 연산이 빠르다.
큐(Queue): 선입선출(FIFO) 방식으로 데이터를 저장하고 처리하는 자료구조이다. 데이터를 추가하고 삭제하는 연산이 빠르다.
- 비선형 자료구조
비선형 자료구조는 데이터 간의 관계가 복잡한 형태이다. 대표적인 비선형 자료구조로는 트리와 그래프가 있다.
트리(Tree): 계층적 구조로 데이터를 표현하는 자료구조로, 이진 트리와 일반 트리로 나뉜다. 이진 트리는 각 노드가 최대 2개의 자식 노드를 가지며, 일반 트리는 자식 노드의 개수에 제한이 없다.
그래프(Graph): 노드와 간선으로 구성되어 데이터 간의 관계를 표현하는 자료구조이다. 방향 그래프와 무방향 그래프로 나뉜다.
정적 자료구조
프로그램 실행 시 미리 정해진 크기의 메모리 공간을 할당받는다.
크기가 고정되어 있어 실행 중에 크기를 변경할 수 없다.
대표적인 예로 배열(Array)이 있다.
데이터 접근이 빠르지만, 크기 변경이 어렵다는 단점이 있다.
동적 자료구조
프로그램 실행 중에 메모리 공간의 크기를 동적으로 변경할 수 있다.
데이터 추가/삭제 시 메모리 공간을 자동으로 조절한다.
대표적인 예로 연결 리스트(Linked List)가 있다.
크기 변경이 유연하지만, 데이터 접근이 상대적으로 느리다.
1. 문제 링크
https://www.acmicpc.net/problem/3015
3015번: 오아시스 재결합
첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람
www.acmicpc.net
2. 문제 선정 과정 및 문제 내용
4월 과제는 자료구조를 활용한 도전적인 문제 해결이었다. 이를 위해 나는 백준에서 자료 구조를 활용하여 해결할 수 있는 문제를 찾아보았고, 정답률이 50% 이하인 문제 중 본 문제가 간단하지만 까다로운 부분이 많을 것 같아서 선정하게 되었다. 또한 스택이라는 자료구조를 활용하는 문제를 아직 풀어본 적이 없었는데 시도해보고 싶어서 본 문제를 선정하기도 했다. (평소 오아시스 노래를 즐겨 들어서 컨셉에 이끌려 선정하기도 했다)
문제 내용
문제:
오아시스의 재결합 공연에 N명이 한 줄로 서서 기다리고 있다.
이 역사적인 순간을 맞이하기 위해 줄에서서 기다리고 있던 백준이는 갑자기 자기가 볼 수 있는 사람의 수가 궁금해 졌다.
두 사람 A와 B가 서로 볼 수 있으려면, 두 사람 사이에 A 또는 B보다 키가 큰 사람이 없어야 한다.
줄에 서있는 사람의 키가 주어졌을 때, 서로 볼 수 있는 쌍의 수를 구하는 프로그램을 작성하시오.
입력:
첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000)
둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다.
사람들이 서 있는 순서대로 입력이 주어진다.
출력:
서로 볼 수 있는 쌍의 수를 출력한다.
3. 사용한 문제 풀이 전략
본 문제는 시간 초과가 안 나게 해결하는 것이 매우 까다로운 문제였다. 그냥 키를 입력받고 순회한다면 O(n^2)의 시간 복잡도가 나오겠지만 n이 500,000까지 갈 수 있었기 때문에 시간 초과가 발생할 것이다. 따라서 시간 초과 문제를 막기 위해 스택 자료구조를 사용하여 효율적인 데이터 처리를 위한 알고리즘을 세웠다.
3 - 1. 스택
스택: 한쪽 끝에서만 데이터를 넣고 뺄 수 있는 제한적으로 접근할 수 있는 후입선출(Last-In-First-Out) 형태의 선형 자료구조이다.
스택의 가장 큰 특징은 바로 이 후입선출 구조이다. 아래 그림을 보면 후입선출 구조를 보다 잘 이해할 수 있을 것이다.
위의 그림을 보면 가장 나중에 들어온 c가 가장 먼저 나오고, 가장 먼저 들어온 a가 가장 마지막에 나오는 후입선출 구조를 쉽게 이해할 수 있다.
이런 스택에서 알아두어야 할 용어가 몇 가지 있다. 먼저 Bottom은 가장 밑에 있는 데이터 또는 인덱스를 의미하며, 위 그림에서는 a가 Bottom이라고 할 수 있겠다. Top은 가장 위에 있는 데이터 또는 인덱스를 의미하며, 위 긔림에서는 c가 Top이다. 또한 스택은 pop()이라는 연산을 사용하는데, 이는 스택에서 가장 위에 있는 항목을 제거하고 그 항목을 반환하는 것이다. Python에서는 리스트에 적용시킬 수 있는 동명의 연산이 있어 스택을 리스트로 쉽게 구현할 수 있다. 또 다른 연산은 push(item)이라는 연산으로, 이는 item 하나를 스택의 가장 윗 부분에 추가하는 연산을 말한다.
그럼 지금부터 파이썬으로 스택을 구현하는 방법에 대해 알아보자. 파이썬에서는 앞서 언급한 것과 같이 리스트로 스택을 표현할 수 있다. 따라서 스택 자료 구조를 초기화할 때는 빈 리스트를 만들어준다.
stack = []
스택에 push 연산을 통해 원소를 넣을 때에는 append 메서드를 이용해 리스트의 가장 마지막에 원소를 넣을 수 있다.
stack = [1,2,3]
stack.append(4)
print(stack) #[1,2,3,4]
스택에서 원소를 제거할 때에는 pop 매소드를 이용해 리스트의 가장 마지막 원소를 제거해주며, 이때 pop 메서드에 의해 제거한 원소를 리턴받을 수 있다.
stack = [1,2,3]
top = stack.pop()
print(top) #3
print(stack) #[1,2]
스택에서 원소를 제거하지 않고 가져오기만 할 때에는 [-1](-1번째 인덱스)를 이용하면 된다.
stack = [1,2,3]
top = stack[-1]
print(top) #3
3 - 2. 문제에 스택 자료구조 적용
본격적으로 문제에 적용하기 전에, 본 문제는 시간 제한이 엄격하기 때문에 여러 줄로 된 입력을 그냥 input으로 받을 경우 시간 초과가 날 우려가 있다. (실제로 코드를 모두 올바르게 작성해도 시간 초과가 발생했다.) 따라서 이를 방지하기 위해 다음과 같은 코드를 맨 앞줄에 추가해주어야 한다.
import sys
input = sys.stdin.readline
1. 스택 정의: 본 문제에 스택을 적용하기 위해서는 빈 리스트를 정의하고, 사람들의 키가 입력되면 이를 받아서 데이터를 저장해야 한다. 우리는 본 문제에서 스택에 '다른 사람들과 매칭이 될 가능성이 있는 사람들' 만 남겨놓을 것이다.
n = int(input()) #사람 수 입력받음
stack = [] #스택 정의
answer = 0 #답; 경우의 수를 카운트할 변수
이후 중요하게 생각할 것이 스택에 저장할 데이터의 형태이다. 본 문제를 해결하기 위해서는 스택에 [(키),(그 키가 중복되어서 나온 횟수)]로 된 리스트를 추가해야 한다. 그래야 업데이트를 하면서 중복되는 키가 나올 경우를 건너뛰지 않고 셀 수 있기 때문이다. 본 내용은 뒤에 짜려고 하는 알고리즘의 방식을 더 살펴보면 이해할 수 있을 것이다.
2. 새로운 키가 기존의 키보다 클 경우: 스택에 기존에 들어있을 데이터와 새롭게 입력받은 데이터 사이의 관계를 잘 따져야 한다. 새로운 사람의 키가 마지막으로 스택에 넣은 top보다 더 클 경우, 작을 경우, 같을 경우로 나눠서 문제를 해결해보자. 먼저 클 경우는 현재 키(now) 이후에 들어올 사람들이 더 이상 top과 매칭이 되지 못한다. 따라서 top 값은 더이상 스택에 남아있을 필요가 없으므로 pop 연산을 시행한다. 이때, now가 top보다 크지 않게 될 때까지 본 연산을 시행한다. 이때 답(answer)에 top값이 중복되어서 나온 횟수를 더해준다. 이는 now와 top이 매칭될 수 있는 경우의 수를 고려하는 것이다.
for i in range(n):
h = int(input()) #사람 수만큼 키 입력받기
while stack and h > stack[-1][0]: #스택이 비어있다면 비교가 불가능한 것 고려
answer += stack.pop()[1] #now값이 top보다 클 경우 pop 시행, answer update
3. 새로운 키가 기존의 키와 같을 경우: 이 경우가 중복이 되지 않기 위해서 고려해야 하는, 알고리즘을 구상할 때 떠올리기 어려운 가장 중요한 부분이다. 일단 먼저 answer에 top값이 나왔던 횟수를 더해준다. 본 문제에서 키가 같은 사람들끼리도 매칭이 될 수 있기 때문이다. 이후 top값이 한번 더 나온 것이므로 중복해서 나왔던 횟수에 1을 더해준다. 이후, 만약 top값 앞에 또다른 요소가 스택에 저장되어 있었다면 now와 그 요소도 매칭될 수 있는 것이므로, answer에 추가적으로 1을 더해준다.
if h == stack[-1][0]:
answer += stack[-1][1]
stack[-1][1] += 1
if len(stack) > 1:
answer += 1
4. 새로운 키가 기존의 키보다 작을 경우: 이 경우에는 top와 now가 매칭이 되고, 그리고 뒤의 다른 사람들의 키들과 top과 now가 모두 매칭될 수 있으므로 answer에 1을 더하고 stack에 now를 넣어준다.
else:
answer += 1
stack.append([h,1])
5. 스택이 비어있을 경우: 2번에서는 스택이 비어있을 경우도 고려했지만 3,4번에서는 고려하지 않았으므로 스택이 비어있을 경우에는 그냥 now값을 스택에 추가하고 넘어가도록 if-else 문을 구성한다.
위 모든 과정을 고려한 전체 코드는 다음과 같다.
import sys
input = sys.stdin.readline
n = int(input())
stack = []
answer = 0
for i in range(n):
h = int(input())
while stack and h > stack[-1][0]:
answer += stack.pop()[1]
if stack:
if h == stack[-1][0]:
answer += stack[-1][1]
stack[-1][1] += 1
if len(stack) > 1:
answer += 1
else:
answer += 1
stack.append([h,1])
else:
stack.append([h,1])
print(answer)
4. 시행착오
본 문제는 그냥 처음 봤을 때는 O(n^2)으로 반복문을 돌리면 될 것 같은데 왜 플래티넘이지 의문이 들었었다. 그러나 플래티넘이 플래티넘인 데에는 다 이유가 있었다. 시간 제한이 상당히 엄격했다. 그래서 스택이라는 자료 구조를 적용해서 최대한 O(n)으로 풀기 위해 노력했다. 그 과정에서 같은 키가 들어왔을 때의 중복을 고려하지 못했어서 틀린 답을 내놓기도 했었다. 스택에 그냥 사람들의 키만 입력받는 게 아니라 그 키가 나온 횟수까지 입력받는 생각을 하는 것이 정말 어려웠다. 또 어려웠던 부분은 자꾸 시간 초과가 발생했던 부분이었다. 분명 코드도 맞게 짜고 테스트 케이스를 만들어서 검증해봐도 잘 돌아가는데, 자꾸 시간 초과가 발생했었다. 알고보니 파이썬에서 여러 줄로 된 입력을 받을 때 시간 초과를 막기 위해 사용하는 "sys.stdin.readline"를 사용하지 않아서 발생한 문제였고, 이를 수정하여 문제를 해결할 수 있었다.
5. 느낀점
본 문제를 풀어보면서 스택이라는 자료구조에 대해 공부하게 되었는데, 자료구조 자체는 매우 어렵지 않고 특히 파이썬에서는 리스트로 쉽게 구현할 수 있었으나 이를 활용하여 알고리즘에 적용시키는 부분이 정말 어렵다는 것을 느꼈다. 간단한 자료구조가 이렇게 사용되어 시간 복잡도를 혁명적으로 줄일 수 있다는 것에 다시 한번 자료구조의 중요성을 느꼈기도 했다. 스택을 활용한 다른 도전적인 알고리즘 문제도 풀어보고 싶다.
'AP프로그래밍과 문제해결' 카테고리의 다른 글
| 5. [Python] 나만의 문제 설계하기 (1) | 2024.07.01 |
|---|---|
| 4. [Python] 객체지향 프로그래밍: One-card game (1) | 2024.06.09 |
| 3. [Python] BOJ 2014 소수의 곱 (1) | 2024.05.01 |
| 1. [Python] BOJ 2243 사탕상자 (2) | 2024.03.17 |
