나름 개발자의 IT블로그

현대사회에서 대부분의 사람은 PC나 모바일 기기등 통신이 가능한 기기를 하나 이상은 가지고 있다. 이 말은 통신이 가능한 기기를 가진 사람들은 인터넷에 접속하여 원하는 정보를 얻고 전자 상거래를 하며 게임을 할 수 있는 환경에 있다는 뜻이다. 서버의 입장에서는 이러한 많은 사람들의 요청을 문제없이 수행할 수 있도록 해야한다. 이를 가능하게 하기 위해선 단일 노드보다는 다중 노드에서 애플리케이션을 구동시키려는 시도가 필요하다. 분산 시스템 아키텍처분산 시스템(Distributed system)은 여러 컴퓨팅 노드를 사용하여 하나의 목적을 이루기 위한 시스템이다. 여기서 노드는 서버라고 생각하면 편하다. 가장 단순한 분산 시스템으로 대부분의 프로젝트에서 사용하는 애플리케이션 - 데이터베이스 구조를 생각할 수..

오늘 3월 18일은 내가 카카오에 정규직으로 입사한지 1년이 되는 날이다. 즉 2024년 3월 18일에 정규직으로 첫 출근을 했다!! 이를 기념하여 지금까지 어떻게 살아왔는 지 남겨보려고 한다. 인턴 생활은 여기에 있으니 그 이후의 이야기를 다룬다. 입사하고 나서인턴때와 같은 팀으로 입사했기 때문에 인턴때의 자리로 돌아왔고 본격적으로 다른 팀원들이 하는 것과 동일한 업무를 시작하게 된다. 하는 일은 여기에서 설명한 카카오의 IaaS인 Krane을 개발하는 업무를 한다. 한 3개월간의 부서 온보딩을 받고 그 이후부터가 진짜 시작이다. 온보딩에는 부서 코드를 숙지하고 코어 도메인에 대해서 학습하게 된다.인턴때도 느꼈고 늘 느끼는 거지만 팀원들이 너무 뛰어난 분들만 모여있어서 늘 감동했다. 모두 도메인에 대..

점근적 표기법점근적 표기법(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..