전체 글 검색 결과

해당 글 904건
백준 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
c++ vector reserve vs resize : 미리 공간을 만들어 놓고 쓰면 안 될까요?

예전에 vector가 인자로 들어왔을 때, 어떻게 해야 되는지를 올렸습니다. 어느 분이 댓글로 피드백을 주셨습니다. 그 내용에 관해서 보강 설명을 하도록 하겠습니다. 사실 동적 배열에서 중요한 것은 딱 3개입니다. capacity, size. 그리고 grow rate. ps를 하시다 보면, vector의 reserve와 resize 함수를 써야 하는 경우가 있습니다. 어떤 경우인지는 밑에서 설명해 드리도록 하겠습니다. 동적 배열의 기본 동작 먼저 설명해 드리겠습니다. 먼저, 4개의 원소를 저장할 수 있는 공간에 3개의 원소가 있다고 해 봅시다. 이 경우에, capacity는 4이고, size는 3입니다. 이걸 그림으로 나타내면 아래와 같습니다. 여기서, push_back(3)이 호출되면 어떤가요? 이 때..
레퍼런스/분석 2020. 2. 5. 05:21
c언어 fopen 함수 : 파일을 연다.

안녕하세요. 포인터에 대해 다 끝났으니, 파일을 가지고 천천히 놀아보도록 하겠습니다. 이 포스팅에서는 파일을 잘 여는 방법만 익히시면 됩니다. file_name과, mode를 넘겨주면, FILE 구조체의 포인터를 리턴합니다. 그러면 파일을 열고, 그것을 스트림과 연관을 시킨다고 링크에서는 설명을 하고 있습니다. 스트림, 버퍼. 벌써부터 어질어질해 집니다. 이에 대한 것들은 후에, 작성하도록 하겠습니다. 리턴을 하는 게 FILE 포인터인데요. 만약에 파일을 여는 것을 실패했다면, NULL 포인터를 리턴합니다. 이 처리를 잘 해주시면 좋을 듯 싶습니다. 열지도 못했는데 내용을 읽지는 못할 거니까요. 일단, 이 포스팅에서는 3개만 알고 계시면 됩니다. 그리고 뒤에 +가 붙는 경우가 있어요. 추가로 binary..
코딩/C 2020. 2. 3. 18:08
트리에서 최단 경로를 구하기 위한 또 다른 방법?

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