트리 순회 Skill 모든 트리를 순회하며 부모 정보를 갱신한다. Depth (높이) 정보도 갱신한다. 핵심 아이디어 사실 트리 자료구조는 그래프에서 Cycle 이 사라지고 계층 (부모-자식 관계)가 남은 것이므로 그래프 순회 이론을 거의 그대로 적용 가능하다. 부모 노드를 제외한 다른 모든 노드를 자식으로 갖는다. 모든 자식 노드의 depth는 부모 노드의 depth + 1 이다. BFS 를 이용한 방법 // 부모를 담을 배열 parents 와 // 깊이를 보관할 배열 depths // 인접 노드를 담은 adjacentList 만 필요하다. private fun bfs(rootNode: Int, parents: IntArray, depths: IntArray, adjacentList: Array) { ..
Algorithm/Algorithm (이론)
합차 분배법칙 $$ (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 =..
비트마스킹 기법을 사용하기 위해 익혀야할 비트연산자를 정리해보자. 1. 길이 N을 갖는 이진수를 모두 1 (flag on) 상태로 만들기 표현식 $$ (2 11111 // 십진수로는 2 ^ N - 1 로 표현가능하다. // 2 ^ 6 - 1 == 63 val num = (1 shl (5 + 1)) - 1 println("=============") println("All flag on") println(toDecimalString(num)) println(toBinaryString(num)) println("=============") } 결과 2. 특정 index flag bit 키기 표현식 $$ num\; or \; (1 11111 // 십진수로는 2 ^ N - 1 로 표현가능하다. // 2 ^ 6 ..
알고리즘 문제에 간간히 등장하는 행렬 회전 로직, N * N 정사각형은 물론 N * M 직사각형 행렬에도 활용 가능한 코드를 미리 작성해보자. 📝 규칙 요점 정리 90도 회전함수 원본 행렬을 90도 회전시켜서 회전된 행렬을 반환한다. fun rotate(originalArray: Array) : Array { val originalRowSize = originalArray.size val originalColSize = originalArray.first().size // 행 열 크기 전환 val rotatedArray = Array(originalColSize){IntArray(originalRowSize)} for (row in originalArray.indices) { for (col in ori..
순열 N : 자연수 R : 뽑을 갯수 nPr 구하기! 자연수 import org.junit.jupiter.api.Test import java.util.* class Permutation { private var N: Int = 0 private var R: Int = 0 private fun dfs(curNum: Int, visited: BooleanArray, depth: Int, strBuilder: StringBuilder, answerList: LinkedList) { strBuilder.append(curNum) if (depth == R) { answerList.add(strBuilder.toString().toInt()) strBuilder.setLength(strBuilder.length..
