programmer life guidance 101

> SCC Strongly Connected Component 강한 연결 요소 방향 그래프에서 임의의 두 정점 u, v가 있을 때 u -> v로 가는 경로가 존재 한다면 그 그룹이 바로 SCC입니다. 이 때, u -> v로 가는 경로는 직/간접적인 경로를 의미합니다. 즉, SCC는 집합 내 정점들이 서로 왕복 가능한 최대 크기의 집합을 의미합니다. SCC의 특징 같은 SCC내에서 뽑은 임의의 u, v 점에서 u -> v 혹은 v -> u의 경로는 항상 존재한다. 서로 다른 SCC에서 뽑은 임의의 u, v 점에서 u -> v 혹은 v -> u의 경로는 존재하지 않는다. => 서로 다른 SCC끼리는 사이클이 존재 하지 않는다! SCC는 Maximal한 성질을 가지고 있어 SCC가 형성 된다면 항상 형성될 수..

Kadane Algorithm 카데인 알고리즘 [6, -1, 5, -3, 9] 와 같은 수열이 있다고 하자. 이 때 각 수들을 더했을 때 가장 큰 수가 나오는 연속된 부분합을 찾는 알고리즘을 카데인 알고리즘 이라고 한다. 풀이의 핵심 순서는 이러하다. 수열의 각 요소를 하나씩 더하기 더한 값을 변수에 저장 더한 값이 마지막에 저장해놓은 변수보다 크다면 변수를 대입 자바 코드로 보자 int nums = {6, -1, 5, -3, 8}; int getMaximumSubArray(int[] nums) { if (nums.length == 1) { return nums[0]; } int maxNum = Integer.MAX_VALUE; int sum = 0; // 1. 배열 요소를 하나씩 탐색하면서 값을 넣어본..

이 포스트는 https://m.blog.naver.com/PostList.nhn?blogId=kks227 의 블로그를 참조하여 따로 공부한 내용을 정리한 글입니다. > 최소 공통 조상(LCA) Lowest Common Ancestor LCA 알고리즘이란 주어진 트리에서 최소 공통 조상을 찾는 알고리즘입니다. 최소 공통 조상 이란 두 정점 u, v에서 가장 가까운 공통 조상입니다. u이거나 u의 조상이면서 동시에 v이거나 v의 조상인 노드들 중 가장 깊은 노드(가까이 있는) 노드이죠. 이런 트리가 있을 때, 4번 정점과 3번 정점의 LCA는 1번 정점입니다. 이때 빨간색으로 칠해진 간선들을 이어보면 두 정점 사이의 최단 경로가 됩니다. 10번 정점과 14번 정점의 LCA는 2번 정점입니다. 3번 정점과 1..

> 비트마스킹 bitmask : 정수의 이진수 표현을 자료구조로 쓰는 기법 데이터들은 0과 1의 집합이라고 합니다. 비트는 네트워크 외에도 운영체제 등에서도 자주 접할 수 있는데요 때문에 최적의 성능을 위해 여러 곳에서 쓰이고 있습니다. 이진 숫자로 0, 1 값을 가질 수 있고 이에 따라 true/false, on/off 와 같은 상태를 나타내는 것이 가능합니다. 비트마스크 장점 먼저 비트마스킹의 장점을 알아 보겠습니다. 빠른 수행시간 시간복잡도 O(1)에 구현되는 것이 많습니다. 비트마스크를 사용할 수 있다는 말은 원소의 수가 많지 않다는 뜻이기 때문에, 큰 속도 향상을 기대할 수는 없지만 여러번 수행해야 하는 경우에는 작은 최적화도 큰 속도 향상을 가져올 수 있습니다. 간결한 코드 양한 집합 연사자들..

> Prefix Sum 누적 합, 구간 합 누적합 또는 구간 합을 빠르게 구하는 알고리즘입니다. 여기서 주의해야할 것은 부분 합 은 0 ~ k까지의 합을 의미하는 것이고 구간 합은 a ~ b까지의 합을 의미 합니다. 이러한 알고리즘은 어디에 쓰일까요? 아래와 같은 문제를 예시로 봅시다. int arr[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} 배열이 존재한다. 이 때 a에서 b의 구간 합을 요구하는 쿼리 "2천만개"가 들어온다. 이러한 문제에 대해 어떻게 해결 할 것인가? 가장 쉬운 방식은 브루트 포스를 이용해 일일이 더하는 것입니다.하지만 쿼리 2천만개를 1초만에 해결해달라고 요구 했을 때, 이 코드의 시간복잡도를 보면 쿼리 2천만개 * (a에서 b의 합 구하는 for 문의 최악..

Longest Increasing Subsequence) 최장 증가 부분 수열 임의의 수열이 주어졌을 때, 이 수열에서 몇 개의 수 들을 선택해 부분수열을 만들 수 있는데, 이 때 만들어진 부분수열 중 오름차순으로 정렬 된 가장 긴 수열을 최장 증가 수열이라고 한다. 여기서의 부분 수열은 반드시 연속적이거나 유일하지 않아도 된다. 예를 들어 arr[ ] = {10, 20, 10, 30, 20, 50}의 수열이 있다고 할 때 여기서의 LIS는 {10, 20, 30, 50}이고 길이는 4일 것이다. 이제 이를 O(N2)과 O(nlogn)의 시간복잡도를 가지는 두 가지 방법을 알아보자. 1. DP 풀이 과정은 아래와 같다. i번째 인덱스에서 끝나는 최장 증가 부분 수열의 마지막에 arr[k]를 추가했을 때의 ..

> Levenshtein 알고리즘 편집 거리 알고리즘 (edit distance) Levenshtein distance 는 string 간 형태적 유사도를 정의하는 척도입니다. 만약 우리가 단어 사전을 가지고 있고, 사전에 등록되지 않은 단어가 발생한다면 Levenshtein distance 가 가장 가까운 단어로 치환함으로써 오탈자를 교정할 수 있습니다. 그러나 Levenshtein distance 는 계산 비용이 비쌉니다. 이 때 간단한 inverted index 를 이용하여 비슷할 가능성이 있는 단어 후보만을 추린 뒤 몇 번의 Levenshtein distance 를 계산함으로써 효율적으로 오탈자를 교정할 수 있습니다. String 간의 형태적 유사도를 정의하는 척도를 string distance ..

Longest Common Subsequence 최장 공통 부분 수열 여기서 substring은 연속된 부분 문자열이고, subsequence는 연속적이지 않은 부분 수열이다. 예로, "iamstudent" 라는 문자열에서 연속된 부분 문자열 mstu은 substring이 되고 연속적으로 이어지지는 않지만 순서는 맞는 mtue는 subsequence가 된다. 그렇다면 공통 부분 수열이란, 두 문자열이 공통으로 가지고 있는 부분 수열이다. 에를 들어 "CDABE" 와 "CDEGT"가 있다면 공통부분 수열은 {}, {C}, {D}, {E}, {C, D}, {D, E}, {C, E}, {C, D, E} 일 것이다. 최장 공통 부분 수열이란 공통 부분 수열 중에서 길이가 가장 긴 부분 수열을 뜻한다. 대표적으로..

> 트라이(Trie) 여튼 또 문자열인데, 이번엔 매칭 문제가 아니라 여러 문자열을 저장하는 자료구조를 소개해드릴 겁니다. 바로 트라이(Trie)인데, 트리와 굉장히 스펠링이 비슷하면서 트리와도 유사합니다. 아니, 아예 트리의 한 종류라고 해도 될 겁니다. 래딕스 트리(radix tree)나 접두사 트리(prefix tree)라고도 합니다. 예를 들어 {"he", "she", "her", "him", "show"}라는 문자열 집합이 있다면, 그들을 담고 있는 트라이는 그림과 같습니다. 빨간색 겹선 노드가 여기서 끝나는 문자열이 있다는 뜻으로, output이 있다고 하거나 final state, accepting node라고도 하는 등... 그런 의미가 있습니다. 왜 트라이의 별칭 중 접두사 트리라는 것이..

> 스위핑 기법(Sweeping Algorithm) 이번에 소개해 드릴 기법은 스위핑 알고리즘(sweeping algorithm)이라고 하는데, 기법 개념 자체는 굉장히 간단하고 범용적인 대신에, 대부분 겁나게 어렵습니다. 기본적으로 다른 기법이나 자료구조와 반드시 얽힙니다. 스위핑이라는 건 그냥 어떤 선이나 공간을 한쪽에서부터 싹 쓸어버린다는 건데 한 번만 전체 공간을 스캔하면서 마주치는 요소들에 대해 뭔가를 해 주면 정답이 구해지는 형태입니다. - BOJ[2170] : 선 긋기 https://www.acmicpc.net/problem/2170 [ 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N(1≤N≤1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점이 주어진다. 선택..

> 레이지 프로퍼게이션(Lazy Propagation) 이번에도 트리에 관한 내용인데, 아마 다음엔 기하 관련 내용을 쓰지 않을까 싶습니다. 특히나 세그먼트 트리에 관한 내용입니다. 지금까지는 세그먼트 트리에는 2개의 연산이 있었습니다. 특정 인덱스의 값을 바꾸는 것과, 특정 구간의 합, 최댓값 등을 구하는 것. 그런데 레이지 프로퍼게이션(lazy propagation)이란 것을 사용하면 이런 연산도 가능합니다. 특정 구간 [a, b]에 값 c를 동시에 더한다 더한다는 연산은 다른 연산이 될 수도 있습니다. 보통은 구간합 트리가 많이 쓰이므로 더하는 연산이 됩니다. 저 연산을 naive하게 구현한다면 구간 [a, b] 안의 모든 인덱스에 c씩을 더하는 업데이트 연산을 할 것이므로 구간 길이가 K면 O(K..

> Convex Hull(볼록 껍질) 볼록 껍질(convex hull)이라는 개념은 2차원 평면상에 점이 여러 개가 있을 때 이 점들 중 일부를 골라서 만들 수 있는, 나머지 점들을 모두 포함하는 볼록다각형을 말합니다. 이때 포함한다는 말은 점이 다각형의 경계에 걸쳐 있는 것도 인정합니다. 즉, 변 위에 있어도 된다는 것. 이런 점들이 있다면, 이것이 바로 볼록 껍질입니다. 볼록 껍질에 속한 점 개수는 6개군요. 그럼 이러한 다각형이 왜 항상 볼록다각형으로 결정될 수 있을까요? 사실 그건 조금만 생각해 보면 직관적으로 당연합니다. 점을 모두 포함하는 어떤 오목다각형이 있다고 해도, 오목한 지점의 점을 다각형에서 제외시키고 전후의 점을 그냥 이어버려도 새 다각형에 그 점도 포함이 되니까요. 또한, 볼록다각..

> 이분매칭 번에 올릴 글은 네트워크 플로우 개념의 연장...은 아닌 것 같고, 유량 그래프의 아주 특수하면서 메이저한 형태 하나를 다룰 겁니다. - BOJ[2188] : 축사배정 https://www.acmicpc.net/problem/2188 2188번: 축사 배정 농부 존은 소 축사를 완성하였다. 축사 환경을 쾌적하게 유지하기 위해서, 존은 축사를 M개의 칸으로 구분하고, 한 칸에는 최대 한 마리의 소만 들어가게 계획했다. 첫 주에는 소를 임의 배정해� www.acmicpc.net 저번 글에서 축사 배정 문제를 다뤘는데요. 이 문제의 유량 그래프 형태가 이러했고, 이런 형태가 상당히 특수하고 자주 나타난다고 말했는데, (모든 간선 용량은 1입니다) 여기서 왼쪽 열의 정점들은 모두 소스에서 갈 수 있..

> 네트워크 유량(Network Flow) 안녕하세요. 그래프에 대해서 1차적으로 쓸 내용 중에서는 마지막 개념에 달했습니다. 그런데 마지막 개념이기는 한데, 이 개념 한 부류를 설명하는 데 또 글을 엄청 써야 할 것 같네요. 그만큼 중요한 개념입니다. 최단 경로만큼이나... 아니 어쩌면 더... 최단 경로 알고리즘의 경우는 자료구조 수업 때 먼저 접하는 것도 있고, 최단경로가 무엇인가 하는 개념도 기초적인 편이라서 그렇게 어렵지는 않은데(알고리즘 자체는) 이번에 소개하려 하는 네트워크 유량(network flow)이란 개념은 상대적으로 생소합니다. 그래프의 간선에 거리, 시간이나 가중치, 즉 cost 대신에 용량(capacity)이라는 개념이 추가됩니다. 이제 두 정점 u, v를 잇는 간선 (u, v)..

> 오일러 경로, 오일러 회로 이번에 소개할 내용은 오일러 경로(Eulerian trail) 및 오일러 회로(Eulerian circuit)입니다. 위상수학, 이산구조 시간의 그래프 이론 챕터에서 한 번쯤 보셨을 내용입니다. 무향이나 유향 그래프가 있을 때, 그래프에 존재하는 모든 간선을 정확히 1번씩만 방문하는 연속된 경로가 바로 이것들입니다. 이때 시작점과 도착점이 같으면 오일러 회로가 되고, 아닐 경우 그냥 오일러 경로가 됩니다. 이와 같은 무향 그래프가 있을 때, 경로 [A, B, C, D, A]는 시작점으로 돌아오기는 했으나 모든 간선을 사용하지는 않으므로 오일러 회로가 아니지만(물론, 오일러 경로조차 아닙니다), 경로 [A, B, C, E, F, C, D, A]는 오일러 회로입니다. 모든 간선..