Algorithm 썸네일형 리스트형 LIS (Longest increasing subsequence) nlogn 해법 LIS(Longest Increasing Subsequence) 정의컴퓨터 공학에서, 최장 증가 부분 수열(Longest Increasing Subsequence) 문제는, 주어진 수열에서 오름차순으로 정렬된 가장 긴 부분수열을 찾는 문제이다. 여기서의 부분 수열은 연속적이거나 유일할 필요는 없다. 최장 증가 부분 수열 - 위키백과https://ko.wikipedia.org/wiki/%EC%B5%9C%EC%9E%A5_%EC%A6%9D%EA%B0%80_%EB%B6%80%EB%B6%84_%EC%88%98%EC%97%B4 LIS 문제는 수열에서 주어진 순서에서 벗어나지 않으면서 숫자가 증가하는 가장 긴 부분수열을 찾는 문제이다. 예를 들어 6개의 숫자가 주어져있다고 하자. 0 1 2 3 4 5 10 20 10.. 15. 위상정렬 (Topological Sorting) 위상 정렬(topological sorting)은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미합니다. 위상정렬 - 위키백과https://ko.wikipedia.org/wiki/%EC%9C%84%EC%83%81%EC%A0%95%EB%A0%AC 정의를 보아서는 쉽게 와닫지 않을듯하여 예시를 들어 설명하도록 하겠습니다. 스타크래프트를 플레이한다고 가정해보겠습니다. 게임에서 승리하기 위해서는 유닛을 생산하고 상대방을 공격하여 상대방의 모든 건물을 부숴야합니다. 유닛을 생산할 때에 더 높은 파워를 가진 고급 유닛을 생산하기 위해서는 고급 유닛을 생산할 수 있는 건물을 지어야하는데 단순히 원한다고 지을 수가 있는게 아니라 사전에 지어야하는 여러 건물들이 있습니다. 기초 건.. 14. 인덱스 트리(Indexed Tree) 인덱스 트리는 순서를 갖는 정보들이 주었을 때, 구간의 대표값이나 연산 결과를 빠르게 얻을 수 있는 자료구조입니다. 구간의 정보를 빠르게 파악할 수 있는 이유는 정보들을 2진 트리로 구성하여 두 개 노드의 부모노드에 대표값이나 연산결과를 저장했다가 구간이 주어졌을 때 최대한 커버가 가능한 구간 정보부터 압축적으로 정보를 추출하기 때문입니다. 아래와 같이 8개의 정보를 갖고 있는 배열이 주어졌다고 해봅시다. 1 ~ 8자리까지 각 배열의 자리에는 랜덤한 숫자가 주어져 있고 우리는 구간이 주어졌을 때 그 구간의 합이 얼마인지 알고 싶습니다. 1 2 3 4 5 6 7 8 3 2 8 1 2 3 5 6 만일 구간의 합을 구한다고 했을 때 단순하게 계산한다고 하면 매번 그 범위 내에서 for문을 이용하여 합을 구해야.. 1102번: 발전소 - Baekjoon Online Judge 외판원 문제(TSP: Traveling Salesperson Problem)로 대표되는 NP-난해에 해당하는 문제이다. 외판원 문제는 여러 도시가 주어졌을때 외판원이 도시별로 이동하는데 드는 비용이 각각 다른 경우 모든 도시를 다 돌고오는데 드는 비용을 어떻게 최소로 만들 것인지를 물어보는 문제이다. 외판원 문제 - 위키백과, 우리 모두의 백과사전https://ko.wikipedia.org/wiki/%EC%99%B8%ED%8C%90%EC%9B%90_%EB%AC%B8%EC%A0%9C 발전소 문제도 이와 유사하다. 여러 발전소가 주어지고 발전소가 켜져있는 경우 그 발전소를 이용하여 다른 발전소를 켤 수 있고 그때의 비용은 각각 다르게 주어진다. 이때 최소한 켜져야하는 발전소의 숫자가 주어졌을 때 그 발전소 .. 1654번: 랜선 자르기 - Baekjoon Online Judge 1654번: 랜선 자르기 - Baekjoon Online Judgehttps://www.acmicpc.net/problem/1654 랜선 자르기 문제는 이분 탐색을 이용하여 범위 내에서 원하는 개수의 랜선을 만들되 그 길이는 최대값이 되도록 하는 문제이다. 원하는 값을 찾기에는 너무 많은 값을 하나씩 대입해야 하기 때문에 이분 탐색을 이용하여 가능한 후보군을 줄임으로써 시간내에 원하는 값을 찾을 수 있다. 이분 탐색 문제를 푼다고 했을 때 구현에서 차이가 나는 부분은 어떤 기준으로 중앙값을 옮겨줄 것인가이다. 이 문제의 경우 주어진 랜선을 적절하게 잘라서 원하는 개수를 맞춰주는 것이기 때문에 랜선의 길이가 중앙값 이동의 기준이 된다. 처음 중앙값은 0에서 int의 max값 사이에 있다는 것을 가정하고 그.. 13. 이분 탐색 (Binary Search) 이진 탐색이라고도 부르는 이분 탐색은 간단하면서도 강력한 알고리즘입니다. 기본적인 알고리즘의 아이디어는 이미 정렬이 되어 있는 자료구조에서 특정 값을 찾을 때에 탐색 범위를 절반씩 나눠가면서 해당 값을 찾아가는 것입니다. 절반씩 나눠가면서 탐색하는 것에서 이분 탐색이라는 이름이 나왔다는 것을 알 수 있습니다. 이진 탐색 - 나무위키https://namu.wiki/w/%EC%9D%B4%EC%A7%84%20%ED%83%90%EC%83%89 예를 들어 설명해보도록 하겠습니다.아래와 같이 배열이 하나 주어졌다고 해봅시다. 0 1 2 3 4 5 6 7 8 9 2 5 6 10 12 13 15 17 19 23 여기서 우리가 알고 있는 것은 이 배열이 작은 수부터 큰 수까지 오름차순으로 정렬이 되어 있다는 것 뿐이고,.. 2162번: 선분 그룹 - Baekjoon Online Judge 선분 그룹이라는 문제는 기하 알고리즘 문제풀이의 기초이자 꽃이라고 할 수 있는 CCW를 이용하는 동시에 유니온 파인드를 섞어 놓은 문제였다. 문제를 보면서 대충 어떤 식으로 풀면되겠다는 것이 머리 속에 그려져서 로직도 금방 세우고 코딩도 금방했는데 의외로 계속 오답이 나서 짜증나는 문제였다. 문제를 살펴보면 여러 선분이 주어졌을 때, 만일 선분끼리 교차되거나 겹치게 되면 그 선분들은 하나의 그룹이 된다. 이 때 선분들을 몇 개의 그룹으로 묶을 수 있고 그룹 중에 가장 많은 선분을 포함하고 있는 그룹에 속한 선분이 몇 개인지 출력하면 된다. 문제를 보고 생각난 것은 CCW였다. 기하 문제를 풀어본 사람은 알겠지만, CCW를 이용하면 두 선분의 교차 여부를 쉽게 파악할 수 있다. 만일 CCW가 익숙하지 않은.. CCW(CounterClockWise) 알고리즘 CCW(CounterClockWise)는 외적을 이용해서 두 벡터의 상대적 위치를 파악하는 알고리즘이다. 좀더 구체적으로 설명하자면 하나의 정점을 기준으로 다른 두 정점으로 향하는 벡터가 존재할 때 각 정점의 상대적 위치를 판단하는 공식이다. 만일 하나의 정점에서 다른 정점으로 향하는 벡터를 기준으로 왼쪽에 존재하는 정점의 경우 외적은 양의 값을 갖게 되고, 상대적으로 우측에 있게 되면 외적은 음의 값을 갖게된다. 마지막으로 세 점이 하나의 직선 위에 놓이게 되었을 때 외적은 0이 된다. 이를 이용하여 다각형의 넓이 구하기, 정점의 위치판단(다각형 내부/외부 위치 구분), 볼록다각형 그리기(Convex Hull) 등 다양한 기하 문제를 풀어낼 수 있다. 2차원 평면상에 각각 x, y 좌표를 갖고 있는 세.. 이전 1 2 3 4 5 다음