알파-베타 가지치기는 미니맥스와 같은 답을 내면서 결과를 바꿀 수 없는 가지를 건너뜁니다. 두 경계를 추적하는데, alpha는 MAX가 이미 확보한 최선의 점수이고 beta는 MIN이 이미 확보한 최선의 점수입니다.
게임 트리는 완전 트리입니다. 모든 내부 노드는 branching개의 자식을 가지고, 모든 리프는 같은 깊이에 있습니다. leaves는 리프 점수를 왼쪽에서 오른쪽으로 나열합니다. 루트는 MAX 노드이고 층은 MAX, MIN, MAX, … 순서로 번갈아 나옵니다.
alpha = -∞, beta = +∞에서 시작해 자식을 왼쪽에서 오른쪽으로 탐색합니다.
- MAX 노드에서는 각 자식 다음에 best = max(best, value), 그다음 alpha = max(alpha, best).
- MIN 노드에서는 각 자식 다음에 best = min(best, value), 그다음 beta = min(beta, best).
- alpha ≥ beta가 되는 즉시 그 노드의 나머지 자식을 건너뜁니다.
alpha_beta(leaves, branching)를 구현하세요.
입력
leaves: 왼쪽에서 오른쪽으로의 리프 점수. 길이는 branching의 거듭제곱입니다.
branching: 내부 노드당 자식 수.
출력
[value, evaluated]를 반환합니다. 루트의 미니맥스 값과 평가한 리프 수입니다.
제약 조건
2 ≤ branching ≤ 5, leaves 길이 = branching^depth (1 ≤ depth ≤ 8), 리프는 최대 10,000개
-1,000 ≤ 각 리프 ≤ 1,000
예시
입력:
leaves = [3, 12, 8, 2, 4, 6, 14, 5, 2]
branching = 3
예상 출력:
[3, 7]설명
첫 번째 MIN 노드는 3, 12, 8을 보고 3을 반환하므로 alpha = 3입니다. 두 번째 MIN 노드는 2를 보고 beta = 2 ≤ alpha가 되어 4와 6을 건너뜁니다. 세 번째는 14, 5, 2를 보고 2를 반환합니다. 루트 값은 max(3, 2, 2) = 3이며, 9개 중 7개의 리프를 확인했습니다.
입력:
leaves = [5, 6, 7, 4]
branching = 2
예상 출력:
[5, 4]설명
왼쪽 MIN 노드는 5와 6을 평가하고 5를 반환하므로 alpha = 5입니다. 오른쪽 MIN 노드는 7 (beta = 7), 다음으로 4 (beta = 4 ≤ 5)를 평가합니다. 리프 4개가 모두 평가되고 값은 5입니다.
참고 자료
-
예시 1 미실행입력:
leaves = [3, 12, 8, 2, 4, 6, 14, 5, 2] branching = 3예상 출력:[3, 7]내 출력 -
예시 2 미실행입력:
leaves = [5, 6, 7, 4] branching = 2예상 출력:[5, 4]내 출력
제출 시 4개의 숨겨진 테스트도 실행됩니다. 코드가 하나라도 실패하면 그 테스트를 볼 수 있습니다. 챌린지를 해결하면 모두 볼 수 있습니다.
Online Kotlin Compiler
Write, compile, run, and debug Kotlin code online in a full-featured browser IDE. Work with multiple files, save your workspace, and collaborate in real time.
🧩 이 Kotlin 온라인 실행기 소개
CodeUtility Kotlin Executor를 사용하면 브라우저에서 바로 Kotlin 코드를 작성, 컴파일, 실행할 수 있습니다 - 설치, IDE, SDK 설정이 필요 없습니다. 격리된 샌드박스에서 실제 Kotlin 컴파일러가 동작해 안전하고 실제와 같은 실행 환경을 제공합니다.
이 도구는 여러 Kotlin 버전 - 1.6, 1.9, 2.1 - 을 지원하므로 문법 업데이트를 살펴보고, 코드 호환성을 테스트하며, 코루틴, 데이터 클래스, 봉인 인터페이스 같은 최신 언어 기능을 자유롭게 실험할 수 있습니다.
Kotlin 기초를 배우는 학생, 스니펫을 실험하는 Android 개발자, 혹은 브라우저를 벗어나지 않고 JVM 환경에서 로직을 테스트하려는 백엔드 엔지니어에게 안성맞춤입니다.
각 스니펫은 보안 컨테이너 런타임에서 실행되어 일관된 성능과 안전한 코드 실행을 보장합니다.
하나의 실행기에서 다중 파일 편집기, 격리된 실행 터미널, 런타임별 라이브러리, 영구 작업 공간, 공유 및 실시간 협업을 이용하세요.
이 실행기는 어떻게 사용하나요?
런타임을 선택하고 파일을 열거나 만든 다음 코드를 작성하고 실행을 선택하세요. 출력은 터미널에 표시되며, 로그인한 사용자는 작업 공간에 파일을 보관하고 라이브러리를 설치하며 공유를 통해 협업할 수 있습니다.
- 버전을 선택하고 현재 파일을 편집하거나 작업 공간의 다른 파일을 여세요.
- 코드를 실행하고 요청 시 터미널에 입력한 다음 저장된 실행 기록을 확인하세요.
- 작업에 둘 이상의 코드 조각이 필요하면 라이브러리, 작업 공간 도구, 공유 및 채팅을 사용하세요.
💡 초보자를 위한 Kotlin 기본 가이드
1. 변수와 상수 선언
Kotlin은 val은 변경 불가능, var는 변경 가능한 변수에 사용합니다.
val name: String = "Alice"
var age: Int = 30
val pi = 3.14 // 타입이 추론됨
// 상수
const val MAX_USERS = 1002. 조건문 (if / when)
if 표현식이나 여러 분기는 when을 사용하세요.
val x = 2
if (x == 1) {
println("하나")
} else if (x == 2) {
println("둘")
} else {
println("그 외")
}
when (x) {
1 -> println("하나")
2 -> println("둘")
else -> println("그 외")
}3. 반복문
반복에는 for, while, do-while을 사용합니다.
for (i in 0..2) {
println(i)
}
var n = 3
while (n > 0) {
println(n)
n--
}4. 배열
Kotlin은 arrayOf() 함수를 사용해 배열을 지원합니다.
val numbers = arrayOf(10, 20, 30)
println(numbers[1])5. 리스트 다루기
동적 리스트에는 mutableListOf를 사용하세요.
val nums = mutableListOf(1, 2, 3)
nums.add(4)
nums.removeAt(0)
for (n in nums) {
print("$n ")
}6. 콘솔 입력/출력
입력에는 readLine(), 출력에는 println()을 사용합니다.
print("이름을 입력하세요: ")
val name = readLine()
println("안녕하세요, $name")7. 함수
함수는 fun 키워드와 선택적 반환 타입을 사용합니다.
fun add(a: Int, b: Int): Int {
return a + b
}
println(add(3, 4))8. 맵
mutableMapOf는 키-값 쌍을 저장합니다.
val ages = mutableMapOf("Alice" to 30)
println(ages["Alice"])9. 예외 처리
try, catch, finally로 오류를 처리하세요.
try {
val result = 10 / 0
} catch (e: ArithmeticException) {
println("오류: ${e.message}")
}10. 파일 입출력
파일 작업에는 java.io의 File을 사용합니다.
import java.io.File
File("file.txt").writeText("안녕, 파일")
val text = File("file.txt").readText()
println(text)11. 문자열 다루기
Kotlin 문자열은 다양한 메서드와 문자열 보간을 지원합니다.
val text = "안녕하세요 세상"
println(text.length)
println(text.substring(0, 5))
println(text.contains("세상"))12. 클래스와 객체
Kotlin 클래스는 간결하며 기본 생성자를 지원합니다.
class Person(val name: String) {
fun greet() = println("안녕하세요, 저는 $name입니다")
}
val p = Person("Alice")
p.greet()13. 널 안전성
Kotlin은 널 허용 타입과 널 비허용 타입을 구분합니다. 안전을 위해 ?와 ?:를 사용하세요.
val name: String? = null
println(name?.length ?: 0)