🔒 문제 🧠 아이디어 $$ 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 자료형이..

합차 분배법칙 $$ (A + B) mod C = {(A mod C) + (B mod C)} mod C $$ 곱셈 분배법칙 $$ AB mod C = (A mod C * B mod C) mod C $$ 거듭제곱 법칙 $$ A ^B mod C = (A ^{B/2} mod C * A ^ {B/2} mod C) mod C $$ $$ a \,\%\, m == b \,\%\, m \;이면\; a^k \,\%\, m = b^k \,\%\, m $$ 🔗 Reference 빠른 모듈로 거듭제곱법 (개념 이해하기) | 암호학이란? | Khan Academy ko.khanacademy.org

정의 최소/최대 값을 구하는 최적화 문제를 결정 문제로 변환하여 이분탐색으로 풀이하는 방식 $$ 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에서 만든 배열..

🔒 문제 🧠 아이디어 ArrayDeque 를 사용하여 테트리스의 밀어 붙이기 아이디어를 사용. 이 때, index 방향을 제대로 설정해줘야한다. 합치는 구간에서도 진행 방향쪽 블록을 먼저 합쳐야 하기 때문에 index 진행 방향에 유의해야한다. 이 부분에서 실수하기 굉장히 쉬운 문제다. 🔑 Kotlin Code import java.io.BufferedReader import java.io.InputStreamReader import kotlin.math.max enum class Direction{ EAST, WEST, SOUTH, NORTH } // (1) 0으로 빈칸은 모두 당겨오기 처리 // (2) 당겨온 다음에 겹치기. // 겹칠 때 상태 확인 // Current modification 방지 p..