No Longer Coder

문제https://www.acmicpc.net/problem/25793줄 요약계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 구하기 위해 다음과 같은 점화식을 세웁니다.memo[i] = max(memo[i-3] + stairs[i-1], memo[i-2]) + stairs[i]현재 계단을 밟을 때, 이전에 밟은 계단이 i-3번째 계단인 경우와 i-2번째 계단인 경우 중 더 큰 점수를 선택하여 현재 계단의 점수를 더합니다.메모이제이션 기법을 사용하여 이전에 계산된 값을 저장하고 재사용함으로써 중복 계산을 피하고 효율성을 높입니다.memo 배열을 사용하여 각 계단까지의 최대 점수를 저장합니다.점화식을 이용하여 계산할 때, 이미 계산된 값은 memo 배열에서 가져와 사용합니다.최종적으로 memo[n]에..

문제https://www.acmicpc.net/problem/117263줄 요약2×n 직사각형을 채우는 방법의 수를 구하기 위해 점화식을 세웁니다.2×n 직사각형의 가장 오른쪽에 1×2 타일을 세로로 놓는 경우, 나머지 부분은 2×(n-1) 직사각형을 채우는 방법의 수와 같습니다.2×n 직사각형의 가장 오른쪽에 2×1 타일을 가로로 2개 놓는 경우, 나머지 부분은 2×(n-2) 직사각형을 채우는 방법의 수와 같습니다.따라서 2×n 직사각형을 채우는 방법의 수는 2×(n-1) 직사각형을 채우는 방법의 수와 2×(n-2) 직사각형을 채우는 방법의 수를 합한 것과 같습니다.이를 점화식으로 표현하면 memo[i] = memo[i-1] + memo[i-2]가 됩니다.메모이제이션 기법을 사용하여 이전에 계산된 값을..

문제https://www.acmicpc.net/problem/14633줄 요약동적 계획법을 이용하여, 각 수에 대해 2로 나누기, 3으로 나누기, 1 빼기 중 최소 연산 횟수를 선택하여 메모이제이션 배열에 저장합니다.memo[i] = min(memo[i/2], memo[i/3], memo[i-1]) + 1의 점화식을 사용하여 계산합니다.N에 대한 최소 연산 횟수를 출력합니다.코드// package boj1463;import java.io.*;public class Main { public static void main(String[] args) throws Exception { // 입력 파일에서 데이터 읽기 (테스트용) // System.setIn(new FileInput..

문제https://www.acmicpc.net/problem/90953줄 요약메모이제이션을 이용한 동적 계획법으로 1, 2, 3의 합으로 나타내는 방법의 수를 계산합니다.memo[i] = memo[i-3] + memo[i-2] + memo[i-1]의 점화식을 사용하여 계산합니다.각 테스트 케이스에 대해 계산된 결과를 출력합니다.코드// package boj9095;import java.io.*;import java.util.Arrays;public class Main { public static void main(String[] args) throws Exception { // 입력 파일에서 데이터 읽기 (테스트용) // System.setIn(new FileInputStr..

문제https://www.acmicpc.net/problem/25123줄 요약지방의 수 N, 각 지방의 예산요청 A, 총 예산 M을 입력받습니다. 이분 탐색의 범위를 설정하기 위해 예산요청 중 최댓값에 1을 더해 상한값으로 사용합니다. 이는 모든 예산요청이 상한액과 같은 경우를 포함하기 위함입니다.이분 탐색을 사용하여 상한액을 조정해가며 총 예산이 M 이하가 되는 최대 상한액을 찾습니다. 이는 Upper Bound를 찾는 과정으로, 조건을 만족하는 최댓값을 찾습니다.Upper Bound로 찾은 값은 조건을 만족하는 최솟값보다 1 큰 값이므로, 최종 결과에서 1을 빼줍니다. 이렇게 얻은 값이 실제로 배정 가능한 최대 예산이 됩니다.코드// package boj2512;import java.io.*;impo..

문제https://www.acmicpc.net/problem/16543줄 요약K개의 랜선과 필요한 랜선의 개수 N을 입력받아, 각 랜선의 길이를 배열 A에 저장합니다. 랜선 길이의 최댓값이 2^31-1일 수 있으므로, s, e, mid를 비롯한 관련 변수들을 long 타입으로 선언하여 오버플로우를 방지합니다.이분 탐색을 사용하여 랜선을 자를 수 있는 최대 길이를 찾습니다. 중간 길이 mid로 랜선을 잘랐을 때 나오는 랜선의 개수를 long 타입의 result에 누적하여 N과 비교합니다. 이는 upper bound를 찾는 과정으로, 조건을 만족하는 최대 길이를 탐색합니다.최종적으로 이분 탐색이 종료되었을 때의 끝 길이 e가 최대 랜선 길이가 되며, 이를 출력합니다. Upper bound 탐색 결과로 얻은 ..

문제https://www.acmicpc.net/problem/28053줄 요약이분 탐색을 사용하여 시작 높이와 끝 높이를 조정해가며 최적의 높이를 찾습니다.Upper bound는 조건을 만족하는 가장 큰 값을 찾는 것으로, 이 문제에서는 적어도 M미터의 나무를 집에 가져갈 수 있는 절단기의 최대 높이를 의미합니다.잘린 나무의 길이를 누적하여 필요한 길이와 비교하며, 조건에 따라 탐색 범위를 좁혀나갑니다. 잘린 나무의 길이가 필요한 길이보다 크거나 같을 때 시작 높이를 증가시키고, 작을 때는 끝 높이를 감소시키는 방식으로 upper bound를 찾아갑니다.코드// package boj2805;import java.io.*;import java.util.stream.Stream;public class Mai..

문제https://www.acmicpc.net/problem/19203줄 요약입력받은 배열 A를 정렬하고, 배열 B의 각 원소에 대해 이분 탐색을 수행합니다.이분 탐색이란 정렬된 배열에서 특정 값을 찾는 알고리즘으로, 배열의 중간 위치를 기준으로 찾고자 하는 값과 비교하여 왼쪽 또는 오른쪽 부분 배열을 선택하여 탐색 범위를 반씩 줄여나가는 방식으로 동작합니다.이분 탐색은 시간 복잡도 O(log N)으로, 선형 탐색의 O(N)보다 훨씬 빠르게 탐색을 수행할 수 있습니다.코드// package boj1920;import java.io.*;import java.util.Arrays;import java.util.stream.Stream;public class Main { public static void..

문제https://www.acmicpc.net/problem/77853줄 요약출입 기록의 수 n을 입력받고, n개의 줄에 걸쳐 출입 기록을 읽어와서 "enter"인 경우 HashSet에 이름을 추가하고, "leave"인 경우 HashSet에서 이름을 제거합니다.HashSet에 저장된 현재 회사에 있는 사람들의 이름을 배열로 변환하고, 배열을 내림차순으로 정렬합니다.정렬된 배열의 이름을 한 줄에 한 명씩 출력하여 현재 회사에 있는 사람들의 이름을 사전의 역순으로 출력합니다.코드// package boj7785;import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws Excepti..

문제https://www.acmicpc.net/problem/172193줄 요약저장된 사이트 주소의 수 N과 비밀번호를 찾으려는 사이트 주소의 수 M을 입력받고, N개의 줄에 걸쳐 사이트 주소와 비밀번호를 입력받아 HashMap에 저장합니다.M개의 줄에 걸쳐 비밀번호를 찾으려는 사이트 주소를 입력받습니다.입력받은 사이트 주소를 이용하여 HashMap에서 해당 사이트 주소의 비밀번호를 찾아 출력합니다.코드// package boj17219;import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws Exception { // 입력 // 입력 파일로부터 데이터를 ..