초보몽키의 개발공부로그

알고리즘, 자료구조 여러가지 메모

28 May 2017 |

기본 알고리즘

알고리즘

알고리즘 이란 어떤 값을 입력으로 받아 원하는 값으로 출력하는 잘 정의된 계산 절차 를 말한다. 따라서 알고리즘은 어떤 입력을 어떤 출력으로 변환하는 일련의 계산 과정이라 할 수 있다.

자료구조

자료구조 란 데이터에 편리하게 접근하고, 변경하기 위해서 데이터를 저장하거나 조직하는 방법 을 말한다. 모든 목적에 맞는 자료구조는 없다. 따라서 각 자료구조가 갖는 장점과 한계를 잘 아는 것이 중요하다.

자료구조의 미션 : 메모리의 효율적인 사용

  • 컴퓨터에는 3가지 중요한 부품이 존재하며 다음과 같은 특성을 가진다.
    • CPU : 중앙정보처리장치, 레지스터, 데이터를 연산/처리하는 가장 중요한 부분, 아주 빠름 (기억 떠올리기)
    • 메모리 : RAM(Random Access Memory), CPU에서 직접 접근이 가능, 사용자가 자유롭게 내용을 읽고 쓰고 지울 수 있다. 휘발성 기억장치, 빠름 (책에서 특정한 내용 찾아 읽기)
    • 스토리지 : HDD, SSD, 비휘발성 기억장치, 용량이 아주 크지만 느림 (지구를 한바퀴 돌아서 찾기)
  • 상기와 같은 이유로 데이터는 기본적으로 스토리지에 저장된다.
  • 하지만 스토리지는 매우 느리기 때문에 CPU와 함께 일하기에는 속도면에서 부족하다.
  • 따라서 어떤 프로그램을 실행하면 해당 프로그램과 데이터는 메모리로 옮겨진다.
  • CPU는 메모리에 로드된 데이터를 이용해서 여러가지 일을 하게 된다.
  • 그러므로 실행속도를 결정하는 것은 대체로 메모리 이며, 자료구조를 배우는 이유는 메모리의 효율적인 사용 이라고 할 수 있다. 2917

정렬

정렬은 아래와 같은 이유로 알고리즘 연구에서 가장 기본적인 문제로 여겨지고 있다.

  • 정보를 정렬하는 것 자체가 필요한 응용 분야가 있다. (ex. 은행의 고객 청구서)
  • 정렬을 핵심 서브 루틴으로 사용하는 알고리즘이 많다. (ex. 바이너리 서치)
  • 정렬은 역사가 길고, 기술도 풍부하다. 역사가 긴 정렬 알고리즘에는 중요한 기술이 포함되어 있다.
  • 정렬 알고리즘 구현시 여러 공학적 논쟁점이 나타난다. (캐시와 가상 메모리 등 메모리 계층구조)

힙정렬과 우선순위 큐

힙은 데이터에서 최대값 (혹은 최소값)을 빠르게 찾아내도록 만들어진 자료구조 이다.
힙은 완전이진트리에 기반한 자료구조로, 부모노드와 자식노드의 대소관계에 따라 최소힙 / 최대힙으로 구분된다. (힙이란 완전 이진트리에 있는 노드 중에서 키 값이 가장 큰 노드나, 키 값이 가장 작은 노드를 찾기 위해서 만든 자료구조)

힙정렬

  • 힙 정렬(Heapsort)이란 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법으로서,
    내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다.
  • 힙 정렬이 가장 유용한 경우는, 전체 자료를 정렬하는 것이 아니라 가장 큰 값 몇개만 필요할 때이다.
  • 힙 정렬은 훌륭한 알고리즘이지만 퀵정렬이 일반적으로 더 빠르다. - 시간복잡도 O(n log n)
  • 하지만 힙은 그 자체로 대단히 쓸만한 자료구조이며, 대표적으로 우선순위 큐 구현시에 힙이 사용된다.

우선순위 큐

  • 우선순위를 가진 항목들을 저장하는 큐, 입력순서와 상관없이 우선순위가 높은 데이터가 가장 먼저 처리된다.
  • 선입선출 개념에서 약간 변형을 한것으로 나중에 들어왔지만, 먼저 처리해야 하는 자료가 발생할 경우에 필요로 한다. 이러한 판단은 어떤 상황을 회피하거나, 우선 순위를 두어야 하는 상황에서 사용한다.
  • 활용예시
    • OS에서 프로세스 스케줄링에 우선순위 큐를 활용할 수 있다.
    • 최대 우선순위 큐의 응용분야 중 하나는 공유 컴퓨터에서 작업 순서를 계획하는 것이다. 최대 우선순위 큐는 실행할 작업과 상대 우선순위를 계속 기억하고 있다. 한 작업이 끝나거나 중단될 때, Extract-max를 이용하여 대기중인 작업 중 가장 우선순위가 높은 작업을 선택한다. 새로운 작업은 insert를 사용하여 큐에 새로 들어갈 수 있다.

기본 자료구조

스택과 큐

스택과 큐는 삭제 연산에 의해 집합에서 삭제되는 원소가 미리 제한된 동적집합이다.
(삽입과 삭제의 위치와 방법이 제한된 유한 순서 리스트)

스택

  • 스택 에서는 가장 최근에 삽입된 원소가 삭제된다. 스택은 후입선출(LIFO) 정책을 구현한 것이다.
  • 스택에서 삽입 연산은 Push, 삭제 연산은 Pop이라 불린다.
  • 비어있는 스택에서 원소를 추출하려고 할 때 stack underflow라고 하며, 스택이 넘치는 경우 stack overflow 라고 한다.
  • 활용예시 : 후입선출(LIFO)의 특징을 활용하여 여러 분야에서 활용 가능하다.
    • 웹 브라우저 방문기록 (뒤로가기)
    • 실행취소 (undo)
    • 역순 문자열 만들기
    • 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)
    • 후위표기법 계산

큐

  • 큐 에서는 집합에서 가장 오랜 시간 존재했던 원소를 삭제한다. 큐는 선입선출(FIFO) 정책을 구현한 것이다.
  • 큐에서 삽입 연산은 Enqueue, 삭제연산은 Dequeue라 한다.
  • 스택에서는 원소의 삽입, 삭제가 스택의 한 끝에서 이루어지고, 큐에서는 원소의 삽입, 삭제가 큐의 서로 다른 쪽 끝에서 이루어진다.
  • 양방향 큐 (deque) - 데크 는 원소의 삽입, 삭제가 양쪽 방향에서 이루어진다.
    (큐와 스택을 합친 것으로 선입선출/후입선출의 복합적인 성격이 필요한 경우에 사용)
  • 활용예시 :선입선출(FIFO)의 특징을 활용한 활용예시
    • 우선순위가 같은 작업 예약 (인쇄 대기열)
    • 선입선출이 필요한 대기열 (티켓 카운터)
    • 콜센터 고객 대기시간

해시 테이블

  • 해시 테이블은 사전을 구현하는 가장 효율적인 자료구조이다.
  • 이론적으로는 해시 테이블에서 원소를 찾는 것이 연결 리스트에서 원소를 찾는 것 (O(n)) 만큼 오래 걸릴 수 있지만, 실제 해싱은 성능이 탁월하다.
  • 일반적으로 해시 테이블에서 원소를 찾는 데 걸리는 수행시간은 O(1)이다.
  • 해시 테이블은 단순한 표현인 배열을 일반화 한 것이다.
  • 일반적인 배열에 대한 직접 번지화 방법은 배열의 임의의 위치를 O(1)안에 접근하게 하는 효율적인 방법이다.

Related Posts