나름 개발자의 IT블로그

점근적 표기법점근적 표기법(Asymtotic notation)은 함수의 증감 추세를 비교하는 표기법이다. 다른 말로 란다우 표기법(Landau notation)이라고도 한다. 어떤 함수의 정확한 함수식을 표현하는 것이 아닌 근접한 함수식으로 표현하는 표기법이다. 점근적 표기법으로는 대표적으로 다음과 같은 표기가 있다. Big-$O$: $O(g(n))$Big-$\Omega$: $\Omega(g(n))$Big-$\Theta$: $\Theta(g(n))$little-$o$: $o(g(n))$little-$\omega$: $\omega(g(n))$We often want to know a quantity approximately, instead of exactly, in order to compare it to..

정신을 차려보니 벌써 2024년이 다 갔다. 작년에 이어 올해도 어떻게 살아갔는지 회고해보고자 한다. 카카오로 이직가장 큰 변화이다. 2024년 카카오 인턴을 거쳐 정직원으로 전환되어 이직에 성공하였다. 전환이 안되면 어쩌지 하는 고민도 많았지만 다행히 나의 인턴 생활을 좋게 봐주셔서 전환에 성공했던 것 같다. 정직원 전환 후 본격적으로 도메인에 대해 학습했다. 도메인은 클라우드 컴퓨팅이었는데 상당히 폭 넓은 분야를 알아야 했다. AWS제품으로 보면 EC2, VPC, ELB, EBS 정도를 다룬다. 개발팀이기 때문에 웹 개발 지식은 물론 서비스를 다루기 위한 컴퓨터 구조, 운영체제, 컴퓨터 네트워크 같은 CS지식도 폭 넓게 필요하다. 나는 실무에 사용되는 알고리즘에 대해서는 자신감이 있었지만 다른 과목에..

Splay Tree 를 사용하면 백준 태그에 Splay Tree가 붙은 문제 외에도 많은 문제를 해결할 수 있다. 여기에서 해결할 수 있는 문제들을 유형별로 정리하고 풀이를 간단하게 소개한다. 문제의 순서는 난이도 순이 아닐 수 있다. 기본 연산 유형Splay Tree는 값의 insert, delete, find연산을 지원한다. 이를 사용하여 해결할 수 있는 문제들이다.11723. 집합원래는 비트마스킹 연습하라고 메모리가 적게 세팅된 문제이지만 Splay Tree를 잘 구현하면 제한 안에 통과할 수 있다. Splay Tree를 연습하기 좋다. insert와 delete, find같은 기본 연산만으로 해결할 수 있다.1269. 대칭 차집합11723을 해결하며 toggle을 잘 구현했다면 toggle만으로 ..

Splay Tree는 Balanced Binary Search Tree의 한 종류로 데이터의 삽입, 삭제, 탐색을 $O(\log N)$에 준하는 속도로 처리할 수 있도록 하는 자료구조이다. 보통 학부과정에선 저런 기본 연산들을 배우게 되는데 Splay Tree를 사용해야만 해결할 수 있는 알고리즘 문제에서는 극한의 테크닉을 사용하여 많은 쿼리를 처리할 수 있다. 이 글에서는 Splay Tree가 어떤 자료구조인지 소개하기보다는 해결할 수 있는 application을 중점으로 소개한다. Splay Tree는 1985년에 Self-Adjusting Binary Search Tree라는 논문으로 소개가 되었고 여기에도 Tarjan이 저자로 들어가있다. 정말 많은 공헌을 하신 분이다. BasicSplay Tre..

소인수분해를 하는 가장 쉬운 방법은 약수를 구하듯이 $\sqrt N$까지 검사하며 나누어질 경우 인수로 가져가는 방식이 있을 것이다. 이러한 방법도 괜찮지만 $N \le 10^{18}$정도 된다면 TLE가 나는 느린 방법이다. 위 방법의 시간복잡도는 $\sqrt N$이지만 입력이 숫자이기 때문에 복잡도상으로 보면 지수시간을 가지는 느린 알고리즘이다. 소인수분해는 그만큼 어려운 문제이기 때문에 암호에도 많이 쓴다. 위 방법보다 빠르고 $10^{18}$범위까지 해결할 수 있는 Pollard rho 알고리즘에 대해 알아보자. Pollard rho를 이해하기 위해 몰라도 되지만 알면 좋은 사전지식이 있다.Birthday Paradox사람들이 얼마나 모여야 생일이 같은 사람이 존재할 수 있을까?비둘기집의 원리에 ..

우리는 암호를 왜 사용할까? 어떠한 정보에 도달하기 위해 내가 그 정보에 도달할 수 있는 유효한 사람임을 증명하기 위해 사용할 것이다. 예를 들어 웹사이트에서 나의 정보를 얻기 위해 나라는 것을 증명하기 위해 로그인을 하는 행위가 있을 것이다. 굉장히 심플한 방법이지만 보통 로그인을 할 때 패스워드를 서버에 보내서 서버에 있는 패스워드와 일치하는지 확인하는 방법을 사용하기 때문에 서버에 패스워드를 보내는 행위 자체가 찝찝할 수 있다. Zero Knowledge Proof어떤 문제를 해결하려는 사람 $P$(Prover)와 $P$가 제출한 데이터가 유효한지 검증하는 $V$(Verifier)가 있다고 하자. $P$는 $V$에게 어떤 데이터 $X$를 알고있다는 사실을 알려주고 싶다. 여기에서 $X$에 대한 정보..

가장 쉬운 문자열 자료구조나 알고리즘은 무엇일까? 아마 트라이정도가 있을 것이다. 이런 트라이도 상당히 고난이도의 자료구조에 속하기 때문에 문자열을 사용하는 자료구조나 알고리즘은 많이 어렵다. 문자열의 꽃이라고 볼 수 있는 Suffix 자료구조도 굉장히 고난이도에 속한다. 우리나라에서는 Suffix Array나 Suffix Tree (Suffix Trie) 등이 알려져있지만 Suffix Automaton은 잘 알려져있지 않다. 여기에서는 엄밀한 증명은 제외하고 Suffix Automaton이 무엇인지 알아보도록 한다. Automaton이름에서 볼 수 있듯이 Suffix Automaton은 어떤 문자열의 Suffix로 Automaton을 그린 것이다. Automaton가 뭔지 모른다면 여기를 참고하자. S..

CLRS 한글판을 보면 목차에 푸시-재명명, 재명명후-앞보내기 알고리즘이라고 있다. 뭔가 힙하고 새로워보이는 알고리즘같아 살펴보니 Push-Relabel을 한국어로 번역하다가 나온 이름이었다. (...) 그런 의미에서 이번 포스트에서는 Push-Relabel에 대해 알아본다. Push-Relabel도 1984년에 나온 비교적 최신 논문에 들어있다. SCC로 유명한 Tarjan이 저자로 있다! 해당 논문에 명시적으로 Push-Relabel이라는 알고리즘 이름은 없지만 전해 내려오면서 지어진 이름인 것 같다. 소개네트워크에서 전송 가능한 데이터를 계산하는 등 유량을 계산하는 것은 중요하다. Push-Relabel도 이러한 최대 유량을 구하는 알고리즘이며 $O(NM^2)$을 가지는 에드먼드 카프나 $O(N^2..

Berlekamp-Massey 알고리즘은 내가 가장 좋아하는 알고리즘 중 하나이다. 지금까지 이 알고리즘을 블랙박스 형태로 내부 동작을 모르는 채 사용했지만 이번 기회에 한 번 알아보는 것도 좋을 것 같아서 찾아보게 되었다. (몰라도 쓰는데 문제는 없다.) Shift-Register Synthesis and BCH Decoding 이라는 1969년에 나온 오래되고 클래식한 논문에 있는 알고리즘이었다. 정말 정말 좋은 리소스가 있어서 쉽게 접할 수 있었다. 엄밀한 증명은 하지 않고 어떻게 동작하는지만 남긴다. 선형 점화식DP에도 많이 나오는 선형 점화식은 1차원 수열상에서 이전 몇 개의 항들의 선형 결합을 통해 다음 항을 만드는 수열이 된다.$a_{i} = \displaystyle\sum_{j=1}^n c..

SQL과 NoSQL의 차이가 무엇인가요? 누군가가 위와 같은 질문을 한다면 무엇이라고 답하나요? 질문한 사람은 면접관, 친구 또는 동료가 될 수 있습니다.관계형 DB vs 비관계형 DB스키마가 정적임 vs 동적임MySQL, PostgreSQL이 있음 vs MongoDB, DynamoDB가 있음등등.. 각자 자신만의 방식으로 답변을 할 것 같습니다.  최근에 저는 이러한 질문을 받으면 그 히스토리에서 답을 찾는 방법에 감동을 받아서 해당 내용으로 답변해보고자 합니다.SQL데이터베이스는 언제부터 필요했을까요? 아마 컴퓨터가 사용되기 시작하고 데이터가 많아짐에 따라 관리되기 시작했을겁니다. 더 이상 파일만으로 관리하기 힘들고 복잡한 join연산과 집계를 위해 데이터베이스에 대한 수요가 나타나기 시작했습니다. ..