[자료구조] 자료구조와 알고리즘 기초

자료구조와 알고리즘이란

• 음식과 그릇?

우리 일상에는 수많은 음식이 존재하고 음식의 형태에 따라 어떤 그릇에 담기는 지가 상당히 중요하다. 만약 파스타가 컵에 담기거나 음료수가 일반 그릇에 담긴다면 먹기가 굉장히 불편하지 않겠는가?

이처럼 데이터(Data)와 자료 구조(Data structure)도 이와 같은 관계에 놓여있다. 데이터는 음식, 자료구조는 그릇이 되어 올바른 데이터 구조에 데이터를 담아야 효율적인 코딩이 가능해 진다.

즉, 자료를 어디에, 어떻게 관리할 지를 제대로 알아야 코딩을 통해 내가 원하는 결과물을 얻을 수 있다.

• 예) 검색, 순회(iterate), 저장, 삭제, 변경

Data와 Data Structure

컴퓨터의 자원은 한정적이며(CPU, 메모리 등…) 제한된 제약 조건 내에서 정확하고 가장 최적의 결과를 내는 것은 매우 중요하다고 할 수 있다.

당연히 이는 자료구조가 핵심적인 역할을 하며 데이터의 형태와 쓰임에 따라 적합한 자료구조를 쓰는 것이 중요하다.

자료구조는 또한 선형 자료구조와 비선형 자료구조로 나뉘며 이에 대한 내용을 앞으로 자세히 배워 볼 것이다.

앞으로 공부를 하면서..

자료구조와 알고리즘이라는 것은 예전부터 쭉 이어져 왔고 기존의 알고리즘 및 구조에 엄청난 수정을 거쳐서 현재까지 발전한 것이다.

그런만큼 앞으로 이 과목을 공부하면서 그저 알고리즘과 자료구조의 종류에는 어떤 것이 있고, 어떻게 사용 하는지만을 생각하는 것이 아니라 이 자료구조가 왜 요즘 사용하는 것이며 이 자료구조 혹은 알고리즘의 한계가 있다면 어떤 것이 있는 지, 이를 어떻게 해결할 수 있는지를 곰곰히 생각해 보는 것이 이 과목을 온전히 받아들일 수 있고 스스로 발전할 수 있는 방법 중에 하나라고 생각이 든다.

알고리즘

• 어떤 문제가 주어졌을 때, 문제를 풀기 위한 동작들의 절차

알고리즘이란 사전적 정의로서 위와 같이 정의됩니다. 쉽게 말해 Input 값을 통해 Output 결과를 내는 과정이라고 볼 수 있다.

예를 들어,

게임 캐릭터를 특정한 위치를 지정하여 이동시킬 때, 그 지점까지 가는 경로(route)의 수는 무한대일 것이다. 하지만 우리가 만들고자 하는 알고리즘이라는 것은 캐릭터와 지점 사이의 경로 중 최단 거리, 최적의 거리를 생각해내는 방법인 것이다.

빅오 표기법

좋은 알고리즘이란?

집에서 학교까지 가는 방법을 한 번 생각해 보자.

• 자동차를 타고 가기
• 버스를 타고 가기
• 도보로 가기

이 방법들은 모두 학교를 도착한다는 목적이 일치하기는 하지만 모든 방법이 학교를 가장 빨리가는 방법은 아닐 것이다. 빅오 표기법은 이러한 경우의 수들을 시 공간적 측면으로 비교하는 것을 도와주는 표기법이라고 할 수 있습니다.

빅오 표기법은 점근 표기법의 일종으로 실제로 점근 표기법이라고도 불리기도 하며 세타 표기법, 오메가 표기법과는 구별된다.

“위(상한 점근)에서부터 순서대로 빅오표기법, 오메가 표기법, 세타 표기법이다.”

표현식

위 그림처럼 7개의 데이터가 있다고 가정하고 맨 왼쪽부터 순회하면서 우리가 원하는 데이터를 찾는다고 가정을 해 보자.

한 칸을 순회하는 데 걸리는 시간은 0.1초이다. 즉, 우리가 원하는 데이터가 가장 처음에 있을 경우 이 데이터를 찾는데 걸린 시간은 0.1초가 되고 가장 마지막에 있을 경우 0.7초가 된다.

• 가장 앞 칸의 데이터는 어떤 경우라도 이 경우 보다는 찾는데 오래 걸리기 때문에 하한선이라 하고 가장 뒷 칸의 데이터는 어떤 경우도 이 경우 보다는 찾는데 빨리 걸릴 것이기 때문에 상한선이라 한다.

• 위 두 값의 중간 값은 평균값으로 정해진다.

빅오표기법은 이 중 가장 상한인 값을 기준으로 복잡도를 표기하게 된다. 따라서 정확한 소요시간을 알기는 어렵지만 어떤 경우도 이 범위 안에는 들어온다는 사실을 대략적으로 알 수 있다는 것에 의의가 있다.

그래서 데이터가 늘어날 수록 시간 복잡도는 늘어나기 때문에 O(N)의 시간 복잡도로 나타낼 수 있다.

점근 표기법의 특징

• 가장 큰 영향력이 있는 항만 표시한다.
  • O (N^3+N^2+N) -> O(N^3
• 상수항은 무시한다.
  • O(2N+1) -> O(N)
• 크기 비교

점근 표기법의 크기 비교는 O를 빼고 그 안의 식만을 생각한 것과 크게 다를 바가 없다.

그렇다면 복잡도에는 어떤 것들이 있는 지 보자.

공간 복잡도

공간 복잡도란 데이터 관리에 필요한 공간을 나타내는 개념이며 데이터 개수에 따라 공간이 어떤 식으로 되어있는지를 쉽게 확인 할 수 있는 지표이다..

시간 복잡도

반면 시간 복잡도는 데이터 처리에 소요되는 시간을 나타내는 개념으로서 데이터 양에 따라 바뀌는 소요 시간의 변화를 확인 할 수 있고 예상 처리 시간을 측정한다.

아무리 좋은 프로그램도 지연되거나 속도가 느리다면 사용자에게 불쾌감을 줄 수 있기 때문에 시간 복잡도가 공간 복잡도보다 더 중요하다고 볼 수 있고 지연 장애가 발생했을 때 왜 발생 했는지를 찾을 수 있는 근거로 활용하기도 한다.

실제로 백준 같은 사이트에서 코딩 문제를 풀어 볼 때 문제가 어려워 질수록 시간 소요는 굉장히 중요한 인자가 된다.

시간 복잡도

앞서 말했 듯 시간 복잡도가 중요한 만큼 이에 대해 더욱 자세히 알아보도록 할 것이다.

O(1)

가장 짧은 시간이 걸리는 O(1)은 연산 횟수가 고정되어 입력 데이터의 크기와 상관없이 항상 **일정**한 시간이 걸리는 알고리즘이다.

• 배열의 Random Access
• Hash

그 예로 뒤에서 배우게 될 위와 같은 것들이 있다.

O(N)

O(N)은 입력 데이터의 크기에 비례해서 시간이 소요되는 알고리즘이다.

for i in range(N):
    #do something

위의 for문이 대표적인 O(N)으로 N의 크기가 10이면 10번 100이면 100번 동안 순회의 과정을 거치게 되어 그(N)만큼의 시간이 소요가 될 것이다.

O(N^2)

이도 마찬가지로 입력 데이터의 제곱에 비례해서 시간이 소요가 되는 알고리즘이다.

for i in range(N):
    for j in range(N):
        #do something

이와 같은 경우는 위처럼 이중 for문의 형태가 그 예시이다. N번 순회하는 것이 두 번 중첩되어 제곱의 형태로 시간이 소요 되는 결과가 나오는 것이다.

O(logN)

O(logN)의 대표적인 예시는 이진 탐색(Binary search)가 있다. 이진 탐색은 차후에 배울 내용으로 간단히 설명하자면 업다운 게임을 한다고 생각해 보면 된다. 상대가 생각한 숫자를 맞추기 위해서는 물론 무작위 숫자를 마구잡이로 불러서 맞춰 버리거나 아예 1부터 불러서 맞출 수도 있을 것이다. 하지만 범위가 10, 100 이런 것이 아니라 몇 만, 몇 억이 된다면 그만큼의 굉장한 시간 걸릴 것이기 때문에 더 효율적인 방법은 만약 범위가 1~100인 숫자를 생각했다면 절반씩 나누어 불러서 그 숫자가 포함되는 범위를 좁혀나가면서 찾는 것이 가장 최선일 것이다.

보통 한 번의 연산이 진행될 때마다 연산의 범위가 반 씩 줄어들기 때문에 이를 O(logN)이라고 할 수 있다.

(이진 탐색에 대한 그림)

O(NlogN)

O(NlogN)은 추후에 배우게 될 Merge sort(합병 정렬)가 대표적인 예시이다.

정렬을 할 때 여러가지 방법이 있는데 merge sort는 주어진 데이터 집합 내에서 절반씩 나누면서 데이터 분할 과정이 진행되고 이 과정을 통해 앞서 얘기했던 logN이 취해지는 것이고 그 후에는 반 씩 나누어진 데이터들을 하나하나 다시 sorting하는 과정이 이루어지게 되는데 이때 N번 만큼 정렬을 하는 것이므로 NlogN 형태의 시간복잡도가 나오게 되는 것이다.

References

위키피디아