알파-베타 가지치기는 미니맥스와 같은 답을 내면서 결과를 바꿀 수 없는 가지를 건너뜁니다. 두 경계를 추적하는데, 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 JavaScript Runner
Write, run, and debug JavaScript or Node.js online in a full-featured browser IDE. Work with multiple files and packages, save your workspace, and collaborate in real time.
⚡ 이 JavaScript(Node.js) 온라인 실행기 소개
CodeUtility JavaScript 실행기는 브라우저에서 최신 JavaScript 코드를 별도 설정 없이 즉시 작성하고 실행할 수 있게 해줍니다. 실제 Node.js 환경에서 샌드박스된 컨테이너로 코드를 안전하게 실행하며, 16, 18, 20 버전을 지원합니다.
이 도구는 Node.js 코드 조각을 테스트하고, ES6+ 문법을 살펴보거나, 반복문, 함수, 배열, 프라미스, async/await 동작 같은 핵심 JavaScript 개념을 학습하는 데에 딱 맞습니다.
알고리즘 검증, 작은 스크립트 디버깅, 런타임 로직 실험에도 유용하며, 로컬에 Node를 설치하지 않아도 됩니다. 학습자, 백엔드 개발자, 또는 브라우저에서 빠르게 JavaScript 코드를 실행해야 하는 모든 분께 이상적입니다.
하나의 실행기에서 다중 파일 편집기, 격리된 실행 터미널, 런타임별 라이브러리, 영구 작업 공간, 공유 및 실시간 협업을 이용하세요.
이 실행기는 어떻게 사용하나요?
런타임을 선택하고 파일을 열거나 만든 다음 코드를 작성하고 실행을 선택하세요. 출력은 터미널에 표시되며, 로그인한 사용자는 작업 공간에 파일을 보관하고 라이브러리를 설치하며 공유를 통해 협업할 수 있습니다.
- 버전을 선택하고 현재 파일을 편집하거나 작업 공간의 다른 파일을 여세요.
- 코드를 실행하고 요청 시 터미널에 입력한 다음 저장된 실행 기록을 확인하세요.
- 작업에 둘 이상의 코드 조각이 필요하면 라이브러리, 작업 공간 도구, 공유 및 채팅을 사용하세요.
💡 초보자를 위한 Node.js 기초 가이드
1. 변수와 상수 선언
let 또는 const로 블록 스코프 변수를 선언합니다. const는 상수에 사용합니다.
let x = 10;
const PI = 3.14;
let name = "Alice";
let isActive = true;2. 조건문 (if / switch)
제어 흐름에는 if, else if, else 또는 switch를 사용합니다.
let x = 2;
if (x === 1) {
console.log("하나");
} else if (x === 2) {
console.log("둘");
} else {
console.log("기타");
}
switch (x) {
case 1:
console.log("하나");
break;
case 2:
console.log("둘");
break;
default:
console.log("기타");
}3. 반복문
데이터를 순회할 때 for, while, forEach를 사용합니다.
for (let i = 0; i < 3; i++) {
console.log(i);
}
let n = 3;
while (n > 0) {
console.log(n);
n--;
}4. 배열
값의 순서 있는 목록은 배열에 저장합니다. 인덱스로 접근합니다.
let fruits = ["apple", "banana", "cherry"];
console.log(fruits[0]);
console.log(fruits.length);5. 배열 조작
push, pop, slice, reverse 같은 메서드를 사용합니다.
fruits.push("kiwi");
fruits.pop();
console.log(fruits.slice(0, 2));
console.log(fruits.reverse());
let squares = [1, 2, 3, 4, 5].map(x => x * x);
console.log(squares);6. 콘솔 입출력
출력에는 console.log, 입력에는 readline 모듈을 사용합니다.
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
rl.question("이름이 뭐예요? ", name => {
console.log(`안녕하세요, ${name}`);
rl.close();
});7. 함수
함수는 선언식 또는 표현식으로 정의할 수 있습니다. 최신 JavaScript에서는 화살표 함수가 자주 사용됩니다.
function greet(name) {
return `안녕하세요, ${name}`;
}
const add = (a, b) => a + b;
console.log(greet("Alice"));
console.log(add(2, 3));8. 객체(Map)
객체는 키-값 쌍을 저장합니다. 사전이나 맵과 비슷합니다.
let person = { name: "Bob", age: 25 };
console.log(person.name);
console.log(person["age"]);
// ES6 맵
const map = new Map();
map.set("a", 1);
console.log(map.get("a"));9. 예외 처리
try, catch, finally로 오류를 안전하게 처리합니다.
try {
throw new Error("문제가 발생했습니다");
} catch (e) {
console.log(e.message);
} finally {
console.log("필요 시 정리");
}10. 파일 입출력
파일 읽기/쓰기는 Node.js의 fs 모듈을 사용합니다.
const fs = require("fs");
fs.writeFileSync("test.txt", "Hello File");
const data = fs.readFileSync("test.txt", "utf8");
console.log(data);11. 문자열 조작
trim(), toUpperCase(), replace(), split() 같은 메서드를 사용합니다.
let text = " Hello World ";
console.log(text.trim());
console.log(text.toUpperCase());
console.log(text.replace("Hello", "Hi"));
console.log(text.split(" "));12. 클래스와 객체
ES6+에서는 OOP를 class 문법으로 지원합니다.
class Person {
constructor(name) {
this.name = name;
}
greet() {
return `안녕, 나는 ${this.name}`;
}
}
const p = new Person("Alice");
console.log(p.greet());13. 참조
JavaScript에서 객체와 배열은 참조로 전달됩니다.
function update(arr) {
arr.push("changed");
}
let data = ["original"];
update(data);
console.log(data); // ["original", "changed"]