- 첫 풀이 및 정답풀이 재귀를 통해 간단하게 풀 수 있는 대표적인 문제인 피보나치 수를 구하는 문제이다. 단, 문제에서 피보나치 수를 1234567로 나눈 나머지를 원하며, n의 범위가 100000 이하 이므로 dp를 활용해 풀어야 한다. dp를 활용해 중복되는 계산과정을 반복하지 않고, 한 번만 계산을 수행해 해당 값을 저장해 둔 뒤 참조만 하는 형식으로 진행하면 된다. 과정은 아래와 같다. 1. 피보나치 수 0은 0, 1은 1이므로 재귀메소드로 들어온 값이 0이면 0, 1이면 1을 반환한다. 2. 2 부터는 초기의 dp 배열에 값이 존재하지 않으므로 dp [2] = ( fibonacci(n-1) + fibonacci(n-2) ) % 1234567;을 수행한다. 3. 3은 fibonacci(2)+fi..

- 첫 풀이 및 정답풀이 이 문제에서 우선 잘못 출력된듯한 부분이 있는데, 문제 설명 부분의 예시에서 "A에서 첫번째 숫자인 1, B에서 두 번째 숫자인 5를 뽑아 곱하여 더합니다." 라고 나와있지만, 입출력 예를 보면 알 수 있듯이 B에서 5의 위치는 첫 번째이기 때문에 이를 혼동하면 안 된다. 처음 문제를 읽고 이해한 것은 예를 들어 A에서 0번째 인덱스를 선택했다면, B에서 0번째 인덱스를 선택하면 안 된다고 이해했지만, 예시를 설명하는 부분을 보면 A와 B 배열 모두 첫 번째 숫자를 선택했기 때문에 잘못 이해했다는 것을 깨달았다. 다시 잘 생각해보니, 한 번 선택한 숫자는 다시 사용할 수 없다는 소리였다. 문제에 대한 이해를 마치고, 어떻게 풀어볼까 고민하던 중 DFS를 활용해 완전 탐색을 수행하..

- 첫 풀이 및 정답풀이 레벨 2의 문제라고 생각되지 않는 간단한 문제였다. 문자열로 주어지는 정수의 나열들 중 최댓값과 최솟값을 찾아 반환하면 되는 문제로, 정렬 후 0번 인덱스와 마지막 인덱스를 반환하면 되는 문제이다. 단, 문제는 정렬하는 방식에 있어서의 선택일 것이다. 필자는 Comparator인터페이스를 애용하므로 이를 활용해 정렬하였다. 처음에는 Comparator 인터페이스를 오버 라이딩하여, 문자열을 비교하는 메소드인 compareTo를 사용하는 방식을 시도했었는데, 음수의 경우 -와정 수로 구분되기 때문에 한 문자열에 양의 정수와 음의 정수가 함께 있는 문자열로 인해 실패하는 테스트 케이스가 존재했다. 따라서 그냥 비교하는 문자열들을 정수로 변환하여 Integer.compare() 메소드..

- 첫 풀이 및 정답풀이 이 문제의 핵심은 연속된 자연수들로 n이라는 특정 수를 만들 수 있는 경우의 수를 찾는 것이다. dp로 푸는 방법이 있을까 하고 규칙성을 찾아보았지만, 찾지 못했고 단순한 완전 탐색 문제라고 생각되어 반복문을 이용해 간단하게 해결할 수 있었다. class Solution { public int solution(int n) { int answer = 0; int temp; // 1. 1부터 n까지 반복, 각 경우의 시작 숫자. for(int i = 1;i

- 첫 풀이 및 정답풀이 이 문제는 처음 읽자마자 dp를 활용해야 하는 문제인 것을 알 수 있었다. 한 줄의 선택 횟수는 1번이고, 다음 줄에선 이전 줄에서 선택한 열의 숫자는 선택하지 못한다는 제약사항이 존재한다. 이러한 규칙 속에서 dp를 위한 점화식을 세워보면, x번째 행에서 0번째 열은 이전 행의 값들 중 가장 큰 값을 선택하고 와야 한다. 그렇기에 dp [x][0] = max(dp [i-1][1], dp [i-1][2], dp [i-1][3]) + land [x][0]와 같은 식이다. 이 과정을 n번째 행까지 수행하면, 각각의 경우의 수들 중 최댓값들이 저장되어 있으며 그 중에서도 가장 큰 값이 문제가 원하는 답이다. class Solution { int solution(int[][] land)..

- 첫 풀이 및 정답풀이 이 문제를 읽은 후, 바로 Integer.toBinaryString() 메서드를 활용해야겠다는 생각이 들었고 바로 정답 처리를 받을 수 있었다. 로직은 간단하다. 1. 입력된 n을 2진수로 변환한다. 2. 변환된 2진수의 비트가 1인 개수를 카운팅한다. 3. n+1부터 위 과정을 반복해 앞서 구한 개수와 일치하는 수를 찾는다. class Solution { public int solution(int n) { int answer = 0; // 1. n을 2진수 변환. String str = Integer.toBinaryString(n); // 2. n의 1인 비트의 수를 저장하는 변수. int cnt =0; // 3. 1인 비트의 수를 카운팅. for(int i = 0;i

- 첫 풀이 및 정답풀이 이 문제를 읽고 처음에는 정렬을 통해 각각의 괄호 개수를 카운팅 하는 방식으로 풀어보고자 했지만, 다시 생각해보니 주어진 문자열의 괄호들의 순서가 변하면 안된다는 사실을 알 수 있었다. 따라서 문자열 s를 탐색하면서 풀어나가야 되겠다고 생각했다. 우선 첫 번째로 배제한 경우는 문자열 s의 첫 문자가 ) 닫힌 괄호가 먼저 나오는 경우였다. 이렇게 처리하면 다음으로 고려해야 하는 것은 ( 열린 괄호부터 시작하는 경우뿐이다. 본인은 열린괄호의 개수를 통해 풀어보고자 했다. 1. 열린 괄호가 나오면 open이라는 변수를 증가시킨다. 2. 닫힌 괄호가 나오면 open을 감소시킨다. 3. 단, 열린 괄호가 1개 나온 상태에서 닫힌 괄호가 2번 나오는 경우를 배제하기 위해 닫힌 괄호를 만나면..

- 첫 풀이 이 문제를 처음 풀 때는 board를 탐색하면서 1을 만나면 1부터 board의 길이만큼 증가시키며 정사각형을 만족하는지 판단하는 방식으로 진행하였는데, 몇몇 테스트 케이스는 통과하지만 이 경우는 모든 1에 대해서 수행하기 때문에 효율성 측면에서도 시간 초과가 발생한다. DFS나 BFS를 이용해 풀어볼까 했지만 불가능할 것 같아 다른 방법이 있나 찾아보게 되었다. - 정답풀이 결국 이 문제는 DP를 활용해야 한다. 자세한 설명은 다른 블로그를 참고하면 쉽게 알 수 있다. class Solution { public int solution(int [][]board) { // 1. DP 배열. int dp[][] = new int[board.length][board[0].length]; int a..

- 첫 풀이 및 정답풀이 DFS, BFS를 이용한 완전 탐색 문제를 풀 때는 항상 무엇을 탐색의 대상으로 삼아야 하는지에 대한 기준을 내리지 못해 삽질을 많이 하는 것 같다. 문제에 대한 이해는 간단했다. 완전탐색을 이용해 모든 경우의 수를 고려하면 된다. 예를 들어, 예제의 경우 1이 5가지가 있다. 이것을 이용해 만들 수 있는 경우의 수는 +1+1+1+1+1 / +1+1+1+1-1 / +1+1+1-1+1/ +1+1+1-1-1........ 등과 같이 다양하게 존재한다. 모든 숫자에 대한 탐색이 끝났을 때, 해당 식의 값이 target값과 동일하다면 카운팅 해주면 된다. 본인은 위의 내용을 모두 생각한 뒤 반복문을 이용해 짜보려고 하였지만 결국 삽질이었다. 결국 적절한 변수 하나만을 이용하면 간단하게 ..

- 첫 풀이 이 문제를 읽고 처음 발견해낸 사실은 노란색 격자가 들어가기 위해선 무조건 세로의 길이가 3 이상이어야 한다는 것이다. 가로의 길이에 상관없이, 갈색 테두리인 두 개의 라인을 제거했을 때 노란색 격자가 존재하기 위해서는 3 이상이어야 했다. 두 번째 알게 된 것은 갈색 격자 + 노란 격자 = 총 격자의 수이므로 총 격자의 수만큼 카펫을 만들 수 있는 경우는 총격자의 수의 약수들로 구할 수 있다는 사실이다. 입력 예제 3의 경우 갈색 격자 24개, 노란 격자 24개이므로 총격자의 수는 48이 되며, 만들 수 있는 경우의 수는 {1, 2, 3, 4, 6, 8, 12, 16, 24, 48}로 세로 1, 가로 48 /세로 2, 가로 24/ 세로 3 가로 16.....으로 총 5가지의 경우의 수가 발..