본문 바로가기

두들낙서/프로그래밍5

[노트] 모든 약수를 구하는 알고리즘은 O(sqrt(n))이다. 학원 학생들이 약수를 모두 찾는 (또는 약수의 합, 개수를 구하거나, 소수 판별 등등) 코드를 어떻게 짜는지 살펴보면, 백이면 백 \(O(n)\) 알고리즘을 사용한다. 하지만 어떤 수의 모든 약수를 구하는 일은 \(O(\sqrt n)\) 시간만에 할 수 있다. 대부분의 사람들이 이 사실을 모르거나 알더라도 적극적으로 이용하지 않는 것 같아 적어본다. 우선 다음 두 정리를 살펴보자. 약수랑 제곱근이 뭔지만 안다면, 직관적으로 "그렇겠구나" 정도는 생각할 수 있는 것들이다. 1. 자연수 \(d\)가 자연수 \(n\)의 약수이면, \(n/d\)도 \(n\)의 약수이다. 2. 양수 \(d\)와 \(n\)에 대해 \(d\le\sqrt n \Longleftrightarrow n/d\ge\sqrt n\). 1 증명).. 2021. 4. 23.
[노트] 최소공통조상(LCA) 찾기 문제: www.acmicpc.net/problem/11438 알고리즘을 나름 오랫동안 공부해왔던 나도 그래프와 트리 관련 문제는 많이 풀어보지 못한 것 같아, 요즘 가끔 생각날 때마다 관련 알고리즘들을 찾아보고 있다. 최근에는 LCA를 찾는 효율적인 알고리즘을 찾아보았는데, 경로에 대한 정보 없이 간단히 LCA만 딱 찾아내고 싶을 때는 복잡한 알고리즘이나 자료구조 없이 아주아주 간단한 테크닉으로도 가능하다는 것을 알게 되어 짧게 적어본다. 다음 사실을 관찰하는 순간 게임이 끝난다. 관찰: 노드 a와 b의 LCA는 a와 b 사이를 Euler tour로 방문하는 동안 지나친 노드들 중 가장 상위에 있는 노드이다. (솔직 고백을 하자면, Euler tour of tree라는 개념도 이걸 배우면서 처음 알게 되.. 2021. 3. 1.
PyOpenGL로 3차원 색상구(球) 만들기 1편 - HSV와 HSL 얼마전 갑자기 아이디어가 떠올라서 만들어본 프로젝트. 3차원이기 떄문에 색상환은 아니고 색상구(球)라 하는 게 맞을 듯하다. 결과물은 대충 이렇게 생겼다. 일반적인 컴퓨터 모니터는 빨강, 초록, 파랑 LED를 사용하기 때문에, 컴퓨터에서 색을 저장할 때 보통 빨강, 초록, 파랑 LED의 밝기, 즉 RGB로 색을 나타내곤 한다. 각막의 원뿔세포가 빨강, 초록, 파랑에 해당하는 파장의 빛에 반응해 뇌로 신호를 보내면 뇌가 어떤 색깔인지를 인식한다. 그런데 대부분의 사람들은 색깔을 단순한 RGB 정보로 인식하는 데 익숙하지 않다. '빨간 빛 50%, 초록 빛 30%, 파란 빛 10%가 섞인 색'이라 말하면 그래픽이나 웹 디자인 쪽에 일하는 사람이 아닌 이상 어떤 색인지 감을 잡기 힘들다. 참고로 그 색은 이렇.. 2020. 2. 29.
[C/C++] 정수를 뒤집는 5가지 방법 목표는 간단하다. 입력 받은 정수를 거꾸로 뒤집은 정수를 출력하면 된다. 물론 뒤집었을 때 0으로 시작하는 경우는 0을 출력하지 않는다. 입력 예 1024 출력 예 4201 입력 예 12300 출력 예 321 1. 문자열 변환 후 뒤집고 정수 변환 (C++ 스타일) 가장 직관적이고, 단순한 방법이다. string 타입을 사용한다. 문자열로 변환하기 위해서는 to_string 함수를, 정수로 변환하기 위해서는 atoi 함수를 쓴다. atoi 함수는 원래 에 들어 있으나 웬만한 라이브러리에 이미 include 되어 있다. #include #include using namespace std; int rev(int n) { string s = to_string(n); reverse(s.begin(), s.end.. 2019. 6. 2.
[C++] 영어에서 인접한 두 글자의 빈도수 구하기 단일 치환 암호를 풀 때 빈도수를 이용하면 효과적으로 해독할 수 있다. 그런데 한 글자의 빈도수를 세는 것만으로는 부족할 때가 많다. code.org에서는 단일 치환 암호를 알파벳 치환을 실시간으로 바꾸며 해독해볼 수 있다. 위의 사진은 원본 암호이고, 글자들을 빈도순으로 나열하고 나서 영어의 알파벳 빈도 순서와 1:1로 치환하면 다음과 같이 된다. Yah ogt ni tse giwsahtel bawkcatehr oy tse giyarsnoiabde eil oy tse certehi rmnhad ahu oy tse Padajf dner a ruadd gihepahlel feddoc rgi. 전혀 이해할 수가 없다. 이때 우리는 많이 쓰이는 특정 단어들의 패턴을 유추해서 그에 맞게 해독할 수가 있다. 예를.. 2019. 2. 10.

티스토리툴바