Concept 기존 dp 메모이제이션을 활용한 LIS에서 시간복잡도를 줄이기 위해 이분탐색을 활용 기존 LIS에서 앞쪽 수열을 보고 큰 값을 찾고 값을 갱신하는데 드는 시간인 O(N)을 줄일 수 없을까에서 비롯된 방식 사전지식으로 LowerBound 이분탐색에 대한 이해와 O(N^2)방식의 이해가 요구. Feature 시간복잡도의 경우 모든 원소를 탐색하는 시간 O(N)에 대해 이분탐색 O(NlogN)을 수행함으로 총 O(N * NlogN)이므로 O(NlogN)의 시간으로 최장 증가 수열을 구할 수 있음. Implement 1. 각각의 원소 i에 대해서 현재 기록된 lis배열의 끝 인덱스와 비교하여 i가 더 크다면 뒤에 추가 2. i가 더 작을 경우 이분탐색을 통해 해당 원소가 들어갈 수 있는 자리를 탐..

문제 https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 풀이 DP Knapsack 문제 접근법 전형적인 Knapsack문제라 처음 배열의 행을 최대 BYTE 수인 10,000,000으로 두고 풀이하려함. 하지만 시간복잡도가 N이 최대 100이라 O(NM)이면 1억을 넘기 때문에 시간초과가 나기에 포기. 두번째로는 1차원 dp배열의 값을 최대 비용으로 두고 접근. 해당 문제에서 앱은 최대 100개, 비용은 각 앱 당 최대 100까지 나오기 때문에 최대 1..

문제 https://www.acmicpc.net/problem/1535 1535번: 안녕 첫째 줄에 사람의 수 N(≤ 20)이 들어온다. 둘째 줄에는 각각의 사람에게 인사를 할 때, 잃는 체력이 1번 사람부터 순서대로 들어오고, 셋째 줄에는 각각의 사람에게 인사를 할 때, 얻는 기쁨이 1번 www.acmicpc.net 풀이 부분집합으로 풀이가 가능한 문제 DP Knapsack으로 접근해봤던 문제임 접근법 Knapsack으로 풀어보자고 권유를 받아 DP 상향식으로 접근 세준이의 최대체력은 100으로 각 체력을 행으로 주어지는 사람을 열로 2차원 dp배열을 초기화 각 j번째 사람에 대해 hp[j]가 현재 체력 i보다 낮을 경우 이전 부분문제의 해와 비교하여 최대값을 갱신 누적값이 필요하기 때문에 체력 i보다..

문제 https://www.acmicpc.net/problem/17835 17835번: 면접보는 승범이네 첫째 줄에 도시의 수 N(2 ≤ N ≤ 100,000), 도로의 수 M(1 ≤ M ≤ 500,000), 면접장의 수 K(1 ≤ K ≤ N)가 공백을 두고 주어진다. 도시는 1번부터 N번까지의 고유한 번호가 매겨진다. 다음 M개의 줄에 걸쳐 www.acmicpc.net 풀이 역 인접리스트를 활용한 데이크스트라 문제 첫번째 접근법 소프티어 8차를 보고난 후 1번문제와 비슷하다 판단하여 그리디하게 접근함… 각 면접장마다 i번째 면접장소를 end로 잡고 각 정점으로부터 i번째 면접장까지의 최단거리를 구함 두번째 접근법 제일 처음 떠올렸던 접근인데 각 면접장으로부터 다른 정점들까지의 최단경로를 구함으로써 한번..