본문 바로가기

백준756

백준 14381 자바 - 숫자세는 양 (Small) (boj 14381 java) 문제 : boj14381 0부터 9까지의 모든 숫자를 체크하는건 HashSet을 사용하거나(size()가 10이 된다면 모두 찾은 것), 10칸짜리 배열을 사용하면 할 수 있다. 이제 시뮬레이션을 만들면 된다. 어떤 시뮬레이션이냐면, N을 입력받은 후 1N, 2N, 3N, ... 하고 적당히 100N 까지 각 숫자를 만들면서 각 자리수를 HashSet이나 배열에 담는다. 중간에 10개의 숫자가 모두 나왔다면 중지하고, 그렇지 않다면 적당히 큰 수 까지 직접 가보면 된다. 예를들어 다음과 같다. N이 11이었다면 다음과 같은 숫자가 체크될 것이다. 1N = 11 -> 1 2N = 22 -> 2 ... 9N = 99 -> 9 10N = 110 -> 0 최종적으로 10N일 때 10개의 수를 모두 찾았고, 11.. 2022. 3. 27.
백준 16955 자바 - 오목, 이길 수 있을까? (boj 16955 java) 문제 : boj16955 '.'인 곳 중 한 곳을 'X'로 바꾸었을 때, 'X'가 가로, 세로 혹은 대각선으로 연속으로 5개 이상인지 체크해보면 된다. 10x10의 입력값에서 '.'인 곳 모두를 한번씩 'X'로 바꿔보면서 위의 사항을 체크해보면 된다! 대략 O(10x10x5x4) 정도 될 것으로, 매우 널널하다(10x10은 오목판의 크기, 4는 가로 확인, 세로 확인, '↗'형태의 대각선, '↘' 형태의 대각선이다. 5는 대강 5 이상 됬으면 답일테니 5 미만으로만 갈테니 5이다 ㅋㅋ) 이 때 매번 전체 오목판을 모두 확인하면서 5개가 연속인지 확인하면 비효율적이다. 그러니 현재 '.'을 'X'로 변경한 위치부터 다음과 같이 가로, 세로, 대각선을 각각 확인하면 된다. 위의 경우 가로로는 4개, 세로로는.. 2022. 3. 26.
백준 20420 자바 - 화살표 미로 (Normal) (BOJ 20420 JAVA) 문제 : boj20420 매운맛의 BFS 문제였다. BFS에 대해서는 여기에 작성해놨다. 해당 글의 내용만 있으면 풀 수 있는 문제이다. 이 문제를 풀 수 있는 BFS 적용 아이디어를 작성해보겠다. A. BFS 진행 시 인접한 곳은 원래 주어진 방향, 좌측으로 회전해서 갈 수 있는 만큼의 방향(예를들어 남은 L이 2라면 좌측으로 2번까지 돌 수 있다.), 우측으로 회전해서 갈 수 있는 만큼의 방향 이다. B. 좌측으로 4번 혹은 우측으로 4번을 돌면 원래 방향이 되므로 무조건 손해이다. 따라서 좌측으로 3번, 우측으로 3번까지만 확인해야 한다. 이 때, 예를들어 좌측으로 3번이 우측으로 1번과 동일하다고 해서 2번까지만 확인하면 안된다. 남은 횟수가 한쪽이 더 많을 수도 있다. C. 방문체크는 모든 경우.. 2022. 3. 25.
백준 13537 자바 - 수열과 쿼리 1 (BOJ 13537 JAVA) 문제 : boj13537 기본적으로 알고 있어야 하는 알고리즘 기법들이 좀 있어야 이해할 수 있는 풀이 입니다. 모르는 알고리즘이 있다면 별도로 공부하셔야 이해하실 수 있습니다. 결국 통과된 풀이에 쓰인 오프라인 쿼리는 사실 어차피 값이 변경되지 않으므로, 순서를 바꿔서 쿼리를 진행하더라도 원래 위치만 안다면 순서를 바꿔서 답을 구한 후, 원래 위치에 맞게 답만 출력해주면 된다고만 이해하시면 됩니다. 제곱근 분할법은 여기를 참고하시면 될 것 같습니다. 몰라도 사실 유-명한 세그먼트 트리를 사용하면 더 효율적으로 풀 수 있습니다. (제곱근 분할법인 sqrt(N), 세그먼트 트리는 logN) 1. 시간초과 난 풀이방법 '1'은 오답노트 느낌으로 시간초과 난 풀이방법을 적은 것이니, 통과한 풀이를 보고 싶으시.. 2022. 3. 25.
백준 1417 자바 - 국회의원 선거 (BOJ 1417 JAVA) 문제 : boj1417 1. 시뮬레이션을 돌리자! 이 문제를 만족시키기 위해서 어떻게 해야할지부터 생각해보자. 다솜이가 처음 얻은 듣표수를 a라고 하겠다. 그럼 그 나머지 득표수들을 -시키면서, a를 +시켜나갈 때 나머지 득표수 중 가장 큰 득표수보다 a가 커지면 된다. 그렇다면 중요한 요소는 나머지 득표수 중 가장 큰 득표수이다. 이걸 max라 하겠다. 결국 매번 max값을 -1 시키고, a를 +1 시켜나가면 원하는 답을 구할 수 있다. 예를들어 다음의 경우를 보자. 4 1 3 3 4 답을 찾는 과정은 다음과 같다. 매번 max값을 찾고(빨간색으로 나타냈다), 해당 값을 -1 시키고 a를 +1 시킨다. 그러다가 max1) pq.add(Integer.parseInt(br.readLine())); int .. 2022. 3. 24.
백준 17756 자바 - Kieszonkowe (BOJ 17756 JAVA) 문제 : boj17756 우선 NIESTETY 를 출력해야 하는 경우부터 살펴보자. 결국 n개에 대해 가장 큰 짝수를 구해야 하는데, 짝수로 만들 수 없다는 얘기는 n이 1개였고, 그 한개가 홀수인 경우 밖에 없다. 이제 전체 로직을 살펴보자. 짝수를 만들 수 있는 경우를 살펴보면 된다. 우선 짝수+짝수는 당연히 짝수이다. 홀수+홀수도 역시 짝수이다. 따라서 짝수는 그냥 넘어가면 되고, 홀수는 홀수인 것이 짝수개 있다면 짝수로 만드는데 문제가 없다. 이제 문제는 홀수가 홀수개 있는 경우인데, 이 때는 한 개의 수를 제외해야 한다. 당연히 가장 작은 홀수를 제거하는 것이 이득일 것이다. 최종적으로 전체 로직을 살펴보면 다음과 같다. 코드 : github import java.io.BufferedReader.. 2022. 3. 24.
백준 2003 자바 - 수들의 합 2 (BOJ 2003 JAVA) 문제 : boj2003 우선 i번째 수 부터 j번째 수까지의 합을 쉽게 알 수 있는 방법을 생각해보자. 누적합을 미리 구해둔다면 O(1)에 i번째 수부터 j번째 수까지의 합을 구할 수 있다. 예를들어 '4 7 2 1'을 확인해보자. 다음과 같이 누적합 배열(arr)을 마련해두면, i번째부터 j번째 수까지의 합은 arr[j]-arr[i-1]로 O(1)에 바로 구할 수 있다. 그럼 이제 합이 m이 되는 경우의 수를 구해야 한다. 더 효율적으로 하려면 투 포인터 개념을 활용하면 되지만, 이 문제의 경우 그냥 모든 경우를 확인하면 된다. 즉 i=1일 때 j=i~n의 모든 경우, i=2일 때 j=i~n의 모든 경우, ... i=n일 때 j=i~n인 모든 경우를 다 보면 된다. 코드 : github import j.. 2022. 3. 23.
백준 1707 자바 - 이분 그래프 (BOJ 1707 JAVA) 문제 : boj1707 '그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.' 무슨말이냐면, 정점을 두개의 그룹으로 나눴을 때, 해당 그룹끼리는 간선이 없도록 나눌 수 있으면 이분 그래프라는 얘기이다. 아래의 그림을 보면 바로 이해가 될 것이다. 1,2,3은 이분 그래프를 그려봤다. 4는 이분 그래프가 아닌 경우이다. 즉, 어떻게든 2 종류의 정점으로 나눌 때 간선 연결된 것 끼리 같은 종류만 아니면 된다 (4번의 경우 노란 정점 둘이 간선이 연결되었으므로 이분 그래프가 아니다. 그리고 다른 방식으로 2종류로 나눠도 모두 마찬가지로 이분 그래프가 될 수 없다.). 또 .. 2022. 3. 22.
백준 18384 자바 - PRIM (BOJ 18384 JAVA) 문제 : boj18384 이 문제를 풀기 위해 코드적으로 알아야 하는 것은 다음의 두가지 이다. 1. 1000000보다 처음으로 큰 소수까지의 모든 소수 2. 특정 입력에 대해 빠르게 그보다 작지않은 소수를 구하기 '1'의 경우 에라토스테네스의 체로 구할 수 있다. 참고로 1000000보다 처음으로 큰 소수는 1000003이다. 이건 정확히 몰라도 된다. 대충 1000100 까지 구하면 된다. 참고로 n이하의 모든 소수를 알기위해 에라토스테네스의 체를 사용할 때는 sqrt(n) 까지만 확인하면 된다. 이것에 대한 설명 및 증명은 이 글('에라토스테네스의 체 혹은 소수판정 시 제곱근 까지만 확인하면 되는 이유')에 있다. '2'의 경우 이분탐색을 활용하면 된다. c++의 upper_bound에 해당하는걸 .. 2022. 3. 22.
백준 1035 자바 - 조각 움직이기 (BOJ 1035 JAVA) 문제 : boj1035 처음엔 그리디로 풀어보려 했지만, 별다른 규칙을 찾지 못했다. 와중에 생각해보니 어차피 5x5 밖에 안되고, 조각은 최대 5개 이므로 최악의 경우라도 O(25^5*25*5) 정도로 풀 수 있다. 25^5는 5x5 크기의 보드에 5개의 조각을 모든 위치에 놓는 경우의 수이고, 해당 경우의 수에 대해 *25는 그 중 하나의 조각을 찾는 것이고, *5는 5개가 인접해있는지 확인하는 것이다. 저대로는 당연히 불가능하지만, 여기에 백트래킹을 더해서 이미 나왔던 최소 이동 횟수 이상이라면 해당 경우의 수와 그 이후의 경우의 수를 중간에 중지하는 방식으로 진행한다면 어느정도 가능할 것 같아서 일단 해봤다. 참고로 이 경우 모든 경우의 수는 조각이 n개 있었다면 다음과 같이 확인하면 된다. 1... 2022. 3. 21.

티스토리툴바