나름 개발자의 IT블로그

[알고리즘] 2025 카카오 하반기 코딩테스트 문제 풀어보기

문제 링크2025년 하반기 카카오 공채에 사용된 1, 2차 알고리즘 코딩테스트 문제가 프로그래머스에 올라와서 풀어보았다. 최근 알고리즘을 많이 놓기도 했지만 지금까지 경험해본 코테중에 가장 어려운 난이도에 속한 것 같다... 1차 중요한 단어를 스포방지카카오 코테의 전통일수도 있지만 1번문제는 쉬운 구현문제이다. 스포방지 구간에 포함되는 단어들을 set, map 등으로 관리한 뒤 스포방지가 해제될 때마다 해당 단어들이 얼마나 존재하는지를 더하면 쉽게 풀 수 있다. 1차 노란불 신호등lcm, gcd 같은 느낌이 들지만 제한이 충분히 작아 500만정도까지 돌려봐도 무난하게 통과할 수 있다. 1차 리프 노드 수 최대화트리의 모양이 위에서부터 깊이에 따라 2, 2, 2, 2, ... , 3, 3, 3 또는 3,..

연례행사로 연말이 되면 한 해를 돌아보는 회고글을 쓰곤 하는데 올해도 쓰려고 한다. 올해는 꽤 많은 일이 있었고 그만큼 성장도 한 일이 있었던 것 같다. 회사생활이제 만 2년이 되어간다. 도메인 지식은 아직 알아야 할 부분이 많지만 대부분 알게 되었고 혼자서 이슈해결을 상당수 할 수 있을 정도가 되었다. 또한 부서이동등으로 인해 새로운 팀원이 합류하면 온보딩도 시켜줄 수 있는 수준이다. 올해는 IaaS 를 담당하면서 VM 생성속도를 개선하는데 대부분 시간을 쏟은 것 같다. 이 과정에서 내가 알고 있는 알고리즘 지식을 사용할 수 있어서 좋았고 실제로 벤치마킹 결과가 예상처럼 개선돼서 의미가 있었다. 언젠가 카카오 테크 블로그에 기재할 수도..?업무에 필요한 CS 지식도 꾸준히 학습중이다. 학부에서 배웠지만..

현대사회에서 대부분의 사람은 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$에 대한 정보..