안녕하세요. 조경완입니다. 오랫만에 구현 카데고리로 돌아왔습니다. 문자열 뒤집기는 코테 뿐만이 아니라 면접에서도 물어볼 수 있는 내용입니다. 문제는, 이것입니다. 한글 때문에 조심해야 합니다. 이는, 한글이 1byte로 표현되지 않기 때문입니다. 그리고, 어떤 방식으로 인코딩 된 문자열인지도 언급되지 않았으니, 이 부분도 질문하시는 게 좋겠습니다. 그리고 해당 인코딩으로 표현 가능한 문자 셋만 들어오는지도 질문 해 두면 좋겠습니다. 아래 Solve 클래스 내에 있는 revGetByte를 생각해 보겠습니다. 이 함수는 EUC-KR로 b0a1 b3aa로 인코딩 된 바이트를 b3aa b0a1로 바꾸는 함수입니다. 그리고 이 결과물을 파일 b에다가 씁니다. 파일 a도 EUC-KR로, b도 EUC-KR로 인코딩 ..
구현 검색 결과
백준에서 a^b꼴의 문제를 본 적이 있을 겁니다. 문제는 여기에서 풀어보실 수 있습니다. 물론, b는 0보다 크거나 같고 100보다는 작거나 같은 정수이고, a는 소수점 밑에 자리수가 9개까지 나올 수 있습니다. 사실, 저는 이것을 .을 기준으로 일일히 파싱해서 풀었습니다. 즉, .을 기준으로 나누면 j/m꼴이 됩니다. 그러니, (j/m)^b을 계산하는 문제로 바뀌고, m은 10^q꼴이니, j^b의 결과값에 따라서 적절히 잘 파싱하면 됩니다. 그런데, 그리 한다면, j는 최대 11자리 ~ 12자리의 정수로 바뀔 거고, b는 최대 100이니, 1100자. 결국 이 문제를 제대로 풀려면 큰 수 곱셈을 잘 구현해야 한다는 이야기가 되겠습니다. 이펙티브 자바가 있다면 정확한 답이 필요하다면 float와 doub..
오늘은 다소 빡센 구현 문제를 다뤄보도록 하겠습니다. 백준의 원판 돌리기 문제는 읽어 보셨을 겁니다. 혹시나, 안 읽어보셨다면, 링크로 가셔서 읽어보세요. 생각보다 문제가 깁니다. 중요한 조건은, 원판도 50개 이하, 적혀있는 수도 50개 이하, 회전 연산의 횟수도 50회 이하라는 것입니다. 그러면 1칸씩 회전을 한다고 해도 2500^2, 그리고 원판에서 적절한 연산을 하는 후처리는 연산당 50^3이 걸리겠네요. 일단, 문제를 3개로 쪼개는 것이 필요합니다. 이렇게 쪼갰다면, (1)번부터 차근차근 보도록 하겠습니다. 일렬로 편다는 것이 무슨 말인지 이해가 안 가실 듯 싶은데요. 쉽게 생각해 보겠습니다. 원판에 수가 위와 같이 적혀 있다고 해 보겠습니다. 시계 방향으로 1칸 회전시키면 어떻게 될까요? 요렇..
오늘은 어떤 것을 배워볼까요? 시계처럼 x칸씩 회전하는 연산을 배워보겠습니다. 17406번 배열 돌리기 문제를 보겠습니다. 문제가 요구하는 것은 간단합니다. 그 중에서 가장 중요한 것은 rotate 연산입니다. 이것은 정사각형을 시계방향으로 1칸씩 돌린다는 의미입니다. 문제가 다소 복잡하니, 분할해서 생각해 보도록 하겠습니다. 먼저, 돌아가는 단위를 기준으로 나누면, 기준점을 하나 잡을 수 있습니다. 이 기준점들을 먼저 잡아보겠습니다. 먼저 회전 반경이 1이라고 해 보겠습니다. 0번만 있는 요소, 그리고 1 ~ 8까지 있는 요소 둘로 나눠보겠습니다. 그러면, 제가 보라색으로 칠한 것은 각각의 요소들의 기준점으로 볼 수 있습니다. 그리고, 1번은 1 ~ 8은 하나의 요소로 볼 수 있습니다. 이들이 1칸씩 ..
안녕하세요. 오늘은 큰 수를 어떻게 좌표 압축을 하는지 알아보도록 하겠습니다. 대소 비교하는 방법도 익힐 겸. 백준 17126을 보면, 일반적인 그냥 쿼리 문제인 것 같아 보입니다. key의 조건을 보기 전 까지는요. 여기서, 모든 key 값의 범위는 1이상 (10^99)-1 이하입니다. 여기서 좌표 압축을 한다는 것은, 들어오는 Key나, 중요한 수에 대해서 순서를 재정렬 하는 것을 의미하는데요. 그러려면, sort가 되어야 할 거에요. 정렬을 하기 위해서는 두 큰 수를 compare 해야 합니다. 이것을 어떻게 해야 할까요? 일단 long long 형이나, int형, 그리고 __int128로는 cover가 되지 않음은 자명합니다. 먼저 어떤 수 A가 B보다 작다면 무엇을 만족해야 하는지 생각해 봅시다..
최근댓글