mondegreen

[Part1-Chapter07-Clip09] - 백준 6236 용돈관리 항상 고민하는 부분인데 코드를 간결하게 작성하는 것이 필요하지만 또 한 편으로는 협업을 고려해 구체적으로 작성하다보면 내 코드는 줄줄이 길어지는 경우가 많더라. 아직은 후자를 기준으로 두고 작성하지만 이러다 불필요한 자료구조나 변수 선언으로 메모리 효율이 낮아질 것 같아 고민이다. 아래 코드는 기존의 이분 탐색과 크게 다르지 않다. 다만 금액이 이번에 지출해야 하는 금액보다 적게 남았을 때는 해당 금액을 반환하고 다시 인출한다는데 총 인출할 수 있는 금액이라는 게 정해져 있지 않기 때문에 로직적으로만 생각하면 결국 그냥 잔돈이 기본 인출금액으로 리셋되면 된다. 반대로 금액이 이번에 지출해야 하는 금액보다 많이 남았을 때가 고민되는 지..

[Part1-Chapter07-Clip07] - 백준 2805 나무 자르기 풀고 나니 간단해 보이는데 분기를 짜는데 조금 시간이 걸렸다. 일단 좀 특이한 점은 자르고자 하는 높이를 설정하고 나무가 잘라진 길이를 구할 때 나무를 일단 정렬하고 잘리는 나무들의 시작 인덱스를 이분탐색으로 구했다는 점이다. 기본적으로 자를 높이는 가져가고자 하는 나무 길이의 최솟값이 1이므로 가장 큰 나무의 길이보다 -1한 값을 r로 설정하고 모두 베어버리는 경우가 가장 긴 나무 길이를 가져 가는 것이므로 l 는 0으로 설정했다. 이분 탐색을 통해 가져가고자 하는 길이와 같은 경우, 짧은 경우, 긴 경우를 분기하여 로직을 구현했다. import java.io.*; import java.util.*; public class Ma..

[Part1-Chapter07-Clip06] 매개변수 탐색은 이분 탐색을 이용해 최적값을 탐색하는 기법이다. 연속적인거나 이산적인 값의 집합에서 최적값을 X를 찾고자 할 때 X를 경계로 조건을 만족하는 집합과 답이 될 수 없는 집합을 판정할 수 있을 때 추정 값 A에 대한 판정을 반복해 X를 찾는 방법이다. 이때 판정의 대상이 되는 추정값을 구할 때 이분 탐색을 이용하면 O(logX)의 복잡도의 로직을 짤 수 있다. 보통 ~ 조건을 만족하는 최솟값과 최댓값을 구하라는 문제가 해당된다. 이전에 lowerBound와 upperBound를 찾았던 백준 10816 숫자 카드 2 문제에서 적용했던 것도 이 매개변수 탐색의 일종이라 할 수 있다. - 백준 2417 정수 제곱근 long의 범위에 있는 숫자를 찾으려면..

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

[Part1-Chapter07-Clip04] - 백준 2470 두 용액 문제에서 주의해야 할 점은 '모든 용액의 특성값은 다르다, 산성 두 개 또는 알칼리성 두 개의 용액으로도 가장 0에 가까운 혼합 용액을 만들 수 있다' 라는 부분이다. 이 두 부분에서 정렬 처리와 음수와 양수를 구분하지 말기를 생각할 수 있었다. 이분 탐색으로 처리하다가 코드 상으로는 문제가 없어보였는데 5%에서 오류가 나서 투포인터 방식으로 다르게 구현했다. 두 값을 더한 값의 절댓값이 이전의 최솟값보다 작다면 갱신하여 두 개의 특성값을 저장했고 여기서 l과 r를 변경시키는 로직을 생각해내기가 어려웠는데 두 값을 더한 값이 0보다 작으면 더 작은 값을 키우고 0보다 크면 더 큰 값을 줄이도록 구현했다. import java.io.B..

[Part1-Chapter07-Clip03] - 백준 2295 세 수의 합 문제를 읽고 제일 먼저 두 수를 고정하고 집합의 원소인 set[k] 에서 나머지 한 수를 이분탐색하는 방식을 고민했다. 하지만 코드를 작성하다 먼길을 가버렸고 한참을 단순히 l과 r의 범위나 m을 추출하는 방식을 고치면 탐색의 범위를 조정할 수 있지 않을까라는 바보 같은 생각을 했다. 코드를 작성하면서 l과 r을 다시 의사코드로 작성해보니 l과 r이 아니라 첫수와 두수를 투 포인터 방식으로 고정하고 나머지 한개의 수를 다시 배열에서 이분탐색했어야 했는데 라는 깨달음과 다시 코드를 의도에 맞게 작성했다. 그런데 테스트 케이스도 모두 맞추는데 이상하게 3%에서 틀리는 것이다.... 결국 다른 코드를 참고해보니 결국 내가 작성한 것은 ..

import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); String[] pool = new String[n]; for (int i = 0; i < n; i++) { pool[i] = sc.next(); } // 이분 탐색은 정렬된 배열에서 진행 가능함 Arrays.sort(pool); int cnt = 0; for (int i = 0; i < m; i++) { String thisStr = sc.next(); int l..

[Part1-Chapter05-Clip04] - 백준 17232 생명게임 이전에 푼 구간합 구하기 5의 풀이 과정을 담으면 되는 문제였다. 동일한 문제였지만 *라는 문자로 변경되었다고 누적합을 생각해내지 못해서 강의를 보고 나서야 반영할 수 있었다.. 누적합 배열을 별도로 만들지 않으면 원래 배열에서 변화를 주게되고 그럼 다음 원소를 탐색할 때 변경된 값을 참조하는 큰 문제가 있다. 또한 반복문을 순회하면서 변경사항을 반영하다보면 시간 복잡도가 커지기 때문에 변경되는 부분을 누적합을 먼저 구해주고 한번에 반영하는 것이 시간 초과하지 않는 방법이다. import java.io.*; import java.util.StringTokenizer; public class Main { public static vo..

- 백준 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를 갖게 되어 순서가 중복되는 문제가 발생했었다. 이 코드가 최적인 것 ..