본문으로 건너뛰기
툴허브

최선의 수를 찾을 때 모든 경우를 다시 계산해야 할까?

작은 입력에서는 손으로 경우를 세어 볼 수 있습니다. 이미 푼 상태를 재사용하는지, 가능성이 사라진 가지를 잘라 내는지 구분해 보세요.

툴허브 편집 ·

반복 등장하는 작은 문제 표시하기

F(5)를 F(4)와 F(3)으로 나누고 F(4)도 펼쳐 보세요. F(3)이 다시 필요할 때 저장한 값을 읽으면 같은 가지를 반복해서 계산하지 않아도 됩니다.

피보나치 DP 열기 →

물건을 넣는 선택과 빼는 선택 비교하기

남은 용량이 3일 때 무게 4인 물건은 넣을 수 없습니다. 넣을 수 있는 물건이라도 그 가치와 남은 용량에서 얻는 가치를 합해 다른 선택과 비교하세요.

배낭 문제 열기 →

가장 큰 동전부터 써도 되는지 확인하기

동전이 1, 3, 4이고 금액이 6이라면 4+1+1보다 3+3이 적은 개수입니다. 작은 금액의 최솟값이 더 큰 금액의 후보가 되는 과정을 보세요.

동전 교환 열기 →

연속 구간과 증가 부분 수열 구분하기

3, 1, 2, 0, 4에서 1, 2, 4는 0을 건너뛴 증가 부분 수열입니다. 현재 값을 마지막으로 둘 때 이어 붙일 수 있는 이전 값을 찾아보세요.

LIS (최장 증가 부분수열) 열기 →

충돌이 보이는 자리에서 조기에 되돌아가기

한 행에 퀸을 놓은 뒤 이미 놓은 퀸과 같은 열이나 대각선이 되는 후보를 지우세요. 다음 행에 가능한 칸이 없으면 마지막 선택부터 되돌립니다.

N-Queens 열기 →

상대도 자신에게 좋은 수를 둔다고 보기

내게 이득인 마지막 결과가 보여도 상대가 그 길을 택할 이유가 있는지 보세요. 끝에서부터 두 사람의 선택을 번갈아 올리면 현재 수의 평가가 달라집니다.

Minimax 게임 AI 열기 →