mondegreen

처음 상태에서 모두 동일한 색인지를 확인한 후 그렇지 않다면 1~4사분면으로 시작점을 달리하여 재귀를 진행하도록 구현했다. 해당 범위 내에서 첫 수를 저장하고 달라진다면 다시 길이를 반으로 줄이고 다시 재귀를 돌도록 진행해서 같은 수로 작성된 정사각형인 경우에만 정답 배열에 더해주었다. 처음에는 1~4사분면 순회를 각각 작성했는데 가만히 보니 그냥 재귀의 시작점인 행렬 값을 바꿔주면 되는 것이라서 간단히 작성할 수 있었다. 재귀에 더더더 익숙해지면 좋겠다! import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTok..

N과 M 시리즈N과 M (1)  (각기 다른 수) 1부터 N까지의 수 중 중복 없도록 M개 고른 수열  N과 M (2)  (각기 다른 수) 1부터 N까지의 수 중 중복 없도록 M개 고르는데 각 원소가 오름차순인 수열  N과 M (3)  (각기 다른 수) 1부터 N까지의 수 M개 고른 수열(원소 중복 가능)  N과 M (4)  (각기 다른 수) 1부터 N까지의 수 M개 고르는 데 원소 중복 가능하나 각 원소가 같거나 오름차순인 수열 N과 M (5)  (각기 다른 수) 주어진 수 중 중복 없도록 M개 고른 수열 N과 M (6)  (각기 다른 수) 주어진 수 중 중복 없도록 M개 고르는데 각 원소가 오름차순인 수열 N과 M (7)  (각기 다른 수) 주어진 수 중 M개 고른 수열(원소 중복 가능) N과 M (..

동일한 숫자는 카운트하지 않기 때문에 set을 활용해야겠다고 판단했다. 숫자를 고르는 방법은 특정 인덱스를 기준으로 뒤의 숫자만 고르게 하려고 했었다. 그런데 이렇게 처리하게되면 뽑은 숫자마다 순서를 직접 달리 배치해봐야 하는 번거로움이 발생한다. 따라서 방문 배열을 생성하고 해당 숫자를 뽑았는지를 체크하며 고르고 모든 인덱스를 순회하도록 처리했다. 이렇게 처리하면 모든 숫자를 순회하는 대신 뽑은 숫자 간의 숫자를 바꿔서 배치할 필요가 없다. k개의 카드만 뽑아야 하므로 cnt 변수로 뽑은 숫자를 관리했다. package BaekJoon.backtracking; import java.util.Arrays; import java.util.HashSet; import java.util.Scanner; pub..

구하고자 하는 바를 기준으로 로직을 생각하니 금방 구현할 수 있었다. 여기서 구하고자 하는 건 질투심 즉, 가장 사탕을 많은 아이의 사탕 갯수이다. 사탕 갯수 배열을 두번만 돌아도 백억을 넘기 때문에 시간 초과가 발생할 것이고 이분 탐색을 활용해서 풀이한다. left는 [1, 10^9] 구간 중 1이 가장 적은 사탕의 수가 되고 가장 사탕의 수가 많은 종류를 한 아이가 다 받는 경우 즉, 10^9가 right이다. 이를 테스트케이스에 적용하면 색상별 사탕의 수를 입력 받고 해당 배열을 정렬하면 첫번째 원소에는 최소 질투심이 될 수 있는 수, 마지막 원소에는 최대 질투심이 될 수 있는 수가 담겨있다. 이를 통해 이분 탐색을 진행하고 중간 값인 m 값이 질투심이라고 가정했을 때, 반복문을 돌면서 해당 질투심..

- 백준 2143 두 배열의 합 개인적으로 그간 이분탐색을 작성하며 느꼈던 자괴감을 해소할 수 있었던 문제였다. 처음부터 로직을 먼저 의사코드로 설계한 후에 코드로 작성했다. 부 배열을 만들어내는 과정에서 자꾸만 3중 반복문을 순회하게 되어 분명 시간 초과가 날 것이라고 생각했다. 또한 부배열을 구성하는 원소의 개수를 구분해서 그룹으로 비교하려다 보니 ArrayList[] 라는 자료구조에 담게 되었고 이를 다시 한 배열마다 정렬을 진행했다. 당연히. 시간초과가 날 수밖에 없었다. 한참 돌다가 다른 사람들의 풀이를 보니 해시맵을 이용해 풀던데 도저히 내 코드를 버릴 수가 없었고 코드 최적화를 통해 풀어낼 수 있었다. 수정한 사항은 위에서 말한 두 가지이다. 첫째는 부배열을 추출하는 방식이다. 원소의 개수별..

- 백준 10836 여왕벌 누적합을 공부한 덕분에 풀 수 있었던 문제이다. 시간 제한이 있어서 최적화를 요하는 문제였는데 모든 누적합을 매번 계산하는 것이 아니라 태상이의 어쩌고 저쩌고 처럼 시작점과 끝점에서 계산해주고 복원하는 인덱스 접근으로 시간 복잡도를 낮추어서 처리하는 방식을 적용했다. import java.io.*; import java.util.Arrays; import java.util.StringTokenizer; public class Main { public static int m, n; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStre..

- 백준 24479 알고리즘 수업 - 깊이 우선 탐색 1 엄청난 시간과 메모리이다. DFS 문제를 푼 지 오래되었지만 찾아보지 않고 직접 구현해보고자 했다. 인접배열로 만들 경우 당연 n과 m의 크기 때문에 메모리를 초과할 것 같았고 어차피 배열로 순회하면 시간도 초과해버린다고 생각했다. 정점에 비해 간선이 적을 경우에는 배열보다 인접리스트를 쓰는 것이 유리하다고 기억했고 이를 활용해 구현했다. 순회하는 정점의 순서대로 값을 넣기 위해 order 배열을 생성하고 idx를 dfs 함수를 호출할 때마다 하나씩 증가시켜 값으로 넣도록 처리했다. 처음에는 dfs인자에 담아서 처리하려 했는데 같은 정점에서 뻗어나가는 간선의 경우 동일한 idx를 갖게 되어 순서가 중복되는 문제가 발생했었다. 이 코드가 최적인 것 ..

개인적으로 재귀를 직관적으로 이해하는 게 많이 어려웠다. 그래서 재귀를 다시 익숙하게 만들기 위해서 그나마 정답률이 높은 이 문제를 선택했지만 고민을 해봐도 영 감이 잡히지 않아서 풀이를 참고해서 풀었다. 그나마 할 수 있는 건 풀이를 보고 따라치는 게 아니라 손으로 스택에 함수를 쌓아가며 다시 의사코드를 작성해보고 이를 다시 코드로 옮기면서 로직을 이해하려 노력했다. 여기서도 문제를 작게 나눠서 보는 것이 필요한데 n이 3일 때는 3*3의 배열을 가진 칸에 5번째 칸 즉, (1,1) 칸이 비어있어야 한다. n이 9인 경우에도 9*9의 배열이지만 각각의 3*3의 배열로 이루어져 있어서 5번째 3*3 즉, (3,3) 부터 우하향으로 (5,5)까지의 배열이 비어있어야 한다. 이걸 깨달은 사람은 천재들인가....

0. 문제 1. 내 코드 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 { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int cpNum = Integer.parseInt(br.readLine()); int[][] wP = new int[102][102]; for (int cP = 0; cP < cpNu..

알고리즘이 잘 풀리지 않을 때 1) '변수를 적극 활용하자'는 것과 2) '코드를 따라가며 시뮬레이션을 하자'고 생각한다. 1) 변수활용: 개인적으로는 기존에 입력한 코드에 갇혀서 사고의 틀이 제한되기 때문에 습관적으로 변수 활용을 생각한다. 2) 시뮬레이션: 코드 작성 전에 떠오른 대로 코드가 맞을 것이라고 생각하지만.. 항상 오류가 발생한다. 그 때 내가 작성한 코드의 결함을 발견하기 위해서는 테스트 케이스를 한 개 정하고 코드 수행에 따른 단계적 결과를 확인해본다. 이 두 가지는 너무 당연한 과정이지만 마음만 조급해져서 자꾸 놓치고, 결국에는 한참 뒤에야 다시 밟게되는 과정이었다. 앞으로는 코드 작성 초반부터 습관을 들여야겠다. 0. 문제 1. 내가 작성한 코드 package algorithm.BA..