병아리 개발자의 실력 양성기

NOT 연산: Indexing 에서 반대편 끝으로 보내기 A = [3,4,5,2,6] 가 있다. 만일 앞에서 부터 두번째를 나타내는 인덱스 값을 i에 저장하면 i = 1 이 되며, A[i] 는 4 가 된다. 그러면 끝에서 두번째 즉 -2 번째를 i 와의 관계식으로 나타내려면 -1 - i 라고 해야 하는데 이것은 앞에서부터 인덱싱할 경우 0부터 시작하지만 뒤에서부터 인덱싱 할 경우 -1부터 시작하기 때문이다. 그러면 이것을 간단하게 나타내려면 보수를 쓰면 된다. 즉, ~i 라고 하면 정확히 대칭이 되는 뒤에서부터의 위치를 구해준다. 왜 그럴까. NOT 연산은 어떤 경우든 다음의 간단한 규칙으로 정리된다. 1. 부호 뒤집기 2. 1 빼기 x값 -2 2 1단계. 부호 뒤집기 2 -2 2단계. 1빼기 2-1 -..

이분탐색은 이미 정렬이 된 자료에서 내가 목표하는 값(target value)의 위치(index)를 자료를 반으로 나누어 탐색하는 과정을 반복하는 방법을 말한다. 이 경우 O(logn) 시간에 결과를 찾게 된다. bisect 모듈을 이용하면 쉽게 이를 수행할 수 있다. bisect_left는 목표값과 같거나 큰 첫 숫자의 인덱스를, bisect_right과 bisect는 목표값보다 큰 첫 숫자의 인덱스를 돌려준다. 함수들의 첫번째 인자는 검색대상이 되는 정렬된 리스트, 두번째 인자는 찾으려는 목표값이다. import bisect bisect.bisect_left([.5, .8, .9, 1], .5) # 0 bisect.bisect_right([.5, .8, .9, 1], .5) # 1 bisect.bis..

랜덤(random)한 수를 다루는 문제는 수학적 코딩 문제의 대표적 유형으로서 자주 출제되나 이 문제를 해결하려면 결코 녹록지가 않다. 이산수학, 조합수학, 추상대수 등의 개념을 담고 있기 때문이다. 하지만 그런 어려운 수학을 전부 공부하지 않더라도 직관과 상식으로 이를 풀어낼 수 있고, 대표적 문제들을 풀다보면 변형된 형태에도 대응할 수 있을 것이라 믿는다. 이 번 포스트에서는 몇 가지 연관된 문제를 풀어본다. EPI (Elements of Programming Interviews in Python)과 LeetCode 등을 참고했다. 부분집합 1 문제: 서로 다른 숫자로 된 배열(원소 n개) A에서 정해진 크기(k)만큼의 원소를 갖는 부분집합 1개를 찾기. 각 부분집합이 나타날 확률은 동일해야 한다. ..

지난 두 달 간 약 200여 개의 문제를 고민하고 풀이를 이해했다. 실제로 코딩을 해 본 것도 있었지만 대체로 말을 하면서 손으로 코드를 적고 모범 코드와 맞춰보면서 내가 로직을 맞게 가져간 것인지를 확인한 것이 많았다. 물론 처음에는 자료구조나 알고리즘 자체에 대한 이해가 미진해서 아예 답을 떠올릴 수도 답안을 봐도 이해 할 수도 없어 며칠을 고민해야 했던 문제도 많았다. 하지만 지나고 나면 그것이 다 실력이 되었다. 이런 경험을 한 번도 해 본 적이 없는 것 같다. 고등학교 때 수학문제를 보면 그저 풀이를 외웠던 것 같다. 하지만 지금은 내 마인드 자체가 알고리즘적으로 사고하게 된 것 같다. 그리고 침착해졌다. 얼마전에는 고급 그래프 알고리즘 중 대표적인 것을 공부하고 코드를 정리했다. 앞으로 그 부..

정의 해시 테이블(hash table)은 키(key) (필요한 경우 연관된 value)를 저장, 삭제, 열람 할 때 평균 O(1) 만큼 시간이 걸리는 것을 목표로 한다. 이를 위해, key는 hash 함수를 통해 변환되어 hash code (int)로 array (=hash table)에 저장된다. key가 hash 함수를 통과하여 array에 매핑된 결과는 가급적 균일하게 분포하도록 hash 함수를 설계하는 것이 필요하다. (주의깊은 해싱함수의 설계에도 불구하고) 두 key가 array의 같은 위치에 매핑되는 것을 충돌(collision)이라고 부른다. 이를 처리하기 위해 각 위치에 연결리스트(linked list)를 두거나 open addressing, linear probing 등의 방법을 활용한다..

LRU cache LRU cache (Least Recently Used cache) 는 일정한 capacity를 정해두고 최근에 참조(lookup) 나 삽입(insert) 된 것을 Most Recently Used entry 로서 삭제 순위를 가장 후순위로 보내는 캐시를 말한다. 이 캐시로서 dict 등의 해시 테이블 자료구조가 쓰일 수 있다. 왜냐하면 O(1) 시간만에 참조와 변경을 할 수 있기 때문이며, 쓰이지 않는 기록은 자연히 삭제의 선순위로 밀려 새로운 key가 들어올때 쫒겨나기 때문이다. 구현 capacity를 주고 queue를 이용해서 LRUCache를 구현하되 lookup(key) 해도 키가 없으면 -1을, erase(key) 할때 key가 있으면 True 없으면 False를 돌려주며, ..

BST BST는 node.left.data > t = bintrees.RBTree([(3, 'Ryan'), (2, 'Muzi'), (5, 'Jay-Z'), (1, 'Chunshik')]) >>> t[2] 'Muzi' >>> t.min_item() (1, 'Chunshik') >>> t.max_item() (5, 'Jay-Z') >>> t.insert(8, 'Pengsoo') >>> t RBTree({1: 'Chunshik', 2: 'Muzi', 3: 'Ryan', 5: 'Jay-Z', 8: 'Pengsoo'}) >>> t.discard(5) >>> a = t.pop_min() >>> a (1, 'Chunshik') >>> b = t.pop_max() >>> b (8, 'Pengsoo') >>> t RBT..

공부를 하면 할 수록, 기본 개념은 간단하며 소위 '기초'로 분류되는 주제이나 실제로 문제를 풀기에는 여간 까다롭지 않은 것이 연결 리스트라는 생각이 든다. 주변 엔지니어에게 경험을 물어봐도 이 주제를 어렵다고 평가하는 것을 들을 수 있었다. 대표적 문제를 풀면서 심층적으로 탐구해 보고자 한다. 정의 연결 리스트는 아래와 같이 정의된 노드들의 연결로 이루어진다 (Goodrich et al. [1]) class _Node: def __init__(self, element=0, next=None, prev=None): # initialize node's fields self._element = element # user's element self._prev = prev # previous node refer..

나는 원래 고등-대학 모두 문과생이었다. 그러나 이과에는 관심이 있었고 곁다리로 조금씩 과목을 듣기도 했다. 그리고는 나중에 뜻한 바 있어 유학을 가게 되어 이과 공부를 하고 왔다. 요새 머신러닝 쪽 실무를 하면서 효율적 코드 작성을 위해 알고리즘과 자료구조 공부를 할 필요가 있다고 생각되어 최근 들어 공부를 시작하였는데, 2개월 정도는 꽤 힘들었지만 지금은 나 스스로도 문제를 이해하고 구상하고 푸는 속도도 빨라지고, 실력이 한차원 높은 궤도에 올랐다는 느낌이 든다. 아직 목표한 수준까지는 갈 길이 멀지만, 그래도 코드를 보는 나의 눈이 많이 달라지고 깊어진 것을 스스로 느낄 때면 알고리즘 공부를 하길 잘했다는 생각이 들어 뿌듯하다. 알고리즘 공부란 무엇일까, 하고 오늘 느낀 점을 간략히 적어보도록 하겠..

DP의 핵심요소는 메모이제이션(캐싱)이라고 할 수 있다. 이미 계산한 결과를 저장하는 재귀라고도 할 수 있다. 기억 공간을 반복될 계산결과의 저장에 할당함으로써 귀중한 연산시간을 절약하는 것이다. DP를 이용해 해결할 수 있는 대표적이며 가장 간단한 예로 피보나치 수열이 있다. 어떻게 이 문제가 재귀, top-down DP, bottom-up DP, 그리고 그 기억공간을 추가로 절감하는 방식으로 수행되는지를 살펴본다. 재귀 피보나치 수열은 수학적으로 다음 점화식(recurrence relation)으로 정의된다. $$ f_n = f_{n-1} + f_{n-2} $$ $$ f_0 = 0; \ f_1 = 1 $$ n번째 수를 구하기 위해서는 n-1번째, n-2번째 수를 알아야 하고, 그들을 알기 위해서는 다..