Joonas' Note

2018년 4월 26~27일(1박 2일)동안 진행된 네이버 AI HACKATHON 2018(https://github.com/naver/ai-hackathon-2018)에 참가했다.대회 방식은 네이버에서 개발중인 클라우드 머신러닝 플랫폼 NSML을 사용하여 진행되었다.미션은 네이버 지식iN 질문 유사도 예측 문제와 네이버 영화 평점 예측 문제, 이렇게 2개였다. 나는 팀명 "error 모르게따"로 참가하여, 네이버 지식in 미션에서 2등으로 대회를 마쳤다. 숙소식사부터 숙소까지 대회가 진행되는 동안 너무 좋았다! 저희 팀은 3명이라 숙소 배정이 어떻게 될 지 몰랐는데, 3명 모두 1인 1실로 배정돼서 와 대박이네 하면서 편하게 쉬었다. 덕분에 팀원끼리도 편하게 쉬면서 같이 움직이니 더욱 잘 진행되는 기분..

링크: 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)개가 있으며, 전부..