Sign in Subscribe

Computer Science

Pollard's Rho Algorithm

Pollard's Rho Algorithm

❗이 글에는 Miller-Rabin 소수판별법에 대한 선행 지식이 필요합니다. 혹 이에 대해 잘 모르는 독자들은 임한결 작가의 Miller-Rabin 소수판별법에 관한 글을 읽어보는 것을 추천합니다. Introduction 소인수분해. 개념만 들어서는 중학교 1학년때 잠시 배우고 지나간, 굳이 수학의 길로 들어서지 않는다면 영원히 모르고 살아도 될 것 같은 느낌이 드는 개념이다. 혹여나 이런 생각을 하는

String Matching Algorithms

String Matching Algorithms

1.Introduction "나는 제발 제발 제발 제발 제발 자고 싶다"라는 문장에서 "제발"의 위치를 모두 찾아보자. "나"를 position \(0\)라고 했을때 \(3, 6, 9, 12, 15\)에 있다는 것을 알 수 있다. 위에는 농담이고, 아무튼 위와 같은 작업을 수행하는 것을 String Matching이라고

Shortest path problem

Shortest path problem

Introduction Shortest path problem이란 무엇일까. 한글로 직역하면 최단거리 알고리즘이 되는 이 알고리즘은 이름 그대로 어떤 그래프에서 위치간의 최단 거리를 찾는 알고리즘이다. 말만 들어서는 체감하기 힘들지만, 최단거리 알고리즘은 우리의 내비게이션부터 네트워크 시스템, 물류 배송 등 여러 분야에서 이미 빠질 수 없는 필수 기술로 자리잡았다. 하지만 그렇다고 해서 최선의 최단거리 알고리즘을 구현하는

RSA, and Bézout's Numbers

RSA, and Bézout's Numbers

Introduction 최근 인터넷을 돌아다니다 보면 이런 뉴스를 심심찮게 볼수 있다 양자컴퓨터가 벌써 RSA 암호화 알고리즘을 깼다고? RSA는 뭐고, 이건 양자컴퓨터랑 무슨 관련이 있는 것일까? 양자컴퓨터 부분은 담에 알아보고, 우선은 RSA가 뭔지, 이것은 어떻게 작동하는지를 알아보고 증명해보자. 암호화의 기본 원리 내가 10m 떨어진 친구한테 abcd라는 비밀, 즉 Secret를 전해야 한다고 생각하자.

The Grundy Number

The Grundy Number

Introduction 어린 시절을 한국에서 보낸 독자라면 아마 '배스킨라빈스 31게임'에 대하여 들어봤을 것이다. 그래도 모르는 사람을 위해 간략히 설명하자면, 이 게임의 규칙은 다음과 같다 : 배스킨라빈스 31 게임은 숫자 1부터 시작하여 번갈아 가며 숫자를 1개에서 3개까지 외치고, 31을 먼저 말하는 사람이 지는 게임이다. 자, 필자가 이제 여러분을 위해 매우

CCW

CCW

개요 오늘은 CCW 알고리즘을 소개하려고 한다. 정말 정말 간단한 알고리즘이라서 길게 설명할 필요도 없다. 바로 시작하자. CCW? 일단 CCW가 뭘까? CCW는 counter clockwise라는 뜻이다. 흠... 무슨 말인지 잘 이해가 되지 않을 수도 있다. 간단하게 설명하자면 점 사이의 위치 관계를 알아내는 알고리즘이다. 좀 더 자세히 알아보자. 평면 위에 점 3개가 있다.

Utilization of The Runge-Kutta Method - Part 2

Utilization of The Runge-Kutta Method - Part 2

Part 1 was written a while ago, so for some readers this may be first post they are encountering on this topic. In this case, I suggest reading part 1 first. Introduction In the last post, we dived into the basic terms and proofs for the Runge-Kutta method. In this