백준 검색 결과

해당 글 24건
백준 원판 돌리기 : deque를 사용하면 쉽다.

오늘은 다소 빡센 구현 문제를 다뤄보도록 하겠습니다. 백준의 원판 돌리기 문제는 읽어 보셨을 겁니다. 혹시나, 안 읽어보셨다면, 링크로 가셔서 읽어보세요. 생각보다 문제가 깁니다. 중요한 조건은, 원판도 50개 이하, 적혀있는 수도 50개 이하, 회전 연산의 횟수도 50회 이하라는 것입니다. 그러면 1칸씩 회전을 한다고 해도 2500^2, 그리고 원판에서 적절한 연산을 하는 후처리는 연산당 50^3이 걸리겠네요. 일단, 문제를 3개로 쪼개는 것이 필요합니다. 이렇게 쪼갰다면, (1)번부터 차근차근 보도록 하겠습니다. 일렬로 편다는 것이 무슨 말인지 이해가 안 가실 듯 싶은데요. 쉽게 생각해 보겠습니다. 원판에 수가 위와 같이 적혀 있다고 해 보겠습니다. 시계 방향으로 1칸 회전시키면 어떻게 될까요? 요렇..
구현 2020. 5. 1. 00:04
백준 배열 돌리기 4 : 요소별로 나누면 어렵지 않다.

오늘은 어떤 것을 배워볼까요? 시계처럼 x칸씩 회전하는 연산을 배워보겠습니다. 17406번 배열 돌리기 문제를 보겠습니다. 문제가 요구하는 것은 간단합니다. 그 중에서 가장 중요한 것은 rotate 연산입니다. 이것은 정사각형을 시계방향으로 1칸씩 돌린다는 의미입니다. 문제가 다소 복잡하니, 분할해서 생각해 보도록 하겠습니다. 먼저, 돌아가는 단위를 기준으로 나누면, 기준점을 하나 잡을 수 있습니다. 이 기준점들을 먼저 잡아보겠습니다. 먼저 회전 반경이 1이라고 해 보겠습니다. 0번만 있는 요소, 그리고 1 ~ 8까지 있는 요소 둘로 나눠보겠습니다. 그러면, 제가 보라색으로 칠한 것은 각각의 요소들의 기준점으로 볼 수 있습니다. 그리고, 1번은 1 ~ 8은 하나의 요소로 볼 수 있습니다. 이들이 1칸씩 ..
구현 2020. 4. 14. 00:25
백준 공유기 설치 : 왜 이분탐색이 가능한가?

안녕하세요. 백준에서 chogahui05로 활동하고 있는 조경완입니다. 백준의 공유기 설치 문제는 많이 풀어보셨을 겁니다. 정확히 말하면, N개의 point가 있고, 그 중, C개를 설치하려고 할 때, 가장 인접해 있는 두 공유기 사이의 거리를 최대화 하라는 문제입니다. 어렵네요. 이를, 먼저 결정 문제로 바꾸어 봅시다. 그러면, 먼저 f(x)의 값을 어떻게 구해야 할 지 생각해 봅시다. N개의 집을 x 좌표 오름차순으로 정렬했다고 해 봅시다. 그러면 첫 공유기는 어디에 설치해야 할까요? 1번째 집에 설치해야 합니다. 왜 그럴까요? 문제 조건에 따르면, 같은 x좌표를 가지는 집은 없다고 했습니다. 그렇기 때문에, 집이 n개가 있고, i번째 집의 위치를 x[i]라고 하면, 아래의 식이 성립합니다. 이는 집..
자료알고/알고리즘 2020. 3. 27. 01:52
백준 화성지도 : 구간에 장벽을 세운다.

백준 화성지도라는 문제는, 저를 골치 아프게 하던 문제 중 하나였습니다. 저는 이 문제를, 어떠한 상황으로 바꿔서 풀었습니다. 그 방법으로 접근해 보도록 하겠습니다. 세그 트리라는 말은 이 블로그에서는 언급하지 않았으니, '구간을 관리하는 자료 구조' 정도로 생각합시다. 그러면 조금 더 편하지 않을까 싶어요. 문제를 보셨고, sweeping에 대한 개념이 어느 정도 쌓여 있다면, 다음과 같은 쿼리를 처리해야 한다는 것을 알 수 있습니다. 문제의 특성상, 전체 구간을 보았을 때, 어떠한 특정 구간의 값이 0 미만으로 떨어질 일 또한 없다는 것을 알 수 있습니다. 구간 [a,b] 에 1이나 -1을 더하는 건 lazy 기법을 이용하면 쉽게 할 수 있을 듯 싶은데, 3번 쿼리가 문제입니다. 이 문제를 해결하기 ..
자료알고/알고리즘 2020. 2. 24. 00:00
코딩테스트에 나올 만한 백트래킹 쉽게 정복해 봅시다.

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