문제링크: 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. 레드 노드의 자식노드 양쪽은 언제나..

확장 유클리드 알고리즘(Extended Euclidian Algorithm)은 유클리드 호제법을 확장한 것이다. $as + bt = gcd(a,b)$을 만족하는 정수 $s$, $t$ 짝을 찾아낼 수 있다. 증명은 생략하고 어떻게 사용하는가를 적어볼까 한다. 초기 조건 $s_0 = 1, s_1 = 0, ~~t_0 = 0, t_1 = 1, ~~r_0 = a, r_1 = b$ 진행 $$ \begin{align} q_i \leftarrow & \lfloor~r_{i-1}~/~r_i~\rfloor & (i \ge 1)\\ r_i \leftarrow & ~r_{i-2} - r_{i-1} \cdot q_{i-1} & (i \ge 2)\\ s_i \leftarrow & ~s_{i-2} - s_{i-1} ..

​중국인의 나머지 정리(CRT; Chinese Remainder Theorem)연립 합동식의 유일한 해를 찾는 정리이다. 예를 들면서 설명과 함께 전개하는 게 가장 이해하기 쉽다. 개념 이해를 위해 연립 합동식이 2개일 때만 생각해보자. $$\begin{cases} x \equiv 3 ~ (mod~ 5)~\dashrightarrow~ (a) \\ x \equiv 4~ (mod~ 7)~\dashrightarrow ~(b) \end{cases}$$ 위 두 합동식 (a), (b)를 모두 만족하는 어떤 정수 $x$는 어떻게 찾을 수 있을까?어떤 수 $x$는 위 두 합동식을 모두 만족하기 위해 (a), (b)의 해를 각각 $A_1$, $A_2$라고 하면 아래의 형태가 된다.$$ x \equiv A_..

예전에 SICP 수업을 들었을 때, 참고한 링크이다. 수업 때 언어는 Scheme이었고 IDE는 DrRacket (다운로드 링크)를 썼다. 교재 번역/인사이트: 링크 (개정된 거 같다)아마존: 링크 함수형 프로그래밍 언어를 기초부터 가르치는 데, 되게 새로운 패러다임이라 어려우면서 재밌었다. 일단 반복문이 기본적으로 재귀의 형태였던걸로 기억한다.. 수업 후반에는 각 좌표를 리스트로 저장해서 그림을 출력하는 게 과제인데, 중간 중간에 예제들이 이렇게 생겼다. 출처: http://valvallow.blogspot.kr/2010/01/sicp.html 하나의 그림을 객체처럼 다뤄서, 해괴하고 괴랄한 자신만의 특별한 모양을 만들으라고 하셨는데 기본 예제가 너무 심심해서 심슨을 그렸다. (드라이브를 정리하다가 우..

Maze Generator in C++ 2학년때 학교 수업으로 MFC 배우고 방학 때 심심하고 해서 미로 생성기를 만들자! 했다. (사실은 배운게 C++, MFC 밖에 없어서..)윈도우 7 + Visual Studio 2012 로 개발한 걸로 기억한다.미로는 생각보다 단순하게 만들 수 있다. 상/하/좌/우 중 랜덤하게 하나씩 선택해서 DFS를 하면 된다. DFS를 마치고 돌아가면서 백트래킹으로 방문한 셀들을 방문할 때 진행했던 방향의 칸을 닫으면 된다. 각 셀을 4비트로 나타내면 벽의 상태를 저장할 수 있다. 백트래킹 하면서 진행한 방향에 따라 해당 셀의 비트를 적절히 건드리면 쉽다.나중에 경로 찾을때도 벽의 존재를 비트의 상태로 확인하면 편하다. 아래에 코드 첨부 랜덤으로 칸을 누비면서 미로를 만들어야..

2017/10/30 - 파일구조 요약 (1~2장) 2017/10/30 - 파일구조 요약 (3~4장) 2017/10/30 - 파일구조 요약 (5~6장) (이 글)5장. 레코드 관리 Record length레코드의 길이는 field의 크기와 상관있다. 따라서 Access, fragmentation, 구현의 정도를 보고 적절한 구조를 선택한다.header (meta-data)파일에 관한 전반적인 정보(수정 시간, 레코드의 수 등)를 기술한다. 보통 파일의 앞쪽에 적는다.IO Buffer Class MethodsWrite: 파일에 record를 적는다.Read: 파일로부터 record를 읽는다.WriteHeader: 파일의 앞에 “IOBuffer”라고 적지만, 어떤 버퍼로 풀어야하는가를 의미한다.ReadHead..