확장 유클리드 알고리즘(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..

2017/10/30 - 파일구조 요약 (1~2장) 2017/10/30 - 파일구조 요약 (3~4장) (이 글) 2017/10/30 - 파일구조 요약 (5~6장)3장. Secondary StorageMagnetic Tape과 Disk, CD-ROM에 대하여 이야기한다.Disk의 구성을 소개한다.Buffer를 사용하여 효율을 높이는 기술을 소개한다.DiskSector : 디스크에 접근하기 위한 가장 작은 단위TrackCylinder (vertical collection of tracks)# of sectors per track. * bytes per sector. 와 같은 식으로 주어진 디스크 용량에서 몇 개의 실린더 혹은 섹터가 있는 지 계산하는 문제가 나올 가능성이 높다.Interleaving 어떤 계수..

2017/10/30 - 파일구조 요약 (1~2장) (이 글) 2017/10/30 - 파일구조 요약 (3~4장) 2017/10/30 - 파일구조 요약 (5~6장)교재 : File Structures: An Object-Oriented Approach with C++ 3th edtion(지금은 절판된걸로 안다)시험 보기 직전에 보려고 정말 간략하게 요약한 키워드 위주의 정리다.파일 구조가 무엇인가? 파일구조란 파일들의 데이터들을 표현하거나 그 데이터에 접근하는 연산들을 관리하는 것의 결합이다. 파일구조는 데이터를 읽고, 쓰고, 수정하는 것이 가능해야한다. 그리고 그것들을 검색하거나 특정 순서로 읽을 수 있어야한다.왜 배우는가?컴퓨터는 데이터를 크게 세 군데에 저장한다.Primary Storage : 메모리S..

사이트를 개발할 때, 외부 STMP를 많이 사용하곤 한다. 그 이유는 안정적인 것도 한 몫 하겠지만, 빠르고 편하기 때문일 것이다. 대표적으로 MailGun도 있고 하지만, 난 SendGrid가 좋았다.Free plan이라도 하루 100통의 메일은 무료로 제공해준다. 가입은 이메일이랑 이름, 사용 목적 등만 작성하면 되는데 Free plan으로 진행하면 카드 등록 절차도 필요없다. 예전에 Node.js에서 외부 메일 서버를 찾다가 SendGrid를 접했는 데, API 사용이 너무 편하고 설명도 잘 되어있어서 그 때부터 애용하고 있다. (링크: node.js에서 SendGrid 사용하기 공식 도큐먼트) 로그인하고 들어가면 아래와 같은 Dashboard가 나온다.최근에 안써서 월별(Mo) 그래프로 캡쳐했는데..