상인과 수행원 강 건너기 문제의 DFS 알고리즘 구현
문제 정의
세 명의 상인과 각각 한 명의 수행원이 강을 건너야 한다. 작은 배는 최대 두 사람만 탑승할 수 있으며, 상인들이 직접 조종해야 한다. 강의 어느 쪽이든 수행원 수가 상인 수보다 많아지면 상인들을 해칠 계획이다. 상인들이 안전하게 강을 건너려면 어떻게 해야 할까?
수학적 모델링
이 문제를 해결하기 위해 깊이 우선 탐색(DFS) 알고리즘을 적용한다. 선박의 ...
8월 8일 18:46에 게시됨
무가중 그래프 탐색 알고리즘: 깊이 우선(DFS)과 너비 우선(BFS)
그래프는 많은 애플리케이션에서 중요한 데이터 구조이며, 이를 효율적으로 탐색하는 것은 매우 중요합니다. 가중치가 없는 그래프의 경우, 방향성이 있거나 없음에 관계없이 두 가지 주요 알고리즘이 돋보입니다: 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS). 이 두 방법 모두 두 노드 사이에 경로가 존재하는지 여부를 판단하고 해당 경로를 재구성할 수 있습니다. 특히, ...
7월 28일 06:55에 게시됨
ABC356 대회 문제 해설 및 풀이 코드
A
주어진 범위 1부터 n까지의 수열에서 l부터 r까지의 부분만 뒤집어 출력하는 문제다.
즉, 1부터 l-1까지는 순서대로, l부터 r까지는 역순으로, r+1부터 n까지는 다시 순서대로 출력하면 된다.
#include <bits/stdc++.h>
using namespace std;
int n, L, R;
int main() {
cin >> n >> L >> R;
for (int i = 1; i < L; i++) cout & ...
7월 19일 20:14에 게시됨
리트코드 78: 재귀와 백트래킹을 활용한 부분 집합 문제 풀이
부분 집합(Subsets) 문제는 주어진 정수 배열의 모든 가능한 조합(멱집합, Power Set)을 찾는 알고리즘 문제입니다. 재귀적 사고를 통해 문제를 작은 단위로 분해하고, 결정 트리(Decision Tree)를 구축하여 해결하는 과정은 백트래킹의 기초를 다지는 데 매우 효과적입니다.
1. 문제 핵심 이해하기
리트코드 78번 문제는 정수로 이루어진 배열 nums가 주어졌을 때, 해당 ...
7월 6일 17:54에 게시됨
Codeforces Round 2204 풀이: A~F번 문제 해설
A. 공 던지기
간단한 시뮬레이션으로 해결할 수 있다. 현재 위치에서 지시에 따라 좌우로 이동하며, 처음 방문하는 지점의 개수를 기록하면 된다.
코드 보기#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int n;
st ...
7월 4일 01:15에 게시됨
2025년 2월 4일~9일 주차 문제 정리
주간 개요
이번 주는 생활 리듬이 불규칙하여 학습 효율이 저하되었고, 이를 개선하기 위해 환경을 변경하였다. 새로운 일정으로 인해 다음 주부터는 더 체계적인 학습과 경기 준비를 할 계획이다.
문제 해결 기록
SMU Winter 2025 Round 6
B. 스트리머의 밤
문제 요약: 여러 프로그램의 시작 및 종료 시간이 주어질 때, 전체 시간 내에 볼 수 있는 최대 프로그램 수를 ...
7월 1일 05:37에 게시됨
AtCoder ABC368 풀이: A~F번 문제 분석
A - Cut
문제 요약
길이 n인 수열에서 마지막 k개 원소를 앞으로 이동시킨 결과를 출력한다.
핵심 아이디어
배열을 회전시키는 기초적인 구현 문제이다. n-k 인덱스부터 끝까지의 원소를 먼저 출력한 뒤, 나머지 원소를 순서대로 출력하면 된다.
구현
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nu ...
6월 30일 23:02에 게시됨
2024 CCPC 동북 4성 초청 대회 알고리즘 문제 해설 및 구현
Problem J. Breakfast
이 문제는 주어진 공식을 기반으로 한 간단한 산술 연산을 요구합니다. 표현식의 결과를 계산한 후, 출력 형식에 맞게 소수점 둘째 자리까지 포맷팅하면 됩니다.
#include <iostream>
#include <iomanip>
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
double base_value = 32.0;
...
6월 27일 16:56에 게시됨
그래프 순회 알고리즘: 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)
너비 우선 탐색 (Breadth-First Search, BFS)
너비 우선 탐색은 시작 정점으로부터 가까운 노드를 우선적으로 탐색하는 알고리즘으로, 이진 트리의 레벨 순회(Level-order traversal) 방식과 유사합니다. 탐색 과정에서 큐(Queue)를 사용하여 정점을 관리하고, 방문 여부를 기록하기 위한 불리언 배열을 사용합니다.
시작 정점을 큐에 넣고 방문 처리한 뒤, 큐가 ...
6월 8일 16:40에 게시됨
삼차원 던전 탈출 문제 - BFS 알고리즘 풀이
문제 출처
백준 온라인 저지(BOJ) 2251번, POJ 2251, 정보학奥賽一本通
알고리즘 분류
너비 우선 탐색(BFS), 삼차원 그래프 탐색
문제 설명
삼차원 던전에서 가장 빠른 탈출 경로를 찾아야 한다. 던전은 여러 층으로 구성되어 있으며, 각 층은 행과 열로 구분되는 单位 격자로 이루어져 있다.
각 이동은 北, 南, 東, 西, 上, 下 중 하나의 방향으로 정확히 한 칸 이동하 ...
6월 8일 03:29에 게시됨