✍️ 코테 준비 44

[프로그래머스] 124 나라의 숫자

문제 코딩테스트 연습 - 124 나라의 숫자 programmers.co.kr 풀이 언어 Python 풀이 방법 우선 진법 변환 문제이다. 좀 특이하긴 한데 3개의 숫자를 사용하므로 3진법을 생각하면 된다. 하지만 10진수 3을 변환했을 때 10이 아니라 4가 나오는 것을 볼 수 있다. 어떻게 변환을 해야하는 것일까? 우선 변환 전과 변환 후를 표로 나타내봤다. 10진법 3진법 124 나라 1 1 1 2 2 2 3 10 4 4 11 11 5 12 12 6 20 14 3으로 나누어 떨어지는 경우에만 특이한 값을 갖는 걸 볼 수 있는데 여기에도 규칙이 있다. 맨 앞 숫자에서 -1 을 하고 뒤의 0을 4로 변환해준다는 점. 즉, 3으로 나누어 떨어지는 경우 몫에서 -1을 해준다는 의미이다. 코드 def solu..

[LeetCode] 167. Two Sum II - Input Array Is Sorted

입력 예시 풀이 언어 Python 풀이 방법 정렬된 배열에서 target을 만족하는 두 원소의 index를 반환하는 문제였다. 오름차순을 정렬된 배열이었기에 BST 문제라고 생각했다. 어렵지 않게 해결했다. 코드 class Solution: def twoSum(self, numbers: List[int], target: int) -> List[int]: start = 0 end = len(numbers) - 1 while start < end: mid = numbers[start] + numbers[end] if mid > target: end -= 1 elif mid < target: start += 1 else: return [start + 1, end + 1] 결과

[백트래킹 / Kotlin] BOJ 14889 - 스타트와 링크

문제 풀이 언어 Kotlin 코드 import java.lang.Integer.min import java.util.* import kotlin.math.abs import kotlin.system.exitProcess lateinit var board: Array lateinit var visited: Array var min_value = Int.MAX_VALUE var n = 0 fun main() = with(Scanner(System.`in`)) { n = nextInt() board = Array(n) { Array(n) { nextInt() } } visited = Array(n) { 0 } search(0, 0) println(min_value) } fun search(index: Int,..

[백트래킹 / Kotlin] BOJ 1759 - 암호 만들기

문제 풀이 언어 Kotlin 코드 import java.util.* var l = 0 var c = 0 lateinit var array: Array lateinit var sortedArray: Array lateinit var visited: Array var stringBuilder = StringBuilder() fun main() = with(Scanner(System.`in`)) { l = nextInt() c = nextInt() array = Array(c) { next() } sortedArray = array.sortedArray() visited = Array(c) { 0 } dfs(0, 0) println(stringBuilder) } fun dfs(index: Int, depth:..

[백트래킹 / Kotlin] BOJ 1987 - 알파벳

문제 풀이 언어 Kotiln 코드 import java.lang.Integer.max import java.util.* var n = 0 var m = 0 var max_value = 0 val dx = listOf(-1, 1, 0, 0) val dy = listOf(0, 0, -1, 1) lateinit var board: Array lateinit var check: Array fun main() = with(Scanner(System.`in`)) { n = nextInt() m = nextInt() board = Array(n) { Array(m) { "" } } check = Array(26) { 0 } for (i in 0 until n) { val s = next().chunked(1) for..

[수학 / Kotlin] BOJ 11050 ~ 11051 이항 계수 (1 ~ 2)

이항 계수 1 문제 풀이 언어 Kotiln 코드 import java.util.* lateinit var array: Array var n = 0 var k = 0 fun main() = with(Scanner(System.`in`)) { n = nextInt() k = nextInt() // 재귀 대신 DP로 팩토리얼 구현 array = Array(n + 1) { 1 } // 팩토리얼 계산 for (i in 2..n) { array[i] = array[i - 1] * i } // 조합 공식 적용 // nCr = n! / (n-r)! * r! println(array[n] / (array[n - k] * array[k])) } 풀이 방법 고등학교 때 배운 조합 공식 을 적용하면 어렵지 않게 해결할 수 있..

[구현 / Kotlin] BOJ 13459 - 구슬 탈출

문제 풀이 언어 Kotlin 코드 import java.util.* data class Point( val x: Int, val y: Int ) data class Points( val red_x: Int, val red_y: Int, val blue_x: Int, val blue_y: Int, val depth: Int ) data class Infos( val x: Int, val y: Int, val cnt: Int ) lateinit var array: Array val dx = arrayOf(1, -1, 0, 0) val dy = arrayOf(0, 0, 1, -1) var n = 0 var m = 0 var red = Point(0, 0) var blue = Point(0, 0) fun mai..

[백트래킹 / Kotlin] BOJ 14888 - 연산자 끼워넣기

문제 풀이 언어 kotlin 코드 import java.lang.Integer.max import java.lang.Integer.min import java.util.* var n = 0 var max_value = Int.MIN_VALUE var min_value = Int.MAX_VALUE lateinit var array: Array lateinit var operator: Array fun main() = with(Scanner(System.`in`)) { n = nextInt() array = Array(n) { nextInt() } operator = Array(4) { nextInt() } calculate(array[0], 1) println(max_value) println(min_va..

[백트래킹 / Kotlin] BOJ 2580 - 스도쿠

문제 풀이 언어 Kotlin 코드 import java.util.* import kotlin.system.exitProcess lateinit var board: Array fun main() = with(Scanner(System.`in`)) { board = Array(9) { Array(9) { 0 } } // 주어진 배열을 입력받음 for (i in 0 until 9) { for (j in 0 until 9) { board[i][j] = nextInt() } } // (0, 0) 부터 시작 sudoku(0, 0) } fun check(row: Int, col: Int, value: Int): Boolean { // 1. 같은 행, 다른 열에 같은 값이 존재하는지 확인 for (i in 0 unti..

[백트래킹 / Kotlin] BOJ 9663 - N Queen

문제 풀이 언어 Kotlin 코드 import java.util.* import kotlin.math.abs lateinit var array: Array var n = 0 var cnt = 0 fun main() = with(Scanner(System.`in`)) { n = nextInt() array = Array(n) { 0 } nQueen(0) println(cnt) } fun nQueen(depth: Int) { // depth는 row if (depth == n) { println(depth) cnt++ return } for (i in 0 until n) { // i는 col array[depth] = i if (check(depth)) { nQueen(depth + 1) } } } fun ..