Algorithm10 BOJ 10868 - 최솟값 가장 먼저 떠오른 건 우선순위 큐였지만 당연하게 시간 초과가 났습니다. 사실 제출할 때도 그렇게 큰 기대 없이 냈기 때문에 다른 로직을 생각해야 했고... 그러다가 합병 정렬 진행 과정이 불현듯 스쳐갔습니다. 시간 복잡도를 줄이려면 반드시 트리 구조여야 할 텐데, 합병정렬에서 분할 정복을 통해 모든 엘리먼트를 최소 단위까지 쪼갠 기억이 난 것이죠. 합병 정렬을 그림으로 그리고, 위 과정에서 정렬 대신 최솟값만 취하면 훨씬 빠르지 않을까? 하는 생각이었습니다. 쪼갠 후, 정렬 과정을 생략하고 최소 값만 모아봤습니다. 이렇게 보니 시간 초과를 극복할 수 있다는 예감이 강하게 듭니다. 이제 트리를 만들고, 범위 값을 찾는 과정을 생각해 보겠습니다. 배열이 있고, 트리의 노드는 포함한 범위 정보와 그 범위 안.. 2024. 6. 4. BOJ 3080 - 아름다운 이름 [Java / Python] 상근이가 뭐 하고 살든 알 바 아니지만 이런 이상한 짓은 좀 안 했으면 좋겠다. 사람이름은 타고나길 이쁜 거지 뭘 위치를 정해가며 아름답네 마네 한단 말인가... 여하튼 참여 중인 캠프에서 문제는 던져줬고, 나는 풀어야 하는 입장이었다. 문제만 보면 어떤 규칙인지는 알겠는데, 그냥 사전순 정렬하면 끝나는 거 아닌가 하는 생각이 든다. 필자는 예제 데이터를 보고나서야 문제가 요구하는 조건을 이해할 수 있었다. 예제를 먼저 살펴보자. 예제 1번은 비교적 쉽다. I로 시작하는 문자 하나와 J로 시작하는 문자가 2개 있으므로, J문자들을 정렬하는 2가지 경우에 앞뒤로 IVO를 붙여주는 걸 생각할 수 있다. 그렇게하면 2 * 2로 4가 나온다. 이 추측이 맞는지 아래 예제로 확인해 보자 문자의 한 열씩 비교하.. 2024. 6. 2. BOJ 2568 - 전깃줄 2 이름이 재밌어 보여서 골랐는데, 직전에 풀었던 BOJ 12015 가장 긴 증가하는 부분 수열과 동일한 문제다. A의 번호를 index, B를 value로 생각하면 이 문제와 동일한 방법으로 남겨야 할 줄의 개수를 찾을 수 있다. BOJ 12015 - 가장 긴 증가하는 부분 수열 2단계별 풀어보기 DP단락에 있는 BOJ 11053 - 가장 긴 증가하는 부분 수열과 동일한 문제입니다.다만 입력값의 범위가 크게 늘어난 만큼, 풀이 방법에 개선이 필요합니다. 먼저 입력이 1 인 BOJ 11053의dooduz.tistory.com 그러나 이번에는 길이만 구하는 게 아니라, 몇 번 줄을 잘라냈는지 함께 보여줘야 한다. 기존 방법에선 index에 상관없이 dp[n]의 길이별 최소값을 저장했는데, 이번엔 해당 인덱스에.. 2024. 5. 29. BOJ 12015 - 가장 긴 증가하는 부분 수열 2 단계별 풀어보기 DP단락에 있는 BOJ 11053 - 가장 긴 증가하는 부분 수열과 동일한 문제입니다.다만 입력값의 범위가 크게 늘어난 만큼, 풀이 방법에 개선이 필요합니다. 먼저 입력이 1 인 BOJ 11053의 풀이입니다.public class Main { static int[] dp; static int[] arr; static int N; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); N = Integer.parseInt(br.readLine()); .. 2024. 5. 27. 이전 1 2 다음
