8퀸 난제: 재귀와 반복을 활용한 백트래킹 구현
8퀸 난제는 체스판 위에 8개의 퀸을 서로 공격하지 않도록 배치하는 고전적인 백트래킹 문제다. 이번 글에서는 재귀적 접근과 반복적 접근 두 가지 방식으로 해결해본다.
재귀적 백트래킹
재귀 방식은 현재 행에 퀸을 배치하고, 유효성 검증 후 다음 행으로 진행하는 구조다. 모든 행에 성공적으로 배치되면 해답을 출력한다.
#include <iostream>
#include <c ...
7월 1일 02:16에 게시됨
순환 연결리스트를 이용한 원숭이 왕 선정 알고리즘
문제: head가 헤더 노드가 없는 순환 연결리스트를 가리키고 있을 때, 각 노드에는 데이터 필드(num)와 포인터 필드(link)가 포함됩니다. 데이터 필드에는 정수가 저장되며, i번째 노드의 데이터 필드 값은 i입니다. 함수를 작성하여 순환 연결리스트를 사용하여 원숭이 왕을 선택하는 과정을 시뮬레이션하세요: 첫 번째 노드부터 시작하여 "카운트"를 반복하고, ...
6월 29일 01:47에 게시됨
2023년 7월 상하이 컴퓨터학회 경쟁 플랫폼 초급반 문제 풀이
T1 행 우선 탐색
문제 개요
n×m 크기의 격자가 다음 규칙으로 채워져 있습니다:
열 1열 2...열 m
행 112...m
행 2m+1m+2...2m
행 32m+12m+2...3m
...............
행 n.........nm
정수 c가 주어지면, c가 위치한 행과 열을 "행 열" 순서로 출력합니다.
핵심 아이디어
격자의 구조를 분석하면 두 가지 핵심 관계를 도출할 수 있습니다:
열 계산: c를 m으로 나눈 나머지 ...
6월 28일 00:15에 게시됨
알고리즘 노트 및 문제 해결 전략
P2569 https://www.luogu.com.cn/problem/P2569
이 문제를 참고하세요.
/*단조큐로 dp 최적화
주식을 매수하는 전이 방정식에서 j는 순차적으로 열거됩니다. 주식을 매수하는 것이므로 보유한 주식은 점점 증가할 것이며,
현재의 결정이 나중에(j가 더 클 때) 사용될 수 있으므로 먼저 구해야 합니다.
마찬가지로 주식을 매도할 때 보유한 주식은 점점 줄어들고,
즉 현재 ...
6월 27일 03:51에 게시됨
C++에서의 STL 알고리즘 활용과 핵심 패턴
비수정형 시퀀스 알고리즘
이러한 알고리즘은 컨테이너 내 요소를 변경하지 않고 조작합니다. 주로 탐색, 카운팅, 조건 검사에 사용됩니다.
요소 탐색: find 계열 함수
std::find: 지정된 값과 일치하는 첫 번째 요소를 반환합니다.
std::find_if: 조건을 만족하는 첫 번째 요소를 찾습니다.
std::find_end: 특정 하위 시퀀스가 마지막으로 나타나는 위치를 반환합 ...
6월 24일 20:32에 게시됨
C++ 표준 라이브러리(STL) 알고리즘 활용 가이드
1. 비수정(Non-modifying) 시퀀스 알고리즘
이 범주의 알고리즘은 대상 컨테이너의 요소 값을 변경하지 않으면서 정보를 검색합니다.
1.1 요소 찾기: find, find_if, find_end
find(begin, end, value): 주어진 범위에서 특정 값과 일치하는 첫 번째 요소를 찾아 해당 위치의 이터레이터를 반환합니다. 찾지 못하면 end 이터레이터를 반환합니다.
find_if(begin, ...
6월 24일 17:29에 게시됨
코드포스 라운드 988 (Div. 3) 문제 해설
A. 동일 숫자 페어 계산
배열 요소의 빈도를 저장하는 카운터를 활용하여 동일한 숫자 쌍의 최대 개수를 계산합니다. 각 숫자에 대해 발생 횟수를 2로 나눈 몫을 합산하여 해결합니다.
#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int testCase ...
6월 23일 03:04에 게시됨
스택 기반 알고리즘 문제 분석 및 해결
문제 1: 소수의 숫자 게임 (P1427)
스택의 후입선출(LIFO) 특성을 활용하여 입력된 숫자를 역순으로 출력하는 문제. 초기 코드에서 size() 호출 후 pop()을 수행하면서 크기 계산 오류가 발생했다.
#include <bits/stdc++.h>
using namespace std;
stack<int> num_stack;
int main() {
int value;
while (cin >> value && value != 0) {
num ...
6월 21일 23:38에 게시됨
문자열 변환 문제(무향 그래프 중복 제거)
문자열 변환 문제
문제 설명
이 문제는 문자열 A와 B, 그리고 최대 6개의 문자열 변환 규칙을 주고, A를 B로 변환하는 최소 단계 수를 찾는 문제입니다. 각 변환 규칙은 "A1→B1" 형식으로 주어집니다.
예를 들어, A가 "abcd", B가 "xyz"이고 변환 규칙이 다음과 같다면:
abc→xu
ud→y
y→yz
이 경우, A는 3번의 변환을 통해 B로 변환될 수 ...
6월 21일 20:45에 게시됨
기초 알고리즘 문제 풀이: 조합, 수학적 추론 및 주기성 분석
백전백계 문제 (100전으로 100마리 닭 구입)
한 마리의 수탉은 5전, 암탉은 3전, 병아리는 3마리에 1전이다. 총 100전을 사용해 정확히 100마리의 닭을 사야 할 때, 각각의 수탉, 암탉, 병아리 수를 구하는 문제다.
이 문제는 세 변수에 대한 방정식으로 표현할 수 있다:
x + y + z = 100 (총 수)
5x + 3y + z/3 = 100 (총 비용)
여기서 x는 수탉, y는 암탉, z는 병 ...
6월 21일 19:03에 게시됨