본문 바로가기

PS831

[자바] 백준 9715 - 면적 구하기 (boj java) 문제 : boj9715 이하의 예시를 확인해보자. 2 3 312 103 그림으로 그려보면 아래와 같다. 면적, 즉 다른 상자에 닿아있지 않고 공기(?)와 닿아있는 면의 수를 세면 될 것이다. 우선 어떻게 해야 면적을 구할 수 있을지 생각해보자. 우선 가장 간단한 바닥에서 위로 본 형태와, 위에서 바닥쪽으로 본 형태부터 생각해보자. 둘 다 아래와 같이 2차원 평면의 형태로 보일 것이다. 따라서 0이 아닌 위치라면 면은 항상 +2를 해주면 된다(바닥 하나 뚜껑 하나). 그럼 이제 동서남북 4개의 방향에서 공기와 닿아있는 면을 세주면 된다. 우측에서 좌측으로 보는 경우를 한번 생각해보자. 아래 그림과 같은 방향이다. 설명을 돕기 위해 판이 하나 이동하면서 본다고 해보면, 아래와 같은 두 가지 부분에서 면이 공.. 2022. 5. 31.
[자바] 백준 15881 - Pen Pineapple Apple Pen (boj java) 문제 : boj15881 아무튼 'pPAp'의 개수만 세면 되는 문제이다. 겹칠여지도 없으니 문자열만 잘 찾아주면 된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { private static final String PPAP = "pPAp"; private void solution() throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); String s = br.readLine(); int cn.. 2022. 5. 30.
[자바] 백준 1867 - 돌멩이 제거 (boj java) 문제 : boj1867 Minimum Vertex Cover 문제이다. 즉, 최소한의 정점만을 선택했을 때, 모든 간선들이 양 끝점 중 하나는 선택된 정점이어야 한다. 이 문제의 경우 열 번호와 행 번호를 각각 정점으로 두고, 돌멩이가 존재하는 위치를 간선으로 두자. 그럼 예제 입력 1의 경우 다음과 같이 그래프로 변경해볼 수 있다. 3 4 1 1 1 3 2 2 3 2 이 때 Minimum Vertext Cover는 다음과 같다. 이 때, 행과 열에 대해 이분그래프로 나타낼 수 있으므로 쾨니그의 정리(위키)를 적용해볼 수 있다. 복잡하게 써있지만 결론은 이분그래프에서 Minimum Vertext Cover는 이분 그래프의 최대유량 문제와 동일하다는 의미이다. 이분그래프의 최대유량이므로 이분 매칭(MIT .. 2022. 5. 30.
[자바] 백준 12780 - 원피스 (boj java) 문제 : boj12780 H에서 N이 몇 번 나오면 되는지 확인하면 된다. 이 때 명확하지 않은 점이 예를들어 아래와 같은 경우, 2번이 답이 될지 3번이 답이 될지였다. 애초에 문제로 파악할 수 없었으므로 그냥 제출해보고 틀리면 변경하려 했다. 결론은 후자가 맞았다. AAAA AA 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String a = .. 2022. 5. 29.
[자바] 백준 24480 - 알고리즘 수업 - 깊이 우선 탐색 2 (boj java) 문제 : boj24480 내림차순으로 다음 정점을 선택해야 한다. 이걸 위해 인접 행렬로 간선을 저장할 경우 O(N^2)이 필요하므로 시간초과가 나게 될 것이다. 그러니 인접 리스트로 간선을 표현하자. 이 때 내림차순으로 다음 정점을 선택해야 하므로, 미리 내림차순으로 각 정점의 간선들을 정렬시켜두면 된다. 혹은 Priority Queue 등을 사용해 다음 정점을 저장해둬도 될 것이다. 위의 내용 이외에는 기본 DFS로 구현하면 된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Collections; import java.util... 2022. 5. 28.
[자바] 백준 2559 - 수열 (boj java) 문제 : boj2559 이하 설명에서 arr[i]는 입력으로 주어진 i번째 수를 뜻한다. 총 세 가지 방식으로 풀이를 진행한다. 1. 누적합 (prefix sum) prefix sum (누적합)을 미리 구해둬보자. 누적합 배열을 sumArr이라고 하고, sumArr[i]는 arr[1]+arr[2]+...+arr[i] 라고 하자. 그렇다면 sumArr[i] = arr[i] + sumArr[i-1]이 될 것이다. 이렇게 누적합 배열을 구해둔다면, 이후 아래의 공식을 통해 각각 O(1)로 arr[i]부터 이전 K개의 합을 구할 수 있다. 따라서 O(N)으로 답을 구할 수 있다. 코드1 : github - prefix sum import java.io.BufferedReader; import java.io.In.. 2022. 5. 27.
[자바] 백준 1671 - 상어의 저녁식사 (boj java) 문제 : boj1671 문제에서 제시된 상황이 그래프로 표현 가능한 경우 그래프로 바꿔서 생각해보는 것이 이득인 경우가 많다. 이 문제의 경우에도 주어진건 상어의 크기, 속도, 지능으로 3개나 되지만, 사실 그래프의 간선으로 생각해본다면 값이야 어떻든 조건을 만족한 경우 그냥 방향이 있는 간선 하나가 추가될 뿐이다. 예시 입력 1을 그려보면 다음과 같다. 간선은 [먹는쪽 -> 먹히는쪽]으로 연결할 것이다. 5 4 5 5 10 10 8 5 7 10 8 7 7 8 10 3 그럼 동일 정점을 좌우로 둬서 다음과 같이도 그려볼 수 있다. 결국 최대한 많이 잡아먹으면 남아 있는 수가 최소가 되므로, 최대유량 문제인데 이분그래프 이므로 이분매칭을 사용해서 좌측의 상어가 우측의 상어를 먹는다고 생각해보자. 그리고 좌.. 2022. 5. 26.
[자바] 백준 11660 - 구간 합 구하기 5 (boj java) 문제 : boj11660 prefix sum을 이용하는 문제이다. 1차원 배열에 대해 prefix sum을 계산해두면 1차원 배열의 모든 구간에 대한 구간합을 O(1)로 구할 수 있다. 따라서 모든 행에 포함된 열에 대해 행의 개수만큼 prefix sum을 계산해둔다면, O(MN)으로 문제를 풀 수 있다. 이렇게 짠 코드는 여기(github)에 있다. 이하 풀이는 2차원 prefix sum을 사용한 풀이이다. 2차원 배열에 대해 prefix sum을 유지한다면 O(M)으로도 가능하다. arr[a][b]를 (1, 1)부터 (a, b) 까지의 합이라고 정의하자. 그럼 arr[a][b] = '[a. b]의 값' + arr[a-1][j] + arr[a][b-1] - arr[a-1][b-1] 이라고 할 수 있다... 2022. 5. 26.
[자바] 백준 21939 - 문제 추천 시스템 Version 1 (boj java) 문제 : boj21939 우선 한글적으로 좀 해맬만한 부분이 있어서 그것부터 써보겠다(제가 그래서 틀렸었단 얘깁니다 ㅠ). add의 '(추천 문제 리스트에 없는 문제 번호 P만 입력으로 주어진다. 이전에 추천 문제 리스트에 있던 문제 번호가 다른 난이도로 다시 들어 올 수 있다.)' 라는 설명과 solved의 '(추천 문제 리스트에 있는 문제 번호 P만 입력으로 주어진다.)' 라는 설명 때문이었다. 결론적으로 '추천 문제 리스트'는 처음 N개의 입력만을 뜻한다. 그리고 '이전에 추천 문제 리스트에 있던 문제 번호'라는 말은 즉, N개에 존재했었으나 solved로 제거된 경우엔 add로 동일한 번호가 들어올 수 있다는 말이었다. 마찬가지로 solved의 설명 또한 해석하자면 결국 N개에 존재했던 녀석들만 .. 2022. 5. 25.
[자바] 백준 18221 - 교수님 저는 취업할래요 (boj java) 문제 : boj18221 문제 제목이 상당히 무섭고, 지문이 길긴 하지만 정리해보면 결국 알아야 하는건 어렵지 않다. 알아내야 하는걸 정리해보자. 1. 성규가 앉은 위치의 좌표 2. 교수님이 앉은 위치의 좌표 3. '1'과 '2'의 거리가 5이상인지 4. '1'과 '2'로 만들어지는 직사각형 혹은 선 위에 몇 명의 학생이 있는지 위와 같이 알 수 있으면 풀 수 있다. '1'과 '2'는 입력을 받으면서 알 수 있다. '3'은 문제에서 제시된 공식으로 알 수 있다. 다만, double로 처리하는건 항상 소수점 오차의 문제가 생길 가능성이 있다. 따라서 아래와 같이 공식을 바꿔서 int내에서 처리가 되도록 하자. 이하의 조건을 만족하지 않는다면 바로 0을 출력하고 종료하면 된다. '4'의 경우엔 결국 직사각형.. 2022. 5. 24.

티스토리툴바