siino's 개발톡

https://school.programmers.co.kr/learn/courses/30/lessons/43238 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제의 힌트는 제약사항에서 확인할 수 있습니다. 결국 기다리는 사람은 최대 10억명이므로 각각의 대기자에 대해서 문제를 해결할 순 없습니다. 결국 심사관 관점에서 문제를 풀어야함을 알 수 있고 문제가 결국 가장 효율적으로 심사하는 시간의 최솟값을 구하는 문제라는 것에 주목한다면, 최적화문제를 결정문제로 바꾸는 Parametric Search를 생각해볼 수 있습니다. 심사관이 심사하는데 걸린 소요시..

https://www.acmicpc.net/problem/11053 최장 증가 부분 수열은 말 그대로 수열의 부분 수열 중에 가장 길이가 긴 것을 구하는 문제이다. 최장 증가 부분 수열을 푸는 방법은 크게 3가지로 분류된다. 1. 무식하게 풀기 - 완전탐색 (재귀) 2. dp 풀이 - 메모이제이션을 활용 3. 이분탐색을 활용한 풀이 - LIS(k): 길이가 k인 LIS 중 마지막 수가 최소인 수를 저장 ## 각각의 시간복잡도는 어떻게 될까? 1. 완전탐색 --------> O(2^N) 2. dp --------> O(N^2) 3. 이분탐색 --------> O(NlogN) 개념이 계속 헷갈려서 각각의 방법을 활용하여 직접 java 코드로 구현해보았다. 아래의 java 코드를 함께 보면서 알아보도록 하자...