구현 검색 결과

해당 글 14건
백준 원판 돌리기 : 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
코테에서 답을 미리 저장하는 방법도 쓸만한가요? 네

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