비전공자를 위한 알고리즘 강의 2부 - 자료구조 큐, 스택, 덱

이번시간에는 자료구조에 대해 알아보겠습니다.

 

알고리즘 문제를 풀기 위해서는 자료구조를 활용하는것이 몹시 중요합니다.

 

여러분은 다음과 같은 내용의 자료구조를 알고 사용법에 대해 아시면 됩니다.

 

 

Queue

Stack

Deque

Set

Map

Priority Queue

 

이 글에서는 가장 쉬운 자료구조인 Queue, Stack, Deque에 대해 알아보고 1부에서 나왔던 옥상정원 문제를 Stack을 이용하여 풀어보겠습니다!

 

0. 개요

 

먼저 알고리즘 문제를 풀 때 자료구조가 무슨 역할을 하는지 왜 중요한지에 대해 설명드리겠습니다.

 

자료구조란 일단 배열처럼 데이터를 담는 그릇이라고 생각하시면 됩니다.

단, 데이터를 담을때 특정한 규칙을 가지고 있습니다.

 

그리고 앞서 1부에서 강의했던것 처럼 자료구조를 이용하면 O(N^2)이 걸리는 알고리즘을 O(NlogN)이나 O(N) 의 형태로 바꿀 수 있습니다.

 

이러한 이유로 자료구조 사용법에 대해 익혀놔야 합니다.

 

 

1. Queue

 

 

큐는 데이터를 위의 그림처럼 데이터를 한 방향으로 담는 자료구조입니다.

 

Queue안에 데이터를 넣을때 Push 라고 하며 꺼낼때는 Pop 이라고 합니다.

 

먼저 들어간 데이터가 먼저 나온다 하여 선입선출(First input First Out, FIFO) 라고 불립니다.

 

 

큐를 사용할때 세가지 동작만 기억하시면 됩니다.

 

• 푸시 : 큐에다가 데이터를 넣습니다.
• 맨 앞 값 꺼내기 : 큐에서 맨앞의 데이터를 읽어오기, pop을 하지 않으므로 큐의 데이터가 보존됨
• 팝 : 큐의 맨앞 데이터를 pop, 큐의 맨앞 데이터가 큐에서 꺼내져 나오므로 데이터를 잃는다.

 

c++

c++의경우 stl의 queue 클래스를 이용합니다.

push(), front(), pop() 함수를 사용합니다.

 

push() => 푸시

front() => 큐의 맨 앞 값 읽어오기

pop()  => 팝

#include<iostream>
#include<queue>

queue<int> q;

int main{
    q.push(1); // 큐에다 데이터를 푸시
    int a = q.front(); // 큐에 들어간 맨앞 데이터를 꺼내옴
    q.pop(); // 큐에서 데이터를 팝
}

 

Java

java의 경우 LinkedList를 이용하여 큐를 구현합니다.

offer(), peek(), poll() 메소드를 이용합니다. 

 

offer() => 푸시

peek() => 큐의 맨 앞 값 읽어오기

poll()  => 팝

import java.util.LinkedList;
import java.util.Queue;

Queue<Integer> que = new LinkedList<Integer>();

q.offer(1); // 큐에다가 push
q.peek(); // 큐의 제일 앞에 값을 꺼내옴
q.poll(); // 큐를 pop

 

파이썬

파이썬의 경우 리스트를 이용하여 큐를 구현합니다.

q = []

q.append(1) // 큐에다 push
q[0] //큐의 맨앞 데이터 꺼내오기
q.popleft() // 큐를 팝

 

2. Stack

다음은 Stack에 대해 배워보겠습니다.

 

 

앞에서 배운 큐가 마치 기다란 막대의 뒷구멍에 무언가를 쑤셔 넣고 앞에 있는 구멍으로 나오는 느낌이라면

스택은 마치 책을 쌓는다는 느낌으로 생각하시면 됩니다. 쌓으니깐 Stack이라는 단어를 사용한거죠!

 

스택을 다른표현으로 LIFO 라고 합니다. Last Input First Out, 가장 늦게들어온 놈이 가장 먼저나간다.

그림으로 보면 2번 데이터가 가장 늦게 들어왔는데 팝 하니 가장 먼저나가지요?

 

 

형태만 다를뿐 사용법은 큐와 비슷합니다.

 

동작 세가지만 기억하세요.

 

• 푸시 : 스택에다가 데이터를 쌓습니다.
• 맨 위의 값 꺼내기 : 스택의 가장 위에있는 값을 읽습니다. pop은 하지않고 데이터는 보존됩니다.
• 팝 : 스택의 맨 위의값을 꺼냅니다. 

 

 

c++

stl의 stack 클래스를 이용합니다. vector를 이용해도 상관 없습니다. 여기서는 stack만 설명하겠습니다.

 

• push() => 푸시
• top() => 스택의 맨 위의값 읽어오기
• pop()  => 팝

#include <stack> 

stack<int> st;

st.push(1); // 푸시
int a = st.top(); // 스택의 맨 위의값 읽어오기
st.pop(); // 팝

 

Java

자바는 stack 클래스를 이용합니다.

 

• push() => 푸시
• peek() => 스택의 맨 위의값 읽어오기
• pop()  => 팝

Stack<Integer> st = new Stack<>();

st.push(1);  // 푸시
int a = st.peek();  // 스택의 맨 위의 값 읽어오기
st.pop();  // 팝

 

 

파이썬

역시나 파이썬은 리스트를 이용합니다.

st = []
st.append(1) // 푸시
st[-1] // 스택의 가장 위의 값 읽어오기
st.pop()

 

 

 

 

 

3. 덱

 

마지막 자료구조인 덱 입니다.

 

 

 

덱은 간단히 말하면 스택+큐 라고 생각하시면 됩니다. 앞뒤로 푸시 팝을 할 수 있는 자료구조입니다.

 

덱을 쓰는 문제는 자주 나오진 않지만 그래도 알아두셔야 합니다! 알아두면 언젠가 유용하니깐요.

 

 

 

c++

deque STL을 이용합니다.

c++에서

덱은 배열처럼 인덱스로 값을 읽어 올 수도 있습니다. dq[0] 이런식으로요!

• push_front(), pop_front() : 덱의 앞부분에 푸시, 팝
• front(), back() : 덱의 가장 앞에 원소, 가장 뒤의 원소를 읽어오기
• push_back(), pop_back() : 덱의 가장 뒷부분을 푸시, 팝

#include<deque>

deque<int> dq;

dq.push_front(1);
dq.push_back(2);

int a = dq.front();
int b - dq.back();

int c = dq[0];  // 1
int d = dq[1];  // 2

dq.pop_front();
dq,pop_back();

 

 

Java

자바의 deque은 인터페이스로 되어있고 구현은 여러 클래스로 가능합니다.

비전공자 입장에서는 머리아프니 큐에서 이용한 LinkedList를 또 이용해줍시다.

c++처럼 인덱스로 값을 읽어올 수는 없군요 ㅠㅠ 처음알았습니다.

 

• offerFirst(), offerLast() : 덱의 앞뒤로 푸시를 해줍니다.
• pollFisrt(), pollLast() : 덱의 앞뒤로 팝을 해줍니다.

Deque<String> dq = new LinkedList<>();

dq.offerFirst(1);
dq.offerLast(2);

dq.pollFisrt();
dq.pollLast();

 

 

파이썬

collection 패키지의 deque를 이용합니다.

파이썬의 덱은 좀더 강력한 기능이 많네요.

• deque.append(item): 덱의 오른쪽 끝에 푸시
• deque.appendleft(item): 덱의 왼쪽 끝에 푸시
• deque.pop(): 덱의 오른쪽에서 팝
• deque.popleft(): 덱의 왼쪽에서 팝
• deque.extend(array): 주어진 배열을 덱의 오른쪽에 가져다 붙인다
• deque.extendleft(array): 주어진 배열을 덱의 왼쪽에 가져다 붙인다.
• deque.remove(item): item을 덱에서 찾아 삭제한다.
• deque.rotate(num): 덱을 num만큼 회전한다(양수면 오른쪽, 음수면 왼쪽).

from collections import deque

dq = deque()

dq.append(1)
dq.appendleft(2)

print(dq)
#deque([1,2])

dq.extend([3,4,5])
print(dq)
#deque([1, 2, 3, 4, 5])

dq.extendleft([-2, -1, 0])
print(dq)
#deque([-2, -1, 0, 1, 2, 3, 4, 5])

dq = deque([1, 2, 3, 4, 5])

dq.rotate(1)
print(deq)
# deque([5, 1, 2, 3, 4])

dq.rotate(-1)
print(deq)
# deque([1, 2, 3, 4, 5])

 

 

 

4. 대망의 옥상정원 풀기

 

자 이제 본격적으로 대망의 옥상정원을 풀어보겠습니다!!!

 

https://www.acmicpc.net/problem/6198

6198번: 옥상 정원 꾸미기

문제

도시에는 N개의 빌딩이 있다.

빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다.

i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으로만 볼 수 있다.

i번째 빌딩 관리인이 볼 수 있는 다른 빌딩의 옥상 정원은 i+1, i+2, .... , N이다.

그런데 자신이 위치한 빌딩보다 높거나 같은 빌딩이 있으면 그 다음에 있는 모든 빌딩의 옥상은 보지 못한다.

예) N=6, H = {10, 3, 7, 4, 12, 2}인 경우

             = 
 =           = 
 =     -     = 
 =     =     =        -> 관리인이 보는 방향
 =  -  =  =  =   
 =  =  =  =  =  = 
10  3  7  4  12 2     -> 빌딩의 높이
[1][2][3][4][5][6]    -> 빌딩의 번호

• 1번 관리인은 2, 3, 4번 빌딩의 옥상을 확인할 수 있다.
• 2번 관리인은 다른 빌딩의 옥상을 확인할 수 없다.
• 3번 관리인은 4번 빌딩의 옥상을 확인할 수 있다.
• 4번 관리인은 다른 빌딩의 옥상을 확인할 수 없다.
• 5번 관리인은 6번 빌딩의 옥상을 확인할 수 있다.
• 6번 관리인은 마지막이므로 다른 빌딩의 옥상을 확인할 수 없다.

따라서, 관리인들이 옥상정원을 확인할 수 있는 총 수는 3 + 0 + 1 + 0 + 1 + 0 = 5이다.

입력

• 첫 번째 줄에 빌딩의 개수 N이 입력된다.(1 ≤ N ≤ 80,000)
• 두 번째 줄 부터 N+1번째 줄까지 각 빌딩의 높이가 hi 입력된다. (1 ≤ hi ≤ 1,000,000,000)

출력

• 각 관리인들이 벤치마킹이 가능한 빌딩의 수의 합을 출력한다.

예제 입력 1 복사

6
10
3
7
4
12
2

예제 출력 1 복사

5

 

 

풀이

이 문제는 요약하면 다음과 같습니다.

• 각 건물마다 자신의 오른쪽을 봅니다
• 볼수 있는 옥상의 갯수를 셉니다
• 건물 높이차에 따라 가려진 건물들은 옥상을 볼 수 없습니다

 

어떻게 하면 이 문제를 풀 수 있을까요?

 

 

 

1. 이중 for문을 이용하기

• 각 건물을 for문으로 돈다
• for문안에 또다른 for문을 만들어 자신의 오른쪽 건물들을 순회한다
• 건물 높이를 체크해가며 옥상을 볼수 있는 수를 센다

아주 간단한 아이디어입니다. 자바로 풀어보면 다음과 같이 풀 수 있겠네요!

import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        
        int n=0;
        int cnt=0;
        Scanner sc= new Scanner(System.in);

        n= sc.nextInt();
        int []h= new int[80000];
        
        for(int i=0; i<n; i++){
            h[i]=sc.nextInt();        
        }
        
        for(int i=0; i<n; i++) {
            for(int j=i+1; j<n; j++) {
                if(h[i]>h[j]) {                    
                    cnt++;
                }else {
                    break;
                }
            }
        }
        System.out.println(cnt);
    }
}

 

 

자 이제 이 알고리즘이 퍼포먼스에도 문제가 없는지 확인해 봅시다.

 

1부에서 배운 Big - O 표기법을 이용해 계산해봅시다.

이중 for문이 사용되었습니다. 둘다 N값을 이용하고 있네요. 고로 O(N^2) 입니다.

 

N의 범위는 1 ≤ N ≤ 80,000 입니다. N^2 해보면 어라... 6400000000 으로 10^9이 넘네요!!

시간초과가 나는 알고리즘입니다 ㅠㅠ 결국에 이 풀이는 틀린 답이 되겠네요..

 

 

 

어떻게든 O(N^2)보다 빠르게 해야 합니다.

방법은 여러가지가 있겠습니다만

 

알고리즘을 풀 때 하나 기억해두셔야 합니다

자료구조 스럽게 생각하라!

 

이 말이 무슨뜻이냐면 방법은 여러가지가 있겠습니다만 우리는 컴퓨터를 이용해 문제를 풉니다.

그리고 컴퓨터는 사람처럼 다양하고 창의적으로 생각하지 못합니다.

그저 코드 한줄 한줄 읽고 데이터는 자료구조를 통해 처리하지요

 

어차피 문제는 컴퓨터로 풀기에 컴퓨터처럼 생각할 필요가 있다는 말입니다!

 

 

자 그럼 여기서 해야할 행동은 다음과 같습니다.

 

"이 문제는 자료구조중에 어떤걸 이용해야 될 까? 스택? 큐? 맵? 셋? 우선순위큐? 스택을 이용하면 되겠군!"

 

이렇게 생각하면 성공입니다. 알고리즘을 풀 때 항상 저 문구를 기억해 두세요!

 

 

 

 

자 앞선 강의에서 말씀드린것 처럼 이 문제는 스택을 이용해 푸는 문제입니다.

 

 

말로 설명하면 어려우니 그림으로 설명드리겠습니다.

 

 

 

스택에 건물 하나가 들어옵니다!

 

 

신입 건물이 들어왔네요! 기존에 있던 건물은 신입 건물의 정수리를 볼 수 있습니다. 답에다가 +1을 해줍니다!

 

난쟁이 건물이 들어왔습니다! 기존에 스택에 있던 건물은 2개이고 이 건물들은 난쟁이 건물의 정수리를 볼 수 있습니다.

고로 +2를 해줍니다. 아까 +1을 해 주었으니 답은 3이 되겠네요.

 

 

난쟁이건물보다 더 큰 건물이 들어오려 합니다! 이제 난쟁이 건물은 자기보다 키큰 건물이 들어오면 이후 새로운 건물들의 정수리를 볼 수 없습니다.

고로 새로 건물이 들어오기 전에 난쟁이 건물을 팝 해줍니다!

 

 

 

 

 

자 이제 마지막입니다. 새로온 건물은 자기보다 키가 작은 건물들을 전부다 pop 시켜버립니다.

그리고 자기보다 키가 큰 건물들에게 정수리가 보이는지 확인 받죠. 위 그림에서 두개의 키큰 건물들이 있으니 +2를 해줍시다.

그럼 답이 5로 늘어나는군요.

 

 

이러한 방식으로 계속해서 푸시 팝을 해 줍니다.

 

요약하면 다음과 같습니다.

 

스택에 건물을 넣는데, 건물을 넣기전에 자기보다 작은 건물들은 전부 팝 시켜버리고 푸시를 합니다. 푸시를 할 때 정답에 푸시전의 스택사이즈를 더해줍니다.

 

시간복잡도는 많이 해봤자 N개를 전부 푸시한번 팝 한번 해봤자 2N이니 O(N) 이군요!

 

 

아래에 자바와 파이썬 코드로 답을 공유드립니다. 스스로의 힘으로 한번 해보시고 안되면 코드를 똑같이 따라 쓰면서 이해하는것도 방법입니다(클론코딩).

혹시나 안풀려서 클론코딩 하는거에 좌절하지 마세요! 모두들 그렇게 시작하고 배웁니다!

 

 

오늘도 읽어주셔서 감사합니다!

 

 

 

 

 

java하실때 주의점!

백준 문제가 좀 더러워서 답의 범위가 int형을 초과합니다. 고로 아래 cnt변수는 long으로 선언한걸 기억하세요!

import java.util.Scanner;
import java.util.Stack;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		long cnt=0;  // 답의 범위가 int를 초과하여 long으로 설정!!
		Scanner sc= new Scanner(System.in);
		int n =sc.nextInt();	//건물 갯수	
		Stack<Integer> st = new Stack<>();	//스택
		int h;;	//건물 높이
		for(int i=0; i<n; i++) {
			h= sc.nextInt();
			if(st.size()==0) {
				st.push(h);
				continue;
			}else {
				while(st.peek()<=h) {
					st.pop();
					if(st.size()==0) {
						break;
					}
				}
				cnt+= st.size();
				st.push(h);
			}
		}
		System.out.println(cnt);
	}

}

 

import sys
N = int(sys.stdin.readline())
stack = []
ans = 0
for i in range(N):
    height = int(sys.stdin.readline())
    if len(stack) == 0:
        stack.append(height)
        continue
    while stack[-1]<= height:
        stack.pop()
        if len(stack) == 0:
            break
    ans += len(stack)
    stack.append(height)

print(ans)

 

+하나 더

자료구조를 다루면서 해당 자료구조의 사이즈가 0인지 아닌지 판별해야 할 일이 많습니다.

c++, java에서는 보통 isEmpty() 함수나 size()함수가 보통 내장되어 있으며 파이썬으 경우 len(자료구조) == 0 을 이용합니다.

 

기억해 두세요!