모항이코딩한다

풀이방법 사용된 것: 브루트포스 알고리즘 2022.04.21 가능한 수를 모두 구하고 그 중 최솟값을 출력하면 된다. 처음엔 브루트포스로 풀면 시간초과가 날까봐 다른 방법을 생각해내려 애썼다. 그런데 전혀 생각이 나지 않았다... 그래서 문제의 카테고리를 펼쳐보니, 이럴 수가 브루트포스 문제였다. 그냥 다 구하면 된다. 알고리즘은 다음과 같다. 칸의 색이 흰색 혹은 검은색으로 두 가지이므로 boolean값을 이용해 색을 구분하였다. 검은색은 true로, 흰색은 false로 하였다. 하나의 8$\times$8 크기 구획 내에서 고쳐야 하는 칸의 최소 개수를 구하는 함수를 정의한다. 그리고, 이 함수를 해당 체스판에서 만들어질 수 있는 모든 8$\times$8 크기 구획에 대하여 수행하면 된다. 그 중 최솟..

풀이방법 사용된 것: Queue 2022.04.21 큐를 이용하여 풀었다. 먼저 큐에 1부터 N까지의 수를 순서대로 넣는다. 가장 앞 사람을 poll()하여 맨 뒤에 add()하는 작업을 K-1번 반복한다. 그럼 제거해야하는 사람이 가장 앞에 오게 된다. 한 명을 poll()하여 정답 배열에 추가한다. 이 과정을 N번 반복하면 된다. 코드 Java(2022.04.21) import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = ne..

풀이방법 사용된 것: 해시맵(HashMap) 이분탐색법 해시맵을 사용하는 방법, 이분탐색법을 이용하는 방법이 있다. 시간은 해시맵이 덜 걸리고 메모리는 이분탐색법이 덜 사용한다. 2022.04.19 먼저 해시맵을 사용하는 방법이다. 의 데이터 쌍을 저장하는 해시맵을 하나 선언한다. Key에는 카드의 번호, Value에는 카드의 개수를 저장할 것이다. 상근이가 가지고 있는 카드들의 번호를 차례차례 읽어오면서 개수를 세어준다. 처음 세는 카드라면 해시맵에 (해당 카드의 번호, 1)의 요소를 새롭게 추가한다. 이미 센 적 있는 카드라면 해시맵에 (해당 카드의 번호, 현재까지 센 개수에 1을 더한 값)의 요소를 추가한다. 해시맵은 키가 동일한 다수의 요소를 저장하지 않으므로 자동으로 이전의 요소는 지워진다. 이..

풀이방법 사용된 것: 수학 2022.04.19 이항계수의 수학적 정의대로 계산해주면 된다. 코드 Java(2022.04.19) import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); int a = sc.nextInt(); int b = sc.nextInt(); int ans = 1; for(int i = 0; i

풀이방법 사용된 것: Deque 2022.04.17 주어진 수를 한 글자씩 덱에 넣는다. boolean타입 변수 v를 선언하고 true로 초기화한다. 덱의 양쪽 끝에서 글자를 하나씩 poll() 해와서 두 글자를 비교하는 과정을 덱이 텅 비거나 덱에 글자가 하나 남을 때까지 반복한다. 꺼내온 두 글자가 동일하면 continue한다. 한 번이라도 두 글자가 서로 다르면 v의 값을 false로 바꾸고 즉시 반복문을 끝낸다(break). 두 글자가 다른 적이 한 번도 없다면 v의 값이 바뀌지 않는다. 따라서 v가 true로 남은 채 반복문이 끝난다. 따라서 주어진 수가 팰린드롬수라면 v는 true로 남고, 그렇지 않으면 v는 false가 된다. 코드 Java(2022.04.17) import java.io.B..

풀이방법 사용된 것: TreeSet 브루트포스 알고리즘 2022.04.17 가능한 모든 수 3개의 쌍(순서 관계 없이)을 모두 만든 다음, 그 중 합이 m보다 작거나 같은 것들을 모두 TreeSet에 넣는다. TreeSet은 자동으로 숫자를 오름차순으로 정리하므로, TreeSet의 가장 뒤에 있는 수를 화면에 출력하면 된다. 모든 쌍을 점검해야 하므로 브루트포스 알고리즘 문제이다. 코드 Java(2022.04.17) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; import java.util.TreeSet; public cla..

풀이방법 사용된 것: Deque 2022.04.17 덱을 사용하면 쉽게 풀리는 문제이다. 덱에 1부터 N까지를 순서대로 넣은 다음, removeFirst() 한 번, removeFirst()를 해서 그 값을 temp에 저장하기, temp를 addLast()하기를 N-1번 반복하면 된다. 그 후 남아있는 하나의 값을 화면에 출력한다. 스택이나 큐로도 풀 수 있지만 그렇게 하면 다른 쪽 끝을 조작하는 함수를 따로 만들어주어야 하므로 편하게 덱을 사용하였다. 코드 Java(2022.04.17) import java.util.Deque; import java.util.LinkedList; import java.util.Scanner; public class Main { public static void main..

풀이방법 사용된 것: 수학 에라토스테네스의 체 2022.04.17 에라토스테네스의 체의 방식으로 1부터 1000까지의 모든 소수를 구해둔 다음, 구해둔 소수 목록을 이용하여 입력으로 주어지는 수들이 소수인지를 판별하면 된다. 코드 Java(2022.04.17) 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{ // TODO Auto-generate..

풀이방법 사용된 것: 수학 2022.04.17 간단한 수학 문제이다. 최대공약수를 구하는 방법은 다음과 같다. 주어진 두 수 중 작은 쪽의 약수를 모두 구하여, 가장 작은 약수부터 큰 약수까지의 순으로 스택에 넣는다. 스택의 top부터 하나씩 꺼내면서, 즉 가장 큰 약수부터 작은 약수까지의 순서로 꺼내면서 해당 수가 주어진 두 수 중 큰 쪽의 약수인지 확인한다. 주어진 두 수 중 큰 쪽의 약수인 수가 발견되면 즉시 그 수를 최대공약수로 취하고 반복문을 종료한다. 최소공배수를 구하는 방법은 다음과 같다. 주어진 두 수 중 작은 쪽에 2, 3, 4, ... 갈수록 1씩 큰 자연수를 곱해가면서 곱의 결과값이 주어진 두 수 중 큰 쪽의 배수인지 확인한다. 주어진 두 수 중 큰 쪽의 배수인 수가 발견되면 즉시 그..

풀이방법 사용된 것: 그리디 알고리즘 브루트포스 알고리즘 2022.04.16 각 라운드별 친구들이 낸 가위의 수, 바위의 수, 보의 수를 세놓으면 그 다음부터는 쉽다. 알고리즘은 간단하지만 코드로 구현하기가 조금 귀찮은 문제였다. 푼 방법은 다음과 같다. 백준의 세 번째 예제를 보면, 4 SPRS 4 RPRP SRRR SSPR PSPS 1라운드에서 가위를 낸 친구는 2명, 바위를 낸 친구는 1명, 보를 낸 친구는 1명이다. 2라운드에서 가위를 낸 친구는 2명, 바위를 낸 친구는 1명, 보를 낸 친구는 1명이다. 3라운드에서 가위를 낸 친구는 0명, 바위를 낸 친구는 2명, 보를 낸 친구는 2명이다. 4라운드에서 가위를 낸 친구는 1명, 바위를 낸 친구는 2명, 보를 낸 친구는 1명이다. 이렇게 개수를 싹..