와드의 블로그

문제N마리의 소가 길을 건너려고 합니다. 소는 한 번에 한 마리씩만 길을 건널 수 있으며, 각 소가 도착한 시간과 길을 건너는 데 걸리는 시간이 주어집니다. 모든 소가 길을 건너는 데 걸리는 최소 시간을 구하는 문제입니다.입력: 첫째 줄에 소의 수 N (1 ≤ N ≤ 100)이 주어집니다. 둘째 줄부터 N개의 줄에 각 소가 도착한 시간과 길을 건너는 데 걸리는 시간이 주어집니다.출력: 모든 소가 길을 건너는 데 걸리는 최소 시간을 출력합니다.링크: https://www.acmicpc.net/problem/14469풀이이 문제는 소들이 도착한 순서대로 길을 건너게 하는 것이 가장 효율적입니다. 따라서 도착 시간을 기준으로 오름차순 정렬한 뒤, 소요 시간을 누적해 나가는 그리디 방식을 사용합니다.객체 생성 ..

문제n개의 정수로 이루어진 임의의 수열이 주어집니다. 우리는 이 중 연속된 몇 개의 숫자를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 합니다. 단, 숫자는 적어도 하나 이상 선택해야 합니다.입력: 첫째 줄에 정수 n (1 ≤ n ≤ 100,000)이 주어지고, 둘째 줄에 n개의 정수로 이루어진 수열이 주어집니다.출력: 첫째 줄에 가장 큰 연속합을 출력합니다.링크: https://www.acmicpc.net/problem/1912풀이: 다이나믹 프로그래밍 (DP)이 문제는 이전까지의 계산 결과를 활용하여 현재의 최적해를 구하는 전형적인 다이나믹 프로그래밍(DP) 문제입니다. (카데인 알고리즘과 동일한 원리입니다.)DP 배열 정의: d[i]를 i번째 원소를 마지막으로 포함하는 연속 부분 수열의 최..

문제식재료 N개 중에서 몇 개를 선택해서 단백질, 지방, 탄수화물, 비타민의 합이 주어진 최소 영양소 기준을 만족하도록 할 때, 그 비용의 최솟값을 구하는 문제입니다. 조건을 만족하는 최소 비용 조합이 여러 개라면, 그중 사전 순으로 가장 빠른 것을 출력해야 합니다.입력:첫째 줄: 식재료의 개수 N (3 ≤ N ≤ 15)둘째 줄: 단백질, 지방, 탄수화물, 비타민의 최소 요구량셋째 줄부터 N개의 줄: 각 식재료의 단백질, 지방, 탄수화물, 비타민, 가격출력: 조건을 만족하는 최소 비용과 선택된 식재료 번호들을 오름차순으로 출력. 만족하는 경우가 없으면 -1 출력.링크: https://www.acmicpc.net/problem/19942풀이 1: 비트마스킹 (Bitmasking)을 활용한 부분 집합 탐색식..

DTO(Data Transfer Object)는 계층 간(Layer-to-Layer) 데이터 교환을 위해 사용하는 객체입니다. 비즈니스 로직을 포함하지 않고 순수하게 데이터만 담고 있어야 하며, 도메인 객체(Entity)를 보호하고 클라이언트 요구사항에 맞는 데이터만 전달하는 핵심적인 역할을 수행합니다.안전하고 유지보수하기 쉬운 DTO를 설계하기 위한 주요 전략들을 정리했습니다.1. 불변 객체와 record 사용DTO는 데이터를 전달하는 '운반체' 역할을 하므로, 전달 과정에서 데이터가 변경되지 않음을 보장하는 불변(Immutable) 객체로 설계하는 것이 가장 이상적입니다. Java 14부터 도입된 record는 이러한 불변 DTO를 만드는데 최적화된 문법입니다.사용하는 이유 및 장점데이터 무결성 보장..

도메인 객체를 설계하고 생성할 때, 개발자는 객체의 일관성을 유지하고 코드의 가독성을 높이기 위해 다양한 생성 전략을 선택할 수 있습니다. 대표적으로 생성자(Constructor), 빌더 패턴(Builder Pattern), 정적 팩토리 메서드(Static Factory Method) 세 가지 방식이 있으며, 각각의 장단점과 적합한 사용 상황이 다릅니다.1. 생성자 (Constructor)가장 기본적이고 전통적인 객체 생성 방식입니다. new 키워드와 함께 호출되어 객체를 초기화합니다.사용법public class User { private String name; private int age; private String email; // 필수 값을 받는 생성자 public Use..

문제n개의 서로 다른 양의 정수로 이루어진 수열이 주어졌을 때, $a_i + a_j = x$ (1 ≤ i 입력: 첫째 줄에 수열의 크기 n이 주어집니다. 둘째 줄에 수열에 포함되는 수가 주어집니다. 셋째 줄에는 x가 주어집니다.출력: 문제의 조건을 만족하는 쌍의 개수를 출력합니다.링크: https://www.acmicpc.net/problem/3273풀이 1: 정렬과 투 포인터배열을 오름차순으로 정렬한 뒤, 양 끝에서부터 포인터를 좁혀오며 합을 찾는 정석적인 투 포인터 풀이입니다.정렬: 배열 a를 오름차순으로 정렬합니다. 시간 복잡도는 O(N log N)이 소요됩니다.투 포인터 탐색: 시작 포인터 s를 0, 끝 포인터 e를 n - 1로 설정합니다.a[s] + a[e] == x: 두 수의 합이 x와 같다면..

문제비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하는 문제입니다.add x: S에 x를 추가합니다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시합니다.remove x: S에서 x를 제거합니다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시합니다.check x: S에 x가 있으면 1을, 없으면 0을 출력합니다. (1 ≤ x ≤ 20)toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가합니다. (1 ≤ x ≤ 20)all: S를 {1, 2, ..., 20} 으로 바꿉니다.empty: S를 공집합으로 바꿉니다.입력: 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어집니다. 둘째 줄부터 M개의 줄에 수..

문제지민이는 길이가 64cm인 막대를 하나 가지고 있습니다. 지민이는 이 막대를 이용해 Xcm 크기의 막대를 만들려고 합니다. 막대를 자르는 과정은 다음과 같습니다.지민이가 가지고 있는 막대의 길이를 모두 더합니다. 처음에는 64cm 막대 하나만 가지고 있습니다.가지고 있는 막대의 길이 합이 X보다 크다면, 아래 과정을 반복합니다.가지고 있는 막대 중 가장 짧은 것을 절반으로 자릅니다.만약, 자른 막대의 절반 중 하나를 버리고 남아있는 막대의 길이 합이 X보다 크거나 같다면, 그 절반을 버립니다.그렇지 않다면 버리지 않고 모두 보관합니다.위 과정을 거친 후 남은 막대들을 풀로 붙여서 Xcm를 만듭니다.목표 길이 X가 주어질 때, 몇 개의 막대를 풀로 붙여서 Xcm를 만들 수 있는지 구하는 문제입니다.입력..

문제AC는 정수 배열에 연산을 하기 위해 만든 언어입니다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있습니다.R: 배열에 있는 수의 순서를 뒤집습니다.D: 첫 번째 수를 버립니다. 배열이 비어있는데 D를 사용하면 에러가 발생합니다.초기 배열과 수행할 함수들이 주어졌을 때, 최종 결과를 구하는 문제입니다.입력: 첫째 줄에 테스트 케이스의 개수 T가 주어집니다. 각 테스트 케이스는 수행할 함수 문자열 p, 배열에 들어있는 수의 개수 n, 배열 형태의 문자열 [x_1, ..., x_n] 순서로 주어집니다.출력: 각 테스트 케이스마다 수행 결과를 [x_1,x_2,...] 형태로 출력하거나, 에러가 발생한 경우 error를 출력합니다.링크: https://www.acmicpc.net/problem/..

문제피카츄는 "pi", "ka", "chu" 세 가지 음절을 발음할 수 있으며, 이 세 음절을 합친 단어만 발음할 수 있습니다. 어떤 문자열이 주어졌을 때, 피카츄가 발음할 수 있는 문자열인지 아닌지 판별하는 문제입니다.입력: 첫째 줄에 알파벳 소문자로만 이루어진 문자열 S가 주어집니다. (문자열의 길이는 최대 5000)출력: 문자열 S가 "pi", "ka", "chu" 로만 이루어져 있으면 "YES"를, 아니면 "NO"를 출력합니다.링크: https://www.acmicpc.net/problem/14405풀이: 인덱스 기반의 패턴 매칭정규표현식이나 replaceAll 메서드를 사용할 수도 있지만, 주어진 코드는 문자열의 첫 글자부터 끝까지 직접 인덱스(idx)를 이동시키며 해당 위치의 부분 문자열을 검..