lis
-
LIS 최장증가수열 알고리즘 -2- :: 마이구미알고리즘 2018. 3. 18. 14:52
이전에 LIS 알고리즘을 다룬적이 있다.다뤘던 글의 시간복잡도는 O(n^2) 이라면, 이번에는 O(nlogn) 을 다룬다.또한, 응용된 LIS 추적도 살펴본다.결론적으로 가장 긴 증가하는 부분 수열 시리즈(1 ~ 5) 등과 같은 문제들을 해결할 수 있다.이 방식은 이분 탐색을 요구한다.LIS O(n^2) - http://mygumi.tistory.com/69이분 탐색 - http://mygumi.tistory.com/72참고 링크 - http://www.crocus.co.kr/681 O(nlogn) 방식의 경우에는 이분 탐색을 활용한 방식이다.구현에 대한 흐름은 다음과 같다. 배열 마지막 요소보다 새로운 수가 크다면, 배열에 넣는다.그렇지 않다면, 그 수가 들어갈 자리에 넣는다. (이분 탐색을 통해 들어..
-
백준 7570번 줄 세우기 :: 마이구미알고리즘 풀이/동적계획법 2017. 12. 24. 18:42
이 글은 백준 알고리즘 문제 7570번 "줄 세우기" 를 풀이한다.정올 초등부, 중등부에서 출제된 문제이다.동적계획법과 구현을 통한 2가지 풀이를 다뤄본다.문제 링크 - https://www.acmicpc.net/problem/7570 예를 들어, 5명의 어린이들에게 1부터 5까지의 번호가 주어져 있고, 다음과 같은 순서로 줄서 있다고 하자. 5 2 4 1 3위 방법을 이용해서 다음과 같이 번호순서대로 줄을 세울 수 있다. (1) 1번 어린이를 제일 앞으로 보낸다. (5 2 4 1 3 → 1 5 2 4 3)(2) 4번 어린이를 제일 뒤로 보낸다. (1 5 2 4 3 → 1 5 2 3 4)(3) 5번 어린이를 제일 뒤로 보낸다. (1 5 2 3 4 → 1 2 3 4 5)위의 예에서는 세 명의 어린이를 제일..
-
백준 2631번 줄세우기 [LIS] :: 마이구미알고리즘 풀이/동적계획법 2017. 4. 2. 00:33
이번 글은 백준 알고리즘 2631번 "줄세우기" 를 다뤄본다.이 문제는 LIS 알고리즘을 활용하여 해결할 수 있다. LIS 알고리즘, 최장증가수열은 본인이 다른 글에서 이미 다뤘었다.모른다면, 참고하고 읽으면 도움이 될 것이다. (LIS 알고리즘 관련글) 왜 LIS 알고리즘을 활용할 수 있는 지 문제를 보며 설명하겠다. KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 위해 목적지까지 번호순서대로 일렬로 서서 걸어가도록 하였다. 이동 도중에 보니 아이들의 번호순서가 바뀌었다. 그래서 선생님은 다시 번호 순서대로 줄을 세우기 위해서 아이들의 위치를 옮기려고 한다. 그리..
-
백준 3745번 오름세 [LIS] :: 마이구미알고리즘 풀이/동적계획법 2017. 2. 17. 16:00
이번 글은 백준 알고리즘 문제 3745번 "오름세"를 다뤄본다.문제의 접근은 LIS(최장 증가 부분 수열) 알고리즘 문제이다.LIS O(nlogn) - http://mygumi.tistory.com/303 본인은 LIS 알고리즘을 다룬 글이 있다. (관련 글)관련 글은 시간 복잡도 O(n^2)으로 문제를 해결했다. 오름세 문제는 O(n^2)으로는 문제를 해결할 수 없다.시간초과를 초래하니 LIS의 또 다른 접근 방식으로 문제를 해결한다. 이번에 다룰 LIS의 시간복잡도는 O(nlogn)을 가진다.이분 탐색 또는 이진 탐색이라고 불리는 알고리즘을 이용하는 방식이다. (관련 글) 전체적인 의사코드로 표현하면 아래와 같다. // nums - 주어진 수열for each num in nums if(list.siz..