[백준 15685] Java - 드래곤 커브

https://www.acmicpc.net/problem/15685 드래곤 커브 1) 문제드래곤 커브는 다음과 같은 세 가지 속성으로 이루어져 있으며, 이차원 좌표 평면 위에서 정의된다. 좌표 평면의 x축은 → 방향, y축은 ↓ 방향이다. 시작 점 시작 방향 세대 0세대 드래곤 커브는 아래 그림과 같은 길이가 1인 선분이다. 아래 그림은 (0, 0)에서 시작하고, 시작 방향은 오른쪽인 0세대 드래곤 커브이다.1세대 드래곤 커브는 0세대 드래곤 커브를 끝 점을 기준으로 시계 방향으로 90도 회전시킨 다음 0세대 드래곤 커브의 끝 점에 붙인 것이다. 끝 점이란 시작 점에서 선분을 타고 이동했을 때, 가장 먼 거리에 있는 점을 의미한다.2세대 드래곤 커브도 1세대를 만든 방법을 이용해서 만들 수 있다...

• format_list_bulleted Baekjoon Coding Test/Java
• · 2025. 5. 22.

[백준 14503] Java - 로봇 청소기

https://www.acmicpc.net/problem/14503 로봇 청소기 1) 문제로봇 청소기와 방의 상태가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 방은 N x M 크기의 직사각형으로 나타낼 수 있으며, 1 x 1 크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북 중 하나이다. 방의 각 칸은 좌표 (r, c)로 나타낼 수 있고, 가장 북쪽 줄의 가장 서쪽 칸의 좌표가 (0, 0), 가장 남쪽 줄의 가장 동쪽 칸의 좌표가 (N-1, M-1)이다. 즉, 좌표 (r, c)는 북쪽에서 (r+1)번째에 있는 줄의 서쪽에서 (c+1)번째 칸을 가리킨다. 처음에 빈..

• format_list_bulleted Baekjoon Coding Test/Java
• · 2025. 5. 22.

시뮬레이션 (Simulation)

시뮬레이션 (Simulation) 1) 시뮬레이션이란?문제에서 주어진 조건과 규칙을 그대로 구현하여 상황을 재현해 나가는 방식의 알고리즘이다. 즉, 문제에서 말한 게임 규칙, 이동 방식, 회전 조건, 충돌 처리 등을 논리 흐름에 따라 직접 구현하는 것이 핵심이다 2) 시뮬레이션의 특징 항목 내용 핵심 포인트"문제를 읽은 그대로" 구현하는 능력자료구조 사용배열, 2차원 배열, 큐, 리스트 등수학적 개념거의 없음 또는 간단한 연산만 사용중요 능력조건 분기, 상태 추적, 좌표/인덱스 계산난이도쉬워 보이지만 디버깅과 구현이 매우 까다로움 3) 동작 원리 1. 상태 정의위치, 방향, 점수, 체력, 타이머 등 초기 상태 정의 2. 조건 처리문제에서 요구하는 행동 규칙을 조건문/반복문으로 구현..

• format_list_bulleted Algorithm/이론
• · 2025. 5. 22.

[백준 9663] Java - N-Queen

https://www.acmicpc.net/problem/9663 N-Queen 1) 문제N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.입력: 첫째 줄에 N이 주어진다. (1 ≤ N 출력: 첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다. 2) 예시예제입력 1:8예제출력 1: 92 3) 풀이 * 핵심 조건1. 퀸은 가로, 세로, 대각선으로 이동 가능2. 즉, 서로 같은 행, 열, 대각선에 두면 안 됨3. 퀸 N개를 서로 공격하지 않도록 한 개씩 배치 * 아이디어핵심 전략: 백트래킹 + 한 줄씩 퀸 배치 1. 행 단위로 한 줄씩 퀸을 배..

• format_list_bulleted Baekjoon Coding Test/Java
• · 2025. 5. 22.

백트래킹

백트래킹 (Back Tracking) 1) 백트래킹란?백트래킹은 모든 경우의 수를 탐색하되, 조건을 만족하지 않는 경우 탐색을 중단하고 이전 단계로 되돌아가는 방식의 탐색 알고리즘이다. DFS 기반의 완전 탐색 기법 중 하나로, 불필요한 탐색을 줄여주는 가지치기(pruning) 기법이 포함된다. 2) 백트래킹 동작원리 1. 가능한 모든 경우를 시도한다 (DFS 기반 탐색). 2. 탐색 도중 조건에 맞지 않는 경우 더 이상 진행하지 않고 되돌아간다 (backtrack). 3. 조건을 만족하는 경우 정답 처리한다. 4. 다음 탐색을 위해 상태를 복구하고(undo), 새로운 경우의 수를 시도한다. // 백트래킹 구조void backtrack(int depth) { if (종료 조건) { ..

• format_list_bulleted Algorithm/이론
• · 2025. 5. 21.

[백준 1182] Java - 부분수열의 합

https://www.acmicpc.net/problem/1182 부분수열의 합 1) 문제N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.입력: 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.출력: 첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다. 2) 예시예제입력 1:5 0-7 -3 -2 5 8예제출력 1: 1 3) 풀이* 아이디어1. 모든 부분수열을 탐색해야 하므로 → 부분집합 문제 → 각 원소..

• format_list_bulleted Baekjoon Coding Test/Java
• · 2025. 5. 21.