이미 쓰고 있는 것들의 이름 - 이름과 비용: 자료구조 ep.00

매일 배열과 Map을 쓰면서도 그것이 어떤 대가를 치르는지는 모른 채 지나갑니다. 이 시리즈는 이미 손에 익은 도구들의 이름과 비용을 다시 확인합니다.

자료구조와 알고리즘을 두 개의 시리즈로 나눠 다룹니다. 자료구조 시리즈는 데이터를 담고 정리하는 구조를, 알고리즘 시리즈는 그 안에서 찾고 결정하는 방법을 봅니다. 각 편이 독립적으로 읽히도록 구성했고, 이 편은 전체 지도 역할을 합니다.

이미 쓰고 있는 것들의 이름 - 이름과 비용: 자료구조 ep.00 매일 배열과 Map을 쓰면서도 그것이 어떤 대가를 치르는지는 모른 채 지나갑니다. 이 시리즈는 손에 익은 도구들의 비용을 다시 확인합니다. 자료구조와 알고리즘을 두 개의 시리즈로 나눠 다룹니다. 데이터를 담고 정리하는 구조를, 알고리즘 그 안에서 찾고 결정하는 방법을 봅니다. 각 편이 독립적으로 읽히도록 구성했고, 편은 전체 지도 역할을 합니다. 배열은 씁니다. 그런데 배열이 왜 인덱스 접근에서 빠른지는 설명하지 못합니다. 쓰는 것과 아는 것은 다릅니다 경력이 쌓이면 도구가 익습니다. 을 언제 꺼내야 하는지 감으로 압니다. 배열 앞에 값을 넣는 코드가 느려지면 어딘가 이상하다는 느낌도 옵니다. 문제는 감이 맞는지 설명할 수 없을 때 생깁니다. 감은 익숙한 상황에서만 작동합니다. 데이터가 열 배로 늘거나, 조건이 하나 추가되거나, 평소와 다른 형태의 입력이 들어오면 사라집니다. 그때는 알고 있어야 해시 테이블(hash table) 이라는 이름을 알면 평균과 최악이 다르다는 사실도 찾아볼 있습니다. 터지는지 예측할 때려 맞히던 걸 설명 가능한 판단으로 바꿀 살펴보기 담는 일과 찾는 일은 성격이 다릅니다. 자료구조는 모양으로 두느냐를 결정합니다. 결정하고 나면 연산이 싸지고 비싸지는지가 따라옵니다. 이건 정적인 선택입니다. 알고리즘은 위에서 무엇을 할지 같은 두고도 전부 훑을지, 절반씩 버릴지, 이전 계산을 기억할지가 갈립니다. 동적인 둘을 한 시리즈에 섞으면 편수가 편을 넘고 성격도 흐려집니다. 그래서 1부 「이름과 자료구조」와 2부 알고리즘」으로 나눴습니다. 알고리즘의 관계도. 왼쪽 열은 배열, 테이블, 정렬된 트리, 힙, 세그먼트 트리 여섯 개 항목이 세로로 배치됨. 오른쪽 그래프 탐색, 이분탐색, 그리디, 동적 계획법, 문자열 매칭, 정수론 왼쪽에서 오른쪽으로 향하는 화살표 네 개가 의존 관계를 표시함. 배열에서 이분탐색으로, 테이블에서 매칭으로, 트리와 힙에서 탐색으로, 그리디로 연결됨. 아래를 가로지르는 회색 띠에 시간 복잡도라는 라벨이 붙어 있고, 양쪽 모든 띠 위에 놓여 있음을 점선으로 다이어그램 제목은 「자료구조를 먼저 두고, 올립니다」, 부제는 「왼쪽을 모르면 계산할 없습니다」임. 열의 머리글은 「자료구조 시리즈」와 「알고리즘 시리즈」이고 띠의 라벨은 「공통 축 · 복잡도」임. 하단에 「양쪽의 놓입니다. 다릅니다」라는 문장이 적혀 있음. 시리즈에서 다루는 것 1부인 포함해 편입니다. ep.01 크기가 접근법을 정한다: 복잡도를 알아봅니다. 입력 크기만 보고 접근이 가능한지 판단하는 법을 나머지 편의 공통 언어라서 놓았습니다. ep.02 해시의 진짜 테이블을 가장 많이 잘 들여다보지는 않는 구조입니다. 해시가 평균 O(1)인데 O(N)인 이유, 그리고 앞쪽을 건드릴 생기는 ep.03 내장 정렬이 보장하는 것: 정렬을 정렬 함수가 보장하고 보장하지 않는지, 안정 다중 기준 정렬에서 결정적인지 ep.04 트리의 모양이 성능을 만든다: 힙을 넣어도 삽입 순서에 따라 성능이 O(log N)과 O(N) 사이에서 균형이라는 개념이 필요한지가 여기 ep.05 구간을 반복해 묻는다면: 구간 질의를 범위를 반복해서 묻는 상황에서 누적합부터 트리까지 선택지가 있는지 정리합니다. 순서대로 읽지 않아도 됩니다 독립된 질문 하나에 답합니다. 선행 편만으로 완결됩니다. 다만 권장 순서는 | 편 강도 |---|---|---| 없음 독립 필수 ep.05만 구조를 전제하므로 ep.04를 보는 낫습니다. 나머지는 관심 편부터 열어도 괜찮습니다. 코드는 자바스크립트로 씁니다 예제는 통일합니다. 표준 라이브러리가 탄탄하지 않아서 자료구조의 비용이 그대로 드러나기 때문입니다. 우선순위 큐가 내장되어 있지 않다는 설명하기 좋은 출발점이 됩니다. 개념은 언어와 무관합니다. 언어를 쓰신다면 구현이 대신 해주고 확인하는 용도로 읽으셔도 참고 자료 Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, (2009). Introduction to Algorithms (3rd ed.). MIT Press. MDN Web Docs. JavaScript 객체. Mozilla. https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/GlobalObjects 목차 시리즈 정한다 비용 만든다 묻는다면 해보는 그러지 문제를 그래프로 바꿔 보기 탐색 공간을 줄이는 근거 욕심내고 기억하는가 가중치와 순서와 연결성 패턴 찾기 ep.06 정수를 도구들 다음 예고 백만 개라는 조건 하나만 보고도 쓸 방법과 없는 방법이 역산이 어떻게 편에서 있 것들 Map 쓰면서 그것 대가 치르는지 손 익 데이터 정리하 안 결정하 방법 독립적 지 역할 접근 빠른지 쓰 아 경력 도구 감 앞 값 넣 코드 어딘 이상하다 느낌 문제 없 배 하 평소 형태 그때 이라 최악 다르다 사실 판단 담 일 찾 성격 모양 두느냐 연산 비싸지는지 위 무엇 같 두고 계산 기억할지 둘 편수 「이름 자료구조」 알고리즘」 항목 세로 향하 관계 테이블 힙 그리디 아래 가로지르 복잡도라 라벨 있음 점선 제목 부제 「왼쪽 머리글 시리즈」 하단 「양쪽 다릅니다」라 문장 다루 크기 접근법 복잡도 판단하 법 많 들여다보지 않 앞쪽 생기 보장하 함수 성능 넣어 순서 N) 사이 균형이라 개념 필요한지 질의 범위 묻 상황 누적합 선택지 순서대 않아 편만 다 강 구조 전제하므 보 열어 자바스크립트 예제 라이브러리 그대 큐 않다 좋 출발점 언어 구현 확인하 용도 읽으셔 해보 공간 줄이 기억하는 가중치 정수 백 개라 역산

pielog 파이로그