자료구조와 알고리즘 이해하기

자료구조(Data Structure) 이해하기

자료(Data)가 그렇게 귀하다며..?

요즘 세상의 '자료(이하 데이터)'는 '새로운 석유(new oil)'라고 할만큼 AI, 정부, 구글 등 분야를 막론하고 많은 곳들에서 우리의 데이터를 원한다. 그래서 우리가 많은 서비스들을 무료로 사용할 수 있기도 하다. 예를 들어 데이터가 있어야 AI를 훈련시킬 수 있다. 데이터가 있어야 광고를 타겟팅 할 수 있다. 유튜브는 우리의 정보를 바탕으로 맞춤 광고를 설정하고, 영상을 보여준다.

Data is the New Oil - https://mondaymorningmashup.com/data-is-the-new-oil/

그만큼 데이터는 중요하고 개발자라면 항상 데이터를 다루게 된다.

데이터를 효과적으로 다룰 수 없을까?

프로그래밍이 존재할 때부터 데이터는 항상 다루어왔다. 그렇게 데이터의 양이 커짐에 따라 선배 개발자들이 데이터를 효과적으로 다루기 위한 '방법'을 만들었는데, 그게 바로 자료구조(data structure)이다. 자료구조를 '책장에서 책을 배열하는 방법'이라고 묘사하기도 한다.

• 자료구조는 결국 이 데이터란 것들을 잘 정리하기 위해 존재한다.
• 데이터를 어떻게 정리하냐에 따라서 우리의 서비스가 빨라질 수도, 느려질 수가 있는 것이다.
• 자료구조는 여러개가 존재하고, 어떤 구조는 '정렬'에 최적화 되어 있다던가 어떤 구조는 '검색'에 최적화 되어 있다.

자료구조에는 배열(array), 연결 리스트(linked list), 스택(stack), 큐(queue), 트리(tree), 그래프(graph) 등 다양한 형태가 있다. 각 자료구조에는 특징과 장점이 있기 때문에, 이러한 개념을 숙지하면 문제를 해결하는 데 어느 자료구조가 적합한지를 알 수 있게 된다.

출처 : https://gdtbgl93.tistory.com/34

예를 들어, 배열과 연결 리스트는 서로 상반된 특성을 가지고 있다. 배열은 메모리에서 연속적인 공간을 차지하여, 각 요소가 고정된 인덱스를 가지고 있으므로 인덱스를 통한 접근이 빠르며 O(1)의 시간 복잡도를 가진다. 따라서 배열은 빠른 조회가 필요한 상황에서 효과적이다.

 

반면에, 연결 리스트는 메모리의 불특정한 공간에 존재하기 때문에 포인터, 즉 주소를 참조하는 필드를 통해서 연결해 주어야 한다. 이러한 특성 덕분에 상황에 따라 배열에 비해 삽입 또는 삭제가 빠를 수 있다.

자료구조와 추상적 자료형(ADT)의 관계

추상적 자료형(Abstract Data Type)은 말 그대로 자료구조보다 좀 더 추상적이다. 이 둘은 코드로 나타낼 수 있느냐 없느냐에 따라 구분할 수 있다. 즉, 추상적 자료형은 코드로 정의된 것이 아닌 추상적인 개념을 뜻한다.

• 집합, 리스트, 스택, 큐, 트리 등이 해당된다.
• 추상적 자료형은 동작 방식, 자료구조는 동작 방식을 바탕으로 실행(구현)하는 것

예를 들어, 스택 ADT는 'push'와 'pop'이라는 연산을 정의하지만, 이 스택이 배열이나 연결 리스트로 구현되는지에 대해서는 언급하지 않는다.

 

결국, 자료구조는 데이터를 어떻게 저장하고 구성할지에 대한 구체적인 방법을 제시하고, 추상적 자료형은 특정 자료구조의 특징, 속성, 연산들은 다루지만 내부적으로 어떻게 구현되어 있는지에 대해서는 다루지 않는다.

알고리즘(Algorithm) 이해하기

자료구조에 대한 이해를 바탕으로 좀 더 구체적인 구현을 목표로 한다. 잘 구조화된 데이터를 어떻게 정렬할지, 어떤 방법으로 원하는 데이터를 검색할지에 대한 정형화된 방법론이다. 자료구조가 '책장에서 책을 배열하는 방법'이라면 알고리즘은 '책장에서 책을 찾는 방법'으로 묘사한다.

 

알고리즘을 실생활에서 비유할 때 목적지까지 가는 길을 예로 많이 든다. 같은 목적지라도 최대한 빠른 길로 가고싶어 한다. 이처럼 우리에게 시간은 소중하고 효율적으로 사용하기 위한 노력은 항상 존재했다.

 

컴퓨터 프로그래밍도 마찬가지로 시간복잡도가 가장 낮은 알고리즘을 선택해 이러한 상황들을 개선하고 있다.

• 문제를 풀기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것
• 상황에 따라 효율적인 알고리즘이 있다
  • 시간복잡도가 가장 낮은 알고리즘을 선택하여 사용한다
• 훌륭하고 효율적인 알고리즘을 찾아 반복적으로 사용할 수 있다
• 제한된 공간과 시간 안에서 데이터를 어떻게 처리할 것인지를 정해놓은 로직(방법)이다.

위의 예시를 컴퓨터 프로그래밍으로 옮겨보면 지도앱에서 최단경로를 찾는 'path finding' 알고리즘을 사용할 수 있다. 그 외에도 원래의 데이터를 그대로 보존해 압축하는 'lossless compression' 알고리즘 등이 있다.

알고리즘의 실행시간

알고리즘의 실행시간은 1분 1초의 시간으로 계산하지 않는다. 컴퓨터의 하드웨어 또는 프로그래밍 언어에 따라 속도의 편차가 크게 달라지기 때문에 명령어의 실행 횟수(연산 횟수)만으로 고려한다. 일종의 단계인 것이다.

최악의 경우인 빅오 표기법(Big-O Notation)

빅오 표기법은 불필요한 연산을 제거하고 알고리즘 분석을 쉽게 할 목적으로 사용한다.

 

그런데 왜 하필 실행시간을 측정할 때 최악의 경우인 빅오로 표기하는 것일까? 다른 표기법(세타) 같은 경우 좀 더 정확하지만 그만큼 평가하기가 까다롭다. 따라서 평균과 가까운 성능으로 예측하기 쉬운 빅오 표기법으로 표현한다.

• O(1) -> 문제를 해결하는데 오직 한 단계만 처리함
• O(log n) -> 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듦
• O(n) -> 문제를 해결하는데 필요한 단계들이 입력값 n과 1:1 관계를 가짐
• O(n log n) -> 문제를 해결하는데 필요한 단계의 수가 로그(log)만큼 늘어남(선형 로그)
• O(n²) -> 문제를 해결하는데 필요한 단계의 수가 제곱
• O(2ⁿ) -> 문제를 해결하는데 필요한 단계의 수가 2의 n 제곱

https://dev.to/madisonstankevich/big-o-notation-a-brief-overview-for-the-beginner-1o13

실행시간의 공간과 시간 복잡도

• 시간 복잡도란? 입력된 n의 크기에 따라 실행되는 연산의 수
• 공간 복잡도란? 알고리즘이 실행될 때 사용하는 메모리의 양

자료구조와 알고리즘을 알고 프로그래밍을 한다는 것

프로그래밍 초기엔 구현하는 것에 집중했다. 그 후 저마다 시기가 조금씩 다를뿐 개발자라면 필연적으로 접하는 개념이 아닐까 생각된다. 알고리즘 문제에 대해 다시 돌아보게 되는 계기가 되었다. 

 

자료구조의 선택과 기본 개념을 알지 못한 상태로 그저 문제 외우기식으로 풀었던 것 같다. 이제는 스스로 효율적인 자료구조를 선택해서 문제에 집중하고, 선택의 폭이 넓어진 알고리즘을 재미있게 풀이 할 수 있다. 막막했던 알고리즘 문제들이 이제는 재미있는 코드놀이가 된 것 같다. 그래도 여전히 어려운 문제들이지만 답답했던 부분이 많이 해소되었다.

 

이렇게 두 개념이 어플리케이션의 속도와 최적화에 중요하단 것을 안 이상 신경을 안 쓸 수가 없다. 이제는 서비스를 구현하는 것에 그치지 않고 좋은 코드와 빠른 서비스를 향해 나아가야겠다.