[알고리즘] 데이터 구조 1

포스팅 이유

알고리즘 공부를 통해 문제 해결력을 높이고 공부한 내용을 정리하기 위함.

알고리즘이란?

알고리즘은 특정 문제를 효율적이고 빠르게 해결하는 절차, 방법, 명령어를 통틀어 의미합니다.

데이터 구조

데이터 구조란?

데이터 구조는 데이터를 저장하는 방법으로 데이터를 어떻게 사용할 것인지 목적을 정하고 나서 사용하기 쉬운 데이터 구조를 선택합니다.

결국 어떤 데이터 구조를 선택하느냐에 따라 데이터를 쉽게 출력할 수 있는지 그렇지 않은지가 결정됩니다.

간단한 예를 들어 생각해보겠습니다.

다음과 같이 두가지 구조의 자료가 있습니다.

1. A B C

2. A
   B
   C

이 때 B를 꺼내기 더 편한 자료 구조는 어떤것일까요?

정답은 1번입니다.

2번의 경우 위에 있는 A를 치워야 B를 꺼낼 수 있기 때문에 한번의 동작으로 B를 꺼낼 수 있는 1번 구조가 더 유리합니다.

이제 이런 데이터 구조에 대해 조금 더 자세히 알아보겠습니다.

1. 스택

스택이란 ?
스택은 맨 마지막에 저장한 데이터를 가장 먼저 처리할 수 있는 데이터 구조입니다. 마지막으로 저장한 데이터 위에 다음 데이터를 쌓아 올리는 모습입니다.

위 그림과 같이 스택에 데이터를 직접 넣는 작업을 푸쉬(Push)라고 합니다.

반대로 스택에 쌓여 있는 데이터를 꺼내는 작업은 팝(Pop)이라고 합니다.

팝 과정에서 맨 마지막에 넣은 데이터를 가장 먼저 꺼내게 되는데 이런 저장 방식을 last in first out(LIFO) 혹은 후입선출이라고 표현합니다.

Python을 통한 스택 확인법

Stack = ['a', 'b', 'c']

print(Stack)

Stack.append('d')

print(Stack)

print(Stack.pop())

print(Stack)

다음과 같은 코드를 통해 스택을 직접 확인할 수 있습니다.
코드를 실행해 보면

다음과 같은 출력 결과를 볼 수 있습니다.
파이썬의 List 자료형을 통해 a, b, c가 들어 있는 스택 데이터 구조를 만들었고 append와 pop을 통해 데이터 'd'를 넣고 빼는 것을 확인했습니다.

2. 큐

큐란?
큐는 맨 처음 저장한 데이터를 먼저 처리하는 데이터 구조입니다. 다른 말로는 대기 행렬이라고 합니다. 스택과는 반대로 먼저 저장한 데이터를 나중에 저장한 데이터보다 먼저 처리합니다.

큐는 에스컬레이터를 생각하면 쉽게 이해할 수 있습니다. 먼저 탄 사람이 먼저 내리는 구조로 first in first out(FIFO), 선입 선출이라고 합니다.

Python을 통한 스택 확인법

Queue = ['A', 'B', 'C']

print(Queue)

Queue.append('D')

print(Queue)

Queue.pop(0)

print(Queue)

Queue.pop(0)

다음과 같은 코드를 통해 큐를 직접 확인할 수 있습니다.
코드를 실행해 보면

다음과 같은 출력 결과를 확인할 수 있습니다.

append를 통해 삽입된 데이터는 list의 가장 뒤에 위치하게 되고, pop(0)를 통해 추출되는 데이터는 list의 가장 앞에 위치합니다.

이를 통해 큐의 선입선출을 직접 확인했습니다.

3. 스택과 큐 비교하기

문제에서 얻는 답이 같더라도 어떤 데이터 구조를 사용하느냐에 따라 처리 과정에서 겪는 어려움의 정도는 달라집니다.

스택을 사용하는 경우

스택을 사용할 경우 데이터의 개수와 무관하게 마지막에 넣은 값은 한번에 출력할 수 있습니다. 하지만 처음 넣은 데이터를 꺼내려면 넣은 데이터의 개수만큼의 시도해야 가능합니다.

큐를 사용하는 경우

큐를 사용할 경우 먼저 들어간 데이터를 먼저 꺼낼 수 있습니다. 하지만 마지막에 들어간 데이터의 경우 꺼내기 위해 걸리는 시간이 데이터 크기에 비례하여 증가하게 됩니다.