백준

🔒 문제 🧠 아이디어 "마을로부터 면접장 까지의 최단 거리" => 다익스트라. V: 최대 10만 E: 최대 50만 K (면접장): 최대 10만 바로 다익스트라를 돌리면 안된다. 무식하게 모든 마을로부터 면접장까지의 거리를 다 구하려하면 $$ VE Log(E) + VK $$ 로 시간 초과가 발생한다. 모든 면접장에서 마을까지의 거리로 각각 다익스트라를 돌려도 안된다. 면접장 -> 마을까지의 거리도 무식하게 다구하면 $$ KE Log (E) + KV$$ 로 마찬가지로 시간초과 난다. 아니 이거 대체 어케해..? 따라서 마을 -> 면접장이 아닌 면접장 -> 마을까지의 최단 거리를 구하는 방식으로 접근한다. 이를 통해 다음과 같이 시간 복잡도를 줄일 수 있다. $$ E Log(E) + V $$ 여기서는 '시작 ..

🔒 문제 🧠 아이디어 💡 미리 나눈 값을 합산하여 오버플로우 방지 🔑 Kotlin Code import java.io.BufferedReader import java.io.InputStreamReader private fun getRemain(n: Long): Int { var dividend = 1L var cnt = 1 while (dividend % n != 0L) { dividend = (dividend * 10) % n + (1 % n) cnt++ } return cnt } fun main() { val br = BufferedReader(InputStreamReader(System.`in`)) val stringBuilder = StringBuilder() while (true) { val l..

🔒 문제 🧠 아이디어 $$ A^B % C $$ 1. 시간 복잡도 A를 그대로 B 번 곱하면 O(AB) 시간이 걸리고 A 와 B가 모두 Int 최대일때 2^64에 가까운 시간복잡도를 갖게된다. 어떻게 하면 시간 복잡도를 낮출 수 있을까? $$ O (Log B) $$ 로 해결할 수 있게되었다. 이 때, 주의해야 할 것이 지수승이 '짝수'냐 '홀수'냐에 따라 분기되어야 한다는 것이다. 예를 들면 A^6 % c == (A^3 % c * A^3 %c) %c 지만 A^7 % c == (A^3 % c * A^3 %c A^1 % c) %c 로 나뉘어야한다. /2 연산을 할 때 피제수가 홀수인 경우 나머지 1이 버려지기 때문이다. 2. 자료형 Int 자료형은 4바이트로 $$ ~ 2^{32} - 1 $$ Long 자료형이..

정의 최소/최대 값을 구하는 최적화 문제를 결정 문제로 변환하여 이분탐색으로 풀이하는 방식 $$ O (Log N) $$ 으로 시간 복잡도를 줄일 수 있게한다. When to use? 최소/최대 값이라는 용어가 주어지고, 해당 값의 변화가 단조 증가 혹은 단조 감소 함수 일때 파라메트릭 서치가 사용 가능한지 떠올려 볼 수 있다. 대표적인 예시가 다음과 같은 랜선 자르기 문제다. 🔒 문제 🧠 아이디어 🔑 Kotlin Code import java.io.BufferedReader import java.io.InputStreamReader private fun getLowerBoundLength(cables: LongArray, N: Int) : Long{ var left: Long = 1 var right =..

🔒 문제 🧠 아이디어 세 수의 모든 조합을 구해서 해당 숫자가 집합 내에 존재하는지 확인하는 풀이를 떠올릴 수 있다. 그러나 시간초과가 반드시 걸리기 때문에 세 수의 합이라는 상황을 두 수의 합 + 나머지 한 수 == 결과 값 k 라는 식을 변형하여 시간복잡도를 낮추는데 있다. 이로서 $$ O(N^2 \,Log_2N) $$ 시간 복잡도로 풀이할 수 있다. 🔑 Kotlin Code import java.io.BufferedReader import java.io.InputStreamReader fun main() { val br = BufferedReader(InputStreamReader(System.`in`)) val N = br.readLine().toInt() val nums = IntArray(N)..

🔒 문제 🧠 접근 방법 문제풀이 자체보다 이 문제에서 요구하는 아이디어에서 얻어갈게 많다. 수의 범위와 개수가 클 때 순서대로 index 를 두고 해당 숫자를 저장-조회 할 수 없을까? 수의 범위가 크고 갯수가 많은 경우 무조건 큰 배열을 선언해서 대소비교를 하기보다 10, 15, 4, 4, 11, 14 이렇게 있다면 중복을 제거한 (4, 10, 11, 14, 15) 로 만들고 원하는 숫자를 입력했을 때 중복 제거한 배열 내에서 인덱스만 return 하면 된다. 4 -> 0 10 -> 1 11 -> 2 14 -> 3 15 -> 4 🔑 Kotlin Code 자신보다 작은 크기의 원소의 중복 제거 값을 얻기위해 오름차순 정렬 중복 원소 제거 원본 배열로부터 하나씩 해당 원소의 인덱스를 1, 2에서 만든 배열..