이번주 목표 달성률
- 문제해결: basic (10/10), 정수론 이론 공부 (0)
- 설계: 시간복잡도는 계산(0) 다양한 풀이 생각(0), 확장 가능한 로직(X)
- 구현: problem(11/20), core-time(4/4)
- 학습 민첩성: CSAPP 1장(0), git projects 익히기 (0), JWT 와 SSR 관계 이해하기 (X)
기억에 남는 코딩 테스트 문제
하노이의 탑
하노이의 탑은 어려지 않았는데, 백준에서 제시간 조건에 부합하도록 변경하는 과정이 재밌었다. 이동횟수를 먼저 출력하고, 이동하는 과정을 출력했어야 했다.
첫번째에서는 이동 정보를 먼저 저장해두고, 이동횟수를 출력한 뒤, 순회하면서 이동 정보를 출력하고자 했다. 메모리 초과가 떴기 때문에, 저장하는 방식은 어렵겠다 생각했다. 경우수가 2^n - 1 만큼이 나오니까, 메모리를 많이 사용한다는걸 알 수 있었다.
두번째는 재귀를 2번 돌아가는 방식을 생각했다. 그러나 시간 복잡도가 O(2^n)이 였고, 2번 수행할만큼의 시간이 주어지지 않았다.
여기서 얻은 결론은, 재귀를 사용하면 이동 정보를 얻기 전에 이동 횟수를 얻을 순 없다는것이였다. 이동은 재귀로만 구할 수 있겠다 생각해서 이동 횟수를 빠르게 알아낼 방법이 필요했다. 그리고, n에 따른 이동횟수를 관찰해보면 등비수열이 보였다. 따라서 이동횟수는 2^n - 1를 이용해 빠르게 구하고, 재귀를 이용해 이동 경로를 출력하여 해결했다.
백준 플랫폼 leetcode에 비해 문제 수준이나 편의성이 떨어진다 생각했었지만, 이번 문제를 통해 다른 매력이 있다고 느껴졌다. leetcode보다 성능 조건이 빡빡했기 때문에, 작동하더라도 어떻게 성능을 개선할지를 고민하고 시도하는과정에서 배울점들이 있었다.
호제법
호제법을 문제를 통해 처음 알게되었지만, 혼자 원리를 이해하는것은 어렵지 않았다. 내가 이용한 수는 12, 15였는데 두 수를 관찰해보면 호제법이 어떻게 작동하는건지 쉽게 알아낼 수 있었다. 말 그대로, 호(서로) 제(덜다)법이니까.
기억에 남는건 확장된 호제법이였다. 베주 항등식을 통해 두 정수의 조합으로 이루어진 결과가 최대공약수라면, 조합수가 무수히 많이 존재한다는걸 알 수 있다. 그런데, 이 베주 항등식을 재귀적으로 사용하게 되면 정답 중 하나를 확정적으로 구할 수 있었다. 수학 지식을 프로그래밍적으로 응용하는 재밌는 사례였다.
PoW
파이썬으로 제곱 연산을 수행하면, 제출이 되어 6분만에 해결이 되었다는것에 놀랐다. 제출하고도 잘못되었다는걸 생각해, 다른 풀이를 고민하다 떠오르지 않아 찾아보았다. 문제 의도가 확실히 있었고, 정글 알고리즘 기초 강의에서 언급한 내용이라는게 떠올랐다. 아이디어는 간단했는데, 이전에 구했던 결과를 재활용해 연산량을 줄이는것에 있었다.
기존에는 x를 n번 곱하여 시간 복잡도가 O(n)을 따른다면, x^n을 (x^n//2)^2 로 바꾸어 x^n//2만 구하면 되도록 만들 수 있다. 이 방식이라면 O(log(n)) 시간 복잡도를 따르기에, 큰 제곱수를 구할 때 시간이 크게 줄어든다.
골드바흐의 추측
소수를 어떻게 빨리 구할 수 있을지를 오래 생각하게된 문제였다. 1부터 n까지에서 소수를 구할 때, 소수를 구하겠다는 생각대신 합섭수를 제외하고 남은 수만 모으는 '에라토스테네스의 체'를 활용했다. 포인트는 합성수를 미리 제외하는것이였다. 처음에는 소수를 찾는걸로 생각해, 이해하는데 시간이 걸렸다.
수요 코딩회
바이브코딩이란걸 처음 해봤다. 개인적으로 AI에 대한 불신이 있었고, 인턴 시절 문제를 해결하기 위해 활용했다가 해결을 못했기 때문에 신뢰하지 않았다. OpenAI측에서 오셔 codex 사용법과 간단히 프로젝트를 만들어보았다. 알려주셔서 그런지 어렵지 않게 사용해볼 수 있었고, 생각보다 AI의 성능이 좋아서 놀랐다.
그러나 프로젝트를 진행하면서 느끼는건 인턴 시절과 비슷했다. AI와 같이 대화하다보면, 말이 빙빙 도는 듯한 느낌을 받는다. 이건 기술이 얼마나 발전하던지, 사용자가 모르는 영역에 대해서는 프롬프트를 제대로 입력하지 못하기에 겪는 한계로 보인다. AI를 사용하기에, CS 지식이 더 필요해진걸 실감했다.
이번 프로젝트에서 보이스 기능 추가를 담당했는데, 로컬에서는 작동했지만 원격 서버간에서는 음성 데이터가 돌지 않는다는 문제가 있었다. 여기에 대해선 이해가 없었기에 codex에게 의존해야했는데, 결국 해결하지 못했다. 바이브 코딩에 아이디어가 중요하다곤 하지만, 잘 모르기 때문에 기술적으로 어려운걸 선택할 시 실패할 가능성이 높다고 생각된다.
다음주 목표
알고리즘 주차를 한번 진행해보니까, 내가 성장한다는 느낌을 받는 것들이 몇가지 있었다. 이 경험을 토대로 다음 중 어떤 것들을 우선시할지를 결정해 효과적으로 성장해보는게 좋겠다. 그리고 아직까지는 아는 자료구조와 알고리즘이라 문제를 많이 풀 수 있겠지만, 언제든 내가 모르는 자료구조나 알고리즘이 나온다면, 문제풀이 대신 직접 구현해보고 기초 문제를 통해 기본 개념을 먼저 탄탄히 잡는걸 우선시 하는것이 중요하다.
- 2주차 일부 문제 복습
(basic-백트래킹, basic-정수론, 문자열반복, 문자열단어공부, 완전탐색차이를최대로, 골드바흐의 추측, PoW) - 제공된 3주차 문제
(전부 풀 필요는 없다. 내게 맞는 속도로 진행하면 되는데, 대신 풀었던것에 대해서는 온전히 이해하고 있도록 유지) - 3주차 문제에서 링크드리스트 malloc 문제, LRU_cache는 꼭 풀어보고 싶다.
