백트래킹 알고리즘 활용: 증가하는 부분 수열, 순열, 중복 순열 문제 해결

본 문서에서는 백트래킹(Backtracking) 알고리즘을 사용하여 LeetCode의 세 가지 문제를 해결하는 방법을 설명합니다. 각 문제에 대한 핵심 아이디어와 함께 Java 코드를 제공하며, 코드의 구조와 로직을 변경하여 유사성을 줄이고자 했습니다. 1. LeetCode 491: 증가하는 부분 수열 (Non-decreasing Subsequences) 주어진 정수 배열에서 길이가 2 이상인 모든 증가하는 ...

10월 29일 18:26에 게시됨

LeetCode 부분집합 문제: 백트래킹으로 모든 부분집합 생성하기

문제 링크 78. 부분집합 - LeetCode 아래 문제 설명과 예시는 LeetCode에서 가져왔습니다. 문제 설명 정수 배열 nums가 주어집니다. 배열의 원소는 서로 다릅니다. 이 배열의 가능한 모든 부분집합(멱집합)을 반환하세요. 해답 집합은 중복된 부분집합을 포함하면 안 됩니다. 해답은 임의의 순서로 반환할 수 있습니다. 예시 1: <strong>입력:</strong> nums ...

10월 9일 07:53에 게시됨

백트래킹을 활용한 IP 복원 및 부분집합 문제 해결

93. 유효 IP 주소 복원하기 문제는 주어진 숫자 문자열에서 올바른 IP 주소를 생성하는 것입니다. 유효한 IP는 다음과 같은 조건을 만족해야 합니다: 총 네 개의 정수로 구성되며 각각은 0~255 범위에 있어야 함 각 정수는 선행 0을 포함할 수 없음 (예: "01", "00") 정수 간에는 점(.)으로 구분됨 이 문제는 문자열을 분할하는 형태로 백트래킹 알고리즘을 적용하여 모 ...

8월 27일 00:11에 게시됨

알고리즘 문제 풀이: 증가하는 부분 수열, 순열, 중복 순열

1. 증가하는 부분 수열 문제 링크: LeetCode 문제 설명: 주어진 배열의 부분 수열 중에서 각 요소가 이전 요소보다 크거나 같은 모든 가능한 부분 수열을 찾아야 합니다. 배열의 원래 순서를 변경할 수 없습니다. 풀이 방법: 이 문제는 조합 문제와 유사하지만, 각 단계에서 현재 요소가 경로(path)의 마지막 요소보다 작으면 건너뜁니다. 또한 배열에 중복 요소가 있을 수 ...

8월 2일 11:18에 게시됨

조합 문제 해결을 위한 백트래킹 접근 방식

백트래킹(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에 게시됨