비감소 부분 수열과 순열 생성 알고리즘
491 비감소 부분 수열
문제 링크
문제 설명:
정수 배열 nums가 주어졌을 때, 모든 다른 비감소 부분 수열을 찾아 반환하세요. 비감소 부분 수열은 적어도 두 개의 요소를 가져야 합니다. 답변을 임의의 순서로 반환할 수 있습니다.
배열에는 중복 요소가 포함될 수 있습니다. 두 정수가 같은 경우에도 비감소 시퀀스의 특수한 경우로 간주할 수 있습니다.
예시 1:
<stro ...
6월 19일 21:05에 게시됨
조합 합계 문제의 효율적 구현과 최적화 전략
1. 문제 정의
중복되지 않는 양의 정수 배열 candidates와 양의 정수 target이 주어졌을 때, 합이 target이 되는 모든 고유한 조합을 찾는 문제입니다. 배열의 각 요소는 무제한으로 재사용할 수 있으며, 요소의 순서만 다른 조합은 동일한 것으로 간주합니다. 이 문제의 핵심은 최적의 해를 찾는 것이 아니라 조건을 만족하는 모든 해를 탐색하는 것이므로, 백트래킹이 기 ...
6월 18일 16:14에 게시됨
백트래킹, 그리디, 분할정복, 동적계획법 알고리즘 비교
백트래킹 알고리즘
백트래킹은 해결 가능한 모든 경로를 탐색하는 알고리즘으로, 재귀 호출을 통해 결정 트리를 탐색하며 실패 시 이전 상태로 돌아가는 방식을 사용합니다.
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에 게시됨