재냥이😻

[BOJ/Java] 15663. N과 M (9) 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 해석 이 문제는 N개의 자연수 중에서 M개를 선택하여 만들 수 있는 모든 가능한 순열을 사전 순으로 출력하는 문제이다. 주어진 수들 중 중복된 값이 존재할 수 있으며, 출력되는 순열에서 중복되는 시퀀스는 제거되어야 한다. 풀이 과정 변수 선언 및 입력 처리: N은 주어진 자연수의 개수, M은 선택해야 하는 수의 개수이다. arr 배열에 입력받은 수를 저장하고 정렬한다. 중복 제거: 출력 시 중복되는 순열을 제..

[BOJ/Java] 11725. 트리의 부모 찾기 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 해석 본 문제에서는 주어진 노드 수(N)를 바탕으로 트리를 구성하고, 각 노드의 부모를 찾는 작업을 수행해야 한다. 트리는 노드 간 연결 정보를 입력으로 받으며, 1번 노드를 루트 노드로 가정한다. 이 트리 정보를 활용하여 각 노드의 부모를 출력하는 것이 목표이다. 풀이 과정 제출된 코드는 너비 우선 탐색(BFS)을 활용하여 각 노드의 부모 노드를 찾는 방식으로 문제를 해결한다. 주요 절차는 다음과 같다: 입력 처리 및 그래프 초기화: 노드의 수(N)를 입력받고, 인접 리..

[BOJ/Java] 11053. 가장 긴 증가하는 부분 수열 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 해석 이 문제에서는 수열 A가 주어지고, 그 수열에서 가장 긴 증가하는 부분 수열(LIS, Longest Increasing Subsequence)의 길이를 찾는다. 부분 수열은 수열에서 일부 항목을 선택하여 만든 수열이며, 선택된 순서는 원래 수열의 순서를 유지해야 한다. 풀이 과정 변수 초기화 및 입력: N은 수열의 ..

[BOJ/Java] 15657. N과 M (8) 15657번: N과 M (8) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 문제 해석 이 문제는 자연수 N개 중에서 M개를 고른 수열을 모두 구하는 문제이며, 수열은 비내림차순(같거나 커지는 순서)이어야 한다. 입력된 수는 중복될 수 있으며, 수열도 중복될 수 있다. 풀이 과정 입력 받기: N과 M을 입력받고, N개의 수를 배열에 저장한 뒤 정렬한다. 조합 수행: 조합을 재귀적으로 수행하면서, 이미 선택한 수 이후의 수들만 선택할 수 있도록 한다. 이는 비내림차순 조건을 만족시키기..

[BOJ/Java] 15654. N과 M (5) 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 문제 해석 이 문제에서는 N개의 서로 다른 수가 주어지고, 이 수들 중에서 M개를 뽑아 나열하는 모든 경우를 사전 순으로 출력해야 한다. 이는 순열을 구하는 문제의 한 형태이다. 풀이 과정 입력 받기: N개의 수를 입력 받은 후 배열에 저장하고 정렬한다. 조합 함수: 조합을 구현하는 함수 combination을 사용하여, 선택된 숫자가 다시 선택되지 않도록 관리한다. 순열 생성: 사전 순으로 출력하기 위해 ..

[BOJ/Java] 16928. 뱀과 사다리 게임 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 문제 해석 이 문제는 플레이어가 주사위를 굴려 100번 칸에 도달하려고 할 때, 사다리와 뱀을 이용하여 최소 몇 번의 주사위 굴림으로 도달할 수 있는지 계산하는 문제이다. 사다리는 위로 올라가는 효과가 있고, 뱀은 아래로 내려가는 효과가 있다. 각 칸에서 다음 도착지는 미리 정해져 있으며, 1번 칸에서 시작한다. 풀이 과정 입력 처리: N(사다리 수)과 M(뱀 수)을 ..

[BOJ/Java] 20529. 가장 가까운 세 사람의 심리적 거리 20529번: 가장 가까운 세 사람의 심리적 거리 각 테스트 케이스에 대한 답을 정수 형태로 한 줄에 하나씩 출력한다. www.acmicpc.net 문제 해석 이 문제는 N명의 사람들의 MBTI를 입력 받아서 가장 심리적 거리가 가까운 세 사람의 거리를 찾는 문제이다. MBTI 간의 거리는 각 자리마다 다른 문자일 때마다 거리가 1씩 증가한다. 예를 들어, MBTI가 'INTJ', 'ENTJ'인 경우 거리는 1이다. 풀이 과정 비둘기집 원리 활용: N이 33 이상일 경우, 비둘기집 원리에 의해 반드시 최소한 하나의 MBTI가 중복되어 거리가 0인 세 사람을 찾을 수 있다. MBTI 거리 계산: 세 MBTI 사이의 거리를 계산하는 함수를 ..

[BOJ/Java] 21736. 헌내기는 친구가 필요해 21736번: 헌내기는 친구가 필요해 2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 www.acmicpc.net 문제 해석 이 문제에서는 학교 지도에서 'I'로 표시된 시작 위치에서 출발하여 'P'로 표시된 친구들을 만나는 시뮬레이션을 수행한다. 지도는 NxM 그리드 형태로 주어지며, 탐색은 네 방향으로 이동이 가능하다. 목표는 최대한 많은 친구('P')를 만나는 것이며, 만약 하나도 만나지 못했다면 "TT"를 출력한다. 풀이 과정 초기화: 입력을 받아 지도의 크기(N, M)와 각 위치의 문자를 초기화한다...

[BOJ/Java] 17626. Four Squares 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 문제 해석 이 문제는 주어진 수 𝑁N을 최소 개수의 제곱수 합으로 표현할 때 필요한 제곱수의 개수를 찾는 문제이다. 예를 들어, 𝑁=13이면 2^2+3^2=13이므로, 최소 개수는 2개이다. 풀이 과정 다이나믹 프로그래밍(DP) 사용: 문제를 해결하기 위해 다이나믹 프로그래밍 기법을 적용한다. DP 배열 초기화: dp[i]는 숫자 𝑖i를 제곱수의 합으로 나타낼 때 필요한 최..

[BOJ/Java] 17471. 게리맨더링 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 문제 해석 이 문제는 N개의 구역을 두 그룹으로 나누어 각 그룹의 인구 차이를 최소화하는 문제이다. 각 구역의 인구수가 주어지고, 구역 간 연결 정보도 주어진다. 두 그룹은 각각 연결되어 있어야 하며(하나의 연결 요소를 이루어야 함), 불가능할 경우 -1을 출력한다. 풀이 과정 변수 선언 및 입력 처리: N은 구역의 수, num은 각 구역의 인구수를 저장하는 배열이다. 그래프 구성: 각 구역 간 연결 정보를 인접 리스트로 표현한 graph를 ..