0과 1의 쉼터

[백준 08911] 거북이 [Java]

문제http://boj.ma/8911 8911번: 거북이 boj.ma 풀이문제 요약거북이가 이동한 영역을 감싸는 가장 작은 직사각형의 면적을 구하자.아이디어주어진 명령대로 거북이를 이동시켜 가장 큰/작은 x, y값을 기록한 후 두 차를 통해 최소 직사각형의 면적을 구할 수 있다. for (char command : commands) { switch (command) { case 'F': x += dx[dir]; y += dy[dir]; break; case 'B': ..

[백준 10384] 팬그램 [Java]

문제http://boj.ma/10384 10384번: 팬그램 boj.ma 풀이문제 요약문자열에 모든 알파벳이 등장하는 최소 횟수를 구해 적절한 문구를 출력하자.아이디어알파벳에 대한 빈도를 모두 기록 후 최소 빈도를 찾으면 된다.import java.io.*;public class Main { private static final String[] MSG = { "Not a pangram\\n", "Pangram!\\n", "Double pangram!!\\n", "Triple pangram!!!\\n" }; public static void main(String[] args) throws Exception { . . . ..

[백준 01374] 강의실 [Java]

문제http://boj.ma/1374 1374번: 강의실 boj.ma 풀이문제 요약강의 N개의 시작, 종료 시간이 주어졌을 때 모든 강의를 진행하기 위해 필요한 최소 강의실을 수를 구하자.아이디어가장 일찍 끝나는 강의 다음으로 또 다른 강의를 시작할 수 있는 지에 따라 필요한 강의실의 수가 결정된다.우선 강의 정보를 (시작, 종료)를 기준으로 오름차순 정렬 해주자.최소힙에 강의 종료 시간을 차례대로 넣어주며, 가장 일찍 끝나는 강의 시간과, 다음 강의의 시작 시간을 비교하면 된다. 최소힙의 각 노드수는 만약 연강이 가능하다면 루트 노드가 갱신 될 것이며, 결국 최소힙의 노드 수는 강의실 수가 된다. // Solve Arrays.sort(lectures, (a, b) -> { ..

문제http://boj.ma/10158 10158번: 개미 boj.ma 풀이문제 요약벽에 닿으면 이동 방향이 반사되는 W*H 공간에서 (X, Y)에서 우상향 대각선 방향으로 출발해 T시간 후의 위치를 출력하자.아이디어벽에 닿으면 이동 방향이 반사되므로, X와 Y를 각각 계산하면 쉽게 구할 수 있다.X + T 즉, 처음 X로부터 T만큼 이동한 거리를 W로 나누었을 때의 나머지가 벽면으로부터 떨어진 최종 좌표값의 X이며, 이는 X + T를 W로 나누었을 때의 나머지에 따라 왼쪽 또는 오른쪽 벽면을 알 수 있다.Y또한 동일하게 구하면 된다. // Solve int nx = (X + T) % W; nx = ((X + T) / W) % 2 == 1 ? W - nx : nx; ..

문제http://boj.ma/28359 28359번: 수열의 가치 boj.ma 풀이문제 요약주어진 수열이 증가하지 않는 부분 수열(P), 감소하지 않는 부분 수열(C)가 되도록 재배열하여 주어진 규칙대로 수열의 가치가 최댓값을 가지도록 하자.아이디어예제의 경우 P = {1, 2, 2}, Q = {3, 2, 2} 로 구성되며, {2, 2}가 중복되어 최대 가치 12를 가진다.수열의 가치에 중복 계산하는 수를 제외한다면, 수열을 재배열 할 때 P 또는 Q는 1개의 요소로도 충분하므로 정렬을 수행할 수 있다.P 또는 Q는 부분 수열이므로, 중복 계산되는 수를 포함하는 것으로 충분하다.중복 계산되는 수는 빈도와 값의 곱이 큰 수로 결정해주자. // Solve Arrays.sort(A);..

문제http://boj.ma/25185 25185번: 카드 뽑기 boj.ma 풀이문제 요약주어진 4장의 카드가, 3가지 휴식 조건 중 하나라도 만족하는지 확인하는 문제아이디어주어진 휴식 조건을 만족하는 메서드(isStraight, isTripleOrMore, isTwoPairOrFour)를 작성해 휴일인지 판별하면 된다.문제 난이도에 비해 구현이 많은 편이다. /** * 1. 적힌 알파벳이 같으면서 숫자가 연속되는 세 장이 존재한다. * 연속한 세 숫자는 서로 다른 숫자여야 한다. */ private static boolean isStraight(String[] cards) { Map> map = new HashMap(); for (Strin..

문제http://boj.ma/10546 10546번: 배부른 마라토너 boj.ma 풀이문제 요약N명의 참가자 이름과, N - 1명의 완주자 이름을 비교해 마라톤을 완주하지 못한 사람의 이름을 출력하자.아이디어참가자 이름이 중복되는 경우가 있다. Map에 동명이인의 수를 누적해 참가자를 세주고, N - 1명의 완주자 만큼 값을 빼고나면 최종적으로 Map에는 미완주자만 남는다. for (int i = 0; i cur + 1); } for (int i = 1; i cur - 1 == 0 ? null : cur - 1); }풀이시간10분소스코드https://github.com/rogi-rogi/problem-solving/blob/..

문제http://boj.ma/33957 33957번: Golden Section Search boj.ma 풀이문제 요약연속된 부분 수열의 하한/상한 난이도를 적절이 선택해 합이 동일한 두 그룹을 최대한 몇 개 만들 수 있는지 알아내자.아이디어N은 1e5로 완전 탐색은 불가능하다. 선형 탐색을 하며 부분합을 이용해 두 그룹의 하한/상한을 변경해가며 두 그룹의 범위가 겹치는지 확인하자. // Solve long part1_LSum = 0; long part1_RSum = 0; int cnt = 0; for (int i = 0; i 풀이시간20분소스코드https://github.com/rogi-rogi/problem-solving/blob/main..

문제http://boj.ma/1635 1635번: 1 또는 -1 boj.ma 풀이문제 요약1 또는 -1로 이루어진 수열 A의 요소들과 차례로 곱할 또 다른 수열 B만들고, 합한 결과가 0이 되도록 하는 수열 B를 구하자.아이디어수열 A의 합이 0이라면 B는 1로만 이루어진 수열로 충분하다.만약 0이 아니라면, 그 수의 절반만큼 -1로 채워야 한다. 수열의 부분합이 0이 아닌 전체 합의 절반이 되는 지점을 찾아서 1로 채우고, 나머지는 -1로 채워주자. // Solve final int sum = Arrays.stream(A).sum(); if (sum == 0) { sb.append("1 ".repeat(Math.max..

문제http://boj.ma/10736 10736번: XOR삼형제 2 boj.ma 풀이문제 요약1 ~ N 중 임의의 3개의 수들의 XOR 연산 결과가 0이 되지 않도록 하는 최장 부분 수열을 구하자.아이디어임의의 3개의 수 A, B, C의 XOR 연산 결과가 0이 되지 않기 위해서는 A ^ B = C인 경우가 없어야 한다.0이 되는 상황을 위해서는 단 1개의 비트라도 1이면 된다. 문제를 쉽게 보기 위해, 최상위 비트가 1이 되도록 해보자.K는 $floor(log_2{N})$이라 할 때, $2^{K-1}$~ $2^K$ - 1 중 임의의 두 수의 XOR 연산은 최상위 비트가 사라지며, $2^{K - 1}$보다 항상 작다.$2^{K}$이상 $min(N, 2^{K} + 2^{K - 1} - 1)$인 두 수의 ..