전체 글

[백준] 15663번 - N과 M (9) (!) (JAVA) [접근 방법] 중복되는 수열을 여러번 출력해서는 안되고, 수열을 사전순으로 증가하는 순서로 출력해야 한다. 이전 문제와 다른 점은 "둘째 줄에 주어지는 N개의 수" 가 "중복 가능" 하다는 것 이다. 예제 2의 N개의 수를 입력받은 배열인 num = {1, 7, 9 ,9}로 정렬 시킬 수 있다. 기존 방식대로 출력한다면, 1 7 1 9 1 9 7 1 7 9 7 9 9 1 9 7 9 9 9 1 9 7 9 9 로 출력된다. 9가 2개 입력되면서, 출력되는 수열에서 중복이 생기게 되었다. 따라서 같은 값을 추가하여도 (중복된 데이터를 넣어도) 무시하는 Set 을 사용하여야 한다. LinkedHashSet을 사용하여 문제를 해결하였다. [JAVA 코드..

[백준] 15649번 - N과 M (1) (!) (JAVA) [접근 방법] 참 간단해 보이는 문제인데, 손도 못대겠어서 상당히 당황하였다. DFS를 그래프 탐색 알고리즘으로만 알고 있어서, 이러한 문제에도 활용할 수 있는지 몰랐다. DFS를 이용한 다른 사람의 풀이를 참고하였다. 먼저, DFS에 필요한 변수들이 있다. 방문 여부를 판단할 boolean "visit 배열", M개의 숫자의 수열을 저장할 int "arr 배열", 문제에서 입력으로 주어지는 N, M 과 그래프의 깊이를 나타내는 depth 변수이다. static int[] arr; // M개의 숫자로 이루어진 수열 저장 static boolean[] visit; // 방문여부를 기록. static StringBuilder sb; // 출력을 위..

[백준] 14500번 - 테크로미노 (!) (JAVA) [접근 방법] 브루트포스 파트이기에 모든 경우의 수를 탐색해야 한다는 것은 알고있었다. 어떻게 탐색 할 것인가? 가 가장 어려웠다. 첫번째로 고려한 방법은 모든 경우를 일일이 생각하여 구현하는 방법이다. (i , j)를 시작으로 하는 모든 경우의 수를 전부 고려한 후, 그중 최댓값을 구해서 N X M 보드의 모든 칸의 최대값을 비교하여 갱신할 계획이였다. worst case = 500 * 500 * 13 = 3,250,000 으로 시간도 적합했다. 그러나 너무나 까다롭고 귀찮은 구현에 포기하였다. 두번째 고려한 방법은 다른 사람들의 풀이 방법을 보고 풀었다. 위 4가지 도형은 상하좌우 완전 탐색으로 구현하고, 이 모형만 따로 구현하는 방법이다. 탐색..

[백준] 6064번 - 카잉 달력 (!) (JAVA) [접근 방법] 브루트포스 알고리즘 파트이기에, 1년 부터 M, N의 최소 공배수 까지 모두 탐색하고자 하는 것을 생각하였지만, 이는 시간 제한에 막히게 되었다. 실행 시간 1초 = 약 2000만번 연산 (1 ≤ M, N ≤ 40,000, 1 ≤ x ≤ M, 1 ≤ y ≤ N) worst case : M = 39983, N = 40_000 을 모두 탐색하는 경우 (39983은 소수) 39983 * 40000 = 약 16억 (X) 따라서 다른 방법을 찾아야 한다. 구하고자 하는 x을 고정 시키고 i를 +M 만큼 증가 시키며, y를 탐색하는 방법을 채택하게 되었다. 나머지 연산을 이용할 것인데, 이때 0이 나오는 것을 방지하기 위해 , x = x-1, y ..

[백준] 1748번 - 수 이어 쓰기 1 (!) (JAVA) [접근 방법] - 문제를 이해하자. 첫번째로 읽었을 때, 문제가 잘 이해 되지 않았다. N = 5 인 경우를 예로 들었을 경우, 123454321... 과 같이 이전 자리수와 연결되어 있기만 한 수도 가능한 것 인가? 라고 생각했다. 그러나 N = 15를 예로 든다면, 1/2/3/4/5/6/7/8/9/10/11/12/13/14/15 (/는 이해를 위해..) 와 같이 1 ~ N 까지 수를 그대로 뒤에 이어 붙인 것이다. - 어떻게 풀지 생각해보자. N = 120인 경우, 1 ~ 9 까지는 +1을, (한자리수) 10 ~ 99 까지는 +2를, (두자리수) 100 ~ 120 까지는 +3을 하면 된다. (세자리수) 이렇게 구현하기 위해서는 1 ~ 100..

[백준] 1107번 - 리모컨 (!) (JAVA) [접근 방법] 어떻게 접근해야 할까? 에 대한 대답은 쉽게 찾아 내었다. 부서진 번호가 포함되지 않은, N을 기준으로 가장 가까운 번호를 찾아내는 것이 관건 이었다. 브루트포스 알고리즘을 사용하여, 가능한 모든 채널 번호 부터 N까지 최소 누르는 수를 구하였다. 이동하려고 하는 채널인 N은 0 ~ 500_000 이지만, 9를 제외한 모든 버튼이 망가지는 경우, 999_999로 이동한 후, + / - 버튼을 눌러야 하므로, 0 ~ 999_999 까지의 수를 모두 고려하였다. [JAVA 코드] // 1476번 - 날짜 계산 import java.util.*; import java.io.*; public class Main { public static void..