홈

오늘 진행된 2022 KAKAO BLIND RECRUITMENT 1차 코딩테스트에 참여하고 출제된 문제 7개에 대한 풀이를 남긴다. 문제1. 각 유저의 id와 각 유저가 신고한 정보, 그리고 정지 기준이 되는 신고 횟수 $k$가 주어진다. 한 유저가 0명 이상의 다른 유저를 신고할 수 있고, 동일한 유저를 여러번 신고할 시 1회 신고한 것으로 처리되며, $k$번 이상 신고를 당한 유저는 정지되고 해당 유저를 신고한 유저들에게 이메일이 전송된다. 정지당한 유저도 신고를 할 수 있을 때, 각 유저별로 이메일을 받은 횟수를 반환하는 문제다. 풀이 각 유저에 대해서 신고한 유저 아이디 목록을 unique하게 만든 ...

제 7회(2021) SCPC 라운드1운 7월 16일 오후 9시에서 부터 17일 오후 9시까지 24시간 동안 온라인에서 진행되었다. 결과 16일 오후 6시에 퇴근하고 피곤해서 대회에 바로 참여하기 어려웠다. 때문에 다음날 4~5시간 정도를 투자하여 대회에 참여했다. PS를 안한지 꽤 오래되었지만, 올솔을 할 수 있었다. 이번 1차 예선은 뭔가 이전보다 난이도가 낮은 느낌이다. 문제1. 왼쪽부터 순서대로 1부터 $N$번의 번호를 가진 $N$명의 사람들이 좌우로 서있다. 이들은 다음과 같은 규칙에 의해 친구 관계를 가진다. 번호 $i$인 사람은 자연수 $D_i$를 가지고 있다. ($0<D_i\l...

해당 글은 스탠포드 대학의 Speech and Language Processing (by Daniel Jurafsky & James H. Martin) 글 중 일부를 직접 번역 및 정리한 내용이다. original 1. Markov Chains HMM (Hidden Markov Model)은 Markov chain을 기반으로 하여 만들어진다. Markov chain은 순차적인 랜덤 변수들의 확률에 대한 정보를 알려주는 모델이다. 여기서 랜덤 변수들은 states이며, 각각의 state는 어떤 집합에 속하는 값들이 된다. 이런 집합은 단어들의 집합, 날씨의 집합 등 기호로 나타내는 어떤 것이든 될 수 있다...

$ax + by = \gcd(a, b)$ 에서 정수해 $x$, $y$값을 빠르게 찾을 수 있는 알고리즘 이는 다음과 같은 과정을 통해 재귀적으로 구현할 수 있다. $ax + by = \gcd(a, b)$ $a = bq + r$ (단, $q = \left \lfloor \frac{a}{b} \right \rfloor$, $r = a \mod b$) $ax + by = (bq + r)x + by = b(qx + y) + rx = \gcd(a, b) = \gcd(b, r)$ $\Rightarrow bx’ + ry’ = \gcd(b, r)$ $\Rightarrow qx + y = x’, x = y’$ $\Rig...

오늘 진행중인 2021 KAKAO BLIND RECRUITMENT 1차 코딩테스트에 참여하고 출제된 문제 7개에 대한 풀이를 남긴다. 물론, 해당 포스트는 대회가 끝나는 시간인 오후 7시 30분 이후에 포스트할 예정이다. 결과 군필 조건만 없었으면… 문제1. 신규 유저의 아이디가 담긴 string이 주어졌을 때 문제에서 주어진 규칙에 따라 문자열을 변형한 뒤 반환하는 문제이다. 풀이 해당 문제는 문제에서 주어진 7개 단계를 수행하는 함수를 하나 만들고 문자열이 더이상 바뀌지 않을 때까지 돌려주면 된다. 단순 구현문제이다. #include <string> #include <vecto...

첫 ICPC 인터넷 예선이 끝났고 (끝난지 몇일 되었지만..) 우리팀(Taste Why Frame - 맞맛 왜 틀)은 1차 한국 지역 본선 진출자 명단에 확정되었다. 그렇지만 여러모로 아쉬웠다. ICPC 인터넷 예선이 시작되자 마자 웹사이트가 터졌고, 배부받은 문제지의 프린트 상태가 매우 좋지 않아 문제를 제대로 읽을 수 없었다. 그래서 문제지를 새로 달라고 요청했는데 있던 문제지를 그냥 가지고 가는 바람에 꽤 긴 시간 동안 아무것도 하지 못했다. 더욱이 대회 진행중에 I, C번을 AC받은 이후로 B, H, K, L번이 채점이 되지 않았다. (그나마 K, L같은 경우 한번 WA를 받았지만 이후로 계속 Pendi...

해당 글은 “조제프 푸리에의 업적 - 푸리에 급수와 푸리에 변환”라는 제목으로 제출한 “수학과 문명” 과목의 과제물을 수정한 것이다. 1. 조제프 푸리에와 그의 발견 조제프 푸리에(Jean-Baptiste Joseph Fourier; 1768 – 1830)는 프랑스에서 태어나 혁명의 혼란 속에서 젊은 시절을 보냈던 수학자이자 물리학자이다. 본래 푸리에는 본인이 유도한 열전도 방정식을 풀기 위해 푸리에 해석이라는 이론을 전개했다. 1807년 12월 21일 열린 프랑스 과학원 회의에서 39세 수학자이자 물리학자였던 푸리에는 수학사에 새롭고 효과적인 장을 여는 논문을 발표했다. 당시 과학자와 마찬가지로 푸리에...

1. 대각선 논법 시작하기에 앞서 칸토어 역설을 설명하는 과정에 필요한 대각선 논법(Diagonal argument)를 알고 넘어가자. 대각선 논법은 칸토어가 고안한 수학적 증명 방법으로 실수 집합의 크기가 무한하다 즉, 실수 집합은 비가산집합이라는 것을 증명했다. 실제로 실수 집합은 자연수 집합과 같은 크기인 $\left \vert \mathbb{R} \right \vert = \left \vert \mathbb{N} \right \vert = \aleph_{0}$이다. 1.1. 실수 집합의 비가산성 증명 대각선 논법을 이해하기 위해 실수 집합의 비가산성을 증명해 보자. 편의를 위해 실수 집합의 부분집합...