괴물 클럽

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; ...

385. 미니 구문 분석기 (중간) 문자열 s가 정수 중첩 리스트를 나타낸다고 가정할 때, 이를 구문 분석하는 파서를 구현하고 파싱 결과인 NestedInteger를 반환하세요. 리스트의 각 요소는 정수 또는 정수 중첩 리스트일 수 있습니다. 예제 1: <strong>입력:</strong> s = "324", <strong>출력:</strong> 324 <strong>설명:</s ...

8퀸 난제는 체스판 위에 8개의 퀸을 서로 공격하지 않도록 배치하는 고전적인 백트래킹 문제다. 이번 글에서는 재귀적 접근과 반복적 접근 두 가지 방식으로 해결해본다. 재귀적 백트래킹 재귀 방식은 현재 행에 퀸을 배치하고, 유효성 검증 후 다음 행으로 진행하는 구조다. 모든 행에 성공적으로 배치되면 해답을 출력한다. #include <iostream> #include <c ...

동적 프로그래밍의 세 가지 방법: 📈📉💾 동적 프로그래밍은 복잡한 문제를 해결하기 위한 알고리즘입니다. 큰 문제를 작은 문제로 분해하고, 이 작은 문제들의 해를 저장하여 중복된 계산을 피합니다. 이 글에서는 자바 언어를 사용하여 동적 프로그래밍의 세 가지 방법인 상향식(📈), 하향식(📉), 그리고 **메모이제이션(💾)**에 대해 설명하겠습니다. 이러한 방법들은 ...

이번专题에서는 재귀와 백트래킹 알고리즘에 대해 심도 있게 다루어 보겠습니다. 주로 온라인 저지 사이트에서 수집한 문제들을 바탕으로 설명하며, 필요한 경우 예제 코드를 포함합니다. 순열과 조합 ======= 1.1 기본 조합 문제(출처: leetcode) 문제: 두 정수 n과 k가 주어졌을 때, 1부터 n까지의 정수 중에서 k개를 선택하는 모든 조합을 반환합니다. class Solution ...

논리식은 컴퓨터 과학의 중요한 개념으로, 참(1)과 거짓(0) 값을 가지며 논리 연산자로 연결됩니다. 여기서는 AND(&)와 OR(|) 연산자만 고려하며, 연산자 우선순위는 AND가 OR보다 높고, 동일 연산자일 경우 왼쪽에서 오른쪽으로 계산합니다. 괄호 안의 식이 먼저 계산됩니다. 또한, C++ 등 일부 컴파일러는 "단락(short-circuit)" 평가를 사용합니다. a & b에서 ...

문제 개요 주어진 그래프에서 시작 정점 1에서 출발하여 모든 간선을 정방향과 역방향으로 정확히 한 번씩 지나가며, 다시 1로 돌아오는 경로를 찾는 문제이다. 이는 양방향 그래프 내에서 오일러 회로를 구성하는 전형적인 예시이다. 접근 방법 모든 간선이 두 번(정방향/역방향) 방문되며, 시작과 끝이 동일한 특성은 오일러 회로의 조건을 만족한다. 따라서 깊이 우선 ...