모항이코딩한다

풀이방법 사용된 것: 브루트포스 알고리즘 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의 초기 상태는 다음과 같다. 아직 아무 트럭도 다리 위에 올라가지 않았으므로 두 개의 단위길이..

풀이방법 사용된 것: ArrayList 2022.04.30 ArrayList는 새로운 요소를 특정 인덱스에 추가하였을 때 그 인덱스보다 뒤에 있는 요소들을 자동으로 한 자리씩 뒤로 이동시켜준다. 따라서 이 문제는 ArrayList를 사용하면 쉽게 풀리는 문제이다. 학생이 뽑은 번호가 주어질 때마다 맨 뒷자리의 인덱스, 즉 이번 학생이 0을 뽑았을 경우 서야 하는 자리의 인덱스에서 학생이 뽑은 번호만큼을 빼서 그 인덱스에 학생을 add하면 된다. 코드 Java(2022.04.30) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import..

풀이방법 사용된 것: Stack 2022.04.29 #9012 : 괄호 풀이방법 사용된 것: 스택 2022.03.02 boolean 형 변수 v를 사용한다. 해당 문자열이 올바른 괄호 문자열이면 v 를 true로, 그렇지 않으면 false로 설정할 것이다. v의 초기값은 true이다. 반복문 내에서, 주 blowupmomo.tistory.com 백준 9012번 괄호 문제와 매우 비슷한 문제이다.​ 각 문자열마다 아래의 과정을 수행하면 된다. boolean 형 변수 v를 true로 초기화해준 뒤, 문자열이 균형잡히지 않았다는 것이 발견되면 false로 바꾸어줄 것이다. 마지막에 v의 값이 true인 상태로 남아있다면 해당 문자열은 균형잡힌 것이다. 주어진 문자열을 처음부터 한 글자씩 살핀다. 이번 문자가 ..

풀이방법 사용된 것: 그리디 알고리즘 정렬 2022.04.28 물이 새는 곳을 편하게 '구멍'이라 부르겠다. 가장 왼쪽 구멍부터 살피면 되므로 그리디 알고리즘이다. 가장 왼쪽 구멍부터 살피려면 구멍 위치 배열을 오름차순 정렬해야 하므로 정렬이 사용된다. 먼저 구멍들의 위치를 싹 읽어와 int[]형 배열에 저장한 뒤, 이 배열을 오름차순 정렬한다. 2개의 정수형 변수가 사용된다. 정수형 변수 cnt는 현재까지 사용된 테이프의 개수를 저장한다. 즉, 다 풀고 나면 이 문제의 정답이 cnt에 저장되게 된다. 다 쓰지 않았더라도 지금 사용하는 중인 테이프까지 세어야 하므로 초기값을 0이 아닌 1로 선언한 뒤, 새 테이프를 꺼낼 때마다 1씩 증가시킬 것이다. 정수형 변수 left는 지금 사용하는 중인 테이프의 왼..

풀이방법 사용된 것: HashMap TreeSet 2022.04.28 평균, 중앙값, 범위는 매우 쉽게 구할 수 있으나 최빈값을 구하기가 성가신 문제였다. 최빈값을 구하는 데에만 해시맵과 트리셋을 다 사용했다... 더 간단하게 구하는 방법이 있을 것 같은데 뭔가 찝찝하다. 평균은 총합을 구한 뒤 이를 n으로 나누면 된다. 그리고 입력된 수들을 모두 저장한 int[]형 배열을 오름차순으로 정렬한다.(Arrays.sort() 사용) 정렬된 배열에서 인덱스가 n/2인 수가 중앙값이다. 정렬된 배열의 마지막 수에서 첫 번째 수를 뺀 것이 범위이다. 최빈값을 구한 방법은 다음과 같다. 먼저 해시맵을 사용해 모든 수의 등장 횟수를 구한다. 를 저장하는 형 해시맵을 사용하면 된다. 그 다음 위의 해시맵을 처음부터 돌..

풀이방법 사용된 것: 수학 2022.04.23 주어진 벌집은 다음과 같이 여러 개의 겹으로 인식할 수 있다. 안쪽으로부터 몇 번째 겹에 있느냐에 따라, 그 칸에 도착하기까지 거치는 칸의 수가 정해진다. 17은 3번째 겹에 위치하므로, 17이 입력값으로 주어졌을 때 올바른 출력값은 3이다. 따라서, 주어진 수가 몇 번째 겹에 위치하는지를 알아내는 알고리즘을 작성하면 된다. 1번째 겹에 속하는 수는 1개이다. 2번째 겹에 속하는 수는 6개이다. 3번째 겹에 속하는 수는 12개이다. 4번째 겹에 속하는 수는 18개이다. ... n번째 겹에 속하는 수는 6$\times$(n-1)개이다. 이러한 규칙을 이용하여, 각 겹에서 가장 큰 수를 저장하는 정수 배열을 생성할 수 있다. N의 최댓값이 1,000,000,00..