문제 난이도PLATINUM V (문제 링크)  풀이LIS 알고리즘을 이진 탐색을 통해 구현하면 되는 문제로 해당 문제를 어떻게 코드로 풀어낼 것인지에 대한 아이디어도 아래 포스팅에서 자세히 다루기 때문에 구체적인 설명은 필요하지 않을 것 같다. [알고리즘] LIS (Longest Increasing Subsequence)LIS(최장 증가 부분 수열)N크기의 배열이 주어졌을때, 배열에서 일부 원소를 조합하여 만든 부분 수열 중, 오름차순의 조건을 만족하면서 길이가 최대인 부분 수열을 말한다. 아래처럼, {3, 6, 2, 1,mag1c.tistory.com  간단하게 복기하자면, 해당 문제는 전깃줄의 개수가 최대 100,000개이기 때문에, DP로 LIS를 구현해서는 풀 수가 없다.  전깃줄의 시작지점을 오..

LIS(최장 증가 부분 수열)N크기의 배열이 주어졌을때, 배열에서 일부 원소를 조합하여 만든 부분 수열 중, 오름차순의 조건을 만족하면서 길이가 최대인 부분 수열을 말한다. 아래처럼, {3, 6, 2, 1, 7, 8, 5, 4, 9}의 배열이 있다면, LIS는 {3, 6, 7, 8, 9} 이다  DPLIS 문제는 각 요소를 포함하는 증가하는 부분 수열의 최대 길이를 찾는 문제로 이를 효율적으로 해결하기 위해 동적 계획법을 사용한다.단일 배열 내에서, 이전 인덱스의 숫자와 비교하여 증가시켜주면 되기 때문에 DP로 문제를 해결할 수 있다.단일 배열이라는 점만 제외하면 LCS와 유사한 매커니즘이기에, 점화식도 비슷한 방법으로 구현할 수 있다.   [알고리즘] LCS (Longest Common Subseque..

서론 Upper Bound, Lower Bound는 이진탐색을 활용한 알고리즘이다. [알고리즘] 이진탐색(이분탐색) - Binary Search Binary Search 정렬된 데이터 집합을 이분화 하면서 탐색하는 방법 정렬되어 있어야 한다 보통 세 개의 변수를 지정해 두고 (ex : left, mid, right) 찾고자 하는 값, 즉 mid의 값이 찾아낸 값보다 크면 mid는 mag1c.tistory.com 백준에서 이진탐색을 활용한 문제를 풀다가, 깔끔하게 풀리지 않아서 풀고 난 뒤 다른 분들의 코드나 설명을 참조했더니, 내가 사용했던 조건들이 Upper Bound라는 것을 알게되었고, 정리하고자 포스팅을 진행한다. [백준 1654번 / JAVA] 랜선 자르기 문제 링크 https://www.acm..

너비 우선 탐색 ( Breadth-first search )트리나 그래프를 방문 또는 탐색하는 방법으로 루트 노드에서 시작해서 인접 노드를 먼저 탐색하는 방법.   탐색 방법1. 루트노드에서 시작한다.  2. 자식노드들을 저장한다.  3. 저장되어있는 노드를 방문하며 저장되어있는 노드들의 자식들을 저장하며  4. 위의 과정을 모든 노드를 방문할 때 까지 반복하며 완료 시 탐색을 종료한다.   특징1. 어떤 노드를 방문했는지 반드시 검사 해야 한다.2. Queue를 사용하는 경우가 일반적이며 재귀적으로 동작하지 않는다.3. Prim, Dijkstra알고리즘과 유사하다.  장점1. 노드의 수가 적고 깊이가 얕은 경우 빠르게 동작할 수 있다.2. 단순 검색 속도가 깊이 우선 탐색(DFS)보다 빠르다.3. 너비..