남남서의 블로그

AtCoder는 일본의 경기 프로그래밍(competitive programming) 플랫폼이다. APIO 2012를 호스팅했다고도 들은 적이 있고, 다양한 기업들의 스폰서를 받아서 대회를 열기도 한다는 것 같다. (확실하지는 않다.) 또한 여기서는 주기적으로 콘테스트를 여는데, 두 달쯤 전까지만 해도 일본어로 된 콘테스트만 열었다. 그런데 7월 13일쯤에 대대적인 변화가 있었다. 그 예로는 - 영어로 description을 제공한다. - 이전까지는 AtCoder Beginner Contest와 AtCoder Regular Contest만 열었는데, 이제는 AtCoder Grand Contest도 연다. - 거의 매 주 여는 것 같으며, AtCoder Grand Contest만 열리거나, Beginner와..

1. 네 번째 점 2. 색종이 3. 악수 4. 카드1 1. 큐의 배열 구현 2. 큐의 STL 구현 5. 가장 큰 증가 부분 수열 6. 겹치는 선분 7. 예산 8. 전봇대 9. 플로이드 10. 말 1. 네 번째 점 네 번째 점의 x좌표는 주어진 점 중 단 하나에만 등장했을 것이고, y좌표 또한 마찬가지이다. if문을 잘 써서 풀어도 되고, 좀 더 특이하게 혹은 편하게 풀고 싶다면, x좌표를 XOR(연산자 ^)시킨 것이 답의 x좌표와 같다. y좌표도 마찬가지. 2. 색종이 (p,q) 라는 지점에 색종이를 놓으면, x좌표가 p ~ (p+10), y좌표가 q ~ (q+10)에 있는 영역은 모두 색칠된다. A[i][j] = (i,j), (i,j+1), (i+1,j+1), (i+1,j)가 이루는 정사각형이 색칠되어..

1. 3000번 버스 2. 과제 안 내신 분..? 3. Amalgamated Artichokes 4. 카드 방법 1. 방법 2. 5. 두 용액 1. 방법 2. 방법 6. 세 용액 7. 팰린드롬 경로 3 8. 레슬러 9. 커플 깨기 10. 램프 1. Convex Hull을 이용한 방법 2. 이분탐색을 이용한 방법 1. 3000번 버스 2. 과제 안 내신 분..? 배열 a를 만든다. x라는 숫자를 읽고 나면 a[x]에 체크한다. 이후 a 배열을 순회하며 체크되지 않은 x를 찾아 답을 출력한다. 문제 자체는 단순하지만, counting sort 등의 아이디어와 밀접하게 닿아있다. 3. Amalgamated Artichokes 영어라서 어려워 보이지만 읽어보면 쉬운 문제이다. 아래의 리빙포인트를 꼭 참고하자. ..

문제 링크일단, 이웃한 \((M+1)\)개의 숫자들에 대해서, 앞의 \(M\)개와 뒤의 \(M\)개는 \((M-1)\)개가 겹친다. 그렇다면, \((N-M+1)\)개의 수열에서, 한 수열에서 \((M-1)\)개가 겹치는 다른 수열로 옮겨간다고 생각할 수 있다. 그런데 \((N-M+1)\)개를 정점으로 잡으면 Hamiltonian Path를 구해야 하기 때문에 복잡하다. 따라서, \((M-1)\)개를 정점으로 잡고, 각각의 \((N-M+1)\)개의 수열을 간선으로 만들면 Euler Tour를 구하면 된다. (M-1)개를 효과적으로 관리하기 위하여 나는 해싱을 사용했다.

두니발 박사가 탈옥을 했는데, 하루가 지나면 한 마을에서 다른 마을로 옮겨간다.이때 내가 있던 마을에서 갈 마을이 여러 곳이면 그곳으로 각각 갈 확률이 n등분된다.이때 d일이 지났을 때 각 장소에 박사가 있을 확률을 구하여라... 하는 문제이다. 일단은 확률이니까 경우의 수를 전체 경우의 수로 나눈다든가 하는 생각이 들 수도 있지만,잘 생각을 해보면 d일째의 각 확률을 알고 있으면,모든 모서리마다(모든 시작점과 끝점에 대해서)(d+1)일째에 끝점에 있을 확률 += d일째에 시작점에 있을 확률 x (1 / (시작점에서 갈 수 있는 모서리의 수))이 됨을 쉽게 알 수 있다.모든 모서리에 대해서 이 작업을 d번 하면 되므로 시간복잡도는 O(dE)인데,문제에서 이미 인접행렬을 주기 때문에, O(dV²)으로 풀 ..

http://koistudy.net/?mid=prob_page&NO=381간단한 boggle 게임이다. 아래와 같은 격자판을 보자. 위 격자판에서 TARTU를 읽는 방법의 수는 7가지가 있다. 알파벳 대문자로만 이루어진 문자 격자판과 단어가 주어질 때,그 단어를 읽는 방법의 수를 구하는 프로그램을 작성하시오. 이전 문자와 가로, 세로, 대각선으로 연결된 것들만 읽을 수 있다. (가로, 세로 높이 ≤ 200, 문자열길이 ≤ 100,답 ≤ 1018 ) 해법) 1)백트래킹 방식으로 모든 문자열을 찾는다.시간복잡도는 최대 문자열의 수만큼 나온다.그런데 답이 10^18 이하라는 말은 최대 10^18정도의 답도 나올 수도 있다는 것. 2)위의 방법과 비슷하게 다이나믹 프로그래밍을 이용한다. (backtracking..