CS · Compression
허프만 코드 - 자주 나오는 것에 짧은 이름을 준다
반복이 하나도 없어도 아직 줄일 여지가 남아 있다. 모든 글자에 똑같은 길이를 주는 것이 낭비이기 때문이다. 짧은 이름을 나눠 주면서도 어디서 끊을지 헷갈리지 않게 만드는 방법을 본다.
압축의 원리와 한계 3편
CS · Algorithm
느릴 때 무엇부터 의심하나 - 길 고르기 한 장
이 시리즈에서 낸 길들을 한 장에 놓는다. 그리고 실제로 코드가 느릴 때 무엇부터 의심해야 하는지, 그 순서가 왜 알고리즘부터가 아닌지.
알고리즘의 갈림길 9편
CS · Algorithm
그리디 - 지금 제일 좋아 보이는 것
앞뒤 안 재고 매 순간 최선을 고르는 방법. 빠르고 코드도 짧은데, 언제 맞는지는 짐작이 아니라 증명으로만 알 수 있다.
알고리즘의 갈림길 8편
CS · Algorithm
동적 계획법 - 한 번 푼 것은 다시 안 푼다
이름이 어렵지 하는 일은 하나다. 계산한 값을 적어두고 다시 묻지 않는 것. 대신 적어둘 자리를 내줘야 하고, 진짜 어려운 건 무엇을 적을지 정하는 일이다.
알고리즘의 갈림길 7편
CS · Algorithm
분할 정복 - 쪼개서 풀고 합친다
쪼개면 왜 빨라지는가. 이득의 출처는 나누기가 아니라 합치기이고, 그 사실을 알면 n log n이 어디서 나오는지도 같이 보인다.
알고리즘의 갈림길 6편
CS · Algorithm
재귀 - 자기를 부르는 함수
재귀는 어려운 기교가 아니라 '같은 모양의 더 작은 문제'를 그대로 코드로 옮긴 것이다. 필요한 건 둘뿐이고, 무너지는 자리도 정해져 있다.
알고리즘의 갈림길 5편
CS · Algorithm
이진탐색 - 반을 버릴 수 있을 때
정렬해 두면 한 번 볼 때마다 절반을 통째로 버릴 수 있다. 그 조건이 무엇인지, 그리고 왜 이 짧은 코드가 그렇게 자주 틀리는지.
알고리즘의 갈림길 4편
CS · Algorithm
정렬 - 줄을 세우는 값과 그 대가
정렬은 그 자체로 답인 경우보다 다른 일을 싸게 만들려고 하는 경우가 많다. 방식이 갈리는 지점과, 실무에서 진짜로 물어야 하는 안정성 이야기.
알고리즘의 갈림길 3편
CS · Algorithm
완전탐색 - 다 해보는 것이 기준선이다
가장 먼저 떠올려야 할 방법은 전부 해보는 것이다. 무식해서가 아니라, 후보가 몇 개인지를 세어봐야 더 나은 방법이 필요한지 알 수 있어서다.
알고리즘의 갈림길 2편
CS · Algorithm
알고리즘 - 답이 아니라 답에 이르는 길
알고리즘은 어려운 수학 이름이 아니라 답에 이르는 절차다. 목적지가 같아도 길은 여럿이고, 무엇을 골랐느냐가 걸리는 시간을 정한다.
알고리즘의 갈림길 1편