알파-베타 가지치기는 미니맥스와 같은 답을 내면서 결과를 바꿀 수 없는 가지를 건너뜁니다. 두 경계를 추적하는데, 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 Java Compiler
Write, compile, run, and debug Java code online in a full-featured browser IDE. Work with multiple files, save your workspace, and share or collaborate in real time - no setup required.
☕ 이 Java 온라인 실행기 소개
CodeUtility Java Executor는 브라우저에서 바로 Java 프로그램을 작성하고 실행할 수 있게 해줍니다 - 설치, JDK 설정, IDE가 필요 없습니다. 실제 Java 런타임 버전 8, 11, 17, 21, 그리고 최신을 지원하는 안전한 샌드박스에서 동작합니다.
이 도구는 실제 javac 컴파일러와 Java 런타임 환경을 사용해 클라우드에서 코드를 컴파일하고 실행하므로,
로컬과 동일한 방식으로 클래스, 메서드, 로직을 정확히 테스트할 수 있습니다.
객체지향 프로그래밍을 연습하든, 면접을 준비하든, 통합 전에 스니펫을 시험해 보든, CodeUtility Java Executor는 어떤 기기에서든 즉시 실제 Java 코드를 실행할 수 있는 빠르고 신뢰할 수 있는 환경을 제공합니다.
하나의 실행기에서 다중 파일 편집기, 격리된 실행 터미널, 런타임별 라이브러리, 영구 작업 공간, 공유 및 실시간 협업을 이용하세요.
이 실행기는 어떻게 사용하나요?
런타임을 선택하고 파일을 열거나 만든 다음 코드를 작성하고 실행을 선택하세요. 출력은 터미널에 표시되며, 로그인한 사용자는 작업 공간에 파일을 보관하고 라이브러리를 설치하며 공유를 통해 협업할 수 있습니다.
- 버전을 선택하고 현재 파일을 편집하거나 작업 공간의 다른 파일을 여세요.
- 코드를 실행하고 요청 시 터미널에 입력한 다음 저장된 실행 기록을 확인하세요.
- 작업에 둘 이상의 코드 조각이 필요하면 라이브러리, 작업 공간 도구, 공유 및 채팅을 사용하세요.
💡 위에서 바로 시도할 수 있는 Java 기초와 예제
1. 변수와 상수 선언
Java에서는 각 변수의 타입을 선언해야 합니다. 상수에는 final을 사용하세요.
int age = 30;
double pi = 3.14159;
char grade = 'A';
String name = "Alice";
boolean isActive = true;
// 상수
final int MAX_USERS = 100;
final String COMPANY = "CodeUtility";2. 조건문 (if / switch)
제어 흐름에는 if, else if, switch를 사용하세요.
int x = 2;
if (x == 1) {
System.out.println("하나");
} else if (x == 2) {
System.out.println("둘");
} else {
System.out.println("그 외");
}
switch (x) {
case 1:
System.out.println("하나");
break;
case 2:
System.out.println("둘");
break;
default:
System.out.println("그 외");
}3. 반복문
반복에는 for, while, do-while을 사용하세요.
for (int i = 0; i < 3; i++) {
System.out.println(i);
}
int n = 3;
while (n > 0) {
System.out.println(n);
n--;
}4. 배열
배열은 같은 타입의 고정 크기 시퀀스를 담습니다.
int[] numbers = {10, 20, 30};
System.out.println(numbers[1]);5. ArrayList 다루기
가변 크기 리스트에는 ArrayList를 사용하세요.
import java.util.ArrayList;
ArrayList<Integer> nums = new ArrayList<>();
nums.add(1);
nums.add(2);
nums.add(3);
nums.remove(Integer.valueOf(2));
for (int num : nums) {
System.out.print(num + " ");
}6. 콘솔 입력/출력
입력에는 Scanner, 출력에는 System.out을 사용하세요.
import java.util.Scanner;
Scanner scanner = new Scanner(System.in);
System.out.print("이름을 입력하세요: ");
String name = scanner.nextLine();
System.out.println("안녕하세요, " + name);7. 함수
반환 타입과 매개변수를 지정해 메서드를 정의합니다.
public static int add(int a, int b) {
return a + b;
}
System.out.println(add(3, 4));8. HashMap
키-값 저장에는 HashMap을 사용하세요.
import java.util.HashMap;
HashMap<String, Integer> ages = new HashMap<>();
ages.put("Alice", 30);
System.out.println(ages.get("Alice"));9. 예외 처리
런타임 예외 처리는 try와 catch를 사용하세요.
try {
throw new Exception("문제가 발생했습니다");
} catch (Exception e) {
System.out.println(e.getMessage());
}10. 파일 I/O
파일 처리에는 java.nio.file의 Files와 Paths를 사용하세요.
import java.nio.file.*;
import java.io.IOException;
Files.writeString(Paths.get("file.txt"), "안녕, 파일");
String content = Files.readString(Paths.get("file.txt"));
System.out.println(content);11. 문자열 조작
Java 문자열은 length(), substring(), contains() 같은 다양한 메서드를 지원합니다.
String text = "Hello World";
System.out.println(text.length());
System.out.println(text.substring(0, 5));
System.out.println(text.contains("World"));12. 클래스와 객체
Java는 클래스와 인스턴스를 사용한 객체지향 프로그래밍을 지원합니다.
class Person {
String name;
Person(String name) {
this.name = name;
}
void greet() {
System.out.println("안녕, 나는 " + name);
}
}
Person p = new Person("Alice");
p.greet();