DP 동적 프로그래밍이란 복잡한 문제를 더 간단한 하위 문제의 모음으로 쪼갠 후, 각 하위 문제들을 풀어 그 답을 저장하여 문제를 해결하는 문제 해결 방식을 말한다. 적용 가능한 문제 영역이 그리 넓지 않지만, 적용 가능한 경우에는 성능에 있어 아주 큰 차이를 가져온다. 두 가지 특성 Overlapping Subproblems : 한 문제를 더 작은 문제들로 나눌 수 있고, 그 조각들 중 일부가 재활용 가능해야 한다. Optimal Substructure : 하위 문제의 최적 해답을 통하여 더 큰 범주를 갖는 문제의 최적 해답을 구성할 수 있어야 한다. 재귀를 통한 구현 : 피보나치 수열 수열의 첫 번째 숫자와 두 번째 숫자는 1이며, 그 밖의 경우 Fib(n) = Fib(n-1) + FIb(n-2)이다..
SLAM 과목에서 이동체의 경로를 맵핑할 때 스쳐 배웠던 경험이 있다. 다익스트라 알고리즘은 두 정점 사이에 존재하는 최단 경로를 찾는 알고리즘이다. 그래프 구조로 이루어져 있고, 이진 힙을 사용한 우선순위 큐로 작동한다. 실생활에서 굉장히 빈번하게 사용되고 있는 알고리즘이다. 다익스트라 알고리즘 가중 그래프 다익스트라 알고리즘을 구현하기 전에 가중치 그래프를 먼저 소개하려 한다. 그래프의 정점들에 대해 가중치를 부여해 경로의 상대적인 길이를 알 수 있다. 일반적으로 구현했던 그래프의 연결 관계를 담는 키-값 객체에서 가중치가 추가로 매겨지게 된다. 시작점을 지정, 방문하여 다음 이동할 노드를 결정해야 한다. 이 때, 가장 작은 거리 가중치를 가진 노드를 선택한다. 다음 노드로 이동한 후, 그 노드의 인..
그래프 순회와 노드 탐색 그래프 순회를 구현하기 위해서는 일반적인 트리 순회와 달리 루트가 존재하지 않기 때문에, 시작점을 정해주어야 한다. 또한 여러 순서가 존재할 수 있고, 이미 방문했던 노드를 다시 방문하거나 뒤로 돌아가야 하는 경우가 있을 수 있다. 해당 차이점을 제외하고는 트리 순회에서와 마찬가지로 BFS, DFS, 재귀형과 순환형을 통해 구현한다. 웹 크롤링, 최단거리 추천, 미로찾기, GPS 네비게이션 등에서 그래프 순회가 사용된다. 실생활과 굉장히 밀접한 알고리즘이다. 깊이 우선 그래프 순회 (DFS) 이전에 학습했던 트리 구조에서의 깊이 우선 그래프 순회를 간단히 정리하자면, 형제트리를 방문하기 전에 자식 노드를 먼저 방문하는 것을 말한다. 유방향 그래프를 기준 깊이 우선 그래프에서는 ..
그래프 소개 그래프는 유한하고 변할 수 있는 꼭지점이나 노드, 점들의 집합으로 이루어진 자료구조이다. 넓게 보면 트리 구조에 속하지만, 시작점이나 진입점들이 존재하지 않고 오로지 같은 레벨의 노드만 존재한다. 꼭지점 집합에 순서 규칙이 존재하는 경우 유방향 그래프, 존재하지 않는 경우 (양방 통행이 가능한 경우) 무방향 그래프로 분류한다. 또한 연결 관계에 가중치를 부여할 수도 있다. 그래프는 노드와 연결관계로 얽혀있는 메쉬 형태 구조라고 해도 될 듯 하다. 또한 기존에 칭하던 노드를 "Vertex (정점)"으로, 노드 간의 연결관계를 "Edge (간선)"이라고 부른다. 용례 SNS 관계망 지도 기능 : 방향 안내, 위치, 길 찾기 등 웹 라우팅 : 인터넷 생태계나, 특정 웹사이트의 연결 관계 추천 알고..
해쉬 테이블은 키-값 쌍을 저장하는데 사용하는 알고리즘으로, 값을 찾거나 (탐색), 추가하거나 (삽입), 제거하는 처리 속도가 굉장히 빠르다는 특징이 있다. 순서가 있고 연속적인 데이터라면 배열을, 그 밖의 경우 해쉬 테이블(딕셔너리, 객체 등)을 사용하면 된다. 굉장히 빈번히 사용되는 알고리즘으로 많은 프로그래밍 언어들에 해당 기능이 자체적으로 내장되어 있지만, 본 섹션에서는 해쉬 테이블의 알고리즘 구조를 이해하고 직접 구현해보고자 한다. 해쉬 함수 입력받은 키에 따라 무작위 인덱스를 부여하고, 배열에 넣어 데이터를 관리해주는 단방향 함수를 말한다. 이를 통해 String 형태로 이루어진 키를 이용해 원하는 값을 찾을 수 있게 된다. 좋은 함수를 만드는 기준 탐색, 삽입, 제거 등의 데이터 처리 속도가..
이진 힙 (Binary Heap) 기본적으로 힙은 트리 구조의 한 종류이다. 이진 힙 외에도 굉장히 많은 힙 알고리즘이 존재한다. 이진 힙은 최대 힙, 최소 힙으로 구분할 수 있다. 힙 구조는 그래프 순회를 위한 우선순위 큐 (Priority Queue) 구현에 주로 사용된다. 최대 이진 힙에서는 부모 노드가 항상 자식 노드보다 큰 값을 가진다. 루트부터 노드를 타고 내려갈수록 더 작은 값을 갖는다는 뜻이다. 최소 이진 힙에서는 그 반대로, 부모 노드가 언제나 좌우의 자식 노드보다 작은 값을 갖는다. 오름차순, 내림차순으로 생각해도 될 듯 그럼 이진 탐색 트리(BST)와 비슷한 것 아닌가? 할 수 있곘지만, 이진 탐색 트리와 다르게 좌우 자식 노드의 크기 순서를 고려하지 않는다. 힙 정렬 트리 구조를 갖..
트리 순회 모든 노드를 한 번씩 도는 방법. 앞서 학습한 이진 탐색 트리 뿐 아니라, 모든 트리 구조에서 사용가능한 순회 알고리즘이다. 다른 섹션들보다 재귀를 더 많이 사용할 예정. 너비 우선 탐색 (BFS) 요소들을 거쳐가는 일반적인 순서를 기준으로 탐색 방식을 구분하였다. CSS Flexbox의 direction을 row로 주거나, column으로 주는 것도 이와 유사하다고 볼 수 있을 듯 하다. 너비 우선 탐색법(BFS)은 최상단 노드(Root)부터 가로 횡을 기준으로 수평으로 한 줄씩 내려가며 순회하는 방식이다. 구현 선입선출 구조를 갖는 큐 방식을 통해 BFS를 구현한다. 배열이나 리스트에서 Push / Shift 메서드를 사용하면 된다. 큐는 한 줄에 존재하는 노드를 담아놓는 버퍼 역할을 하며..
1. 트리 자료 구조 트리 트리란 연결 리스트와 같이 노드로 이루어진 데이터 구조를 말한다. 또한 노드 간 Branches들을 통해 연결되어 부모-자식 관계를 갖는다. 배열과 연결 리스트는 선형적인 특성을 갖지만, 트리는 비선형성을 갖고 갈 수 있는 경로가 여러 갈래로 나뉘어 진다. 트리 구조에서 노드는 부모-자식 관계에 따라 자식인 노드만을 가리킬 수 있다. *역행할 수 없으며, 형제 노드 또한 가리킬 수 없다. 하나의 출발점(Root)을 갖는다. 자식 노드를 갖지 않는 끝단의 노드를 리프(Leaf)라 한다. 노드에는 정수 뿐 아니라, 문자열이나 배열 등 다양한 형태의 데이터가 들어올 수 있다. 예시 HTML DOM은 하위 요소로서 자식을 중첩해서 가지고 있는 형태의 대표적인 트리 구조이다. 외에도 개..
1. 스택 스택이란 후입선출 원칙을 따르는 데이터 집합을 말한다. 재귀 파트에서의 호출 스택으로 사례를 접해본 적이 있다. 외에도 Undo / Redo Funtion 혹은 방문기록 라우팅 등에 스택 알고리즘이 사용된다. 배열에서는 Push / Pop 혹은 Shift / Unshift 메서드를 통해 스택을 구현할 수 있다. 맨 앞의 요소를 제어할지, 맨 마지막 요소를 제어할지의 차이이다. 연산도 측면에서는 맨 앞 요소를 변경할 경우 뒤따르는 모든 요소를 새로 배정해주어야 하기 때문에 Shift / Unshft가 열세하다. 그렇기 때문에 배열로 스택을 구현하는 것은 가능은 하지만, 효율 측면에 있어 선호하는 방법은 아니다. 연결 리스트를 통한 구현 단일 연결 리스트와 유사하다. 단, 스택에서의 메서드는 상수..
단일 연결 리스트 글과 이어집니다. 1. 이중 연결 리스트 단일 연결 리스트에서 추가적인 포인터가 하나 더 붙는게 다지만, 메서드 구현 시 많은 추가 코드를 필요로 한다. 따라서 지난 학습 때 구현했던 메서드들을 비교해보며 구현할 예정이다. 인덱스가 없고, 노드의 집합으로 이루어졌다는 연결 리스트의 특징을 여전히 갖고 있다. 추가적으로, 각 노드는 이전의 노드를 가리키는 prev 속성을 추가로 갖는다. 그러면 루프를 통해 Head부터 타고 들어갈 필요 없이, Tail부터 연산을 시작할 수 있으니 Reverse()같은 메서드를 구현하기는 더 쉬워질 것 같다. 노드 클래스 셋업 Node - val, next, prev DLL - head, tail, length class Node { constructor(..
