코딩아 재윤해

덱(Double-Ended Queue, Deque)은 양방향 대기열이라고도 불리는 자료구조이다. 외형적으로는 queue와 비슷한 구조를 갖고있으며, 한 방향인 queue와 stack과는 다르게 LIFO, FIFO같은 순서에 구속되지 않는다. 즉, 덱은 양쪽 끝에서 삽입과 삭제가 모두 가능하며 어떤 쪽으로 입력하고 출력하느냐에 따라서 stack과 queue로 사용할 수 있다. 이때, 한쪽으로만 입력이 가능하도록 설정한 덱을 스크롤(scroll)이라고 하고 한쪽으로만 출력이 가능하도록 설정한 덱을 셸프(shelf)라고 한다. 특징 덱은 다음과 같은 특징을 갖고 있다. Stack 및 Queue를 모두 사용할 수 있다. 덱은 양쪽으로 데이터를 추가하고 삭제할 수 있기 때문에 둘 다 구현이 가능하다. 만약 양쪽 ..

탐욕 알고리즘(greedy algorithm)은 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다. 즉, 최적해를 구하는 데에 사용되는 근사적인 방법이다. 순간마다 하는 선택은 그 순간에 한해서는 최적이지만 그러한 선택들을 통해 최종적인 해답을 얻었다고 해서 그 해답이 최적이라는 보장이 없다. 예외의 상황이 있을 수 있기 때문이다. 따라서, 이러한 예외 상황을 배제하고 탐욕 알고리즘을 통해 최적의 해를 구하기 위해서는 다음과 같은 두 가지 조건을 만족시켜야 한다. 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않는다. 최적 부분 구조(Optimal Substructure) : 문제에 대한 최적해가 부분문제에..

알고리즘 로직을 코드로 구현할 때, 시간 복잡도를 고려한다는 것은 연산 횟수에 비해 시간이 얼마만큼 걸리는가를 생각하는 것이다. 즉, 문제를 해결하는 데 걸리는 시간과 입력의 함수 관계를 가리킨다. 효율적인 알고리즘을 구현한다는 것은 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구성한다는 것이다. 시간 복잡도를 표기하는 방법은 Big-O, Big-Ω, Big-θ가 있으며, 이 세 가지 표기법은 각각 최악, 최선, 평균의 경우에 대하여 나타내는 방법이다. 주로 Big-O 표기법을 사용한다. Big-O 표기법을 주로 사용하는 이유는 다음과 같다. 바로 프로그램이 실행되는 과정에서 소요되는 최악의 경우 시간까지 고려할 수 있기 때문이다. '최소 이 정도 시간 이상이 걸린다' 고려하기보다는 ..

탐색 알고리즘이란 방대한 데이터에서 목적에 맞는 데이터를 찾아내기 위한 알고리즘이다. 알고리즘의 영역은 그 범위가 매우 넓어서 프로그래밍을 하는 개발자라면 의도하지 않아도 특정 알고리즘을 사용하는 경우가 대부분일 정도이며, 알고리즘의 종류 중에서도 탐색 및 정렬은 가장 많이 사용된다. 그래프의 탐색은 하나의 노드에서 시작해서 모든 노드들을 한 번씩 탐색하는 것이 목적이다. 예를 들면, 특정 장소에서 다른 장소로 갈 수 있는지, 최단 경로를 찾는 경우 등 있다. 그래프의 데이터는 배열처럼 정렬되어있지 않기 때문에 원하는 데이터를 찾기 위해서는 모두 방문해서 찾아야 한다. 너비 우선 탐색(Breadth-First Search, BFS) 너비 우선 탐색이란 임의의 노드에서 시작해서 인접한 노드를 먼저 탐색하는..

특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것을 트리 순회(tree traversal)라고 한다. 선형 자료 구조(stack, queue 등)는 순차적으로 요소에 접근하지만, 트리 구조는 계층적 구조라는 특징을 갖고 있기 때문에 모든 노드를 순회하기 위해서는 다른 방식을 사용해야 한다. 트리를 순회하는 방법은 크게 전위 순회, 중위 순회, 후위 순회가 있으며, 노드를 방문하는 순서에 의해 결정된다. 트리 구조에서 노드를 순차적으로 조회할 때의 순서는 항상 왼쪽부터 오른쪽으로 한다. 전위 순회(preorder traversal) 전위 순회는 다음과 같은 방법으로 진행한다. 루트 또는 서브트리의 루트 노드를 방문한다. 왼쪽 서브 트리를 방문한다. 오른쪽 서브 트리를 방문한다. 방문 순서 : 1 ..

이진 트리(binary tree)는 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 구조이다. 여기서 자식 노드들은 왼쪽 자식 노드, 오른쪽 자식 노드로 나뉜다. 이진 트리는 자료의 삽입, 삭제 방법에 따라서 다음과 같이 나뉜다. 정 이진 트리(ful binary tree) : 각 노드가 0개 혹은 2개의 자식 노드를 갖는다. 포화 이진 트리(perfect binary tree) : 정 이진 트리이면서 완전 이진 트리인 경우이다. 모든 리프 노드의 레벨이 동일하고 모든 레벨이 가득 채워져 있는 트리이다. 완전 이진 트리(complete binary tree) : 마지막 레벨을 제외한 모든 노드가 가득 차 있으며, 마지막 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 한다. 이진 탐색 트리(bi..

그래프(graph)는 여러 개의 점들이 서로 복잡하게 연결되어 있는 그래프이다. 그래프는 연결할 객체를 의미하는 정점(vertext)과 객체를 연결하는 간선(edge)의 집합으로 구성되어 있다. 두 정점을 이어주는 선이 있으면 직접적인 관계이고 몇 개의 점과 선에 걸쳐서 이어진다면 간접적인 관계이다. 이어진 선에 화살표 방향이 없으면 무방향 간선, 하나의 방향이 있으면 단방향 간선, 양쪽 모두 방향이 있으면 양방향 간선이라고 한다. 실사용 예시로는 포털 사이트의 검색 엔진, 네비게이션(길 찾기) 등이 있다. 표현 방식 인접 행렬 : 두 정점을 바로 이어주는 간선이 있다면 두 정점은 인접하다고 말하며, 가장 빠른 경로를 찾고자 할 때 주로 사용한다. 인접 리스트 : 각 정점이 어떤 정점과 인접하는지를 리스..

트리(tree)란 단방향 그래프의 한 구조로, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태가 나무와 닮아 있어서 트리 구조라고 부른다. 트리 구조는 데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료구조이다. 따라서 데이터를 순차적으로 나열시킨 선형 구조가 아니라, 하나의 데이터 아래에 여러 개의 데이터가 존재할 수 있는 비선형 구조이다. 트리 구조는 계층적으로 표현이 되고 아래로만 뻗어나가기 때문에 사이클이 없다. 즉, 한 노드에서 시작해서 다른 정점들을 순회하고 자기 자신에게 돌아오는 순환이 없는 연결 그래프이다. 컴퓨터의 디렉토리 구조나 월드컵 대진표 등을 트리 구조의 예시로 들 수 있다. 구조와 특징 트리 구조는 위 그림처럼 루트(root)라는 꼭짓점 데이터부터 시작하고..

큐(queue)는 스택(stack)과 반대로 선입선출의 개념을 갖고 있다. 즉 먼저 넣은 데이터가 먼저 나오는 FIFO(First In First Out)의 자료구조로 대기열이라고도 한다. 예를 들면 고속도로의 톨게이트가 있다. 톨게이트에 먼저 진입한 자동차는 먼저 표를 뽑고 지나가게 되고 뒤에는 온 순서대로 자동차들이 대기하고 있을 것이다. 그리고 순차적으로 표를 뽑고 지나간다. 여기서 Queue에 데이터를 넣는 것을 'enqueue', 데이터를 꺼내는 것을 'dequeue'라고 한다. Queue는 보통 데이터가 입력된 순서대로 처리할 때 사용한다. Queue는 원형 큐(Circle Queue), 우선순위 큐(Priority Queue)와 같이 다른 형식도 있다. 특징 데이터는 하나씩 넣고 뺄 수 있다..

스택(stack)이란 후입선출의 특성을 갖는 자료구조이며, 한쪽 끝에서부터 데이터(data)를 순서대로 쌓고 쌓은 부분부터 데이터를 뺄 수 있는 선형 구조로 되어 있다. 프링글스를 예로 들면, 과자를 포장할 때 과자는 포장할 때 맨 밑부터 차곡차곡 쌓이게 된다. 그리고 먹을 때는 제일 마지막에 들어온 과자부터 하나씩 꺼내서 먹게 된다. 프링글스는 가장 먼저 들어간 과자는 제일 나중에 나오고, 가장 마지막에 들어간 과자가 제일 먼저 나오게 되므로 스택의 특성에 알맞을 예시라고 볼 수 있다. 이렇게 스택은 입력과 출력이 한 방향으로 이루어진다는 제한적 접근의 특징이 있다. 이런 스택의 자료구조 정책을 LIFO(Last In First Out) 혹은 FILO(First In Last Out)이라고 부르기도 한..