programmer life guidance 101

> 세그먼트 트리(Segment Tree) 각 구간들을 그대로 보존하고 있는 트리 전체 구간이 [0, N-1]이라 할 때, 즉 N개의 공간이 있을 때 이렇게 리프 노드들은 길이가 1인 각각의 구간을 갖고 있고 부모 노드는 자신의 자식들의 구간의 합을 갖고 있으며 모든 구간은 연속적이어야만 합니다. 루트는 전체 구간을 포함하게 됩니다. 이렇게 각 노드가 구간, 혹은 그 구간의 정보를 저장하고 있는 자료구조를 말합니다. 보통은 완전 이진 트리의 형태를 사용해 전체적으로 동일한 재귀적 구조가 반복되도록 이렇게 표현하며, 값의 개수가 2^n 꼴이 아닐 때 남는 구간을 의미없는, 혹은 기본 값으로 채워서 포화 이진 트리 형태로 사용하는 게 대부분입니다. 이렇게 하면 값이 N개일 때 반드시 트리의 높이가 O(log..

> 분할 정복(Divide and Conquer) 알고리즘 이번에 소개해 드릴 것은 역시 유명한 기법인 분할 정복(Divide and Conquer)입니다. 탐색, DP, 그리디 등에 비해서는 등장빈도가 좀 낮지만, 이 기법의 성질 자체가 직접 문제푸는데 뿐 아니라 다른 여러 효율적인 자료구조나 알고리즘에 기여할 때가 많습니다. 분할 정복은 말 그대로 문제를 두 단계, ①분할과 ②정복으로 나눠서 해결하는 것을 말합니다. 분할하는 단계에서는 말 그대로 주어진 문제를 여러 개의 부분 문제들로 나누는데, 문제가 작아지면 작아질수록 풀기 쉬워지는 성질을 이용한 겁니다. 또한 문제의 크기가 엄청나게 줄어든다면(N=1 또는 N=2 정도) 그야말로 바로 답을 구할 수 있는 수준이 되고, 이게 재귀호출로 문제를 풀 때..

> 플로이드 와샬 알고리즘 Floyd-Warshall algorithm 앞의 두 최단거리 알고리즘과는 다르게 정점 V개가 있고 거리가 다 주어져 있을 때, 단 한번의 시행으로 모든 정점 쌍 사이의 거리를 다 구해낸다. 코드는 굉장히 짧은데, 아주 전형적인 3중 for문의 형태를 하고 있고 O(V^3)입니다. 음의 가중치가 있는 간선 그래프에서도 제대로 동작합니다. -BOJ[11404] : 플로이드 이 문제를 풀 겁니다. 아니 제목부터 대놓고 플로이드입니다. 그러므로 플로이드를 씁시다. 각 정점 u, v 쌍에 대해 u에서 v로 가는 최단 경로를 한 번에 다 구할 것이고, 이를 위해 먼저 2차원 배열 dist를 준비합니다. 초기에는 자기 자신으로 가는 dist[i][i] 꼴은 다 0이고, 나머지는 ∞으로 설..

> 벨만포드 알고리즘 이어서 소개해드릴 것은 또다른 최단경로 알고리즘입니다. 벨만 포드 알고리즘(Bellman-Ford algorithm)인데요, 알고리즘을 개발한 두 학자의 성을 따서 붙인 이름이라고 합니다. 동시에 독자적으로 알고리즘을 개발했던 또다른 학자의 이름까지 붙여서 벨만 포드 무어 알고리즘이라 명명할 때도 있다는군요. 다익스트라 알고리즘과 마찬가지로 시작점을 정해 주면 다른 모든 정점으로의 최단 경로를 구하는데, 다익스트라 알고리즘보다는 시간이 오래 걸려서 O(VE)의 시간이 걸리지만 이 알고리즘은 간선 cost가 음수일 때도 사용할 수가 있습니다!! 아니 도대체 거리가 음수라니 무슨 소리냐, 뭐 그런 거 다 떼어놓고 그냥 최단거리가 정말 작으면 작을수록 좋다고 친다면, 설령 그게 음수가 되..

> 다익스트라 알고리즘 이제부터 그래프에 대한 글만 엄청 쓸 겁니다. 한 11~12개 정도 예정되어 있네요. 그래프... 정말 어렵고, 답없고, 온갖 문제가 많기로 유명합니다. 그 중에서도 처음을 장식할 최단 경로 알고리즘은 그 종류부터 3개나 됩니다. 그 중 첫 번째 알고리즘인 다익스트라 알고리즘(Dijkstra's algorithm)에 대해서 알아보겠습니다. 이 알고리즘이 하는 일은 그래프의 어떤 정점 하나를 시작점으로 선택하고, 나머지 정점들로의 최단거리를 모두 구합니다. 시작점 자신이야 뭐 그냥 0입니다. 정점 개수가 V, 간선 개수가 E일 때 기본적인 최적화를 거치면 O(ElogV)의 시간복잡도를 갖습니다. 그래프는 무향이거나 유향인데 대체로 유향인 경우가 많고, 간선마다 이동거리가 존재합니다...

Two Pointer & Sliding Window:facepunch: > Two Pointer 1차원 배열이 있고, 이 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해가며 원하는 것을 얻는 형태의 알고리즘!! 대표적인 유형으로는 백준 2003 : 수들의 합2 문제를 보겠습니다. N칸의 1차원 배열이 있을 때, 부분 배열 중 그 원소 합이 M이 되는 경우의 수를 구하여라!? 모든 경우의 수를 다 테스트한다면, 구간 합을 구간합 배열로 O(1)만에 구한다고 해도 경우의 수가 이미 O(N2)이라 fail이다. 이 문제에서 각 원소는 자연수이고 M 또한 자연수인데, 이 조건이 성립하면 사용할 수 있는 알고리즘은 아래와 같다. 포인터 2개를 준비한다. (lo, hi), (l, r), (p, q)..

www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 문제 민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다. 어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오. 친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다. 입력 첫째 줄에 테스트 케이스의 개수..

www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 �� www.acmicpc.net 문제 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 반드시 먼저 완료되어야 할 작업들이 있다. 이 작업들은 번호가 아주 예쁘게 매겨져 있어서, K번 작업에 대해 선행 관계에 있는(즉, K번 작업을 시작하기 전에 반드시 먼저 완료되어야 하..

> Iterator Iterator는 자바의 컬렉션 프레임웍에서 컬렉션에 저장되어 있는 요소들을 읽어오는 방법을 표준화 하였는데 그중 하나가 Iterator 인터페이스이다. public interface iterator { boolean hasNext(); Object next(); void remove; } boolean hasNext() : 읽어올 요소가 남아있는지 확인한다. 있으면 true, 없으면 false를 반환 Obejct next() : 읽어올 요소가 남아있는지 확인하는 메소드. 있으면 true 없으면 false를 반환 void remove() : next()로 읽어온 요소를 삭제한다. 따라서 next()를 호출한 다음에 remove()를 호출해야 한다. ( 선택적 기능임 ) List 정렬시..

> 최소 신장 트리(MST) Minimum Spanning Tree Spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리 각 간선의 가중치가 동일하지 않을 때 단순히 가장 적은 간선을 사용한다고 해서 최소 비용이 얻어지는 것은 아니다. MST는 간선에 가중치를 고려하여 최소 비용의 Spanning Tree를 선택하는 것이다. 즉, 네트워크(가중치를 간선에 할당한 그래프)에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결하는 것이다. MST의 특징 간선의 가중치의 합이 최소여야 한다. n개의 정점을 가지는 그래프에 대해 반드시 (n-1)개의 간선만을 사용해야 한다. 사이클이 포함되어서는 안된다. MST의 사용사례 통신망, 도로망, 유통망에서 길이, 구축비용, 전송시간 등을 최소..

> 스패닝 트리(ST) 그래프 내의 모든 정점을 포함하는 트리 Spanning Tree = 신장 트리 = 스패닝 트리 Spanning Tree는 그래프의 최소 연결 부분 그래프이다. 최소 연결 = 간선의 수가 가장 적다. n개의 정점을 가지는 그래프의 최소 간선 수는 (n-1)개이고, (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되고 이것이 바로 Spanning Tree가 된다. 즉, 그래프에서 일부 간선을 선택해서 만든 트리 스패닝 트리의 특징 DFS, BFS를 이용하여 그래프에서 신장 트리를 찾을 수 있다. 탐색 도중에 사용된 간선만 모으면 만들 수 있다. 하나의 그래프에는 많은 신장 트리가 존재할 수 있다. Spanning Tree는 트리의 특수한 형태이므로 모든 정점들이 연결되어..

programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 문제설명 n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요. 다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다. 제한사항 섬의 개수 n은 1 이상 100 이하입니다. costs의 길이는 (..

> 유니온 파인드(Union-Find) 그래프 알고리즘으로 합집합 찾기 알고리즘이다. 상호 배타적 집합(Disjoint-set)이라고도 한다. Disjoint Set이란 서로 중복되지 않는 부분집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조이다. 유니온파인드의 특징 Union-Find란 Disjoint Set을 표현할 때 사용하는 알고리즘이다. 집합을 구현하는 데는 비트 벡터, 배열, 연결 리스트를 이용할 수 있으나 그중 가장 효율적인 트리 구조를 이용하요 구현한다. make-set(x) 초기화 x를 유일한 원소로 하는 새로운 집합을 만든다. union(x,y) 합하기 x가 속한 집합과 y가 속한 집합을 합친다. find(x) 찾기 x가 속한 집합의 대표값(루트 노드값)을 반환한다. 즉 ..

> 위상정렬(Topological Sort) 어떤 일을 하는 순서를 찾는 알고리즘 => 즉, 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것 위상정렬의 특징 하나의 방향 그래프에는 여러 위상 정렬이 가능하다. 위상 정렬의 과정에서 선택되는 정점의 순서를 위상 순서(Toplogical Order)라 한다. 위상 정렬의 과정에서 그래프에 남아 있는 정점 중에 진입 차수가 0인 정점이 없다면, 위상 정렬 알고리즘은 중단되고 이러한 그래프로 표현된 문제는 실행이 불가능한 문제가 된다. => 위상정렬이 가능하려면 DAG(Directed Acyclic Graph, 방향성이 있으며 사이클이 없는 그래프)여야 한다. 말 그대로 두 노드 A, B 사이에 A->B 같은 관계가 성..

문제설명 n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다. 노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요. 제한사항 노드의 개수 n은 2 이상 20,000 이하입니다. 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다. vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다. 입출력 예 입출력 예 설명..