백트래킹, 그리디, 분할정복, 동적계획법 알고리즘 비교
백트래킹 알고리즘
백트래킹은 해결 가능한 모든 경로를 탐색하는 알고리즘으로, 재귀 호출을 통해 결정 트리를 탐색하며 실패 시 이전 상태로 돌아가는 방식을 사용합니다.
def backtrack(current_path, choices):
if is_solution(current_path):
add_to_result(current_path)
return
for choice in choices:
if not is_valid(ch ...
6월 15일 16:23에 게시됨
재귀와 백트래킹: 알고리즘 문제 해결 전략
이번专题에서는 재귀와 백트래킹 알고리즘에 대해 심도 있게 다루어 보겠습니다. 주로 온라인 저지 사이트에서 수집한 문제들을 바탕으로 설명하며, 필요한 경우 예제 코드를 포함합니다.
순열과 조합
=======
1.1 기본 조합 문제(출처: leetcode)
문제: 두 정수 n과 k가 주어졌을 때, 1부터 n까지의 정수 중에서 k개를 선택하는 모든 조합을 반환합니다.
class Solution ...
6월 14일 19:45에 게시됨
전체 순열에서 K번째 수열 찾기
문제 설명
정수 수열 a₁, a₂, …, aₙ의 각 원소가 1부터 n 사이의 값을 가지며 중복이 없다면 이를 전체 순열(전체 배열)이라고 부릅니다. 예를 들어, [1,3,2]와 [4,3,2,1]은 모두 전체 순열입니다.
전체 순열들을 정렬할 때 다음과 같은 우선순위 규칙을 따릅니다:
길이가 n < m이면 a 수열이 앞섭니다.
길이가 n > m이면 b 수열이 앞섭니다.
길이가 같으면 사전순 ...
6월 3일 18:00에 게시됨