두부의 코딩일기

최장 증가 부분 수열 (LIS, Longest Increasing Subsequence) 정의 주어진 수열에서 원소들의 순서를 유지하면서 증가하는 가장 긴 부분 수열을 찾는 알고리즘으로 별도로 정렬이 필요 없다. 위 그림은 주어진 배열에서의 증가하는 부분 수열을 나타낸 예시로 최장 증가 부분 수열(LIS)은 두 번째로 보이는 그림이다. 최장 증가 부분 수열 작동 원리 최장 증가 부분 수열을 찾기 위해서는 다이나믹 프로그래밍(dp)을 사용해야 된다. dp[i]는 i번째 수를 마지막 원소로 가지는 최장 증가 부분 수열의 길이다. i번째의 LIS 길이를 구하는 방법은 0부터 i-1번째까지의 값에서 i번째 수보다 값이 작고 dp값이 가장 큰 값의 +1이다. 위의 그림으로 예제를 보겠다. arr 배열에 첫 번째 ..

플로이드-워셜 (Floyd-Warshall) vs 다익스트라 (Dijkstra) 다익스트라 플로이드-워셜 사용 목적 단일 출발점 최단 경로를 찾음 모든 정점 쌍 간의 최단 경로를 찾음 가중치 제약 음의 가중치를 가진 간선을 처리할 수 없음 음의 가중치를 가진 간선을 처리할 수 잇음 기본 구조 그래프의 인접 리스트 혹은 인접 행렬을 사용함 그래프의 인접 행렬을 사용함 시간 복잡도 O(V+E)logV (우선 순위 큐를 사용했을 경우) O($N^{3}$) 알고리즘 유형 그리드 알고리즘 동적 프로그래밍 플로이드-워셜 개요 플로이드-워셜은 a → b 로 가는 비용과 a → c → b 로 가는 비용 중에 더 적은 값을 최단 거리로 판단하는 알고리즘으로 다음과 같은 점화식을 가진다. dpab= Math.min(dpa..

세그먼트 트리(Segment Tree)의 필요성 특정 구간 내 쿼리를 효율적으로 처리하기 위한 자료구조다. ✅ 구간 쿼리 : 배열 또는 리스트와 같은 시퀀스 데이터에서 특정 구간에 대한 정보를 검색하거나 수정하는 작업을 말한다. 위와 같이 arr[50]의 배열이 있다고 가정했을 때, arr[3] ~ arr[10]까지의 합을 구하고, 특정 값을 변경하려는 행위가 필요하다고 가정해보자. 1. 단순 반복문을 통한 덧셈 연산 이 방법은 O(N)의 시간복잡도를 가지고 있으며, 이를 M번 수행한다고 가정한다면 O(NM)의 시간복잡도를 가지게 된다. 특정 값 A → B로 변경하는 것은 O(1)의 시간복잡도를 가지고, 이를 M번 수행한다면 O(M)의 시간복잡도를 가진다. ▶ 시간복잡도: O(NM) + O(M) = O(..

비트마스크(BitMask)는 이진수를 사용하는 컴퓨터의 연산 방식을 이용하여 정수의 이진수 표현을 자료 구조로 쓰는 기법 ✅ 이진수 0 또는 1을 이용하므로 하나의 비트(Bit)가 표현할 수 있는 경우는 두 가지이다. 비트마스크 장점 1. 빠른 수행시간 비트마스크 연산은 bit 연산이기 때문에 O(1)에 구현되는 경우가 많다. 2. 짧은 코드 다양한 집합 연산들을 비트연산자로 한 줄로 작성할 수 있다. 3. 적은 메모리 사용량 ★ bit가 5인 경우에 $2^{5}$ 개의 경우를 표현할 수 있다. 하나의 정수로 많은 경우의 수를 표현할 수 있기 때문에 메모리 측면에서 효율적이다. 비트 연산자 연산 연산자 설명 AND & 두 개의 비트가 모두 1인 경우, 1을 반환함 OR | 두 개의 비트 중 하나라도 1인..

대학교 교과 과정에서 들어봤을 법한 시간 복잡도는 대체 무엇일까? 필자도 최근에 알고리즘 문제를 많이 접하면서 다양한 알고리즘 구현 방법에 대해서 알아가고있다. 알고리즘 문제를 해결할 때의 핵심이 바로 시간 복잡도다. 시간 복잡도란 입력값의 변화에 따라 연산을 실행할 때 걸리는 시간을 말하는 것으로 시간 복잡도가 낮을 수록 효율적인 알고리즘이라고 할 수 있다. 시간 복잡도 표기법 Big-O (빅-오) : 최악 Big-Ω (빅-오메가) : 최고 Big-θ (빅-세타) : 평균 시간 복잡도를 표기하는 방법에는 위와 같이 총 3가지가 있다. 빅-오 표기법은 최악의 경우를 고려한다. 즉, 프로그램이 실행되는 과정에서 소요되는 최악의 시간을 생각한다. 어떠한 프로그램이든 최악의 사태를 미리 방지하고 고려해야하기 ..

크루스칼 알고리즘 (Kruskal Algorithm) 정의 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘으로 최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘 중 하나이다. 최소 비용 신장 트리 (Minimum Spanning Tree) 는 무엇일까? 정점 N개를 가지는 그래프에서 (N-1)개의 간선을 연결해야한다. 연결한 간선의 가중치 합이 가장 최소가 되는 그래프 모든 정점이 연결되야하지만 싸이클이 되면 안된다. A : 간선이 5개로 N-1개를 가져야하는 신장 트리 법칙에 어긋나고, [1, 3, 4] 정점에서 순환 싸이클을 돌고 있으므로 연결 그래프이다. B : 간선이 4개로 N-1개를 가져야하는 신장 트리 법칙에 어긋나지않지만 가중치 값 (2 + 5+ 7 + 6) 으로 최소 비..

다익스트라 알고리즘 (Dijkstra) 정의 음의 가중치가 없는 그래프의 한 노드에서 각 모든 노드까지의 최단거리를 구하는 알고리즘으로 BFS와 DP를 활용하는게 특징임 다익스트라 알고리즘 작동 원리 1. 방문하지 않은 정점들 중 거리가 짧은 정점부터 방문한다. 2. 해당 정점에서 인접하고 아직 방문하지 않은 정점들의 거리를 갱신한다. 예시를 보면서 살펴보겠다. A에서 E로 가는데 최단 거리는? A → D → C → E : 1 + 2 + 6 = 9 A → C → E : 4 + 6 = 10 A → B → D → C → E : 5 + 2 + 2 + 6 = 15 1. 시작 노드를 'A' 로 설정하고 이웃한 노드 중 거리가 짧은 순으로 노드를 선택해서 가중치(1, 4, 5)를 각 각 노드에 입력한다. 2. 1번..

알고리즘 문제를 풀다보면 이분 탐색을 이용한 문제를 많이 접할 수 있습니다. 이분 탐색이란 오름차순으로 정렬된 배열에서 반으로 쪼개면서 특정한 값을 찾아내는 알고리즘입니다. 이분 탐색 과정 목표값은 42로 설정하고 아래와 같은 배열이 있다고 가정해보겠습니다. 1. 배열의 중간 '25'을 기준으로 목표값 '42'의 크기를 비교한다. 2. 목표값 '42'가 중간값 '25'보다 크기 때문에 mid+1을 low로 변경 후 다시 중간값을 찾는다. 3. 목표값 '42'가 중간값 '59'보다 작기 때문에 mid-1을 high로 변경 후 다시 중간값을 찾는다. 4. 목표값인 '42'가 중간값이랑 일치. ※ 위와 같이 계속 중간값(mid)을 기준으로 크기를 비교해서 low값과 high값을 ±1을 시키면서 일치하게 만든다..

안녕하세요. 두부입니다. 다양한 알고리즘 문제를 해결하다 보면 깊이 우선 탐색, 너비 우선 탐색, 동적 계획법 등 다양한 문제 해결 방법을 접할 수 있는데요. 이번에 알아보고자 하는 건 동적 계획법 (DP)입니다. 동적 계획법 정의 하나의 문제를 작은 문제로 단순화한 다음 점화식으로 만들어 재귀적인 구조를 활용해서 큰 문제를 해결하는 방식으로 피보나치 수열에서 시작되었다. Q. 일반적인 재귀 방식과 매우 유사한 동적 계획법을 사용하는 이유는 뭘까? A. 일반적인 재귀 방식을 사용할 경우 동일한 작은 문제들이 여러 번 반복되며 비효율적인 계산으로 빠질 수 있다. 동적 계획법은 작은 문제들을 재활용해서 사용하는 방식이기 때문에 이러한 문제에서 일반적인 재귀 방식보다 유리하다. Q. 동적 계획법의 사용 조건은..

금일 프로그래머스에서 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) 관련 알고리즘 문제를 풀다가 막혀버린 두부입니다. 이렇게 쉬워보이는 알고리즘도 못 푸니까 스스로에게 화가 나네요. 잡담은 여기까지하고 깊이 우선 탐색의 개념과 작동 방식에 대해서 알아보겠습니다. DFS (Depth-First-Search) 깊이 우선 탐색이라고 불리고 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 특징 자기 자신을 호출하는 순환 알고리즘 (재귀 함수, 스택) 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야함 탐색 하는 중에 더 이상 갈 수 없는 곳까지 가게 되면 가장 가까운 갈림길로 돌아와서 다른 방향으로 탐색을 진행함 모든 노드를 방문하고자 할 때 사용함 너비우선탐색(bfs)에 비해서 간단..