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