[Basic] Data43 [Algorithm] Disjoint Set의 표현: Union-Find (합집합 찾기) Disjoint Set (서로소 집합) 'Disjoint set'는 공통 원소가 없는 부분 집합들이다. 어떤 교양 대면 수업에 여러 학과 사람들이 모여있다고 해보자. 이때 교수님이 갑자기 같은 과 사람들끼리 조를 만들라고 한다. 그럼 학생들은 이리 저리 돌아다니다가 같은 과 사람을 찾으면 팀을 이뤄 같이 움직이게 될 것이다. 그리고 팀끼리도 같은 과인 것을 확인하면 두 팀은 합쳐진다. 만들어진 조들은 공통 원소가 없는 부분 집합들, disjoint set이 된다. 이 상황을 자료구조로 표현한 것이, 즉, disjoint set에 대한 정보를 저장하고 조작하는 자료 구조가 'Union-Find'다. Union-Find 알고리즘 (합집합 찾기) 대표적인 그래프 알고리즘으로 합집합 찾기라고도 불리며, 서로소 .. 2023. 3. 17. [Data Structure] 비선형 - 우선순위 큐 '우선순위 큐'는 우선순위가 가장 높은 자료가 가장 먼저 꺼내지는 큐다. C++과 python은 내장 라이브러리로 우선순위 큐를 제공하지만, 자바스크립트는 직접 구현해 사용해야한다. 우선순위 큐는 보통 힙(heap)이라는 트리를 사용해서 구현한다. 힙은 가장 큰/작은 원소를 찾는 데 최적화된 형태의 이진 트리로, 힙을 사용하면 새 원소를 추가하는 연산과 가장 큰/작은 원소를 꺼내는 연산을 모두 O(lgN) 시간에 수행할 수 있다. 여기서는 가장 큰 원소를 찾는 최대 힙(max-heap)을 만들어보자. 힙의 정의 힙이 갖는 가장 중요한 규칙은 부모 노드가 가진 원소는 항상 자식 노드가 가진 원소보다 크다는 것이다. 힙에서 이 규칙은 부모 자식 관계에만 적용된다. 이 규칙에 의하면 트리의 가장 큰 원소는 루.. 2023. 3. 16. [Data Structure] 선형 자료구조 배열 배열은 가장 기초적인 선형 자료구조다. 배열의 원소들은 메모리 상의 연속된 위치에 저장된다. 이 특성 덕분에 캐시의 효율성을 극대화 할 수 있다. 캐시는 보통 메모리의 일정 영역을 저장해놓기 때문에 배열같이 연속적인 위치에 저장된 데이터의 경우 더 빠른 속도로 접근이 가능하다. 배열의 원소들은 각각 인덱스로 구분 가능하다. 주어진 인덱스에 있는 원소를 반환하거나 변경하는 동작을 O(1)에 할 수 있다. 배열은 선언할 때 배열의 크기를 지정해야 한다는 문제점을 가지고 있다. 처음 선언한 크기보다 더 많은 자료를 집어넣을 수 없다. 동적 배열 (Dynamic Array) 배열의 크기를 변경할 수 없다는 문제를 해결하기 위해 크기가 변경되는 '동적 배열'이 고안됐다. 배열의 특성을 그대로 이어받지만 추가.. 2023. 3. 16. [Algorithm] DFS (깊이 우선 탐색. Depth-first search) 그래프와 완전탐색 자료구조에서 말하는 그래프는 여러 개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한다. 직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있고, 간접적인 관계가 있는 경우 몇 개의 점과 선에 걸쳐 이어진다. 하나의 점을 정점(vertex)라고 표현하고 하나의 선은 간선(edge)라고 표현한다. 그래프의 탐색은 하나의 정점에서 시작하여 그래프의 모든 정점들을 한 번씩 방문(탐색)하는 것이 목적이고 이를 완전탐색이라 부르기도 한다. 모든 정점 탐색 방법에는 여러 가지가 있다. 그 중 DFS가 있다. 위 그림과 같은 그래프가 있다고 가정하겠다. 이 그래프를 어떤 방법으로 완전 탐색하냐에 따라 방문하는 순서가 달라진다. DFS(Depth-First Search) 깊이 우선 탐색 루트.. 2023. 3. 13. [Algorithm] 완전 탐색 - 백트래킹(Backtracking), 깊이 우선 탐색(DFS. Depth-first search) 모든 경우의 수를 전부 고려하는 알고리즘 상태공간을 트리로 나타낼 수 있을 때 적합한 방식이다. 일종의 트리 탐색 알고리즘이라고 봐도 된다. 방식에 따라서 깊이우선탐색(Depth First Search, DFS)과 너비우선탐색(Breadth First Search, BFS), 최선 우선 탐색(Best First Search/HeuristicSearch)이 있다. 모든 경우의 수를 고려해야 하는 문제라면, DFS가 낫다. BFS로도 구현이 물론 가능하지만, BFS로 구현했다간 큐의 크기가, 심지어 속도도 똑같다. 따라서 경우의 수 구하기는 일반적으로 DFS가 편리하다. 대다수의 문제들은 DFS를 써도 일단 답은 나온다. - 나무 위키 - 백트래킹(Backtracking) 비선형으로 구성된 자료 구조를 깊이.. 2023. 3. 13. [Algorithm] BFS (너비 우선 탐색. Breadth-first search) 그래프와 완전탐색 자료구조에서 말하는 그래프는 여러 개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한다. 직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있고, 간접적인 관계가 있는 경우 몇 개의 점과 선에 걸쳐 이어진다. 하나의 점을 정점(vertex)라고 표현하고 하나의 선은 간선(edge)라고 표현한다. 그래프의 탐색은 하나의 정점에서 시작하여 그래프의 모든 정점들을 한 번씩 방문(탐색)하는 것이 목적이고 이를 완전탐색이라 부르기도 한다. 모든 정점 탐색 방법에는 여러 가지가 있다. 그 중 BFS가 있다. 위 그림과 같은 그래프가 있다고 가정하겠다. 이 그래프를 어떤 방법으로 완전 탐색하냐에 따라 방문하는 순서가 달라진다. BFS(Breadth-First Search) 너비 우선 탐색 .. 2023. 3. 13. [Algorithm] 완전 탐색 - 브루트 포스(brute force), 너비 우선 탐색(BFS. Breadth-first search) 브루트 포스(brute force) brute: 무식한, force: 힘 무식한 힘으로 해석할 수 있다. 완전탐색 알고리즘. 즉, 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져온다. 이 알고리즘의 강력한 점은 예외 없이 100%의 확률로 정답만을 출력한다. 일반적 방법으로 문제를 해결하기 위해서는 모든 자료를 탐색해야 하기 때문에 특정한 구조를 전체적으로 탐색할 수 있는 방법을 필요로 한다. 알고리즘 설계의 가장 기본적인 접근 방법은 해가 존재할 것으로 예상되는 모든 영역을 전체 탐색하는 방법이다. 선형 구조를 전체적으로 탐색하는 순차 탐색, 비선형 구조를 전체적으로 탐색하는 깊이 우선 탐색(DFS, Depth First Search)과 너비 우선 탐색(BFS, breadth.. 2023. 3. 13. [Algorithm] 탐욕 알고리즘 (Greedy Algorithm) 탐욕 알고리즘(Greedy Algorithm) Greedy는 ‘탐욕스러운, 욕심 많은’ 이란 뜻이다. 탐욕 알고리즘은 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다. 탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법이다. 탐욕 알고리즘은 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다. 하지만 탐욕 알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들이다. 탐욕 알.. 2023. 3. 13. [Algorithm] 비트마스크 (BitMask) 비트(Bit)란? 컴퓨터에서 사용되는 데이터의 최소 단위 (0과 1) 2진법을 생각하면 편하다. 우리가 흔히 사용하는 10진수를 2진수로 바꾸면? 9(10진수) → 1001(2진수) 비트마스크 (BitMask) 정수의 이진수 표현으로 자료를 표현하는 기법을 '비트마스크'라고 부른다. 예를 들어 그래프에 정점 0, 1, 2, 3 있다고 해보자. 이 그래프를 탐색할 때 DFS로 순회하든, BFS로 순회하든 보통 visited 배열을 둬서 방문한 노드인지 아닌지 확인한다. 정점 0을 방문했다면 배열 [1, 0, 0, 0]로 표현할 수 있다. 이때 배열 대신 비트마스크를 사용할 수도 있다. 비트마스크를 사용하면 정점 0을 방문한 것을 0001로 표현할 수 있다. 2와 3을 추가적으로 방문하게 된다면 1101로 .. 2023. 3. 13. [Algorithm] 다익스트라 (Dijkstra) 다익스트라(Dijkstra) 알고리즘 다익스트라 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘이다. 인공위성 GPS 소프트웨어 등에서 가장 많이 사용되는 알고리즘이다. 다익스트라 알고리즘은 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 계산한다. 이때, 거리가 음수인 간선은 포함할 수 없다. 하지만, 현실 세계에서는 거리가 음수인 경로는 존재하지 않아서 다익스트라는 현실 세계에 적용하기 매우 적합한 알고리즘 중 하나이다. 기본적으로 그리디 알고리즘을 바탕으로 하고 있다. 거리를 기록하며 이미 최단 경로를 구한 곳은 다시 구할 필요가 없기 때문에 다이나믹 프로그래밍으로 보기도 한다. 항상 최단 경로를 찾고 탐욕적으로 선택한다. - 그리디 이미 계산된 경로를 저장후,.. 2023. 3. 13. 이전 1 2 3 4 5 다음
