Algorithm

백준 온라인 저지 문제를 C++로 풀며 문제의 상태를 자료구조로 모델링하고, 제약에 맞는 탐색·동적 계획법·시뮬레이션을 선택하는 과정을 기록한 저장소입니다.

단순히 정답 코드를 모으는 데 그치지 않고, 격자 이동과 충돌 처리, 탐색 상태 중복 제거, 경로 복원, 백트래킹의 상태 되돌리기처럼 구현 문제에서 자주 발생하는 복잡도를 직접 다뤘습니다.

기술 스택

• Language: C++17
• Standard Library: vector, deque, queue, set, map, algorithm
• Algorithm: BFS, 완전 탐색·백트래킹, 동적 계획법, 이분 탐색, 격자 시뮬레이션
• Local runner: Bash, g++

저장소 구성

.
├── baekjoon
│   ├── silver/      # 구현, 문자열 검사, 순열 탐색
│   ├── gold/        # BFS, 백트래킹, DP, 시뮬레이션
│   └── platinum/    # 이분 탐색과 경로 복원을 결합한 LIS
├── main.cpp         # 현재 로컬에서 실행해 보는 풀이
├── data.txt         # main.cpp 테스트 입력
└── run.sh           # 컴파일·실행·실행 시간 확인 스크립트

현재 총 14개의 풀이가 난이도별 디렉터리에 정리되어 있습니다.

대표 문제 해결 접근

문제	핵심 접근	코드에서 확인할 수 있는 역량
14003 가장 긴 증가하는 부분 수열 5	LIS 후보를 이분 탐색으로 갱신하고, 각 원소의 이전 인덱스를 기록해 실제 수열까지 역추적	시간 복잡도를 고려한 탐색 최적화, 인덱스 기반 경로 복원
15644 구슬 탈출 3	보드 상태를 문자열로 직렬화해 방문 여부를 관리하고, BFS의 부모 상태와 이동 방향을 저장해 최단 이동 경로 출력	상태 공간 모델링, 중복 상태 제거, BFS 경로 복원, 실패 상태 가지치기
15683 감시	CCTV별 가능한 회전을 백트래킹으로 탐색하고, 감시 영역을 누적값으로 표시한 뒤 재귀 종료 시 원상 복구	완전 탐색 설계, 겹치는 영향 범위 처리, 명시적인 상태 복구
16235 나무 재테크	칸마다 나무 나이를 관리하며 봄·여름·가을·겨울의 규칙을 단계별 함수로 분리해 반복	다중 객체 격자 시뮬레이션, 처리 순서와 자료구조 선택
3190 뱀	deque로 뱀의 머리부터 꼬리까지 위치를 관리하고 벽·자기 몸 충돌 및 방향 전환을 시간 순으로 처리	큐 기반 상태 갱신, 경계 조건과 이벤트 시점 관리
4198 열차정렬	각 위치를 기준으로 증가·감소 부분 수열 길이를 계산해 최적의 열차 구성을 결정	DP 상태 정의, 양방향 관계를 반대로 해석하는 문제 변환

그 밖에도 두 십자가의 비중첩 조합을 탐색하는 17085 십자가 2개 놓기, 자릿수 순열을 만들며 선행 0을 배제하는 16943 숫자 재배치, 연속 문자 규칙을 분리해 검증하는 4659 비밀번호 발음하기 등으로 구현과 예외 처리 역량을 훈련했습니다.

실행 방법

현재 풀이 실행

run.sh는 main.cpp를 C++17로 컴파일한 뒤 data.txt를 표준 입력으로 전달하고, 실행이 끝나면 생성한 실행 파일을 정리합니다.

./run.sh

필요 환경은 Bash, C++17을 지원하는 g++, 실행 시간 계산에 사용하는 bc입니다.

개별 풀이 실행

각 파일은 백준 제출 형식의 독립적인 프로그램입니다. 원하는 풀이를 직접 컴파일한 뒤 문제의 입력을 전달할 수 있습니다.

g++ -std=c++17 -O2 -Wall \
  "baekjoon/gold/3190 뱀.cpp" \
  -o solution

./solution < input.txt

문제 설명과 입력·출력 형식은 각 파일명에 적힌 백준 문제 번호를 기준으로 확인할 수 있습니다.