본문 바로가기

PS/BOJ764

[자바, 파이썬] 백준 13706 - 제곱근 (boj java) 문제 : boj13706 단순히 제곱근(루트)을 구하는 간단한 문제긴한데, 문제는 정수의 자리수가 최대 800자리나 된다는 점이다. 따라서 큰 수 연산이 필요하다. 파이썬의 경우엔 애초에 무한정 크기의 숫자 표현이 가능하다. 다만 단순히 int(input())**0.5 와 같은 코드로는 불가능한데, 너무 큰 수에대해서는 **0.5가 사용 불가하다고 한다. 찾아보니 math에 isqrt 라는 함수가 있어서 그걸 사용했다. 자바의 경우엔 우선 큰 수의 경우엔 BigInteger로 표현 가능하다. 그리고 BigInteger에 sqrt라는 함수가 있으므로 해당 함수를 사용하면 되는데, 문제는 이게 자바 9에서 추가되었다. 따라서 자바9 이상에서는 간단하다. 자바 8 이하에서 짤려면 비트 연산을 활용해서 직접 제.. 2022. 6. 1.
[자바] 백준 21941 - 문자열 제거 (boj java) 문제 : boj21941 기존에 그리디로 생각해서 풀었었는데, 재채점이 되어 틀려있었다. 기존 틀린 풀이는 여기에 있다. 다시 풀어서 작성한다. 문자열 s를 각 인덱스(이하 idx)를 정점으로 하는 가중치를 가지는 방향 그래프로 바꿔서 생각해보자. 이 때, '문자열 S에서 문자 하나를 지우고 점수를 1점을 얻을 수 있다.' 라는 부분은 idx -> idx+1 로 가는 가중치 1의 간선으로 바꿀 것이다. 그리고 문자열 Ai와 그에 따른 가중치는 예를들어 s가 "abcd"이고, A1이 bc이고 가중치가 3이라고 한다면 idx=1 -> idx=3으로 향하는 가중치 3의 간선이라고 할 수 있다. 예제 입력 1을 봐보자. abcxyzxabc 2 abc 10 xyz 5 위에서 말한 그래프로 그려보면 다음과 같다. .. 2022. 5. 31.
[자바] 백준 6318 - Box of Bricks (boj java) 문제 : boj6318 입력으로 들어온 n개의 hi의 합이 n으로 나누어 떨어진다고 했으므로, 잘 생각해보면 결국 모두 동일한 높이인 sum(hi)/n 으로 맞춰줘야 한다. 즉, sum(hi)/n 보다 큰 hi들에서 하나씩 빼서 sum(hi)/n 미만의 hi들에 더해줘야 한다. 이 말은 다시 말해, n개의 hi들에 대해 이하의 값을 구하면 된다. 여기서 hi_k는 k번째 hi 값을 의미하고, sum(hi)/n은 n개의 hi값의 합을 n으로 나눈 값이다(나누어 떨어진다는 조건이 있으므로 정수). 말로 설명하면, sum(hi)/n보다 큰 hi값을 초과한 값 부분만 다 더해주면 답이 된다. 코드 : github import java.io.BufferedReader; import java.io.IOExcepti.. 2022. 5. 31.
[자바] 백준 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.

티스토리툴바