모항이코딩한다

풀이방법 및 문제점 2022.05.07 문제 없이 알고리즘을 잘 짰다고 생각했는데 50%에서 계속 막힌다. 정답이 2의 31제곱 미만이라는 것을 보고 화끈하게 BigInteger로 다루어보았는데 그래도 똑같이 50%에서 틀린다. 흠... 내가 놓친 분기 또는 반례가 있는 것 같다. 모든 가능한 분기를 하나하나 적어가며 빈틈없이 만들어봐야 하나? 거의 다 왔다는 생각이 들어 구글링하기가 아깝다. 알고리즘은 다음과 같다. 음수와 양수를 따로 다룬다. 음수의 경우 다음과 같이 다룬다. 가장 작은 수 즉 절댓값이 큰 것들부터, 모든 음수를 짝짓는다. 주어진 수들 중 음수가 -1, -5, -2, -7 이렇게 네 개라면 (-7, -5), (-2, -1) 이런 식으로 짝짓는 것이다. 만약 음수가 홀수 개라면 가장 절..

풀이방법 사용된 것: 정렬 수학 2022.05.07 정수 N의 값은 N의 가장 작은 1이 아닌 약수와 N의 가장 큰 본인이 아닌 약수를 곱한 것과 동일하다. 주어지는 약수들을 모두 읽어온 다음, 그 중에서 가장 작은 것과 큰 것을 곱한 값을 화면에 출력하면 된다. 코드 Java(2022.05.07) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException{..

풀이방법 사용된 것: 정렬 Comparator Overriding 2022.05.04 Comparator를 오버라이드하여 정렬하면 된다. ▼Comparator Overriding하는 법 자바에서 내 마음대로 정렬하기: Comparator Overriding 기본 데이터타입이 아닌 객체(Object)를 정렬해야 할 때가 있다. 또한, 자바에서 기본으로 제공해주는 정렬함수로는 수행하기 힘든 복잡한 방식/기준의 정렬이 필요할 때도 있다. 백준 #1931 회의실 blowupmomo.tistory.com 코드 Java(2022.05.04) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; impor..

풀이방법 사용된 것: 수학 2022.05.03 오늘 새벽에 갑자기 올 솔브 배경이 가지고 싶어져서 가장 쉽고 문제 수도 적은 편인 브론즈 5 레벨 문제를 모두 푸는 켠왕을 시작했다. 방금 막 완료했다. ㅋㅋㅋㅋㅋㅋㅋㅋㅋ휴학하니까 별 뻘짓을 다 한다. 브론즈 5 쯤이야 껌이라고 생각했는데 50문제 넘게 풀다 보니 꽤 오래 걸렸다. 그리고 나름 새롭게 알게 된 것들도 있다. 난이도를 버린 대신 유머를 택한 나사 빠진 문제들이 많아서 재미있었다. 아무튼 이 글을 쓰는 것은 배경 얻은 날을 기록하기 위해서이기도 하지만 밤새 푼 브론즈 5 문제들 중 적어둘 만 한 문제가 하나 있기 때문이다. 14928번 문제는 큰 수의 나머지를 구하는 문제인데, BigInteger를 사용하면 시간초과가 난다. BigInteger..

풀이방법 사용된 것: 브루트포스 알고리즘 2022.05.03 1번째부터 10000번째까지의 종말의 수를 모두 미리 찾아두고, 그 중에서 입력값에 알맞은 수를 골라 출력하면 된다. 666부터 시작하여 모든 정수를 점검한다. 해당 수가 종말의 수라면 배열에 저장한다. 배열에 10000번째 종말의 수가 저장되면 점검을 종료한다. 입력값을 N이라 할 때, 배열에 N번째로 저장된 수를 화면에 출력하면 된다. 코드 Java(2022.05.03) import java.util.Scanner; public class Main { public static void main(String[] args){ // TODO Auto-generated method stub Scanner sc = new Scanner(System...

풀이방법 사용된 것: 브루트포스 알고리즘 2022.05.03 모든 사람에 대하여, 본인보다 몸무게도 무겁고 키도 큰 사람의 수를 일일이 세어주면 된다. 코드 Java(2022.05.03) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException{ // TODO Auto-generated method stub BufferedReader br = new BufferedReader(new InputStre..

풀이방법 사용된 것: 수학 2022.05.01 가장 왼쪽 위의 대각선을 첫 번째 대각선이라 하고 오른쪽 아래로 갈수록 2, 3, 4, ... 번째 대각선이라 하자. 입력값으로 N이 주어진다. N번째 수가 몇 번째 대각선에 속하는지를 먼저 구하고, 그 대각선 내에서 몇 번째의 수인지를 구하면 된다. 이 두 가지만 알면 분수를 정확하게 구할 수 있다. 몇 번째 대각선에 속하는지 구하는 방법은 다음과 같다. 1번째 대각선부터 k번째 대각선까지에 속하는 분수의 개수는 1부터 k까지의 정수를 더한 것과 같다. 따라서, 1부터 k까지 더했을 때의 합이 N보다 크거나 같은 가장 작은 k를 찾으면 된다. N은 이 k번째 대각선에 속한다. k번째 대각선 내에서 몇 번째의 수인지를 구하는 법은 다음과 같다. 1~k의 정수..

풀이방법 사용된 것: 수학 2022.05.01 딱 한 문장짜리 식으로 답을 구해야 하는 문제이다. 반복문이나 조건문 같은 것을 쓰면 높은 확률로 시간초과가 발생한다. 2022.04.27 2023년 2월 6일에 시간초과 기준이 바뀌어, 조건문을 사용해도 시간초과가 발생하지 않게 되었다. 그래서, 2022년 4월 27일에 제출했다가 시간초과를 받았으나 재채점 후 정답 처리가 된 조건문 코드를 하단에 정답 코드로 추가하였다. 반복문을 사용한 코드는 여전히 시간초과를 받는다. 코드 Java(2022.05.01) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Str..

풀이방법 및 문제점 2022.04.30 예제에 대해서는 모두 올바른 값이 출력되지만, 시간 초과가 발생하여 실패하였다. 내가 짠 알고리즘의 시간복잡도가 O(NK)이기 때문이다. 알고리즘은 다음과 같다. 보석을 가치 기준으로 내림차순 정렬하되, 가치가 같은 보석끼리는 무게를 기준으로 오름차순 정렬한다. 가방의 용량은 오름차순 정렬한다. 가벼운 가방부터 순서대로 살핀다. 가장 앞에 있는 보석부터 살피며, 이 가방에 들어갈 만큼 가벼운지 확인한다. 들어갈 수 있으면 그 보석을 가방에 집어넣으면 된다. 아까 가치 기준으로 내림차순 정렬을 해뒀기 때문이다. 이렇게 모든 가방을 살피면 된다. 그러나 보석들 중 가장 가치가 낮은 보석만이 가방에 들어갈 수 있을 정도로 가볍다면 최악의 시간복잡도에 해당하게 된다... ..

풀이방법 사용된 것: Queue 2022.04.30 2개의 큐를 사용하여 푸는 문제이다. 다리에 아직 올라가지 않은 트럭들을 저장하는 Queue trucks 다리 위의 상태를 저장하는 Queue bridge 이렇게 2개를 사용하였다. trucks의 각 요소는 한 대의 트럭마다 할당된다. 각각 해당 트럭의 무게를 저장한다. bridge의 각 요소는 하나의 단위길이마다 할당된다. 각각 해당 단위길이에 실린 무게를 저장한다. 백준 문제 페이지의 1번 예제의 경우에 위 2개 큐의 초기상태는 다음과 같다. 1번 예제의 입력값: 4 2 10 7 4 5 6 trucks의 초기 상태는 다음과 같다. 7 4 5 6 bridge의 초기 상태는 다음과 같다. 아직 아무 트럭도 다리 위에 올라가지 않았으므로 두 개의 단위길이..