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

[이전 블로그로부터 글 옮김]8/24(목)~25(금) 동안 진행된 삼성 대학생 우수 프로그래머 캠프를 다녀왔다. 캠프 참가 여부를 물어보는 별도의 메일이 왔었고, 대상은 S/W 역량테스트 pro 통과자 또는 타 대회 입상자들이라고 하더라. 좋은 기회인 것 같아서 큰 고민없이 일찍 신청했다.후기를 어디까지 자세히 적어야할지 모르겠어서, 그냥 의식의 흐름대로 적어볼까 한다. 전반적으로 장소의 이동이 잦았고, 회사의 분위기 설명이나 회사 소개를 자주 들었다. 그리고 밥은 아쉽지 않을 만큼 맛있었다.양재역에서 모여서 출발하는지라, 전주에서 출발하긴 꽤 먼 거리였기에 출발 시간을 정하기 애매했다. 같이 가는 친구랑 끝까지 고민하다가 친구는 24일 아침, 나는 23일 저녁에 출발하기로 했다. 24일 11시에 양재역..

[이전 블로그로부터 글 옮김]2018 카카오 블라인트 채용 테스트 1차에 참가했다. 요즘엔 기업들이 programmers.co.kr 같은 플랫폼을 사용하여 대회 또는 시험을 진행하는 같다. 제출이나 문제 설명은 codecademy 와 비슷한 방식이고, 문제를 제출하고 검사하는 방식은 TopCoder와 유사하게 class 나 어떤 함수의 반환으로 채점한다.1차 온라인 테스트는 https://programmers.co.kr/competitions/35/welcome-kakao 또는 https://welcomekakao.com 에서 진행되었다.5시간동안 총 7문제가 주어졌었는데, 문제는 난이도순이 아닌 것 같았다.1,2,3,6,7,5번 순서대로 풀었었고, 4번은 읽고 나니 테스트 종료 15분 정도 남았었다. ..

링크: https://www.acmicpc.net/problem/2887 모든 행성을 터널로 연결할건데, 그 비용의 합이 최소가 되게 만드는 최소 스패닝 트리 문제이다. 문제는 \(N\)이 너무 커서, 행성 사이의 간선을 전부 살피는 건 힘들다는 것이다. 두 행성 A와 B의 거리를 \(min(|x_A - x_B|, |y_A - y_B|, |z_A - z_B|)\) 로 정의했기 때문에 어떤 행성에서 가장 가까울 행성의 후보가 확 줄어든다. 행성 A에서 가장 가까운 행성 B는 \(|x_A - x_B|\)가 최소이거나 \(|y_A - y_B|\)가 최소이거나, \(|z_A - z_B|\)가 최소인 것 3개 중 하나이다. \(x, y, z\)마다 정렬하면 된다.

링크: https://www.acmicpc.net/problem/2718[이전 게시글로부터 글 옮김]2x1 크기의 타일로 4xN 크기의 타일을 채우는 경우의 수를 구하는 문제이다.문제를 작은 문제로 쪼개야하는 데 발상보다는 과정이 쉽게 떠오르지 않아서 해결하는 데 오랜 시간이 걸렸다.2xN 타일 크기의 문제와 똑같이 왼쪽부터 1줄씩 채워나가면서 완성해나간다. 하지만 이 문제는 높이가 4N이기 때문에 1줄을 채울 때 여러 개의 경우가 나온다. [그림 1] 한 줄의 상태를 비트로 표현할 때의 정수 외의 경우(1010 이나 0001 등의 형태)는 나올 수 없다. 왜냐하면 "이전의 줄의 모든 칸은 채워져있다."라는 가정에서 나타나는 상태이기 때문이다. 이 가정이 성립하지 않으면 타일은 채워질 수 없다. [그림 ..

문제링크: https://www.acmicpc.net/problem/9373복도에 센서들이 있고 센서들을 피해 복도를 통과할 수 있는 가장 큰 원의 반지름을 구하는 문제이다. 복도의 너비가 주어지고, 각 센서들의 좌표 x, y와 반지름 r이 주어진다.처음에는 센서와 센서 사이에 존재할 수 있는 원들로 어떻게 MST를 잘 만들면 되지 않을까했는데, 가장 큰 원의 반지름을 구하기가 힘들었다. 하루 정도 계속 틀리고 고민하고를 반복하다 솔루션을 찾아봤다. 솔루션을 보자마자 와 이게 뭐지 싶었다. 이렇게 풀 수도 있구나 신기했다.풀이최소 신장 트리 문제는 맞았고 원과 원 사이의 끼인 원으로 어떻게 하는 것도 맞았다. 근데 최종형태가 이런 식이었다.양쪽 벽을 큰 집합이라고 생각하고 두 집합이 연결될 때까지 MST..

문제 링크 : http://119.201.123.184/30stair/sumofinte/sumofinte.php 정답 코드 중에서 실행 시간이 644ms로 1위다. 이럴 날이 별로 없어서 캡쳐 주륵..문제수열의 길이 N과 질문의 수 Q가 주어지는 데, 둘 다 N, Q sum = L.sum + R.sum

Red Black Tree란, Binary Search Tree의 일종으로 입력 순서에 따라 BST가 한쪽으로 기울어지는(skewed) 걸 막기 위해 스스로 균형을 맞추는(self-balanced) 트리이다. 트리가 skewed하면 연결리스트랑 다를 바 없어서 \(O(N)\)의 시간복잡도를 갖기 때문이다. 균형을 맞춘다는 것은 어떤 노드의 (자신 아래의) 모든 리프까지의 거리가 최대한 같도록 조정한다는 말인데, 균형을 잘 맞추면 트리의 깊이가 \( \log_{2}{N} \)이기 때문에 빠르게 검색할 수 있다. 레드블랙트리는 아래의 규칙을 만족하도록 조정된다. 1. 노드는 레드 혹은 블랙 중의 하나이다. 2. 루트 노드는 블랙이다. 3. 모든 리프 노드는 블랙이다. 4. 레드 노드의 자식노드 양쪽은 언제나..