알고리즘 검색 결과

해당 글 51건
백준 balanced cow subsets : 반으로 잘 쪼개 봅시다.

안녕하세요. 오늘은 USACO에 나왔던 Balanced Cow Subsets 문제를 풀어보도록 하겠습니다. 문제는 간단해요. 문제를 해석하는 연습을 하셨다면, 이 정도는 밑줄을 치셨으리라 생각이 듭니다. 왜 n이 20 이하일까요? 그냥 브루트 포스 해도 되는 거 아닐까요? 라는 생각을 하실 수도 있을 듯 싶어요. 그런데, 이 문제는 무려 옛날 USACO gold에 나온 문제입니다. 단순히 브루트 포스 해도 되었다면, Bronze에나 냈을 거에요. 그런데 Gold도 가끔 브루트 포스 하면 풀리는 게 있으니, 그렇게 해도 되지 않을까요? 그러면 어떻게 브루트 포스를 할 건가요? n = 20이라면 많아봤자, 2^20개의 상태가 있으니까, 이들에 대해서 일일히 check를 해 보는 방법이 있습니다. 그렇게 오래..
자료알고/알고리즘 2020. 2. 10. 01:33
부분 문제 그리고 메모이제이션 : 다이나믹 프로그래밍 할 때 많이 나오는 데 무엇일까요?

간혹 가다가, 이런 이야기를 들으실 수 있을 거에요. 사실, 이 용어는 다이나믹 프로그래밍 뿐만이 아니라, 다른 기법에서도 종종 나오니, 고수 분들의 설명을 들으시려면, 정확한 정의는 모르셔도 됩니다. 그냥 아. 이런 거구나. 이해만 하셔도 무난합니다. 솔직하게 말해서, 시험에 나올 일도 거의 없을 겁니다. 간단한 예제를 들기 위해서, 16690번 paper Cuts 문제를 보도록 합시다. 문제를 요약하면 아래와 같습니다. str이 "abbaaddccee"이고 pat이 aaabbeeddcc입니다. 저는 str에서 칸막이 몇 개를 사용해서 잘게 쪼개려고 합니다. 위 그림에서는 "abb", "aa", "ddcc", "ee" 이렇게 쪼개졌습니다. 칸막이 u개를 써서 잘 쪼갠 문자열들을, 어떻게 잘 배치해서 p..
자료알고/알고리즘 2020. 2. 7. 22:02
코딩테스트에 나올 만한 백트래킹 쉽게 정복해 봅시다.

구현, 백트래킹은 코딩 테스트에서 많이 나오는 단골 주제 중 하나입니다. 물론 tree dp나, segment tree하고 조합론을 아름답게 섞어놓은 dp도 나오기는 하지만. 중요도가 상대적으로 높지 않습니다. 그 말인 즉슨, 포기할 건 포기하더라도, 다른 사람들이 다 풀 수 있는 기본부터 챙겨 가자는 의미입니다. 그 기본 중 하나는 백트래킹입니다. 새로 추가된 문제인 18290번과 18292번 문제 NM과 K 시리즈를 보겠습니다. 개인적으로 적당히 난이도가 있으니, 입문 문제로는 좋은 듯 싶습니다. 문제는 아래와 같습니다. 조건을 잘 읽어보시고, 어떻게 풀어야 할 지 잘 생각해 보세요. 18292는 K 조건이 다른데요. K가 구간 [1, min(50,NM)]에 속하는 정수이다. 라는 것만 다릅니다. 그..
구현 2020. 1. 28. 17:03
프로그래머스 가장 큰 수 : 수 2개만 고려해 봅시다.

오랫만입니다. 정렬에 대해서 배웠으니, 오늘은 프로그래머스에 있는 가장 큰 수를 풀어보도록 하겠습니다. 쉽지 않아 보입니다. 옛날 (브, 실, 골 티어로 이루어진) USACO 실버나, 아니면 COCI 2번이나 3번 정도에 나왔던 문제로 기억합니다. 일단, 문제가 무엇을 요구하는지는 알았습니다. 조건을 해석해 봅시다. n의 최댓값이 10만이니, O(nlogn)이나, O(n) 정도의 복잡도를 생각할 수 있습니다. 물론, O(n^2)에서 상수 최적화를 잘 해서 통과할 수도 있겠지만, 상수 최적화 같은 경우에는, ps를 조금 깊숙히 하셔야 하는 부분입니다. 코딩 테스트에서 안 풀리는 복잡도가 정해인데 상수로 잘 뚫어야 하는 문제가 나왔다. 그러면 거르면 됩니다. 일단, 구하고자 하는 것은, 어떻게 배열을 적절히..
자료알고/알고리즘 2020. 1. 24. 02:58
meet in the middle 알고리즘 : 절반씩 쪼개서 생각해 봅시다.

제가 제대로 된 코딩을 한 지 별로 안 되서 그런지, 백준 1442번 같은 문제를 만나면 당황스럽더라고요. 문제는 다음과 같습니다. 부끄럽게도, 어떻게 Dynamic programing을 해서 트래킹을 해야 할 지 감이 오지 않았습니다. 그러면 어떻게 해야 할까요? 손을 놓고 가만히 있어야 할까요? 아닙니다. 정확하게 문제를 앞쪽, 뒤쪽으로 나누었을 때, 적절한 전처리를 해서, 앞쪽만 보고 접근할 수 있다면, 양방향 탐색과 유사한, 중간에서 만나는 meet in the middle 이라는 기법을 고려해 볼 만 합니다. 코딩 테스트에서 제일 중요한 것은 문제를 어떻게 읽느냐였다고 했습니다. 앞에 15개, 뒤에 16개로 왜 나눌까요? 일단, 그 전에 R - L이 20만 이하인 경우부터 해결해 봅시다. 먼저,..
자료알고/알고리즘 2020. 1. 20. 16:01