여섯째, 재귀 및 역 추적 알고리즘

컴퓨터 분야에서는 많은 문제를 재귀 알고리즘으로 해결할 수 있다. 재귀에서 가장 오래 사용하는 방법은 역추적이다. 우리가 문제를 상세히 분석할 때, 이런 문제는 본질적으로 트리 그림이라는 것을 알 수 있다.

재귀 알고리즘의 본질은 원래 문제를 더 작은 동일한 문제로 변환하고 해결하는 것입니다. 일반적으로 두 가지 점에 유의해야 합니다.

1, 반복 종료 조건. 재귀 알고리즘에서 가장 기본적이고 간단한 문제에 해당합니다.

2. 재귀적 프로세스. 재귀 프로세스는 원래 문제를 더 작은 동일한 문제로 점진적으로 푸시해야 합니다. 더 작다는 것은 하위 문제가 더 쉽게 해결된다는 것을 의미합니다. 쓰는 동안 재귀 공식을 찾을 수 있다. 이 과정에서 재귀 함수의 의미를 철저히 이해할 필요가 있다. 이 함수의 입력과 출력이 무엇인지 알아내면 훨씬 더 명확하게 쓸 수 있다.

이 재귀 공식으로 인해 재귀의 종료 조건이 우리가 알고 있는 f(0) 와 f( 1) 라는 것을 쉽게 알 수 있습니다. F(0) 과 f( 1) 를 사용하여 f(n) 까지 f(3) 를 계속 파생할 수 있습니다.

하지만 이제 우리는 재귀 알고리즘의 아이디어만을 사용하여 이 문제를 해결합니다.

체인 테이블, 트리 및 그래프와 같은 일반적인 데이터 구조에는 자연스러운 재귀 구조가 있습니다. 연결된 목록은 선형 구조이기 때문에 일반적으로 직접 순환하여 문제를 해결할 수 있지만 여기서는 반복 방법을 사용하여 LeetCode 위의 문제를 해결합니다.

LeetCode 203 연결된 목록 요소를 제거합니다.

해결: 연결된 목록의 구조는 하나의 노드가 이 짧은 연결된 목록을 연결하여 마지막 노드가 None 이 될 때까지 읽을 수 있습니다. 그러면 현재 반복 종료 조건은 head 가 None 을 가리키고 None 을 반환하는 것입니다.

재귀 알고리즘에 대한 심층적 인 이해 후, 우리는 역 추적 방법을 배우기 시작했습니다. LeetCode 위의 몇 가지 질문을 통해 재귀와 역추적 응용에 대해 자세히 살펴보겠습니다.

지속적인 업데이트 ...

데이터 구조 및 알고리즘 시리즈 블로그:

첫째, 데이터 구조 및 알고리즘 개요

둘째, LeetCode 의 전형적인 테마 정리 및 분석

셋째, 연결된 목록과 LeetCode 문제

넷째, 스택 및 대기열 (Stack and Queue

동사 (verb 의 약어) 트리

여섯째, 재귀 및 역 추적 알고리즘

일곱. 동적 계획

여덟, 분류 및 검색

아홉, 해시 테이블

참조 데이터

1,

2,

3,