1️⃣ 유니온 파인드 개념 유니온 파인드(Union-Find)는 두 개 이상의 노드가 있을 때 특정 2개의 노드를 연결해 하나의 집합으로 묶는 'union' 연산, 두 노드가 같은 집합에 속해 있는지 판단하는 'find' 연산으로 이루어진 알고리즘이다. 쉽게 말해 2개의 노드를 하나의 집합으로 만들 수 있고, 특정 노드가 속한 집합의 대표 노드를 찾을 수 있다. 아래는 각 연산에 대한 설명이다. Union 연산 : 각 노드가 속한 집합을 하나의 집합으로 합치는 연산이다. 노드 a, b가 각각 a ∈ A, b ∈ B 일 때 union(a, b) 는 A ∪ B 를 말한다. Find 연산 : 특정 노드 a에 대해 a가 속한 집합의 대표 노드를 반환하는 연산이다. 노드 a가 a ∈ A 일 때 find(a) 는 ..
1️⃣ 구간 합 (prefix sum) '구간 합' 또는 '누적 합' 은 합 배열을 통해 특정 구간의 합을 구하는 알고리즘이다. 비교적 간단하지만 코딩 테스트 출제 빈도가 꽤나 높다고 하니 잘 공부 해놔야겠다. 구간 합에서 가장 중요한 것은 합 배열이다. 다음은 합 배열을 구하는 방법을 정의한 것이다. // 기존 배열을 arr, 합 배열을 sumArr 라고 한다면 1) sumArr[i] = arr[0] + arr[1] + ... + arr[i - 1] + arr[i] 2) sumArr[i] = sumArr[i - 1] + arr[i] 예시 1) array 5 4 3 2 1 sumArr 5 9 12 14 15 만약 2번 ~ 4번 숫자의 합을 구해야 한다면 간단하게 4 + 3 + 2 = 9 라는 것을 알 수..
DFS (Depth - First Search) 깊이 우선 탐색 (DFS) 는 그래프 탐색 기법 중 하나이다. 간단히 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기의 최대 깊이까지 탐색 후, 다른 분기로 이동한 뒤 탐색을 수행하는 알고리즘이다. 기능 특징 시간 복잡도 (노드 수:V , 에지 수:E) 그래프 완전 탐색 1. 재귀 함수로 구현 2. 스택 자료 구조 이용 O(V + E) DFS 는 크게 두 가지 방법으로 구현할 수 있다. 1. 재귀 함수 2. 스택 나는 두 방법 중 재귀 함수로 구현을 많이 한다. 사실은 재귀 함수 또한 스택의 성질인 후입선출(FIFO)을 갖는다. 또한 DFS 는 한 번 방문한 노드를 재방문하면 안되기에 이를 체크해주는 배열이 필요하다. 이제 예시를 보자. 아래와 같은 그..
알고리즘에서 '그래프(Graph)' 는 굉장히 중요한 자료구조이다. 실제 코딩 테스트에서도 그래프 관련 문제가 자주 나오기 때문에 알고리즘 공부를 한다면 꼭 알아야 한다. 그래프란 노트(Node) 와 에지(Edge) 로 구성된 집합이다. 노드는 데이터의 표현 단위이며 에지는 이를 연결한다. 가장 잘 알려진 그래프 알고리즘인 DFS, BFS, Dijkstra 등 모두 그래프를 알아야 이해할 수 있다. 오늘은 그래프를 표현하는 여러 방법 중 몇 가지를 알아보고자 한다. 코딩 테스트를 준비한다면 꼭 꼭 개념을 공부하고 넘어가도록 하자. 1️⃣ 에지 리스트(Edge List) 에지 리스트는 말 그대로 에지를 중심으로 그래프를 표현하는 방법이다. 보통 2차원 배열을 사용하며 배열에 출발, 도착 노드와 가중치를 저..
1️⃣ Time Complexity : 시간 복잡도 우선 시간 복잡도를 알기 위해선 알고리즘(Algorithm) 의 개념을 이해해야 한다. 사전에 의하면 알고리즘은 수학과 컴퓨터 과학, 언어학 또는 관련된 분야에서 어떠한 문제를 해결하기 위해 정해진 일련의 절차이며, 계산을 실행하기 위한 단계적 절차를 의미한다. 즉, 문제 풀이에 필요한 계산 절차 또는 처리 과정의 순서를 말한다. 그렇다면 좋은 알고리즘, 효율적인 알고리즘은 무엇일까? 어떻게 보면 연산의 횟수와 데이터의 크기에 따른 알고리즘의 수행 시간이 적을수록 효율적인 알고리즘이라고 할 수 있다. 이를 계산하기 위한 방법이 시간 복잡도이며, 주로 'Big-O (빅-오)' 표기법을 사용한다. 이는 알고리즘의 수행 시간을 평가하는 척도라고 할 수 있다...
