본문 바로가기

분류 전체보기1105

백준 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.
[자바] 프로그래머스 - 체육복 [코딩테스트 연습 Lv1] 문제 : programmers-체육복 1. '여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.' 부분부터 처리해야 한다. lost와 reserve에 동시에 포함되는 항목이 있다면 양쪽에서 제거해서, '2' 이후의 로직에 영향을 끼치면 안된다. 2. +-1인 학생한테 체육복을 빌릴 수 있으므로 무지성으로 lost 기준으로 +-1 학생한테 빌릴 수 있으면 바로 빌리고, reserve에서 제거하면 된다. 뭐 오름차순으로 -1인 학생부터 빌리고 이런 과정이 필요 없다. 만약 +-2 이상으로 빌릴 수 있었다면 누가 누구한테 빌리는지에 따라 빌릴 수 있는 학생의 수가 변경될 것.. 2022. 3. 23.
백준 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.
이분 그래프 (bipartite graph) 그래프의 정점의 집합을 둘로 나눴을 때, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있는 그래프를 이분 그래프(bipartite graph)라고 한다. 즉, 정점을 어떠한 방법으로든 두 개의 집합으로 나눴을 때 각 집합의 정점끼리 간선이 존재하지 않게 나눌 수만 있다면 이분 그래프이다. 예를들어 위 이미지에서 1,2,3은 이분 그래프이고 4는 이분 그래프가 아니다(4번의 경우 동일한 집합끼리 간선이 연결되어 있다. 이와 같이 홀수 길이의 사이클이 있다면 이분 그래프가 될 수 없다.). 또 3과 같이 서로 연결된 부분이 없더라도 어쨌든 이분 그래프의 정의를 위반시키지 않으므로 이분 그래프이다. 이분 그래프 판별방법은 다음과 같다. 1. 모든 정점에 대해 각 정점에서 dfs 혹은 bfs를 진.. 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.
백준 9242 자바 - 폭탄 해체 (BOJ 9242 JAVA) 문제 : boj9242 입력받은 문자열을 숫자로 변경만 할 수 있다면 6의 배수인지는 n%6==0 과 같이 쉽게 알 수 있다. 또한 코드는 8자리 이하라고 했으므로 최대 10^8-1의 값이므로 정수로 표현하는데에도 문제가 없다. 따라서 주어진 문자가 잘못된 문자인지 여부를 알 수 있고, 주어진 문자가 숫자로 무엇과 대응되는지만 알면 풀 수 있다. 그럼 주어진 문자를 주어진 기준문자(아래와 같은)와 비교만 잘 하면 된다. 이 때 주의점은 각 문자의 특징을 잡아서, 예를들어 마지막 열에 5개의 별표가 있다면 1 혹은 7일테니 첫번째 열에 *이 있다면 7, 아니면 1 이런방식은 틀린 입력값을 제대로 잡아낼 수 없다. 따라서 문자의 모든 위치(5x3)을 모두 비교하는게 맞다. 내 경우엔 우선 기준 데이터를 파싱.. 2022. 3. 21.

티스토리툴바