드디어! 백준 골드를 달성했습니다. (짝짝짝) 42 서울 라피신을 마치고 알고리즘에 맛들리기도 하고 알고리즘, 자료 구조에 대한 이해의 필요성을 느껴서 매 시험기간 목표던 백준 골드를 찍어보자.. 해서 도전하게 되었네요. 강의를 보면서 공부를 진행하고 언어도 바꾸었습니다. C++의 STL 등을 사용하면 쉽게 구현할 수 있는데 그 동안 C만 사용해왔던 제가 바보같더군요. 더 높은 난이도에 가서는 C++ 로 된 라업들이 많기도 하고,, 다들 C++로 사용하는 걸 보니 자료구조를 문제 마다 일일이 구현하는 것도 참 비효율적이어서 저도 C++로 옮겼습니다. 한 동안 문제 푸는데에 집중했는데, 이제 풀이도 올리면서 풀어봐야겠네용 ~_~
2023/01/09 부터 2023/02/03 까지 길다면 길지만 짧다고 느꼈던 피신을 마쳤다. 9기 1차의 OT는 1월 8일?에 진행되었던 것 같다. 피신은 C11까지 C10을 제외하고 모두 100점으로 통과하였고, 파이널에서 기어코 만점을 받았다. 평가 포인트가 왜이리 많냐고 할 수도 있는데 마지막이 다가올 때 풀이 다 차서 기부가 안되더라.. 9기 1차는 어떻게 보면 황금기수였다. 다른 (피신)리트자들에 의하면 이렇게 빠르게 진도를 나간 기수가 없었다고 했다. 매일매일을 반복하며 일상으로 녹아들던 피신이 이제는 끝이라는게 기분이 오묘하다. 누군가 내게 피신을 추천하느냐고 묻는다면 나는 추천할 것이다. 물론 그 사람의 상황에 따라 다르겠지만. 나에겐 피신이 사회생활의 첫 경험이었다. 피신에서는 다양한 ..
1월 9일 라피신 첫 날이다. 전날 OT로 만났던 사람들 덕분에 더 잘 적응하고 있다. 물에 빠져서 허우적대다보니 적응이 된다. 아직 모든게 완벽하진 않지만.. 오늘은 오전 10시쯤 서초 클러스터에 도착해서 밤 12시쯤 귀가했다. 14시간동안 있었네.. 물에서 허우적대며 경험을 쌓아가는건 당장에 필요없어보이지만 언젠가 수영을 할 수 있게 하리라 생각된다. 첫 날임에도 이것저것.. 재밌었다. 내일(오늘)은 더 바쁘겠지. 한 달간 라피신에만 집중하게 되었다. 다른 일들을 모두 중단하고 오직 하나에만 집중하는 것이 얼마만이던가. 그래서 더 즐겁다. 내가 이 일에 몰두하고 있다. 한 달간 블로그 글은 뜸할 것 같다. 라피신이 끝나고 발전할 내가 기대된다. 끝나면 후기를 올려봐야지.
개념 설명 모듈러 연산 2 우리는 지난 문제로부터 모듈러 p를 고를 것입니다. 그리고 p가 소수일때의 경우로 제한합니다. 정수 모듈러 p는 체(field) $F_p$를 정의합니다. ! 만약 모듈러가 소수가 아니라면, 정수 모듈러 n 집합은 환(ring)을 형성합니다. 유한체 $F_p$는 정수 $\{0,1..., p-1\}$의 집합이며, 덧셈과 곱셈 모두에서 $a+b=0$, $a\times b = 1$과 같이 집합의 모든 원소 a에 대한 역원이 존재합니다. ! 덧셈과 곱셈의 항등원(identity element)는 서로 다릅니다! 항등원은 연산자와 함께 동작할 때 아무것도 수행하지 않아야 합니다. : $a+0 = a$ : $a \times 1 = a$ $p = 17$을 선택한다고 가정합시다. $3^{17}..
개념 설명 모듈러 연산 당신이 몸을 숙이고 암호학자의 노트를 본다고 상상해보라. 여백에 다음과 같은 참고 사항이 표기되어 있는 게 보인다. 4 + 9 = 1 5 - 7 = 10 2 + 3 = 5 처음엔 그들이 미쳤다고 생각할지도 모른다. 이것이 오늘날 많은 데이터유출의 이유라고 생각될 수도 있겠지만, 이것은 모듈러 12에 대한 모듈러 연산에 지나지 않는다. (비록 다소 엉성한 표기법일지라도 말이다.) 당신은 모듈러 연산을 사용해본 적이 없다고 할 수도 있겠지만, 당신은 시간을 말하는 법을 배운 이후로 이런 종류의 계산을 해오고 있다. (위 식을 다시 보고 시간을 더하는 것에 대해 생각해보라.) 형식적으로 "시간 계산"은 합동식 이론에 의해 설명된다. 우리는 두 정수가 $a \equiv b \bmod m$..
https://thfist-1071.tistory.com/entry/C-%EC%96%B8%EC%96%B4-%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C-%ED%98%B8%EC%A0%9C%EB%B2%95-%EC%A6%9D%EB%AA%85-%EC%9E%AC%EA%B7%80%ED%95%A8%EC%88%98%EB%A1%9C-%EA%B5%AC [C 언어] 유클리드 호제법 증명과 재귀함수 구현 유클리드 호제법에 관해서 한 번 글을 썼어야 하는데 이제야 써 보네요. 유클리드 호제법은 최대공약수(GCD : Greatest Common Factor)을 구하는 알고리즘입니다. 여담으로 최소공배수는 (두 수의 곱/gcd) thfist-1071.tistory.com 알고리즘, 자료구조 카테고리에 포함되어 ..
개념 설명 확장된 유클리드 알고리즘 a와 b를 양의 정수로 하자. 확장된 유클리드 알고리즘은 다음과 같은 정수 u, v를 찾는 효율적인 방법이다. a*u + b*v = gcd(a,b) ! 나중에 RSA를 해독하는 방법을 배울 때, Public exponent의 modular inverse를 계산하기 위해 이 알고리즘이 필요할 것이다. 두 소수 p = 26513, q = 33221을 사용하여 다음과 같은 정수 u, v를 구한다. p*u + q*v = gcd(p, q) u와 v중 낮은 숫자를 플래그로 입력한다. ! p와 q가 소수라는 것을 알고, gcd(p, q)가 무엇이라고 생각되는가? 확장된 유클리드 알고리즘에 대한 자세한 내용은 아래 페이지를 참조하자. http://www-math.ucdenver.ed..
Modular Arithmetic의 시작 개념 설명 (Greatest Common Divisor을 최대공약수라고 한다.) 최대공약수(GCD)는 두개의 양의 정수 (a, b)를 나누는 가장 큰 약수로 알려져있다. a=12, b=8의 경우 우리는 a: {1, 2, 3, 4, 6, 12}, b: {1, 2, 4, 8}로 약수를 계산할 수 있다. 이 둘을 비교하면 우리는 gcd(a, b) = 4라는 것을 알 수 있다. 이제 a=11, b=17을 예로 들어보자. a와 b는 모두 소수이다. 소수는 자기 자신과 1을 약수로 가지므로 gcd(a, b) = 1이다. 우리는 임의의 두 정수 a, b에 대해 gcd(a,b) = 1이면 a와 b는 서로소(coprime integers)라고 말한다. a와 b가 소수라면(a !=..
