알고리즘 :: 자료구조와 알고리즘_TIL#14

■ JITHub 개발일지 14일차

□  TIL(Today I Learned) ::

자료구조, 알고리즘(정렬, 스택, 큐, 해쉬)

1. 자료구조와 알고리즘

 - 정렬(sort)

   : 데이터를 순서대로 나열하는 방법을 의미한다. 데이터 정렬을 통해 프로그램이 데이터를 효율적으로 탐색할 수 있도록 만들 수 있다.

  (1) 버블 정렬(bubble sort) : 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘이다. 인접한 2개의 레코드를 비교하고, 차순에 따라 정렬한다. (첫 번째 자료와 두 번째 자료를 비교하고, 두번째 자료와 세번째 자료를 비교하는 식으로 자료를 비교하고 교환하는 수순으로 정렬하는 방식)

  (2) 선택 정렬(selection sort) : 제자리 정렬 알고리즘의 하나로, 주어진 리스트 중 최소값을 찾아 맨 앞에 위치한 값과 교체하고, 맨 처음 값을 빼고 나머지 값들을 같은 방법으로 교체하여 정렬하는 방식이다.

  (3) 삽입 정렬(insertion sort) :  배열의 모든 요소를 맨 앞부터 차례로 정렬된 요소들과 비교하면서 올바른 위치에 도달하면 해당 값을 삽입하는 방식이다.

  (4) 병합(또는 합병) 정렬(merge sort) : '존 폰 노이만(John von Neumann)'이 제안한 방법으로 '분할 정복(Divide and conquer)' 알고리즘의 하나이다. 문제를 2개의 문제로 분할하여 각각을 해결한 후 병합(merge)하여 최종적으로 문제를 해결하는 방식이다. 

 

 - 스택(stack) : 후입선출(LIFO, Last-In First-Out)의 방식으로 가장 나중에 들어온 데이터가 가장 먼저 인출되는 자료구조이다. 프로그램이 자동으로 사용하는 임시 메모리 영역이기도 하다. 자료를 입력한 순서를 기억하여, 직전에 했던 행동을 되돌리고 싶을 때 사용된다. 스택 구조에서 제공하는 기능은 아래와 같다.

  (1) push(data) : 맨 앞에 데이터 넣기

  (2) pop() : 맨 앞의 데이터 뽑기

  (3) peek() : 맨 앞의 데이터 보기

  (4) isEmpty() : 스택이 비었는지 여부 반환하기

 스택은 데이터 입력/출력이 잦은 자료구조로써, 링크드 리스트와 유사하게 구현할 수 있다.

 

 - 큐(queue) : 선입선출(FIFO, First-In First-Out)의 방식으로 가장 먼저 들어온 데이터가 가장 먼저 인출되는 자료구조이다. 스택과는 반대개념이 된다. 주문이 들어왔을 때 주문 순서대로 처리해야 할 때, 프린터의 출력 처리 등과 같이 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있을 때 사용된다. 큐 구조에서 제공하는 기능들은 아래와 같다.

  (1) enqueue(data) : 맨 뒤에 데이터 추가하기

  (2) dequeue() : 맨 앞의 데이터 뽑기
  (3) peek() : 맨 앞의 데이터 보기
  (4) isEmpty() : 큐가 비었는지 안 비었는지 여부 반환해주기

 큐는 데이터 입력/출력이 잦은 자료구조로써, 링크드 리스트와 유사하게 구현할 수 있다.

 

 - 해쉬(Hash)

  (1) 해쉬 테이블(hash table) : 컴퓨팅에서 키를 값에 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료 구조이다. 해시 테이블은 해시 함수를 사용하여 색인(index)을 버킷(bucket)이나 슬롯(slot)의 배열로 계산한다. 데이터를 다루는 기법 중에 하나로 데이터의 검색과 저장이 아주 빠르게 진행된다.

  (2) 해쉬 함수(hash function) : 임의의 길이를 갖는 메시지를 입력하여 고정된 길이의 해쉬값을 출력하는 함수이다

  (3) 충돌(collision) : 같은 어레이의 인덱스로 매핑이 되어 데이터를 덮어써버리는 결과가 나타나는 것을 말한다.

  (4) 체이닝(chaining) : 링크드 리스트를 사용함으로써 충돌을 해결하는 방식

  (5) 개방 주소법(open addressing) : 해시 충돌이 발생하면 테이블 내의 새로운 주소를 탐사(Probe) 한 후, 비어있는 곳에 충돌된 데이터를 입력하는 방식을 말한다.

 

---

□  TIF(Today I Felt) ::

  - 자료구조와 알고리즘에 대한 이론들을 익히고 있는데 내용이 깊이가 있고 쉽지 않다. 컴퓨터가 프로그램을 어떻게 처리하고 있는지, 그리고 개발자가 프로그램이 어떻게 처리되어야 하는지를 잘 인지함으로써 프로그램을 더 빠르게, 또는 원하는 처리방식으로 만들 수 있다. 이 때 알고리즘과 자료구조를 잘 앎으로써 이를 가능케하며, 이 차이는 나중에 '좋은' 또는 '기본이 된' 개발자를 만들게 되지 않을까 싶다.