Joonas' Note

제목 그대로, 트리의 노드 순서를 다시 정리하여 구간으로 표현하는 것이다. 그림으로 보면, 트리의 구조와 왼쪽과 같았다면, 각 트리의 번호를 오른쪽처럼 변경하는 것이다. 순서는 전위순회(pre-order)로 탐색하면서 번호를 붙이면 된다. 이게 왜 필요할까? 제목에서 이미 말한거지만, 구간으로 표현하는 것이 더 용이할 때 사용한다. 특히 트리를 세그먼트 트리나 펜윅 트리 등의 구간합/부분합으로 변형하여 문제 해결이 필요한 경우이다. 노드의 번호를 위처럼 정리하면, 각 노드가 포괄하는 노드는 항상 확실하다. "자신의 번호 + 그 노드의 서브 트리(들)의 크기"가 포함할 수 있는 자식의 마지막 번호와 같다. 그럼 트리를 일렬로 펴서 다룰 수 있다. 코드 관련 문제 (+스포일러)BOJ 2820 - 자동차 공장..

문제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/16964풀이문제의 가장 큰 힌트는 입력된 그래프의 모양이 트리라는 점이다. 즉, 사이클이 없다. 올바른 DFS 방문 순서가 되기 위해서는 자식이 부모보다 먼저 나오는 경우가 있어서는 안된다.이 특징을 살리면, 어떤 순서 \(i\)번째에 등장하는 노드 \(x\)의 깊이는 어떤 순서 \(i\)+\(x\)의 서브트리의 크기까지는 전부 그 노드의 자식이라는 점이다. 위 그림처럼 입력이 주어졌다고 해보자.여러 DFS 방문 순서가 가능하겠지만, 그 중 하나인 [1, 3, 5, 8, 6, 4, 7, 9, 2]의 순서를 예로 들자면 어떤 \(i\)번째 순서에 있는 노드 \(x\)는 자신의 서브트리의 크기만큼 다음 순서가 자신의 형제 노드이다.2번째 순서..

링크: https://www.acmicpc.net/problem/15683문제모든 조합을 살피고 시뮬레이션을 할 수 있어야 하는 문제. CCTV가 보고 있는 방향을 하나씩 선택하면서, 모든 방향이 결정됐을 때 시뮬레이션 후 사각 지대의 개수를 구한다. 모든 조합을 살피다가 사각 지대의 개수가 최소가 되는 조합에서 정답을 출력하면 된다. CCTV의 방향을 처리하는 시뮬레이션이 벽에서 막힌다거나 지도 밖으로 넘어가는 것 외에도 은근히 신경쓰이는 게 많다. 오목이나 틱택토류의 코드를 작성한 경험이 있다면 수월할 듯 상세한 부분을 제외하면 개략적인 구조는 이렇다. 여러 방향을 한번에 담아 처리하기 위해 비트로 각 방향을 표현했다. 비트가 겹치는 것을 확인하는 건 비트 AND연산으로 쉽게 구현할 수 있다. 예를 ..

몇년 전부터 구현해보고 싶던 거였는데, 이러다가 대학을 졸업 전에 못할까봐 날잡고 했다. 근데 1시간만에 끝나버린건 함정hexagrid에 대한 구현을 다루고 있으며, 실제 개발에서는 어떻게 쓰이는 지 정확히 모른다. 그저 "이렇게 하면 되겠지?"라는 생각에서 출발했음을 알린다.2분 요약https://youtu.be/vxnnPselHKI 육각형을 하나의 칸으로 사용하는 벌집 형태의 2차원 평면을 게임에서 많이 찾아볼 수 있는데, 대표적으로 시드마이어의 문명 시리즈가 그렇다.개인적으로 이 벌집 모양을 많이 좋아하는 편인데, 매번 어떻게 구현했을까? 생각만 하고 정작 고민을 해보지 않았었다. 그러다 우연히 생각이 번뜩나서 개발 과정을 녹화해보면 재밌겠다 싶어서 진행했다.녹화 중간에 (엄청 빠르게 지나가지만....