algorithm

트리 순회 Skill 모든 트리를 순회하며 부모 정보를 갱신한다. Depth (높이) 정보도 갱신한다. 핵심 아이디어 사실 트리 자료구조는 그래프에서 Cycle 이 사라지고 계층 (부모-자식 관계)가 남은 것이므로 그래프 순회 이론을 거의 그대로 적용 가능하다. 부모 노드를 제외한 다른 모든 노드를 자식으로 갖는다. 모든 자식 노드의 depth는 부모 노드의 depth + 1 이다. BFS 를 이용한 방법 // 부모를 담을 배열 parents 와 // 깊이를 보관할 배열 depths // 인접 노드를 담은 adjacentList 만 필요하다. private fun bfs(rootNode: Int, parents: IntArray, depths: IntArray, adjacentList: Array) { ..

🔒 문제 🧠 아이디어 "마을로부터 면접장 까지의 최단 거리" => 다익스트라. 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 자료형이..

합차 분배법칙 $$ (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 =..