본문 바로가기

BOJ

[ 백준 ] 13023번 ABCDE (Java 자바)
Coding Test/Graph 2025. 3. 4. [ 백준 ] 13023번 ABCDE (Java 자바) 🔗 문제 링크: 백준 13023번 ABCDE문제 설명문제:BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다. 오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다. A는 B와 친구다.B는 C와 친구다.C는 D와 친구다.D는 E와 친구다.위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오.목표: 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. 풀이 과정📌 문제 요약그래프(무방향)를 구성한 후, 각 사람(노드)에서 DFS를 시작하여 깊이가 5(즉, 5명의 연속된 친구 관계)가 존재하는지 확인한다.DFS 과정 중 경로를 탐색할 때, ..
[ 백준 ] 9663 N-Queen (Java 자바)
Coding Test/Backtracking 2025. 3. 4. [ 백준 ] 9663 N-Queen (Java 자바) 🔗 문제 링크: 백준9663번 N-Queen문제 설명N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.입력 조건입력:체스판의 크기 N (즉, 배치할 퀸의 개수와 동일한 N×N 체스판)풀이 과정📌 문제 요약체스판의 각 행마다 하나의 퀸을 배치하는 경우의 수를 DFS(백트래킹)를 통해 탐색한다.퀸이 서로 공격하지 않도록 하기 위해, 같은 열 및 두 대각선(우하단, 좌하단)에 퀸이 있는지 여부를 체크한다.📌 해결 전략열 및 대각선 체크 배열 사용:열(col): 이미 특정 열에 퀸이 배치되었는지 여부를 기록한다.우하단 대각선(slash): (row + col)이 동일하면 같은 우하단 대..
[ 백준 ] 3109번 빵집 (Java 자바)
Coding Test/Graph 2025. 3. 4. [ 백준 ] 3109번 빵집 (Java 자바) 🔗 문제 링크: 백준 3109번 - 빵집문제 설명R×C 크기의 격자에서 빵집(경로) 문제를 해결하는 문제이다.격자의 각 칸은 빈 칸('.') 또는 장애물('x')로 구성되어 있으며,왼쪽 열에서 시작해 오른쪽 열까지 겹치지 않는 경로를 만들려고 한다.경로는 한 칸씩 이동하며, 이동 방향은 오른쪽 위, 오른쪽, 오른쪽 아래로만 가능하다.최종적으로 만들 수 있는 경로(빵집)의 최대 개수를 구하는 문제이다.입력 조건첫 줄: 격자의 행의 수 R와 열의 수 C가 주어진다.다음 R줄: 각 줄에 길이 C의 문자열이 주어지며, 각 문자는 격자의 상태를 나타낸다.('.'는 빈 칸, 'x'는 장애물)풀이 과정📌 문제 요약격자에서 왼쪽 열의 빈 칸부터 시작해 오른쪽 열까지 도달하는 경로를 찾는 문제.경로는 오른쪽 위, 오..
[ 백준 ] 1167번 트리의 지름 (Java 자바)
Coding Test/Graph 2025. 3. 4. [ 백준 ] 1167번 트리의 지름 (Java 자바) 🔗 문제 링크: 백준 1167번 - 트리의 지름문제 설명주어진 가중치가 있는 트리에서 두 노드 사이의 최대 거리를 구하는 문제이다.즉, 트리의 모든 두 노드 사이의 거리 중 가장 긴 값을 구하면 그것이 트리의 지름이다.입력 조건첫 줄: 노드의 개수 N다음 N줄: 각 줄은 시작 노드 번호와, 해당 노드와 연결된 노드 번호 및 가중치 쌍이 주어지고, -1로 종료된다.예를 들어, 한 줄의 입력은 "1 3 2 2 3 -1"과 같이 주어질 수 있다.풀이 과정📌 문제 요약가중치가 있는 트리에서 두 노드 사이의 최대 거리를 구하는 문제이다.트리의 지름은 임의의 두 노드 사이의 거리 중 가장 긴 값이다.DFS를 두 번 수행하는 방식으로 문제를 해결한다.📌 DFS를 두 번 수행하면 트리의 지름이 나오는 이유? 트리..
[ 백준 ] 2468번 안전 영역 (Java 자바)
Coding Test/Graph 2025. 3. 4. [ 백준 ] 2468번 안전 영역 (Java 자바) 🔗 문제 링크: 백준 2468번 - 안전 영역  문제 설명N×N 크기의 지도에 각 칸의 높이가 주어진다. 강수량에 따라 높이가 해당 강수량 이하인 칸은 물에 잠긴다고 가정할 때, 물에 잠기지 않는 안전 영역(연결된 칸 집합)의 개수를 구하는 문제여러 강수량마다 안전 영역의 개수를 구하고, 그 중 최댓값을 출력입력 조건첫 줄에 지도 크기 N (N×N)이후 N개의 줄에 걸쳐 각 칸의 높이가 공백으로 구분되어 주어진다풀이 과정📌 문제 요약지도에서 강수량에 따라 일정 높이 이하의 칸은 물에 잠긴다고 가정한다.각 강수량마다 물에 잠기지 않은 안전 영역(연결된 칸의 집합)의 개수를 구하고, 그 중 최대 개수를 찾는 문제이다.안전 영역은 상하좌우로 인접한 칸들이 하나의 영역을 이룬다.📌 해결 전략최소, 최대 높..
[ 백준 ] 17281번 야구 ⚾ (Java 자바)
Coding Test/Perm&Comb&Subset 2025. 3. 2. [ 백준 ] 17281번 야구 ⚾ (Java 자바) 🔗 문제 링크: 백준 17281번 - 야구 ⚾ 문제 설명 주어진 이닝 동안 각 선수의 타격 결과를 바탕으로 최적의 타순을 결정하여 최대 득점을 내는 문제이다. ⚾️특히 1번 선수는 반드시 4번 타자로 고정되고, 나머지 2번부터 9번 선수의 순서를 완전 탐색하여 모든 경우의 수를 시뮬레이션하는 방식이다. 🎯 입력 조건 • 첫 번째 줄: 이닝 수  N  • 이후  N 개의 줄: 각 이닝에서 9명의 선수의 타격 결과가 정수 9개로 주어진다. 📊풀이 과정📌 문제 요약 • 목표: 주어진 이닝 동안 최적의 타순을 찾아 최대 득점을 기록 • 제한: 1번 선수는 반드시 4번 타자로 고정된다. 📌 해결 전략 1. 순열 완전 탐색 🔄 • 2번부터 9번 선수의 순서를 완전 탐색하여 가능한 모든 타순을 구한다. •..
[ 백준 ] 1300번 K번째 수 (Java 자바)
Coding Test/BinarySearch 2025. 3. 2. [ 백준 ] 1300번 K번째 수 (Java 자바) 🔗 문제 링크: 백준 1300번 - K번째 수 문제 설명 이 문제는  N * N  크기의 2차원 배열  A 에서 K번째로 작은 수를 구하는 문제이다.배열  A 는  A[i][j] = i * j 로 구성되어 있다. 실제 배열 전체를 생성하거나 정렬할 필요 없이,파라메트릭 서치(Parametric Search)를 이용하여 후보 값  mid 에 대해 배열에서  mid  이하의 숫자가 몇 개 있는지를 세어 K번째 수를 찾는다. 입력 조건 • 첫 줄: 배열의 크기  N 과  k  (K번째 수) • N 은 배열의 행/열 개수,  k 는 정렬했을 때의 순서를 의미한다.풀이 과정📌 문제 요약 • 목표: A[i][j] = i * j 로 구성된  N * N  배열에서 K번째로 작은 수를 구한다. • 특징:실제 배열을..
[ 백준 ] 2343번 기타 레슨 (Java 자바)
Coding Test/BinarySearch 2025. 3. 2. [ 백준 ] 2343번 기타 레슨 (Java 자바) 🔗 문제 링크: 백준 2342번 - 기타 레슨 문제 설명 강의 수 N개와 블루레이 수 M이 주어질 때, 강의 순서를 유지하면서 모든 강의를 M개의 블루레이에 녹화할 수 있는 최소 블루레이 크기를 구하는 문제이다.즉, 강의들을 순서대로 저장하며, 한 블루레이에 담을 수 있는 용량의 한계(size)를 정할 때, 모든 강의를 녹화할 수 있도록 하는 최소 용량을 찾는 것이다. 입력 조건 • 첫 번째 줄: 강의 수 N과 블루레이의 수 M • 두 번째 줄: N개의 강의 길이가 공백으로 구분되어 주어진다. 풀이 과정📌 문제 요약• 목표: • 강의 순서를 유지하며, M개의 블루레이에 모든 강의를 담을 수 있는 최소 블루레이 크기를 찾는다. • 제약 조건: • 강의의 순서 변경 불가 • 한 블루레이의 용량을 초과하면..
[백준] 1005번 ACM Craft (Python 파이썬)
Coding Test/Graph 2024. 7. 4. [백준] 1005번 ACM Craft (Python 파이썬) https://www.acmicpc.net/problem/1005문제 설명서기 2012년! 드디어 2년간 수많은 국민들을 기다리게 한 게임 ACM Craft (Association of Construction Manager Craft)가 발매되었다.이 게임은 지금까지 나온 게임들과는 다르게 ACM크래프트는 다이나믹한 게임 진행을 위해 건물을 짓는 순서가 정해져 있지 않다. 즉, 첫 번째 게임과 두 번째 게임이 건물을 짓는 순서가 다를 수도 있다. 매 게임시작 시 건물을 짓는 순서가 주어진다. 또한 모든 건물은 각각 건설을 시작하여 완성이 될 때까지 Delay가 존재한다.위의 예시를 보자.이번 게임에서는 다음과 같이 건설 순서 규칙이 주어졌다. 1번 건물의 건설이 완료된다면 2번과 3번의 건설을 시작할수 ..

티스토리툴바