조합 문제 해결을 위한 백트래킹 접근 방식
백트래킹(Backtracking)은 특정 문제의 모든 가능한 해를 찾기 위한 일반적인 알고리즘 기법입니다. 이는 본질적으로 깊이 우선 탐색(DFS)의 한 형태로, 해를 찾기 위해 모든 가능한 경로를 탐색하되, 특정 경로가 더 이상 해답으로 이어질 수 없다고 판단될 경우 즉시 해당 경로에서 되돌아와(backtrack) 다른 경로를 시도합니다. 백트래킹은 완전 탐색(exhaustive search ...
7월 9일 23:54에 게시됨
LeetCode 문제 풀이: 31번부터 60번까지
다음 순열
정수 배열의 순열은 모든 요소를 일렬로 나열한 것을 의미합니다. 주어진 정수 배열에서 사전순으로 다음에 오는 더 큰 순열을 찾아야 합니다. 만약 더 큰 순열이 없다면, 배열을 가장 작은 순서로 재배치해야 합니다.
#include <vector>
#include <algorithm>
class Solution {
public:
void nextPermutation(std::vector<int>& n ...
7월 8일 05:51에 게시됨
알고리즘 실습 문제 풀이 분석
1부: 재귀
문제 1: 숫자 세기
/*
n=1, 결과 1
n=2, 결과 2 (12, 2)
n=3, 결과 2 (13, 1)
n=4, 결과 4 (14, 13, 24, 124)
n=5, 결과 4 (15, 25, 125, 5)
관찰 결과:
n이 홀수이면 f[n] = f[n-1]
n이 짝수이면 f[n] = f[n-1] + f[n/2]
*/
#include <iostream>
using namespace std;
const int MAX = 10000;
int dp[MAX];
int main() {
dp[1] = 1;
int n;
...
7월 5일 00:14에 게시됨
알고리즘 시험 주요 유형 정리
주요 알고리즘 패턴별 예제
재귀: 병합 정렬
병합 정렬은 배열을 반으로 나눈 후 정렬된 부분들을 병합하는 전형적인 재귀 알고리즘이다.
#include<iostream>
#include<vector>
using namespace std;
vector<int> data;
vector<int> temp(1000);
void mergeSort(int left, int right) {
if (left >= right) return;
int mid ...
7월 4일 02:32에 게시됨
8퀸 난제: 재귀와 반복을 활용한 백트래킹 구현
8퀸 난제는 체스판 위에 8개의 퀸을 서로 공격하지 않도록 배치하는 고전적인 백트래킹 문제다. 이번 글에서는 재귀적 접근과 반복적 접근 두 가지 방식으로 해결해본다.
재귀적 백트래킹
재귀 방식은 현재 행에 퀸을 배치하고, 유효성 검증 후 다음 행으로 진행하는 구조다. 모든 행에 성공적으로 배치되면 해답을 출력한다.
#include <iostream>
#include <c ...
7월 1일 02:16에 게시됨
이분 탐색과 깊이 우선 탐색 기반 문제 해결
T1. 이분 탐색: 정렬된 배열에서 값 찾기
정렬된 배열 내에서 특정 값을 찾아 그 인덱스를 반환하는 문제입니다. 배열 크기가 최대 106까지 가능하므로, 배열 선언 시 크기를 충분히 확보해야 합니다.
오류 원인: 배열 크기 지정이 부족 (105+7로 설정했으나, 106+7 필요)
핵심 전략: 이분 탐색은 값이 일치할 경우에도 왼쪽 경계를 찾기 위해 r = mid로 업데이트
#inc ...
6월 25일 21:05에 게시됨
비감소 부분 수열과 순열 생성 알고리즘
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에 게시됨