링크: https://www.acmicpc.net/problem/2225 문제의 예시로 n=20, k=2일 때 나올 수 있는 경우의 수는 0 + 20 1 + 19 2 + 18 ...19 + 120 + 0로 총 21개이다. 풀이n=20이고 k=3이라면, 경우의 수는 아래와 같은 모양으로 전개된다.(n=20, k=3) = (n=20, k=2)+ (n=19, k=2)+ ...+ (n=1, k=2)+ (n=0, k=2) 3개의 수를 n=20 내에서 고르는 경우의 수 = 첫 번째 수로 0을 사용하고, 나머지 2개의 수를 n=20 내에서 고르는 경우의 수+ 첫 번째 수로 1을 사용하고, 나머지 2개의 수를 n=19 내에서 고르는 경우의 수+ .... 작은 문제로 쪼개어 해결이 가능하다. dp 테이블을 두고 메모이제..

Github Gist에서 간단한 소스 파일을 작성하여 글에 첨부하기 좋도록 embed 태그로, 또는 보기 편하도록 퍼머링크를 제공한다. 하나의 gist는 만들 때 secret/public 중에 골라서 만들 수 있다. secret은 나중에 Edit에서 Make public으로 공개할 수 있다. 근데 반대로 public gist에서는 비공개로 전환하는 Make secret 버튼이 없다. https://gist.github.com/zmwangx/bc79e7d95d82c2f5e0976975b6e1c6d6왜 Make secret 버튼이 없냐는 질문에 답변은 대충 이렇다.비밀로 바꾸게 되면 URL 주소가 바뀌어서 사용자들에게 혼란이 생긴다.한번 공개된 이상 비밀은 끝났다고 생각하면 이해가 된다. https://he..

링크: https://www.acmicpc.net/problem/3075 문제p개의 은하가 있을 때, n명과 교통비의 합이 최소가 되는 어떤 하나의 은하(미팅 장소)를 찾는 문제이다. 조심할 것조건이 특별히 안 적혀있어서 조심해야 할 게 많은 문제였다. 주의해야 할 조건으로는1. 하나의 은하에 여러 사람이 있을 수 있고2. 은하와 은하 사이에는 여러 개의 길이 존재할 수 있다(doju님의 데이터 추가 글) 나는 외딴 섬에 대한 케이스를 처리 못해서 틀렸었다. 풀이미팅 장소가 될 은하를 하나 잡고, 그 은하로부터 나머지 사람들과의 거리의 합을 구한다. 이 때, 거리의 합이 최소가 되는 은하가 정답이다. 은하의 개수 \(p \lt 100\) 로 작은 크기이기 때문에, 플로이드-와샬 알고리즘으로 구현하면 간단..

링크: https://www.acmicpc.net/problem/15686 문제 설명 마지막 줄에 다 요약되어있다. 도시에 있는 치킨집 중에서 최대 \(m\)개를 골라야한다.문제 조건에서 치킨집의 개수는 최대 13개이고, 도시에 있는 치킨집 \(k\)개 중에 \(m\)개를 고르는 경우의 수는 $$C(k, m) = \frac{k!}{m!(k-m)!}$$숫자가 작아서 많아봐야 1500개가 좀 안되므로 치킨집을 선택하는 모든 경우의 수를 시도해 볼만 하다. 정해진 \(m\)개의 치킨집마다 모든 사람들의 집에 도달하는 최소 거리를 사람이 사는 집 기준으로 저장해둔다. 즉, 어떤 조합에 대해 \(j\)번 집은 가장 가까운 치킨집과의 거리를 저장하고 있다. 매 조합마다 모든 거리를 구하면 오버헤드가 심하므로 미리 ..

링크: https://www.acmicpc.net/problem/15685 문제알고스팟의 JM북에 그려진 그 드래곤 커브가 맞다. 간단한 수학 규칙으로 그려지는 그림인데, 이 문제에서는 드래곤 커브가 네 꼭지점을 모두 지나는 칸이 몇 개인지 구하는 거였다. 풀이드래곤 커브의 규칙을 미리 만들어놓고, 드래곤 커브의 시작점과 시작 방향이 주어졌을 때 규칙에 맞게 이동하면서 주변 칸에 해당 꼭지점이 지나갔음을 기록한다. 드래곤 커브는 이전 세대의 드래곤 커브를 이용하기 때문에 반복적인 구조이다. 각 방향과 관련된 변수들을 잘 설정하면 쉽게 구현할 수 있다. 나는 문제에 맞춰 우,상,좌,하 순서로 0,1,2,3을 사용했다. 원소들은 진행 방향, 드래곤 커브를 \(G_0 = \{\dots, a, b, c, d\}..

링크: https://www.acmicpc.net/problem/12755 2016 전북대학교 프로그래밍 경진대회 A번 비슷한 문제로는 BOJ 1748 - 수 이어 쓰기 1이 있는데, 거기에 조건을 하나 더 얹었다. 앞에서부터 \(N\)번째 자리에 있는 수를 출력하는 것이다. 1부터 \(N\)까지 전부 확인하는 건 시간적으로도 메모리적으로도 무리다. 따라서 탐색 범위를 좁힐 필요가 있는데 이 문제에서는 자리수별로 인덱스를 자르면 좀 낫다. 1자리 수는 1부터 9까지 9개가 있으며, 전부 이어 붙이면 길이가 9이다.2자리 수는 10부터 99까지 90(=99-10+1)개가 있으며, 전부 이어 붙이면 길이가 180(=90*2)이다.3자리 수는 100부터 999까지 900(=999-100+1)개가 있으며, 전부..

[이전 블로그에서 글 옮김] https://www.acmicpc.net/problem/2022 https://uva.onlinejudge.org/...&problem=1507 \(a, b, c\) 가 주어지면 \(k\) 를 구해내는 문제이다. 피타고라스로 A, B를 구해서 기울기를 구하고, 두 직선의 교점 방정식을 이용했다. 그리고 교점의 y 위치가 \(c\) 가 되는 순간을 구하도록 이분 탐색을 했다. 우선 a가 포함된 직선을 g(x), b가 포함된 직선을 f(x)라 한다면 아래와 같은 정보가 나온다. \( \begin{cases} A = \sqrt{a^2 - k^2} \\ B = \sqrt{b^2 - k^2} \end{cases} \) \( \begin{cases} f(x) = \frac{B}{k}x..

분산컴퓨팅 최종 프로젝트 보고서 (2017) Kinesis를 이용한 데이터 수집 from Joonas Yoon AWS 서비스를 활용해보는 것이 분산컴퓨팅 프로젝트였다. EMR를 쓰는 사람도 있었고, Amazon SNS를 사용해보거나 AWS Shield를 분석하거나 Amazon GameLift를 다뤄보는 프로젝트 등 재밌는 발표가 많았다.나는 RedShift를 다루어보고 싶었는데, 그러기 위해선 분석할 데이터나 데이터를 수집하는 과정이 필요했다. 데이터의 수집부터 저장, 그리고 그 분석까지 하면 재밌을 것 같아서 프로젝트 주제를 "데이터 웨어하우스를 위한 데이터 수집 및 저장"으로 정했다.AWS re:invent에서 발표된 PPT들을 많이 참고하면서 아키텍처를 구상하고 서비스를 선택했다.우선 어떤 데이터를..