Stack, Queue, Graph,

문제 풀이 방법

• 테스트에 걸리는 시간을 단축하고 알고리즘 문제 풀이에 집중하기 위해, JavaScript에서 제공하는 배열(Array)과 같은 데이터 타입을 이용해 자료구조의 형태와 유사하게 구현하여 문제를 해결합니다.
• Graph도 Stack이나 Queue와 마찬가지로 사용자 정의 데이터 타입을 정의하지 않고, 배열이나 객체로 구현합니다. 문제에서 주어진 모든 간선 또는 정점을 2차원 배열이나 객체로 그래프를 구현한 다음, 해당 그래프를 활용해 탐색 알고리즘과 같이 나머지 로직을 작성합니다. Tree는 코딩 테스트 내에서 직접 구현하는 게 아니라, 해당 문제가 어떤 자료구조를 가지는지 파악해야 합니다. 그런 다음, Graph 또는 Tree의 탐색 방법을 적용해 알고리즘 로직을 작성하고 문제를 해결

• 스택(Stack)이나 큐(Queue) 등의 단어는 다소 생소하여 어렵게 느껴질 수 있습니다. 그러나 여러분은 이미 대표적인 자료구조 중 하나를 써 왔습니다. 그 자료구조는 바로 배열(Array)

스택(Stack)

• 데이터(data)를 순서대로 쌓는 자료구조
• LIFO(Last In First Out) 혹은 FILO(First In Last Out)
• 입력과 출력이 하나의 방향으로 이루어지는 제한적 접근
• push(), pop()
• ex ) 브라우저의 뒤로 가기, 앞으로 가기 기능을 구현할 때 자료구조 Stack이 활용

큐(Queue)

• 줄을 서서 기다리다, 대기행렬
• FIFO(First In First Out) 혹은 LILO(Last In Last Out)
• push(), shift()
• ex ) 컴퓨터와 연결된 프린터에서 여러 문서를 순서대로 인쇄
  컴퓨터 장치들 사이에서 데이터(data)를 주고받을 때, 각 장치 사이에 존재하는 속도의 차이나 시간 차이를 극복하기 위해 임시 기억 장치의 자료구조로 Queue를 사용합니다. 이것을 통틀어 버퍼(buffer)라고 합니다. 대부분의 컴퓨터 장치에서 발생하는 이벤트는 파동 그래프와 같이 불규칙적으로 발생합니다. 이에 비해 CPU와 같이 발생한 이벤트를 처리하는 장치는 일정한 처리 속도를 갖습니다. 불규칙적으로 발생한 이벤트를 규칙적으로 처리하기 위해 버퍼(buffer)를 사용

그래프(Graph)

• 자료구조의 그래프는 마치 거미줄처럼 여러 개의 점들이 선으로 이어져 있는 복잡한 네트워크망
• 그래프는 여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조
• 하나의 점을 그래프에서는 정점(vertex), 하나의 선은 간선(edge)
• ex ) 포털 사이트의 검색 엔진, SNS에서 사람들과의 관계, 내비게이션 (길 찾기) 등에서 사용
• 인접 정점 (adjacent vertex): 하나의 정점에서 간선에 의해 직접 연결되어 있는 정점을 뜻합니다.
• 인접 (adjacency): 두 정점 간에 간선이 직접 이어져 있다면 이 두 정점은 인접한 정점입니다.
• 가중치 그래프 (weighted Graph): 연결의 강도(추가적인 정보, 위의 예시에서는 서울-부산으로 가는 거리 등)가 얼마나 되는지 적혀져 있는 그래프를 뜻합니다.
• 비가중치 그래프 (unweighted Graph): 연결의 강도가 적혀져 있지 않는 그래프를 뜻합니다.
• 무(방)향 그래프 (undirected graph): 앞서 보았던 내비게이션 예제는 무(방)향 그래프입니다. 서울에서 부산으로 갈 수 있듯, 반대로 부산에서 서울로 가는 것도 가능합니다.
• 단방향(directed) 그래프로 구현된다면 서울에서 부산을 갈 수 있지만, 부산에서 서울로 가는 것은 불가능합니다(혹은 그 반대). 만약 두 지점이 일방통행 도로로 이어져 있다면 단방향인 간선으로 표현할 수 있습니다.
• 진입차수 (in-degree) / 진출차수 (out-degree): 한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇 개인지를 나타냅니다.
• 자기 루프 (self loop): 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다 라고 표현합니다. 다른 정점을 거치지 않는다는 것이 특징입니다.
• 사이클 (cycle): 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다고 표현합니다. 내비게이션 그래프는 서울 —> 대전 —> 부산 —> 서울 로 이동이 가능하므로, 사이클이 존재하는 그래프입니다.

그래프의 표현 방식: 인접 행렬 & 인접 리스트

인접 행렬

• 인접 행렬은 서로 다른 정점들이 인접한 상태인지를 표시한 행렬로 2차원 배열의 형태로 표현
• 정점이 이어져 있다면 1(true), 이어져 있지 않다면 0(false)으로 표시
• 만약 가중치 그래프라면 1 대신 관계에서 의미 있는 값을 저장
• 두 정점 사이에 관계가 있는지, 없는지 확인하기에 용이
• ex ) 가장 빠른 경로(shortest path)를 찾고자 할 때 주로 사용

인접 리스트

• 각 정점이 어떤 정점과 인접하는지를 리스트의 형태로 표현
• ex ) 메모리를 효율적으로 사용하고 싶을 때 인접 리스트를 사용. 인접 행렬은 연결 가능한 모든 경우의 수를 저장하기 때문에 상대적으로 메모리를 많이 차지.

Tree(단방향 그래프)

• 그래프의 여러 구조 중 단방향 그래프의 한 구조로, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태
• 데이터가 바로 아래에 있는 하나 이상의 데이터에 단방향으로 연결된 계층적 자료구조.
• 두 개의 노드가 상하 계층으로 연결되면 부모/자식 관계를 가집니다.
• 순차적으로 나열시킨 선형 구조가 아니라, 하나의 데이터 아래에 여러 개의 데이터가 존재할 수 있는 비선형 구조.
• ex ) 컴퓨터의 디렉토리 구조, 월드컵 토너먼트 대진표, 가계도(족보), 조직도 등.
• 노드(Node) : 트리 구조를 이루는 모든 개별 데이터
• 루트(Root) : 트리 구조의 시작점이 되는 노드
• 부모 노드(Parent node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 가까운 노드
• 자식 노드(Child node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 먼 노드
• 리프(Leaf) : 트리 구조의 끝 지점이고, 자식 노드가 없는 노드

이진 탐색 트리 (Binary Search Tree)

• 트리 구조는 편리한 구조를 전시하는 것 외에 효율적인 탐색을 위해 사용
• 이진 트리(Binary tree)는 자식 노드가 최대 두 개인 노드들로 구성된 트리
• 정 이진 트리(Full binary tree)각 노드가 0 개 혹은 2 개의 자식 노드를 갖습니다.
• 포화 이진 트리(Perfect binary tree)정 이진 트리이면서 완전 이진 트리인 경우입니다. 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리입니다.
• 완전 이진 트리(Complete binary tree)마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 합니다.
• 이진 탐색 트리(Binary Search Tree)는 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가지는 특징
• 이진 탐색 트리는 균형 잡힌 트리가 아닐 때, 입력되는 값의 순서에 따라 한쪽으로 노드들이 몰리게 될 수 있습니다. 균형이 잡히지 않은 트리는 탐색하는 데 시간이 더 걸리는 경우도 있기 때문에 해결해야 할 문제

트리 순회 (Tree traversal)

: 특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것을 트리 순회

• 트리 구조는 계층적 구조라는 특별한 특징을 가지기 때문에, 모든 노드를 순회하는 방법엔 크게 세 가지가 있습니다. 트리를 순회할 수 있는 세 가지 방법은 전위 순회(중간-왼-오), 중위 순회(왼-중간-오), 후위 순회(왼-오-중간)

힙 (heap)

힙 설명

• 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조
• 힙은 일종의 반정렬 상태(느슨한 정렬 상태) 를 유지한다.
• 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도
• 간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리를 말한다.
• 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.)
• ex ) 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조

BFS / DFS

• 그래프의 탐색은 하나의 정점에서 시작하여 그래프의 모든 정점들을 한 번씩 방문(탐색)하는 것이 목적입니다. 그래프의 데이터는 배열처럼 정렬이 되어 있지 않습니다. 그래서 원하는 자료를 찾으려면, 하나씩 모두 방문하여 찾아야 합니다.

내비게이션 그래프 예시

[그림] 내비게이션 그래프 예시

지하철 노선도를 보여주는 애플리케이션에서 경로를 탐색할 때에는, 최단 경로나 최소 환승 등 하나의 목적에도 여러 가지 방법이 있습니다. 이처럼 그래프의 모든 정점 탐색 방법에도 여러 가지가 있습니다. 그중에서 가장 대표적인 두 가지 방법, DFS와 BFS를 소개합니다. 이 둘은 데이터를 탐색하는 순서만 다를 뿐, 모든 자료를 하나씩 확인해 본다는 점은 같습니다.

다음의 예시를 통해 BFS와 DFS의 특징을 학습하세요. 토글 버튼을 클릭하면 예시 이미지를 확인할 수 있습니다.

한국에서 미국으로 가는 비행기를 예약하려고 합니다. 비행편에 따라 직항과 경유가 있습니다. 만약 경유하게 된다면, 해당 항공사가 필요로 하는 공항에 잠시 머물렀다가 가기도 합니다. 경유하는 시간은 비행편마다 다르고, 경유지도 다릅니다. 이렇게 다양한 여정 중에서, 최단 경로를 알아내려면 어떻게 해야 할까요?

BFS(Breadth-First Search) : 너비 우선 탐색

• 가까운 정점부터 탐색, 레벨단위로 탐색 : 깊이(1)모두 탐색 -> 깊이(2)모두 탐색 -> ...
• 주로 두 정점 사이의 최단 경로를 찾을 때 사용. 만약, 경로를 하나씩 전부 방문한다면, 최악의 경우에는 모든 경로를 다 살펴보아야 합니다.
• ex ) 한국에서 미국으로 가는 비행기를 예약하려고 합니다. 비행편에 따라 직항과 경유 중 최단 경로 찾기

DFS(Depth-First Search) : 깊이 우선 탐색

• 한 정점에서 시작해서 다음 경로로 넘어가기 전에 해당 경로를 완벽하게 탐색할 때 사용.
• BFS보다 탐색 시간은 조금 오래 걸릴지라도 모든 노드를 완전히 탐색할 수 있습니다. 만약, BFS로 탐색하게 된다면 제일 첫 번째 경로가 미국행이라도, 다른 모든 경로를 살펴보아야 합니다.
• ex ) 한국에서 출발하는 항공기의 모든 경로 중에 미국에 도착하는 여정을 알아내고 싶을 때