자료구조와 알고리즘

개발자가 되기 위해 공부하다 보면, 자료구조와 알고리즘을 공부하는걸 빼먹어서는 안된다는 얘기를 많이 들어봤을 것이다.

만약에 면접관이 자료구조와 알고리즘의 차이를 설명해보세요~
와 같은 질문을 했다고 가정해보자. 만약에 자료구조?알고리즘? 연결리스트?, 트리?, bfs? 이런거 아닌가요? 라고 까지만 알고 있다면! 내 얘기다

그렇게 해서는 합격을 시켜줄 수 없어

둘 사이에 어떤 차이가 있는지 알아보도록 하자.

자료구조

-자료 구조는 데이터 값의 모임, 또 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미한다-
https://ko.wikipedia.org/wiki/%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0 from wikipedia

직관적으로 와닿지는 않는 말이다. 조금 풀어서 설명을 해보자면, 방에 옷도 있고, 책도있고, 화장품도 있고 할때, 마구잡이로 어질러 놓는 것보다 종류별로 잘 정리해놓는게 공간도 아끼고, 나중에 원하는 물건을 찾기도 빠르고 편할 것이다.

자료구조는 위의 물건들을 정리하는 방법과도 같은 것으로, 때에 맞는 자료구조를 잘 사용하면, 실행시간 혹은 메모리 용량과 같은 자원을 최소한으로 사용하면서 연산을 수행하도록 해준다!

리스트, 스택, 큐, 덱, 트리, 그래프 등등...

알고리즘

-알고리즘(영어: algorithm), 셈법은 수학과 컴퓨터과학, 언어학 또는 엮인 분야에서 어떠한 문제를 해결하기 위해 정해진 일련의 절차이다-https://ko.wikipedia.org/wiki/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 from wikipedia

알고리즘은 어떤 문제를 해결하기 위한 방법론이라고 이해하면 좋을 것 같다. 알고리즘을 짜는 과정에서 자료구조를 사용할 수 도있다.

코딩테스트를 풀때, 코드를 짜 나가는 과정도 알고리즘을 작성하는 것이라고 볼 수 있는데, 그 알고리즘을 작성하기 위해 지금까지 잘 알려지고 사용되는 알고리즘들을 사용할 수 도있다.

이진 탐색, bfs, dfs, 다익스트라, 힙 정렬, 트라이 등등...

시간복잡도

우리가 컴퓨터 프로그램을 작성해서 실행을 했다고 생각해보자. 그럼 이 프로그램이 얼마나 빠르게 동작하는지 누군가에게 어떻게 설명할 수 있을까?

프로그램이 연산을 수행하는 시간을 측정해서 알려줄 수 도 있겠지만, 처리해야하는 데이터의 크기, 컴퓨터의 성능, 운영체제의 성능 등등 연산 시간에 관여하는 요소는 여러가지가 있다.

"호오~ 연산속도가 올라가고 있군요~" 같이 측정할 수는 없다

그래서 어떤 로직의 수행능력을 예상하는 지표로써 빅오(Big-O)표기법을 사용한다.

빅오표기법을 보는 방법은 간단한데, O(f(n))에서 f(n)이 1에 가까울 수록 성능이 좋다고 판단한다.

f(n)은 로직이 반복되는 횟수라고 이해할 수 있는데, 예를 들어 반복문을 n번돌리는 로직이다! 라고한다면 O(n)이라고 쓸 수 있는 것이다.

일반적으로 가능하다면 O(nlogn)까지 시간 복잡도를 줄이는 방향으로 코드를 짜는 것이 바람직 하다고 한다.

그리고 f(n)은 최고차항만 계수를 때고 고려를 하는데, 예를 들어 f(n) = 3n^3 + 6n^2 + 2n 이라고 할 때, f(n)을 O(n^3)이라고 취급할 수 있다는 뜻이다. 그 이유는 n이 굉장히 큰 수라고 할 경우 사실 f(n)에 영향을 가장 크게 끼치는 부분이 n^3 이기 때문이다.

배열

배열에 관해서는 빠르게 짚고 넘어가자!

기본적으로 프로그래밍 언어에서는 연속된! 메모리 주소에 값을 하나씩 할당하고 관리할 수 있는 기능이 있는데, 이를 배열이라고 한다. 그리고 배열 안의 값을 요소라고 부른다.

만약에 데이터 집합이 있고, 그 안에서 데이터를 빠르게 찾고 싶다면, 배열이 좋은 선택이 될 수 있다. 왜냐면 배열에 접근하는 속도는 O(1)이기 때문이다.

하지만 데이터가 꾸준히 삭제되고 추가된다면, 배열은 그렇게 좋은 선택이 아닐 수 있다. 왜냐하면, 배열은 연속된 메모리 구조를 이용하기 때문에, 배열 사이에 요소를 추가하거나 삭제하려면 순차적으로 메모리를 하나씩 다시 할당해주는 작업이 필요함으로 시간복잡도가 O(n)이 되기 때문이다.

참고로 보통 배열은 한번 크기를 정하면 크기를 바꾸기 어려운데, 자바스크립트에서는 크기가 동적으로 변하기 때문에 배열을 가지고 작업을 하기가 편하다.

연결리스트

배열과 같이 데이터를 연속적으로 보관하고 싶을 때 사용하지만, 메모리상에는 연속적으로 보관되지는 않는다!

따라서 추가와 삭제에는 편하지만(O(1)), 탐색에는 어려움이 있을 수 있다(O(n)).

연결리스트는 노드라는 것끼리 연결이 되어있고 노드는 데이터를 담는 부분과, 다음 노드를 가르키는 헤드 부분으로 이루어져 있다. 헤드가 내 옆에 연결되어 있는 노드로 가려면 이 메모리 주소로 가렴~ 하고 알려주는 것이다.

헤드가 내 다음 노드의 위치만 알려주는 노드를 단일연결리스트 바로 전의 노드 위치까지 같이 알려주는 리스트를 이중연결리스트라고 한다.

이중연결리스트

js 코드로 간단하게 연결 리스트를 구현해보면 다음과 같다.

//노드
function Node(data) {
  this.data = data;
  this.next = null;
}
//노드 생성
function LinkedList() {
  this.head = null;
  this.len = 0;
}
//노드 내의 데이터 갯수 확인
LinkedList.prototype.size = function () {
  return this.len;
};

//노드 출력
LinkedList.prototype.printNode = function () {
  for (let node = this.head; node != null; node = node.next) {
    process.stdout.write(`${node.data} -> `);
  }
  console.log("null");
};

//인덱스를 통해 노트 삽입
LinkedList.prototype.insert = function (val, pos = 0) {
  let node = new Node(val),
    cur = this.head,
    index = 0,
    prev;
  if (pos === 0) {
    node.next = cur;
    this.head = node;
  } else {
    while (index++ < pos) {
      prev = cur;
      cur = cur.next;
    }
    node.next = cur;
    prev.next = node;
  }
  this.len++;

  return true;
};
//데이터 값을 찾아 노드 삭제
LinkedList.prototype.remove = function (val) {
  let cur = this.head,
    prev = cur;

  while (cur.data != val && cur.next != null) {
    prev = cur;
    cur = cur.next;
  }

  if (cur.data != val) {
    return null;
  }
  if (cur === this.head) {
    this.head = cur.next;
  } else {
    prev.next = cur.next;
  }

  this.length--;

  return cur.data;
};

let ll = new LinkedList();

ll.insert(1);
ll.insert(2);
ll.insert(3);
ll.insert(4);
ll.insert(5);

ll.printNode();

ll.insert(6, 2);
ll.printNode();

ll.remove(6);
ll.printNode();

console.log(ll.size());

스택

스택은 LIFO구조이다. LIFO 구조란 라스트 인 퍼스트 아웃의 약자로, 맨 나중에 들어간 자료부터 순서대로 꺼낸다는 뜻인데, 우리가 상자에 물건을 넣으면 꺼낼때는 맨 위의 물건 부터 꺼내는 것과 같이, 맨 나중에 들어간 데이터부터 꺼내는 자료구조이다. 술먹고 오바이트 하면 그게 바로 LIFO

스택에 데이터를 넣는걸 push 꺼내는걸 pop이라고 한다.

스택은 여러 cs상황에서 응용되는데, 우리가 사용하는 이 바라우저가 뒤로가기를 하면 바로 이전의 페이지로 갈 수 있는것도 스택을 활용한 사례이다.

자바스크립트에서는 array.push, array.pop 메소드를 통해 손쉽게 스택을 구현할 수 있다!