Joonas' Note

오랜만의 코딩으로 풀어보기 시리즈이다. 오늘은 아주 간단하고 쉬운 문제이다. 문제 1부터 9까지의 숫자를 한번씩만 사용해서, 수식을 성립시키는 문제이다. 이런 유형의 문제는 "복면산 문제"라고 불리는 수학 퍼즐의 한 종류이다. 여담이지만, 개인적으로 좋아하는 문제이다. 이와 관련한 알고리즘 문제를 출제한 적도 있다. 완전 탐색류 알고리즘을 연습하기 좋은 문제라고 생각한다. 아래 링크에서 풀어볼 수 있다. BOJ 15811 - 복면산?! (https://www.acmicpc.net/problem/15811) 위 문제는 9개의 숫자와 9개의 알파벳이니 더 쉽다. 1부터 9까지 A부터 I까지 모두 대응시켜보며 만들어지는 세 값이 일치하는 지 확인하면 된다. 즉, 모든 순열을 확인하면 된다. 경우의 수는 \(9..

※ 정답과 풀이가 포함된 스포일러가 있습니다. [ 문제적 남자 : 브레인 유랑단 13회, 역대급 신비로운 문제]문제와, 이번 문제는 정말 신기하고 신비로웠다.서로 전혀 다른 두 풀이가 같은 답을 만들어냈다.우선 두 정사각형 모두, 가로줄과 세로줄, 대각선줄의 합이 같도록 수를 채워야했는데 그 답으로 위와 같이 채워진 것이다. 규칙 (문제의 정답)왼쪽 사각형에 있는 한 칸의 수를 영어로 적었을 때, 그 단어의 길이가 오른쪽 사각형의 같은 칸에 적혀 있는 것이다.그러면서 모든 줄의 합이 같게 유지된 것이다.오현민은 등차수열로 접근해서 왼쪽 사각형을 풀고, 오른쪽에서 가능한 모든 경우의 수를 추린 후 정답을 찾았다.여기서 나는 의문이 생겼다.그럼, 이런 (두) 사각형은 얼마나 더 있을까? 탐색1부터 99까지의..

링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWK3lS6aF-MDFAWJ문제별표(*) 또는 0~9 숫자가 3개 적힌 카드가 N개 있을 때, 숫자끼리 연결되게 이어 붙여서 그 때의 모든 숫자의 합이 가장 큰 것을 구하는 문제이다. 여기서 별표(*)는 숫자를 연결하지 못하도록 만드는 구분자라고 생각하면 된다. 단순해보이지만 케이스를 제대로 생각못해서 여러번 시도 끝에 맞췄다.풀이는 브루트 포스(Brute force)이다. 먼저 숫자 카드는 아래처럼 6가지의 케이스가 있을 것이다. 편의상 (a) + (b) = 12312* 와 같이 적겠다. 숫자로만 이루어진 (a)는 어디에든 붙을 수 있으니, 그냥 무조건 더해..

문제2019년 초에 신년을 맞아 싱가포르 국립대학교(NUS) 천재들과의 문제 배틀이 있었다.그 중 하나로, 빨간 화살표가 가리키는 방향에는 빨간 화살표가 2개만, 회색 화살표가 가리키는 방향에는 빨간 화살표가 2개가 아니도록 화살표를 색칠하는 문제가 있었다.규칙을 만족하는 포인트를 파악해서 논리적으로 연결해나가는 것이 맞지만, 우리는 컴퓨터가 있다.무식하게 모든 경우를 전부 확인해보자. 정말 답이 하나일까? 세로 4행, 가로 5열 총 전체 20개의 칸을 모두 색칠해보는 경우는, 각 칸을 색칠한다/하지않는다 2가지의 선택이 20개 칸마다 있는 것이므로\(O(2^{20})\)이다. 색칠 후에는 각 화살표들이 모두 규칙을 만족하는 지 확인해야하므로 연산이 조금 더 붙지만, 그래도 3천만번 이하로 계산된다.이 ..

링크: https://www.acmicpc.net/problem/1405문제동서남북 각 방향으로 이동할 확률이 주어지고, 로봇이 동선을 겹치지 않게 n번 움직일 확률을 구하는 문제이다.(0, 0)부터 출발한다고 생각하면 동서남북 경계의 끝은 (14, 0), (-14, 0), (0, 14), (0, -14) 일텐데 음수를 없애기위해 출발점을 (15, 15)로 설정하면 편하다.좌표값을 들고 다니는 이유는 동선이 겹쳐서는 안되기 때문에, 다시 말해 이미 방문한 위치는 다시 방문하지 않도록 하기 위해서이다.어떤 한 위치에서 생각했을 때, 동쪽으로 이동한다면 동쪽에서 나오는 모든 확률은 (그 위치에서 발생하는 확률 * 동쪽으로 이동할 확률)이 된다. 이걸 동서남북 모든 방향과 모든 위치마다 반복한다면 정답을 구할..

링크: 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\}..