FFT의 간략한 수학적 이해
해당 글은 빠른 이산 푸리에 변환(FFT)이 가능한 수학적 내용을 위주로 서술합니다. 따라서 푸리에 변환 및 역변환을 빠르게 수행하는 Cooley-Tukey 알고리즘 등에 대해서는 다루지 않습니다.
합성곱(Convolution)연산은 함수를 입력받고 연산된 함수를 반환한다. 이는 입력된 함수의 특징을 추출할 수 있는 함수를 얻기 위해 사용되며, 원하는 특징을 추출할 수 있는 또 다른 함수가 합성곱 연산에 사용된다. 합성곱을 수행하는 방법 중 푸리에 변환은 가장 유명하다.
푸리에 변환은 오일러 공식(Euler’s formula)을 통해 알 수 있는 $\exp{x}$ 함수의 복소평면에서의 특징을 이용한다. 이런 특...
P-NP 문제
해당 글은 “컴퓨터가 풀기 쉬운 문제와 어려운 문제의 경계”라는 제목으로 제출한 “수학과 문명” 과목의 과제물을 수정한 것이다.
1. 서론
튜링 머신과 같이 작동하는 컴퓨터는 인간이 개발한 알고리즘에 맞추어 주어진 데이터를 빠르게 처리하여 결과를 얻어낼 수 있는 능력을 가지고 있다. 즉, 컴퓨터는 “계산 가능한 문제” 들을 해결할 수 있는 능력을 가지고 있다는 것이다. 일상 속에서도 목적지 까지의 최단 거리, 성적 순으로 정렬하기, 단어 검색하기 등의 문제를 빠르게 해결한다.
하지만 컴퓨터가 아무리 빠르다 해도 처리하기 어려운 문제들이 있다.
N개의 물건이 있고, 각 물건에는 무게와 가치가 정해져 있다...
2017 중앙대학교 프로그래밍 경진대회(CPC) 솔루션
해당 문서는 교내 알고리즘 소모임에서 발표한 내용이다.
중앙대학교 문제들은 형식적(무엇을 물어보기 위한 것인지 쉽게 알 수 있음)인 느낌이 들어서 대부분 쉬운것 같다.
A. 신용카드 판별 (BOJ 14726)
16개의 숫자로 구성된 문자열이 주어졌을 때, 다음을 수행하라.
신용카드의 16자리 숫자에서 맨 우측 수부터 세어 홀수 번째 수는 그대로 두고, 짝수번째 수를 2배로 만든다.
2배로 만든 짝수 번째 수가 10 이상인 경우, 각 자리의 숫자를 더하고 그 수로 대체한다.
이와 같이 얻은 모든 자리의 수를 더한다.
그 합이 10으로 나뉘면 “정당한 번호”(유효)이고 그렇지 않으면 “부당한 번...
Mr.Robot Final Season!
오늘 오랜만에 r/MrRobot reddit에 접속했다가 다음을 발견했다!
Saw on my morning commute from r/MrRobot
드디어 Mr.Robot 시즌4가 10월 6일날 나온다는..
아쉽게도 이번이 마지막 시즌이다.. 이전에 den of geek에서 시즌4가 final season일 거라는 내용을 봐서 알고는 있었지만, 여전히 아쉽다.
SCPC 2019 Round2 후기
제 5회(2019) SCPC 라운드2는 7월 6일 오전 9시에서 부터 오후 9시까지 12시간 동안 온라인에서 진행되었다. 벌써 3달 가까이 지났지만, 늦게나마 후기를 남기려고 한다.
1. 소수 수열
제출자: 639
만점자: 587
평균점수/만점: 92/100
내 점수: 100
수학과 프로그래밍을 좋아하는 $A$와 $B$가 $0$이 포함되지 않은 $30,000$ 미만의 자연수를 각각 제시한다. 각 수에 대해 다음의 과정을 통해 점수를 얻는다.
주어진 수에서 한 자리를 골라 해당 자리의 숫자를 제거한다.
제거한 뒤 숫자가 소수이면 첫 번째 과정을 수행한다.
제거한 뒤 숫자가 합...
2020 카카오 블라인드 채용 1차 코딩테스트 후기
2019년 9월 7일에 2020 KAKAO BLIND RECRUITMENT 1차 코딩 테스트가 있었다. 직접 접수를 해서 풀어본 것이 아니라서 onsite인 2차는 풀 수가 없다는 점이 아쉽다.
각 문제에 대한 간단한 설명과 풀이를 작성했다.
문제1.
문자열이 주어졌을 때, 해당 문자열을 특정 단위로 잘라서 런 렝스 부호화(Run-length encoding)을 수행했을 때, 가장 짧은 경우의 길이를 반환하는 문제다.
예를 들어서 다음의 문자열에 대해 생각해 보자.
abcabcabcabcdededededede
이 문자열을 단위별로 자른 결과는 다음과 같다.
2개 단위: abcabcabcabc6de
...
전체 글 15개, 2 페이지