컴퓨터가 실수를 연분수 표현(continued fraction)으로 나타내는 방법

1. 유리수의 continued fraction continued fraction은 실수를 수렴하는 유리수의 수열로 표현하는 것이다. 이는 problem solving에서 유용할 수 있는데, 쉽게 계산될 수 있으며, 실수의 최적 유리수 근사를 찾는데 효과적으로 사용될 수 있어서 그렇다. 게다가 정수론에서 유용하게 사용되는 유클리드 알고리즘과 연관되어있다. 어떤 정수 $a_{0}, a_{1}, ..., a_{k}$에 대하여, $a_{1}, a_{2}, ... , a_{k}$가 1이상의 자연수일때, $$r = a_{0} + \frac{1}{a_{1} + \frac{1}{... + \frac{1}{a_{k}}}}$$ 를 유리수 r의 연분수 표현(continued fraction)이라고 부른다. 이를 r을 간단하..

• format_list_bulleted 대수학
• · 2023. 9. 20.
• textsms

z - function 활용법1 -패턴이 문자열에서 몇번이나 나왔는가? 찾는법-

1. 부분문자열 검색 z-function의 대표적인 활용으로 특정한 문자열 t에 패턴 p가 몇번이나 존재하는지 찾아낼 수 있다. 이를 위해 새로운 문자열 s = p + # + t라는 문자열을 만들자. 여기서 #은 p와 t를 구분하기 위한 문자로, p,t 어디에도 등장하지 않는 문자여야한다. 이제 s에 대한 z-function을 계산하자. [0,len(t)-1]의 임의의 i에 대하여... z[i+len(p)+1]이 len(p)와 같다면, t의 i번째 위치에 p가 1번 등장한 것이다. 문자열 t 위에 있는 위치인 i+len(p)+1에 대하여.. z[i+len(p)+1]은 s와 일치하는 가장 큰 공통 접두사의 길이로, 이게 len(p)라는 것은 s의 접두사인 p의 길이와 일치하기 때문이다. 2. 연습문제 17..

• format_list_bulleted 문자열 알고리즘
• · 2023. 9. 18.
• textsms

문자열과 접미사의 가장 긴 공통 접두사의 길이를 찾는 z 알고리즘 배우기

1. z - function 길이 n인 문자열 s에 대하여 z[i]는 s의 i번째 접미사 s[i,i+1,...]과 s와의 최대 공통 접두사의 길이를 말한다 정의에 의하면 z[0]는 s와 s의 최대 공통 접두사의 길이로 s 그 자체의 길이 n이 될텐데 일반적으로 잘 정의하지 않는다. z[0] = 0으로 정의하기도 하고 문제에 따라 필요하다면 z[0] = n으로 정의하기도 한다. 예를 들어 'abacaba'에 대하여... z[1]은 'abacaba'와 'bacaba'의 최대 공통 접두사의 길이로... 공통 접두사가 존재하지 않으니 0 z[2]는 'abacaba'와 'acaba'의 최대 공통 접두사의 길이로 'a'가 있으니 z[2] = 1 z[3]은 'abacaba'와 'caba'의 최대 공통 접두사의 길이로..

• format_list_bulleted 문자열 알고리즘
• · 2023. 9. 17.
• textsms

그리디 기초 테크닉 익히기2 - 특별한 정렬, 사고 전환, 상쇄, 올바른 순서 부분문자열 몇개 있는지, 원소 상태 바꾸기-

1. 문제1 3216번: 다운로드 (acmicpc.net) 3216번: 다운로드 첫째 줄에, 다운로드 시작하고 몇 초 후에 노래를 듣기 시작하면, 끊김 없이 들을 수 있는지 출력한다. 그러한 시간이 여러개라면, 가장 빠른 것을 출력한다. www.acmicpc.net 2. 풀이 생각보다 어렵더라..? 다운로드 하면서 음악 재생시간을 누적해오고.. 어느 순간에 음악을 재생시키면.. 모든 다운로드 시간을 커버하면서 음악이 연속으로 흐를수 있게 할려면.. 다운로드가 언제 끝나는지 알아야하는데.. 이게 가능한가?? 리스트를 구성하면서 미리 더해서 남은 시간을 구해놓기도 하고.. 그리디의 기본인 정렬을 해서 짧은 시간부터 다운로드 해나가야하나? 생각은 했는데 정해진 순서대로 다운받아야하기 때문에.. 정렬은 할 수 ..

• format_list_bulleted 그리디 알고리즘
• · 2023. 9. 13.
• textsms

제켄도르프 분해 응용 - 정수를 피보나치 수의 합과 차로 표현하기

1. 문제 8229번: Fibonacci Representation (acmicpc.net) 8229번: Fibonacci Representation The Fibonacci sequence is a sequence of integers, called Fibonacci numbers, defined as follows: Fib0=0, Fib1=1, Fibn=Fibn-2+Fibn-1 for n > 1 Its initial elements are: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... Byteasar investigates representations of number www.acmicpc.net 2. 풀이 어떤 정수를 최소 개수의 피보나치 수만을 사용해서 합과 차로 표현..

• format_list_bulleted 그리디 알고리즘
• · 2023. 9. 13.
• textsms

CCW를 이용한 선분 교차 판정 알고리즘 배우기

1. 선분 교차 기본형 두 선분 (A,B)와 (C,D)가 주어질때 두 선분이 교차하는가? 교차하지 않는가? 직선의 방정식 구해서.. 교점을 구해보고.. 기울기 비교해보는 등 여러 방법을 사용해볼 수 있지만.. 가장 일반적인 방법은 CCW를 이용하는 것이다. https://deepdata.tistory.com/955 기하학의 사칙연산인 CCW(Counter-ClockWise) 알고리즘 배우기 https://rebro.kr/10 CCW (Counter-ClockWise) - (1) CCW (Counter-ClockWise) - (1) CCW 알고리즘은 수 계산에서의 사칙연산처럼, '기하 알고리즘'에서 가장 기본적인 알고리즘이다. 즉, 기하 알고리즘에서 매우 자주 이 deepdata.tistory.com 다음..

• format_list_bulleted 기하학
• · 2023. 9. 12.
• textsms