배열 돌리기 5는 solved 난이도로 골드 1인 문제입니다. 200만개의 쿼리를 브루트 포스하게 실행시키면, 시간초과가 나는 것은 당연해 보입니다. 높이가 100, 너비가 100인 배열을 어떻게 압축을 시키면 좋을까요? 문제가 되는 것은 5번, 6번임을 알 수 있습니다. 가로로 반, 세로로 반을 나눠서 처리해야 하기 때문입니다. 사실 그것만 없었다면, 그냥 시점만 이동해서 풀 수 있었을 겁니다. 일단, 제 풀이는 브루트 포스입니다. 그런데, 100 by 100 전체를 브루트 포스를 하지 않습니다. 데이터를 압축하는 것이 목표입니다. 어떻게 잘 압축을 할까요? 배열 S가 아래와 같이 있다고 해 보겠습니다. 5, 6번 연산 때문에 이렇게 나누었다는 것을 눈치채셨을 겁니다. 이 4개의 영역 중에, 모서리 부..
분류 전체보기 검색 결과
시간 복잡도를 어떻게 대강 분석할까요? 실행 시간을 보고, 추정을 하시면 됩니다. 정말 괴랄한 복잡도가 아니라면, O(n), O(n^2), ... 등은 어느 정도 맞아 떨어집니다. 저는 java에서 메서드를 실행하는 데 걸린 시간을 측정할 때, System.nanoTime()을 이용하는 편입니다. 이것은 정밀한 시간 측정을 해 주지는 못합니다만, 어느 부분에서 시간 초과가 날 수 있는지 후보해를 추릴 수 있습니다. 질문이 하나 들어왔습니다. M자리 수와 N자리 수를 BigInteger로 곱하였습니다. M, N은 30만 자리 정도 되었다고 합니다. 10진수로 M자리 수라면, 32bit 2진수가 10진수 9자리와 대응이 됩니다. 그래서, bit 연산을 잘 이용하면 M과 N이 최대 30만자리까지 나오니까, (..
저번 시간에는 ArrayBlockingQueue에 대해서 잠깐 다룬 적이 있었습니다. 이번에는 Future에 대해서 다뤄 보도록 하겠습니다. Future에 대한 설명을 보면 위와 같습니다. Future는, 비동기적인 계산에 대한 result를 표현합니다. 그리고, 작업이 완료되어야, 결과를 가져올 수 있습니다. 이 말이 이해가 잘 가지 않네요. 비동기는 나중에 보기로 하고, 작업이 완료 되어야 가져 온다는 말을 이해해 보겠습니다. Future에서 쓸 수 있는 것 중 하나는 get입니다. 이것은, 계산이 완료될 때 까지 기다린 다음에, 그것의 result를 찍는 역할을 합니다. 그런데, 여기서 complete가 나옵니다. Task를 잘 생각해 보면, 진행 중인 상태가 있을 겁니다. 이를 run 상태라 하겠..
파이썬에는 dict와 OrderedDict가 있습니다. 이 둘에 대해 간단하게 알아봅시다. 아래 코드를 wandbox에서 python 3.5.0에서 실행시켜 보았습니다. 2번째 줄이 조금 길어보이는데요. 그리 어렵지 않습니다. ord('A')와 ord('Z')는 'A'와 'Z'를 코드로 변환시켜 줍니다. 그러면 i는 'A'의 코드값부터 'Z'의 코드값까지 돌 겁니다. 그런데, 앞에 chr(i)가 있으니, 결론적으로 li는 'A'부터 'Z'까지 들어가 버리게 됩니다. 3번째 줄에서는 li 안에 있는 것들을 돌면서, 'A', 'B', ... , 'Z' 순서대로 넣고 있습니다. 다음에, 5번째 줄에서는 dic를 순회하면서 요소들을 모두 출력합니다. 결과는 위와 같습니다. 중요한 것은 넣은 순서가 자료구조 내에..
c언어 교재에 단골로 나오는 소재는, 달력을 예쁘게 출력하는 것입니다. 처음 접해보면 어려울 수도 있는데요. 기능을 잘 쪼개고 들어가면 됩니다. 코딩 테스트에서도 기능을 잘 쪼개고 들어가는 것은 굉장히 유용한 스킬이니, 익혀 두시면 좋습니다. 일단, 간단한 플로우 먼저 그려봅시다. 복잡해 보이지만, 사실 yyyy년 mm월 1일의 요일과, yyyy년 mm월이 몇 일까지 있는지만 구하면 어렵지 않게 출력할 수 있음을 알 수 있습니다. 이 기능들을 또 쪼개 보겠습니다. yyyy년 mm월 1일의 요일을 알기 위해서는 기준이 되는 날의 요일을 알아야 합니다. 다음에, 월별로 몇 일까지 있는지를 알아야 합니다. 그래야, 기준 요일로부터 몇 일만큼 지났는지를 누적할 수 있기 때문입니다. 해당 기능을 구현하기 위해서 ..
최근댓글