SImpAS

Typescript로 자료구조(Data-Structure)직접 구현해보기: :Intro (1) 본문

Algorithm/자료 구조

Typescript로 자료구조(Data-Structure)직접 구현해보기: :Intro (1)

잡다한 것들은 다 해보겠다 simpas 2020. 3. 23. 21:09

0.1절에서 알고리즘이란 무엇인가? 그리고 0.2절에서 알고리즘을 공부하는 이유에대해서 알아봤습니다.

 

대충 요약을 하자면, 알고리즘은 하고자 하는 일을 하기위한 일련의 절차에 해당하고, 좋은 프로그램을 만들기 위해서는 좋은 알고리즘을 쓸 수 있어야한다는 내용이었습니다.

 

그렇다면 어떻게하면 좋은 알고리즘을 사용할 수 있을까요?

여기서 알고리즘이라면 꼭 세트로 붙어다니는 자료구조가 등장하게 됩니다. 좋은 알고리즘을 구현하기 위해서는, 상황에 맞는 적절한 자료구조를 선택해야하고 그럴려면 다양한 자료구조들을 어떻게 사용할 수 있는지 알아야합니다.

 

근데, 자료구조가 뭘까요?

0. 3 자료구조란?

자료구조는 데이터를 모으고, 모은 데이터들 사이의 관계를 정의하고, 그 관계에 변화를 줄 수 있는 기능들을 제공해줌으로써, 좀 더 효율적으로 데이터에 접근하고 수정할 수 있도록 한 설계입니다.

 

그리고 위키에서의 정의는 다음과 같습니다.


자료구조(資料構造, 영어: data structure)는 컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미한다.

 

출처: 위키


마치 책상정리가 잘 되어있으면 공부가 잘되는 느낌 이라고 볼 수 있죠.

즉 필요한 정보를 편하게 알아내고, 필요없는 정보는 언능 쳐내고, 정보에 변화가 생기면 쉽게 바꿀 수 있게 하는것이 바로 자료구조입니다.

 

그럼 좋은 알고리즘을 구현하기 위해 자료구조를 공부해야하는 이유는 뭘까요?

0. 4 자료구조와 알고리즘

앞서 얘기했듯이, 좋은 알고리즘을 구현하기 위해서는, 상황에 맞는 적절한 자료구조를 선택해야합니다.

 

그럼 그 '적절한'은 무슨 기준으로 정해지는걸까요?

대부분의 자료구조는 다음과 같은 기능들을 제공합니다.

  • 읽기
  • 삽입
  • 검색
  • 삭제

이 4가지의 기본적인 기능들을 모두 빠르게 작동시킬 수 있으면 정말 좋겠지만, 대부분의 자료구조는 장단점이 있습니다. 읽기가 빠르면 삽입이 느리다거나, 삽입은 빠르지만 읽기가 느리다거나 등등의 장단점이 존재합니다.

 

이렇게 장단점이 존재하기 때문에, 읽어들이는 속도가 빨라야하는 프로그램은 읽기 성능이 좋은 자료구조, 검색 속도가 빨라야하는 프로그램은 검색 성능이 좋은 자료구조를 사용해야겠죠.

 

하지만 자료구조만으로는 검색성능을 높일 수 없을지도 모릅니다. 한가지 예를 들어 보겠습니다.

 

다들 Up Down게임을 알거라고 생각합니다만, 간단하게 설명하자면 다음과 같습니다.

 

  1. 한 사람이 1~100 사이의 숫자를 생각한다
  2. 다른 한 사람은 그 사람이 무슨 숫자를 생각했는지 맞춘다.
    1. 단, 입 밖으로 한 개의 숫자를 외칠때마다 게임 횟수 1회로 친다.
  3. 생각한 숫자보다 낮은 숫자를 제시하면 Up, 생각한 숫자보다 높은 숫자를 제시하면 Down을 외친다.

여기서 보통 맞추는 사람은 첫번 째 숫자로 50을 말하죠. 왜 그럴까요?

 

50을 말하면 Up이든 Down이든 절반의 숫자가 후보에서 제외되기 때문이죠. 그래서 맞추는 사람 입장에서는 이렇게 중간값만 말하면 아무리 많이 말해도 7번이면 정답에 도착할 수 있습니다.

 

그런데 이런 게임을 하다보면 간혹, 보통이 아닌 사람이 있습니다. 바로 심리전에 돌입하죠.


쟤는 평소에 낮은 숫자를 좋아하니까 낮은 숫자부터 맞춰야지 ㅎㅎㅎ

바로 맞추는거 아니야? 꺄아 ><

 

단, 설명의 편의를 위해 이 심리학 천재는 앞서 사용한 반반규칙을 사용하지 않는다.


 

이렇게 되면 어떻게 될까요? 상대방이 한 수 앞을 내다봐서 숫자 100을 생각했다면 심리학 천재는 100번 숫자를 제시해야합니다.

물론 심리학 천재가 한번만에 맞출 수도 있었겠지만, 최대는 100번까지 외쳐야한다는게 사실이죠.

 

여기 이 게임에서 1부터 100까지가 순서가 있는 100개의 데이터고, 모든 데이터가 순서에 맞게 저장되어있었다는 상황이라면, 숫자를 어떻게 검색하느냐에 따라서 최대 검색 횟수가 크게 달라지게 됩니다. 이는 곧, 어떤 알고리즘으로 검색을 구현하느냐에 따라서 최대 검색 횟수가 크게 달라진다는 말과 같습니다.

 

심리학 천재는 검색에 용이한 자료구조를 가지고 있었음에도 불구하고, 부적절한 알고리즘으로 상대방의 숫자를 100번이나 맞춰야 했던 거죠.

 

그럼 무조건 순서에 맞게 저장되는 자료구조를 써야겠네~ 라고 생각하는 사람이 있을 수 있겠죠? 상황을 약간 바꿔봅시다.

여기 특수문자들이 그려진 블록들을 가지고 만든 정말 쓸데 없는 UpDown파생 게임이 있습니다.

 

★, ☆, ☂︎, ☀︎, ☻ ... 이러한 특수문자가 그려진 블록이 100개 있습니다.

룰은 다음과 같습니다.

  1. 각 블록들은 1~100 사이의 숫자와 1:1로 매칭된다.
  2. Up Down게임과 룰이 똑같다
  3. 각 블럭들을 순서대로 정렬하고 게임을 시작해야한다. (정말 쓸데 없는 UpDown파생 게임인 이유죠)
    1. 단, 각 블럭들과 매칭하는 숫자가 적힌 종이가 같이 들어있다.

이런 룰을 가진 정말 쓸데 없는 UpDown 파생 게임이 있다면, 저희는 게임 시작을 위해 세팅하면서 대부분의 시간을 날리게 되겠죠..

집어올린 블럭이 어떤 숫자인지 봐야하고, 다음에 올 숫자가 어떤 숫자일지도 생각해야하죠. 이렇게 블럭들을 게임판에 세팅하는데에 너무 긴 시간이 걸리게 됩니다.

이는 자료구조의 기본적인 기능 중에서 삽입에 해당하는 부분이라고 볼 수 있습니다.

 

하지만, 이 쓸데없는 UpDown파생 게임의 정말 쓸데없는 룰인 3번룰을 없애면 꽤나 해볼만 한 게임이 됩니다. 블럭을 아무렇게나 배치하고 상대방이 어떤 그림을 생각했는지만 맞추면 되는 재미난 게임이 되는거죠.

 

이것이 곧 정렬되는 자료구조무조건 좋은게 아니라는 것을 뜻하죠. 정렬되는 자료구조는 결국 정렬되지 않는 자료구조에 비해 새로운 데이터를 삽입하는데에 시간이 오래걸리게 되는거죠.

 

여기 1부터 100까지 아무 숫자를 입력해주면, 순서에 맞게 숫자들을 저장하는 프로그램이 있다고 칩시다. 사실상 컴퓨터 입장에서는 정말 쓸데 없는 UpDown파생 게임을 세팅하는 과정과 비슷한거죠.

입력받는 데이터들을 기존에 있던 데이터들과 하나하나 비교해야하는 과정을 거치게 되니까요.

 

이번 예시에서 알 수 있듯이, 자료구조와 알고리즘은 둘이 따로 생각하는 것이 아닙니다. 필연적으로 세트로 묶여서 공부를 해야하는거죠.


그럼 0.3절, 0.4절에서는 자료구조에대해 알아보고, 자료구조와 알고리즘의 관계를 파악했습니다. 다음은 어떤 자료구조가 좋은 것이고, 어떤 알고리즘이 좋은 것인지 기준이 될 수 있는 시간복잡도에 대해 알아보도록 하겠습니다.

0 Comments
댓글쓰기 폼