구현 검색 결과

해당 글 36건
백준 원판 돌리기 : 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
큰 수를 어떻게 좌표 압축하면 좋을까요?

안녕하세요. 오늘은 큰 수를 어떻게 좌표 압축을 하는지 알아보도록 하겠습니다. 대소 비교하는 방법도 익힐 겸. 백준 17126을 보면, 일반적인 그냥 쿼리 문제인 것 같아 보입니다. key의 조건을 보기 전 까지는요. 여기서, 모든 key 값의 범위는 1이상 (10^99)-1 이하입니다. 여기서 좌표 압축을 한다는 것은, 들어오는 Key나, 중요한 수에 대해서 순서를 재정렬 하는 것을 의미하는데요. 그러려면, sort가 되어야 할 거에요. 정렬을 하기 위해서는 두 큰 수를 compare 해야 합니다. 이것을 어떻게 해야 할까요? 일단 long long 형이나, int형, 그리고 __int128로는 cover가 되지 않음은 자명합니다. 먼저 어떤 수 A가 B보다 작다면 무엇을 만족해야 하는지 생각해 봅시다..
구현 2020. 3. 4. 02:10
배열 원소 삽입 삭제 패턴만 익혀봅시다.

사실, 이런 류의 기능을 하는 함수는 구현을 해야 할 일이 있을 겁니다. 여기에서는 optimize 생각 안 하고, 어떻게 빠르게 구현을 할 지, 패턴 정도만 이야기 해 보도록 하겠습니다. 3 종류의 쿼리가, Q개 들어온다고 생각해 보겠습니다. 이 때, insert 하는 위치와, delete 하는 위치 모두는 vaild 하다고 생각해 봅시다. 먼저, 구조체를 하나 정의하기 전에, 어떤 구조가 적합한지 먼저 생각해 봅시다. 사실, 적절한 자료구조가 있습니다. i번째 위치를 빠르게 찾는다. [s, e]번째 위치에 있는 원소 item들을 모두 delete 하는 것 또한, s번째 item을 찾고, e번째 item을 찾기만 하면 됩니다. 그러면 kth를 빠르게 찾을 수 있는 구조면 좋은데요. 그 중 하나는, sk..
구현 2020. 2. 16. 02:04
코딩테스트에 나올 만한 백트래킹 쉽게 정복해 봅시다.

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