Young

단계별로 풀어보기 jh05013 Edition pt.1단계별로 풀어보기 jh05013 Edition pt.2 단계별로 풀어보기 jh05013 Edition pt.3 단계별로 풀어보기 jh05013 Edition pt.4 BOJ 길라잡이 베타 (1)BOJ 길라잡이 베타 (2) 캠프 파티 (Small) 캠프 파티 (Medium)캠프 파티 (Large) 초등학교에 입학하자 - 지역본선편초등학교를 졸업하자 - KOI편중학교에 입학하자 - 지역본선편 USACO Bronze 2014~2018 USACO Silver problems after the Platinum level is createdUSACO Silver problems until the Platinum level is created USACO Gold ..

오늘은 DP의 특별한 문제 형태라고 할 수 있는 LIS를 알아보겠습니다.보통의 DP로 풀게 되면 O(N^2)으로 풀게 됩니다. 하지만 N의 값이 커지면 O(NlogN)의 알고리즘이 필요합니다. 우선 LIS 문제 정의 부터 알아보겠습니다. The Longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order. For example, the length of LIS for {10, 22, 9, 33, 21, 50, 41, 60, 80} is..

컴퓨터로 문제를 풀 때, 보통 그 문제는 탐색을 기반으로 합니다.문제가 정의하고 있는 '공간'을 탐색합니다. 상태를 논리적으로 정의할 수 없다면, 모든 공간을 커버한다는 보장이 없기 때문에해가 맞는 것인지 판별할 수 없습니다.그 다음 공간은 이전의 상태를 통해 발생하기 때문에, 트리처럼 공간이 뻗어 나갑니다. 그 공간을 방문하는 방법 중에 'BFS'와 'DFS'가 있습니다. 지금은 BFS(Breadth First Search)를 설명하려고 합니다. 영어 뜻 그대로 넓이 우선 탐색이다. 트리의 가지를 따라서 무작정 들어가지 않고, depth를 하나씩 늘려갑니다. 아래는 BFS와 DFS를 비교하는 그림입니다. 문제에 따라 어떤 방문 방법을 선택해야 정답을 빠르게 찾을 수 있을 것인지판단하고 적용해야 합니다...