algorithm

🔒 문제 🧠 아이디어 경우의수 - Backtracking 가능 여부 모든 CCTV가 동서남북 90도로만 회전 가능하다. CCTV 종류별로 다른 감시 영역을 갖도록하는 회전 횟수는 다음과 같다. 1번 : 4회 2번: 2회 3번: 4회 4번: 4회 5번: 1회 최대 CCTV 개수가 8개로 제한되어 있으므로 가장 경우의수가 많은 4회 기준 $$ 4^8\;=2^{16}\ $$ 약 6만 4천회므로 Backtracking 으로 모든 경우의 수를 따져보면 되겠다. 전체 킹우의 수를 어떻게 표현해야할까 모든 배열에 대한 조합이 필요하다. 이게 좀 빡치는데.. 각 CCTV 설치 지점으로부터의 방향 쌍에대한 모든 조합을 미리 keep 해둬서 구현했다. 2차원 배열에서 모든 배열의 쌍에 대한 조합을 구하는 코드가 Geeks..

🔒 문제 🧠 아이디어 N 이 50만개므로 $$ O(N^2) $$ 으로 풀었다간 무조건 시간초과다. 50만 * 50만 => 2,500억 회 로 거진 10초가 소요된다. O(N) 에 가까운 풀이를 생각해한다. == 높이를 앞에서부터 오른쪽으로 순회하며 한 번에 답을 구할 수 있어야한다. 가장 먼저 신호를 받을 타워는 높이가 내 왼쪽에 있는 것중 최신의 것이므로 새로운 타워에서 신호를 보낼 때마다 다음을 검사한다. 새로 나온 타워가 현재 stack top 보다 낮거나 같으면 stack top 타워의 번호를 정답으로 입력하고 새로 나온 타워가 현재 stack top 보다 크면 새로 나온 타워 높이보다 낮은 모든 애들을 pop해서 지워버리고 새로나온 타워 높이와 같거나 큰 애의 타워 번호를 정답으로 입력한다. 위..

🔒 문제 💡 아이디어 로프를 최대 중량 순으로 선택해야 감당 가능한 최대 무게를 구할 수 있다. 총 로프 선택 개수를 1 부터 N개 모두 해보고 최대 중량을 계산해야한다. 그럼에도 로프 중량을 큰 것 순으로 내림차순 하는게 좋은데 하나의 루프를 돌면서 index + 1 번째 로프가 현재 index + 1 개를 선택한 로프중 가장 작은 로프가 되기 때문이다. 로프를 k개 선택했을 때 들 수 있는 $$ 최대 중량값 = 가장\, 작은\, 로프\, 중량\: *\: k개 $$ 여기서 가장 작은 로프 중량 을 루프 안에서 매번 바로 선택할 수 있다. 🔑 Kotlin Code import java.io.BufferedReader import java.io.InputStreamReader import kotlin.ma..

순열 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..

재귀 하나의 함수에서 자기가 자신을 계속 호출하는 알고리즘으로 반드시 종료 조건 (Base condition) 을 갖는다.

🔒 Problem 🔑 BFS approach Create two queue with bread-first search to all nodes. To handle null case, if null, don't add left & right nodes to queue BFS Code (Kotlin) import java.util.LinkedList import java.util.Queue class TreeNode(var `val`: Int) { var left: TreeNode? = null var right: TreeNode? = null } class SameTree { fun isSameTree(p: TreeNode?, q: TreeNode?): Boolean { // 1. queue 2개 초기화 및..