알파-베타 가지치기는 미니맥스와 같은 답을 내면서 결과를 바꿀 수 없는 가지를 건너뜁니다. 두 경계를 추적하는데, 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 Rust Compiler
Write, compile, run, and debug Rust code online in a full-featured browser IDE. Work with multiple files, save your workspace, and share or collaborate in real time.
🦀 이 Rust 온라인 실행기 소개
CodeUtility Rust Executor는 브라우저에서 바로 Rust 코드를 작성하고 실행할 수 있게 해줍니다 - 설치, 툴체인 설정, 로컬 환경이 전혀 필요 없습니다. 보안 샌드박스에서 동작하며, 실제 Rust 컴파일러 버전 1.70, 1.72, 1.73, 그리고 1.74를 지원합니다.
이 도구는 실제 rustc 컴파일러로 클라우드에서 Rust 프로그램을 컴파일하고 실행하여
정확하고 일관된 결과를 보장합니다. 변수, 소유권, 빌림, 패턴 매칭, 트레이트, 제네릭 등
최신 Rust 기능을 손쉽게 실험할 수 있습니다.
Cargo를 설치하거나 로컬 환경을 구성할 필요 없이 Rust의 핵심 개념 - 특히 메모리 안전성, 오류 처리, 동시성 - 을 학습하기에 이상적입니다. 모든 것이 몇 초 안에 브라우저에서 바로 실행됩니다.
하나의 실행기에서 다중 파일 편집기, 격리된 실행 터미널, 런타임별 라이브러리, 영구 작업 공간, 공유 및 실시간 협업을 이용하세요.
이 실행기는 어떻게 사용하나요?
런타임을 선택하고 파일을 열거나 만든 다음 코드를 작성하고 실행을 선택하세요. 출력은 터미널에 표시되며, 로그인한 사용자는 작업 공간에 파일을 보관하고 라이브러리를 설치하며 공유를 통해 협업할 수 있습니다.
- 버전을 선택하고 현재 파일을 편집하거나 작업 공간의 다른 파일을 여세요.
- 코드를 실행하고 요청 시 터미널에 입력한 다음 저장된 실행 기록을 확인하세요.
- 작업에 둘 이상의 코드 조각이 필요하면 라이브러리, 작업 공간 도구, 공유 및 채팅을 사용하세요.
💡 위에서 바로 시도해볼 수 있는 Rust 기본 & 예제
1. 변수와 상수 선언
let으로 변수를 선언합니다. 상수에는 const, 가변 변수에는 mut를 사용합니다.
let x = 10;
let pi: f64 = 3.14;
let name = "Alice";
let is_active = true;
const MAX_USERS: u32 = 100;2. 조건문 (if / match)
조건에는 if, 패턴 매칭에는 match를 사용합니다.
let x = 2;
if x == 1 {
println!("하나");
} else if x == 2 {
println!("둘");
} else {
println!("기타");
}
match x {
1 => println!("하나"),
2 => println!("둘"),
_ => println!("기타"),
}3. 반복문
Rust는 for, while, 그리고 무한 루프인 loop를 지원합니다.
for i in 0..3 {
println!("{}", i);
}
let mut n = 3;
while n > 0 {
println!("{}", n);
n -= 1;
}4. 배열
Rust의 고정 크기 배열은 대괄호를 사용합니다. 뷰에는 슬라이스를 사용하세요.
let nums = [10, 20, 30];
println!("{}", nums[1]);5. 벡터(동적 배열)
동적 배열에는 Vec를 사용합니다.
let mut fruits = vec!["apple", "banana"];
fruits.push("cherry");
fruits.pop();
for fruit in &fruits {
println!("{}", fruit);
}6. 콘솔 입출력
출력에는 println!, 입력에는 std::io를 사용합니다.
use std::io;
let mut name = String::new();
println!("이름을 입력하세요:");
io::stdin().read_line(&mut name).unwrap();
println!("안녕하세요, {}", name.trim());7. 함수
함수는 fn을 사용하며 ->로 값을 반환할 수 있습니다.
fn greet(name: &str) -> String {
format!("안녕하세요, {}", name)
}
println!("{}", greet("Alice"));8. HashMap
키-값 데이터에는 std::collections::HashMap을 사용합니다.
use std::collections::HashMap;
let mut person = HashMap::new();
person.insert("name", "Bob");
println!("{}", person["name"])9. 오류 처리
Rust는 Result와 match 또는 unwrap()으로 오류를 처리합니다.
fn fail() -> Result<(), String> {
Err("문제가 발생했습니다".to_string())
}
match fail() {
Ok(_) => println!("성공"),
Err(e) => println!("{}", e),
}10. 파일 I/O
파일 읽기/쓰기는 std::fs를 사용합니다.
use std::fs;
fs::write("file.txt", "Hello File").unwrap();
let content = fs::read_to_string("file.txt").unwrap();
println!("{}", content);11. 문자열 조작
Rust의 문자열은 힙에 할당되며 다양한 메서드를 지원합니다.
let mut text = String::from(" Hello Rust ");
println!("{}", text.trim());
println!("{}", text.to_uppercase());
text = text.replace("Hello", "Hi");
println!("{}", text);12. 구조체 & 메서드
Rust는 데이터 타입에는 struct를, 메서드에는 impl을 사용합니다.
struct Person {
name: String,
}
impl Person {
fn greet(&self) -> String {
format!("안녕하세요, 저는 {}입니다", self.name)
}
}
let p = Person { name: "Alice".to_string() };
println!("{}", p.greet());13. 참조 & 빌림
Rust에서는 값을 빌릴 때 &, 가변 참조에는 &mut를 사용합니다.
fn update(x: &mut i32) {
*x += 1;
}
let mut value = 10;
update(&mut value);
println!("{}", value);