자료알고/알고리즘 검색 결과

해당 글 87건
좌표 압축 알고리즘 : 범위가 클 때 어떻게 공간을 줄일까요?

ps를 하시다 보면, 좌표 압축이라는 이야기를 심심치 않게 들으실 수 있습니다. 간단하게 말해서, 데이터를 정렬해서, 다시 순서를 부여하는 것을 말합니다. 특히 쿼리 문제에서 많이 보이는데요. 구간이 10^10개, 10^18개가 있는데, 쿼리가 단지 10만개라면, 10^18개를 다 들고 있지 않고, 중요한 구간이나 숫자만 들고 있는 기법입니다. 그러면 압축이 될 거에요. 이런 문제를 생각해 봅시다. 자. 여기서, Lv랑 Rv, 그리고 k는 [0, 10^10]에 속하는 정수라고 해 봅시다. 그리고 n과 Q가, 구간 [1, 10^5]에 속하는 정수라고 해 봅시다. 그러면, k와 Lv, Rv가 [0, 10^10] 범위에 속하는데, 어떻게 하면 좋을까요? 오프라인 처리가 가능하다면, 그냥 k값하고, Lv, Rv..
자료알고/알고리즘 2020. 2. 22. 03:40
백준 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
트리에서 최단 경로를 구하기 위한 또 다른 방법?

간선의 가중치가 모두 같고, 최단 거리를 구하라 그러면 BFS를 써야 한다. 고 생각하시는 경우가 많습니다. 네. 대부분의 경우에는 맞습니다. 그런데 몇 문제는, 특수한 조건을 줍니다. 이 때에는, BFS를 쓰는 게 답이 아닐 수도 있습니다. 백준 10838번 문제를 봅시다. 일단 솔브드 티어로 골드3. 상당히 만만해 보입니다. 보통 이 경우에는 BFS, DFS 응용 문제들도 많이 분포해 있기 때문에, 최단거리가 나왔다. 그러면 다익스트라나, BFS로 섣불리 판단하기 쉽습니다. 문제는 굉장히 길기 때문에, 따로 설명을 드리지는 않겠습니다. 잘 읽어보셨다면 중요한 조건이 몇 가지 있다는 것을 알 수 있는데요. 트리의 노드 갯수는 10^5개 이하입니다. 여기서 왜 제가 4개의 조건에 밑줄을 쳤을까요? 4개 ..
자료알고/알고리즘 2020. 2. 2. 15:07
코테에서 답을 미리 저장하는 방법도 쓸만한가요? 네

메일로 질문이 왔습니다. 코딩 테스트를 준비할 때, 하드 코딩을 하는 것은 별로 안 좋나요? 사실, 그에 대한 답은 제가 쉽게 답할 수 없었습니다. 하드 코딩을 하거나, 답을 미리 저장을 해 놓는 방법으로, 백준 내에 있는 문제를 푼 것이 10개에서 15개 내외밖에 되지 않기 때문입니다. 중요도가 떨어져 보일 수 있어요. 이 기법을 쓰는 이유는 단 하나입니다. 정말 안 풀릴 때 최후의 수단으로 써 보라고. 제가 이 기법을 쓰지 않았다면, 10개에서 15개 정도 되는 문제를 풀지 못했을 겁니다. 오늘은 '답을 미리 저장해 놓는 기법' 을 구현 문제에 어떻게 쓰일 수 있는지 보도록 하겠습니다. 백준 17825번 문제인 주사위 윷놀이를 보도록 하겠습니다. 문제가 상당히 길기 때문에, 제가 링크를 걸어 놓겠습니..
자료알고/알고리즘 2020. 1. 29. 19:33