이번 시간에는 백준 1060번 문제를 풀면서, 후보해를 어떻게 추리는지 보도록 하겠습니다. 문득 떠오르는 시스텟 페일 간단한 알고리즘을 물어보는 코딩테스트에도 이 글에서 간접적으로 설명한 것들은 나올 법 하니, 알아두면 좋을 듯 싶습니다. 사실 코테 접은 지 1년 넘어서 잘 모른다는 것은 함정입니다. 문제는 아래와 같습니다. 어떤 집합 S에는 양의 정수 L개가 있고, f(x)를 아래 조건을 만족하는 구간의 갯수로 정의합니다. 0보다 큰 정수 x, y가 있다고 한다면, f(x) < f(y)이거나, f(x) = f(y)이고 x
안녕하세요. 조경완입니다. 백준에서 문제들을 풀다 보면, 소수인팰린드롬 문제도 보셨으리라 생각합니다. 어렵지 않은 문제이지만, Loop를 칠 때, 어떻게 치면 좋은지 생각해 볼 수 있는 문제인 듯 싶어서 가지고 오게 되었습니다. 문제는 아래와 같습니다. 최악의 경우에는 a가 5, b가 1억이니 만만치 않은 문제인 듯 싶습니다. 그런데, 314명이 풀어냈습니다. 1억까지를 에라스토스테네스의 체로 거른다고 해도 힘들고, 그렇다고 팰린드롬을 로그 복잡도로 판별하고 루트 복잡도로 소수임을 판별하자니. 그것도 힘듭니다. 어떻게 하면 좋을까요? 아이디어는 의외로 단순합니다. 일례로 99823419가 소수인지 판단하는 것은 쉽지 않습니다. 그런데, 팰린드롬인지는 어떻게 판정하면 되나요? 그냥 뒤에서 부터 본 문자랑 ..
(2차원) 배열에서 가장 큰 정사각형을 찾는 것은 dp로 해결할 수 있습니다. 문제를 조금 바꿔보겠습니다. 가장 큰 직사각형은 어떻게 구해야 할까요? 문제의 제한이 딱 하나 바뀌었을 뿐인데, 난이도는 4단계 정도 높아졌습니다. 이 문제를 보도록 하겠습니다. 문제를 요약하면 다음과 같습니다. n이 범위는 1이상 2000 이하입니다. 시간 제한이 3초인 것을 감안했을 때, O(n^2)나 O(n^2logn) 정도에 풀어야 한다는 결론을 얻을 수 있습니다. 그런데, 후자는 생각보다 상수 줄이기가 빡빡하기도 하고 제가 시도해 본 방법이 아니므로, 저는 전자로 시도해 보겠습니다. 먼저 간단한 상식 아닌 상식을 통해서 관찰을 하나 해 보도록 하겠습니다. 길이가 3, 4, 2, 6인 높이 1짜리 직사각형이 있습니다. ..
요새 코테 철이 되었습니다. 저도 간간히 구현력을 잃어버리지 않기 위해서 조금씩 복기만 하고 있습니다. 백준 11003번 문제는 최솟값을 구하는 문제입니다. 특정 구간 [e-k, e]에서의 최솟값을요. 단, 0보다 작은 위치의 구간은 무시하고 구해야 합니다. 별로 어렵지 않아 보이는데, 문제는 n이 500만입니다. 입력 받느라 시간이 많이 가는 건 흐음. O(n)으로 줄일 수 있습니다. 다들 아시는 기법을 소개하도록 하겠습니다. 관찰을 해야 할 것은 2가지 상황입니다. 어떠한 데이터가 추가되는 상황하고, 제거되는 상황. i번째에 있는 데이터가 제거되면, 더 이상 추가되지 않는다는 것을 관찰하는 것 또한 포인트입니다. 현재, 이런 식으로 데이터가 들어갔다고 해 보겠습니다. 그리고 저는 7번째 위치에 있는 ..
이 글을 읽기 전에 잘못 구현된 다익스트라 글을 보고 오시는 것 추천드립니다. 저는 그 글을 읽으셨고, 그 글에 나온 저격 데이터가 어떠한 원리로 작성되었는지 30% 정도 이해했다는 전제 하에 진행하도록 하겠습니다. 보통 이 알고리즘을 구현하실 때 Priority Queue를 이용하는 경우가 많습니다. 저는 그것을 기준으로 작성하였습니다. min_cost와 where_is_from, visit와 con이 있습니다. 이 중에서 con은 graph를 구축하는데 쓰이는 자료구조 정도로 생각하시면 됩니다. C++의 STL에서 vector con과 같습니다. min_cost를 inf로 초기화 합니다. 그리고, where_is_from을 -1로, visit를 false로 초기화를 합니다. 다음에 pq에 시작점을 넣..
최근댓글