ImJay

[BOJ/Java] 1938. 통나무 옮기기 1938번: 통나무 옮기기 첫째 줄에 주어진 평지의 한 변의 길이 N이 주어진다. (4 ≤ N ≤ 50) 주어진다. 이어서 그 지형의 정보가 0, 1, B, E로 이루어진 문자열로 주어진다. 한 줄에 입력되는 문자열의 길이는 N이며 입력 문 www.acmicpc.net 문제 해석 NxN 크기의 격자에서 통나무를 이동시켜야 하는 최소 횟수를 구하는 문제다. 통나무는 'B'로, 목표 위치는 'E'로 표현된다. 통나무는 3개의 연속된 칸을 차지하며, 수직이나 수평 방향으로만 움직일 수 있다. 또한, 통나무는 중심을 기준으로 90도 회전할 수 있으며, 각 격자 칸은 비어 있거나('0'), 장애물('1')이 있거나, 통나무의 시작 위치('B'), 혹은 목표 위치('E'..

[BOJ/Java] 17609. 회문 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 문제 해석 문제 "회문"은 문자열이 회문인지, 유사 회문인지, 일반 문자열인지를 판별하는 문제다. 회문은 정방향과 역방향이 같은 문자열을 말하고, 유사 회문은 한 문자를 제거하여 회문이 될 수 있는 문자열을 의미한다. 이 문제를 해결하기 위해서는 각 문자열에 대해 투 포인터 알고리즘을 활용하여 양 끝에서부터 문자를 비교하면서 회문 여부를 확인해야 한다. 풀이 과정 이 코드는 투 포인터를 활용하여 문자열의 시작 인덱스와 끝 인덱스를 가리키는 start와 en..

[BOJ/Java] 14501. 퇴사 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 문제 해석 "퇴사" 문제는 남은 N일 동안의 상담 스케줄을 고려하여 최대 수익을 얻을 수 있는 방법을 찾는 문제이다. 각 상담은 일정 기간과 해당 기간 동안 얻을 수 있는 금액이 정해져 있으며, 상담은 겹치지 않아야 한다. 풀이 과정 해당 문제를 해결하기 위해 사용된 알고리즘은 동적 프로그래밍(Dynamic Programming)이다. N일 동안 각 날짜에 대해 최대 수익을 저장할 dp 배열을 생성하고, 각 상담의 가능성을 검토하면서 최대 수익을 갱신한다. 입력으로 받은 상담 일정을 Consult 배열에 저장한다. dp 배열의 각 원소를 초기화한 후, 각 상담에 ..

[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 사이의 거리를 계산하는 함수를 ..