리트코드 78: 재귀와 백트래킹을 활용한 부분 집합 문제 풀이
부분 집합(Subsets) 문제는 주어진 정수 배열의 모든 가능한 조합(멱집합, Power Set)을 찾는 알고리즘 문제입니다. 재귀적 사고를 통해 문제를 작은 단위로 분해하고, 결정 트리(Decision Tree)를 구축하여 해결하는 과정은 백트래킹의 기초를 다지는 데 매우 효과적입니다.
1. 문제 핵심 이해하기
리트코드 78번 문제는 정수로 이루어진 배열 nums가 주어졌을 때, 해당 ...
7월 6일 17:54에 게시됨
ABC363 문제 풀이
A - 값의 범위
주어진 값 r이 어느 범위에 속하는지 확인하고, 그 범위의 상한에서 r을 뺀 값을 출력하면 된다.
100 미만이면 100-r, 200 미만이면 200-r, 300 미만이면 300-r을 출력한다.
코드 확인하기
#include<bits/stdc++.h>
using namespace std;
int main() {
int r;
cin >> r;
if(r < 100) {
cout << 100 - r;
...
6월 13일 16:20에 게시됨
h-index 계산 및 구간 합 나머지 연산 등 주요 알고리즘 유형 정리
1. 최적의 h-index 산출 (이분 탐색)
h-index는 연구자가 발표한 논문 중 인용 횟수가 h회 이상인 논문이 h편 이상일 때, h의 최댓값을 의미합니다. 추가적으로 L회의 인용 횟수를 논문들에 배분하여(논문당 최대 1회) h-index를 높일 수 있는 경우, 이분 탐색을 통해 최적의 값을 찾을 수 있습니다.
#include <iostream>
#include <vector>
#include <alg ...
5월 30일 12:16에 게시됨
n-Queens 문제 해결을 위한 백트래킹 알고리즘
문제 개요
n-Queens 문제는 n×n 크기의 체스판 위에 n개의 퀸을 배치하는 조합 최적화 문제입니다. 이때 어떤 두 퀸도 서로를 공격할 수 없어야 하며, 즉 같은 행, 열, 또는 대각선 상에 존재해서는 안 됩니다. 주어진 n에 대해 가능한 모든 배치를 출력하는 것이 목표입니다.
입력 및 출력 형식
입력: 정수 n (1 ≤ n ≤ 9)
출력: 각 해법은 n개의 줄로 구성되며, 각 ...
5월 26일 16:28에 게시됨
01 배낭 문제의 다이나믹 프로그래밍 해법과 아이템 추적
문제 정의
무게 제한이 있는 배낭과 여러 개의 아이템이 주어졌을 때, 각 아이템은 고유한 무게와 가치를 가집니다. 한 번에 하나의 아이템만 선택할 수 있으며, 배낭의 총 무게가 허용 범위를 넘지 않도록 하면서 담을 수 있는 아이템들의 총 가치를 최대화하는 것이 목표입니다.
예시:
아이템 개수: 3개
각 아이템의 무게: [1, 3, 4]
각 아이템의 가치: [15, 20, ...
5월 24일 11:51에 게시됨