앞 글에서 스택과 큐를 만들었다. 그런데 스택과 큐 자체가 목적인 문제는 많지 않다. 그것들은 비선형 자료구조를 훑기 위한 도구였고, 이 글이 그 대상을 다룬다. 트리와 그래프는 "원소들 사이의 관계"를 표현한다. 리스트가 1:1 관계라면 트리는 1:N, 그래프는 N:M이다. 관계가 복잡해질수록 어떻게 저장할 것인가가 성능을 결정하고, 그래서 이 글의 절반은 표현 방식 이야기다. 마지막엔 이진 탐색 트리(BST)를 다룬다. 트리 — 정의부터 재귀적이다성질비선형 구조원소들 간에 1:N 관계를 가지는 자료구조원소들 간에 계층 관계를 가지는 계층형 자료구조정의한 개 이상의 노드로 이루어진 유한 집합이며 다음을 만족한다.노드 중 최상위 노드를 루트(root) 라 한다나머지 노드들은 n개(n ≥ 0)의 분리 집합..

배열은 아무 자리에나 넣고 뺄 수 있다. 그게 장점 같지만, 알고리즘 문제를 풀다 보면 일부러 그 자유를 버리는 자료구조를 계속 만나게 된다. 스택은 한쪽 끝에서만 넣고 빼고, 큐는 넣는 곳과 빼는 곳을 반대로 갈라놓는다. 스택은 "가장 최근 것"을 늘 알고 있고, 큐는 "가장 오래된 것"을 늘 알고 있다. 이 글은 스택 → 큐 → 원형 큐 → 연결 리스트 순으로 간다. 제한의 방향이 자료구조를 가른다스택과 큐의 차이는 딱 하나다. 넣는 곳과 빼는 곳이 같은가, 반대인가. 스택큐삽입한쪽 끝(top)뒤(rear)삭제같은 쪽 끝(top)반대쪽 끝(front)순서후입선출 LIFO선입선출 FIFO공짜로 아는 것가장 최근 원소가장 오래된 원소대표 응용괄호 검사, 함수 호출, 후위 계산, DFS버퍼, 대기 행렬,..

순열과 조합은 고등학교 확률과 통계에서 이미 배운 내용이다. 그런데 알고리즘에서 다시 배우는 이유는 개수를 세기 위해서가 아니라 실제로 만들어 내기 위해서다."경우의 수는 몇 가지인가"와 "그 경우들을 하나씩 만들어 확인하라"는 완전히 다른 요구다. 앞의 것은 공식 한 줄이면 되지만 뒤의 것은 코드가 필요하고, 그 코드가 언제까지 버티는지도 알아야 한다.이 글은 순열·조합·중복 순열·중복 조합 네 가지가 재귀에 넘기는 슬라이스 한 줄 차이로 전부 나온다는 것을 보이고, itertools 와 비트마스크까지 정리한다. 앞 글 재귀와 완전 탐색 에서 다룬 부분집합 재귀 트리를 알고 있으면 훨씬 잘 읽힌다.같은 데이터, 세 가지 질문학습 자료는 도시 여섯 개가 서로 다 연결된 그래프 하나를 놓고 질문만 세 번 ..

반복문으로 풀 수 있는 문제를 굳이 재귀로 푸는 이유가 뭘까. 코드가 짧아져서? 그것만이라면 배울 이유가 크지 않다.진짜 이유는 어떤 문제는 "더 작은 같은 문제"의 답을 알면 즉시 풀린다는 데 있다. 하노이의 탑에서 원판 20개를 옮기는 절차를 반복문으로 적으려면 머리를 싸매야 하지만, "19개를 옮길 줄 안다고 치자"고 가정하는 순간 세 줄로 끝난다. 이 글은 그 구조를 팩토리얼·피보나치·부분집합·하노이의 탑으로 확인하고, 이어서 재귀의 쌍둥이인 완전 탐색이 언제 쓸 만하고 언제 못 쓰는지를 숫자로 잡는다.반복과 재귀는 방향이 반대다반복과 재귀는 같은 답을 낼 수 있다. 다른 것은 일하는 방향이다.반복 — 작은 것부터 쌓아 올린다. sum += 1, sum += 2, … 누적값이 자란다.재귀 — 큰 ..

문제를 다 읽고 나서 가장 먼저 해야 할 일은 코드를 치는 게 아니다. 제한 조건에 적힌 N의 최댓값을 보는 것이다. N이 1,000이면 이중 반복문을 마음 놓고 써도 되고, N이 100,000이면 이중 반복문은 그 자리에서 탈락이다. 이 판단을 코드 작성 전에 못 하면, 논리가 완벽한 풀이를 다 짜고 나서 시간 초과를 받고 처음부터 다시 시작하게 된다.이 글은 그 판단을 하기 위한 기준선 하나를 만드는 정리다. "1억 번 연산 ≈ 1초" 라는 숫자 하나만 손에 쥐면, 제한 시간과 입력 크기에서 허용 복잡도를 역산할 수 있다. 앞쪽 절반은 그 기준선을 세우는 데 쓰고, 뒤쪽 절반은 그 감각을 2차원 리스트 순회와 델타 탐색이라는 실제 코드로 잇는 데 쓴다. 격자 문제에서 삼중 반복문이 나왔을 때 "이게 ..

파이썬을 배운 지 얼마 안 됐더라도, 이런 코드는 이미 수십 번 썼을 것이다.'hello'.upper()[3, 1, 2].sort(){'a': 1}.keys()문자열 뒤에 점을 찍고 함수 같은 걸 부른다. 리스트도 딕셔너리도 똑같이 동작한다. 그런데 왜 upper(문자열) 이 아니라 문자열.upper() 인가? 그냥 파이썬 문법이 그런 것이라고 넘기기 쉽지만, 사실 이 점 하나에 클래스와 객체지향이 통째로 들어 있다.'hello'.upper() 는 파이썬 내부에서 str.upper('hello') 로 동작한다. str 이라는 클래스가 있고, upper 는 그 클래스의 함수이며, 'hello' 는 그 함수의 첫 번째 인자로 들어간다. 우리가 self 라고 부르는 그 자리다.이 글은 그 한 줄에서 출발해 클..

프로그래머스 「여행경로」를 풀었다. ICN에서 출발해 주어진 항공권을 전부 쓰는 경로를 찾는 문제다. DFS/BFS 분류에 있는 문제니까 DFS로 파고들다가 티켓이 남은 채 막히면 되돌아오게 짰고, 통과했다.그런데 코드에 used 배열이 있고, path.pop()이 있고, if dfs(next): return True가 있다. 되돌아가기 위한 장치가 셋이나 붙어 있다는 뜻이다. 이 문제가 정말 되돌아가야만 풀리는 문제인가.아니다. 모든 간선을 한 번씩 지나는 경로에는 이름이 있고, 그 경로는 조건만 맞으면 한 번 걸어가는 것만으로 완성된다. 되돌아갈 일이 원리적으로 생기지 않는다는 보장이 있기 때문이다. 이 글은 그 보장이 무엇이고 왜 성립하는지, 그리고 그걸 아는 것과 모르는 것이 실제로 몇 배 차이가..

"AI를 어디에 쓸까"로 시작한 프로젝트는 대체로 같은 길을 간다. 데이터를 모으고, 잘 알려진 모델을 얹고, 성능이 모자라면 모델을 키운다. 그런데 어떤 문제는 모델을 아무리 키워도 잘 안 풀리고, 어떤 문제는 질문을 한 번 바꾸는 것만으로 작은 모델에서도 풀린다.그 차이를 만드는 게 도메인 전문지식이다. 정확히 말하면 "이 분야의 전문가는 무엇을 보는가" 라는 질문이다. 전문가가 실제로 보는 것을 알아내면, 모델에 무엇을 넣어야 하는지도 어떤 구조가 맞는지도 따라 나온다.이 글은 적응적 센싱 편에서 이어진다.앞 글이 센서를 조절해 입력을 모델에 맞췄다면, 이 글은 한 발 더 나가서 문제 정의 자체를 도메인 지식으로 다시 짠다. 손대는 자리는 다르지만 목적은 같다 — 모델을 키우지 않고 푸는 법.수면의..