mondegreen

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

[Part1-Chapter06-Clip01] 구간 합 계산 시 누적합 배열을 활용한다면 해당 인덱스로 접근하여 한 번에 연산이 가능하기 때문에 시간 복잡도가 현저히 낮아진다. 해당 특정 배열의 원소가 갱신된다면 해당 원소의 인덱스부터 그 이후 모든 누적합 원소에 수정이 필요하기 때문에 배열의 길이인 N만큼 순회해야 하므로 시간 복잡도는 O(N) 이다. 만약 갱신하는 것을 반영해 구간합을 구한다면 누적합 배열을 사용한다 하더라도 시간 복잡도가 크게 낮아지지 않는다는 것을 알 수 있다. - 백준 11659 구간 합 구하기 4 한 달 전에도 풀었던 문제인데 시간 초과 때문에 Scanner 대신에 BufferedReader와 StringTokenizer를 사용했고 String 대신 StringBuilder를 사..

[Part1-Chapter05-Clip08] - 백준 1931 회의실 배정 10개월과 1개월 전에 풀었던 문제이고 오늘 다시 풀었다. 사실 이 문제는 끝나는 시간을 기준으로 오름차순 정렬하고 해당 시각이 같을 경우 시작 시각을 비교해서 오름차순으로 정렬하면 되는 문제이다. 이건 회의가 빨리 끝나는 경우 먼저 배정을 해주는 것이 최대한 많은 "수"의 회의를 진행할 수 있기 때문에 이 부분만 알고 있으면 풀어낼 수 있다. 다만 여기서 회의실 미 사용 시간을 최소화하는 경우를 찾으라고 했다면 이 문제 풀이만으로는 부족했을 것이고 여차하면 이렇게 이해를 할 수도 있는 문제였다. 먼저 2차원 배열로 시작시간과 끝나는 시간을 담고 해당 배열을 Sort할 때 Comprator를 이용해 정렬 로직을 구현해주었다. 이후..

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

[Part1-Chapter05-Clip07] - 백준 2910 빈도 정렬 자료구조로 고민이 많았던 문제이다. 일단 시간제한이 1초로 정해져있었고 최대 들어올 수 있는 숫자가 십억이었기 때문에 카운트 배열을 쓸 수는 없다고 생각했다. 이차원 배열 사용하는 것을 고려하려다가 반복문을 여러번 돌면 시간 제한이 걸릴 것 같아 해시맵을 사용하고자 했다. 초반에는 중첩된 해시맵을 사용하려다가 익숙하지 않아 자꾸 꼬이는 바람에 해시맵을 두개로 분리하여 사용했다. 하나는 빈도를 입력하는 해시맵(map)이고 하나는 기존 순서를 입력하는 해시맵(order)이다. 정렬하는 부분에서는 일단 존재하는 키를 집합으로 꺼내서 순서대로 정렬하는 것이었다. 빈도값인 value가 큰 경우 먼저 위치하도록 역순으로 처리했다. 애를 먹었던..

[Part1-Chapter05-Clip06] - 백준 18870 좌표 압축 로직이 머리 속에서 한참 꼬여서 애를 먹었다. 처음에는 카운팅 배열을 쓰고자 했다. 간단하게 풀이가 가능할 것 같았지만 메모리 초과로 사용할 수 없었다. 어쩔 수 없이 다른 자료구조를 고민했다. 이차원 배열을 쓰자니 중복처리하는데 번거로울 것 같았고 해시셋을 쓰자니 순서부여가 어려워 해시맵을 이용해서 처리했다. 이미 키가 존재한다면 넘어가고 순서를 부여하는 인덱스를 별도로 관리했다. import java.util.Arrays; import java.util.HashMap; import java.util.HashSet; import java.util.Scanner; public class Main { public static voi..

[Part1-Chapter05-Clip03] - 백준 10814 나이 순 정렬 나이를 비교하는 것은 간편했으나 관건은 가입한 순서를 반영하는 것이기에 입력하는 순서인 인덱스를 객체의 속성으로 포함해 클래스로 만들었다. 이렇게 구현하니 하나의 객체의 속성들을 비교하기만 하면 되어서 간편하게 정렬을 구현할 수 있었다. package BaekJoon.sort; import java.util.Arrays; import java.util.Comparator; import java.util.Scanner; public class BJ10814 { public static class MemberInfo { int registerOrder; int age; String name; public MemberInfo(int..

[Part1-Chapter05-Clip02] - 백준 1181 단어정렬 1년 전과 비교해서 나는 어떤 일이 있었던 걸까... 아무리 생각해도 set밖에 생각이 나질 않아 이를 활용해서 아래와 같이 풀었다. 그리고 compareTo가 단기 기억으로만 남고 정작 활용할 때는 잘 떠오르지 않아서 주석처럼 정리했다. 앞에 위치시킨다 이런 표현 대신 순서를 변경한다/안한다로 구분해서 정리하니 헷갈리지 않는다. import java.util.Arrays; import java.util.Comparator; import java.util.HashSet; import java.util.Scanner; public class Main { public static void main(String[] args) { Scann..

[Part1-Chapter05-Clip01] 정렬이란, 일반적으로 숫자를 오름차순으로 정렬하거나 문자를 사전 순으로 정렬하는 것을 말한다. 더 나아가 데이터 집합을 적합한 순서로 배치하는 것을 말하는데 이름과 나이의 속성을 가진 객체가 있다면 그 안에서 나이가 어린 사람을 먼저 정렬하고 나이가 같은 경우 이름이 빠른 사람을 먼저 정렬하는 예시를 들 수 있겠다. 다양한 정렬 알고리즘과 그 시간 복잡도는 다음과 같다. 삽입 정렬은 그동안 많이 구현해왔고 퀵 정렬의 경우 분할 정복 재귀를 사용하며 면접에서도 많이 질문하는 알고리즘이기도 하다. 병합 정렬과 힙 정렬 구현도 잘 알아두어야 한다. 그리고 기본적으로 언어에서도 정렬을 위한 라브러리를 제공하는데 Util 패키지에서 제공하는 Arrays.sort(자바의..

[Part1-Chapter04-Clip09] - 백준 2817 ALPS식 투표 우선순위 큐나 set을 써야하나라는 고민이 들었던 문제였다. 아직 강의 순으로는 해당 자료구조를 배우지 않아서 최대한 배열을 사용하려고 했고 하지만 시간 복잡도를 고려했을 때 가장 높은 점수 순으로 칩을 부여하기 위해서는 적어도 리스트에 담아 정렬할 수밖에 없다는 생각이 들었다. 참가자들의 수가 250만이지만 스태프 수는 10명으로 제한되어 있고 나누는 값도 최대 14까지 적은 수가 반복문을 여러번 돌아도 시간 초과는 나지 않을 것 같았다. 또 칩을 부여하는 과정에서는 내림차순으로 정렬된 수를 각 스태프의 기본 점수로 나누었을 때 나머지가 0.0이면 칩을 부여하는 방식으로 처리했었는데 왜인지 찾을 수 없는 경우가 있어 모든 점..