소프트웨어 개발 1강. 자료구조와 정렬·탐색

자료구조를 고르는 일은 무엇을 빠르게 하고 무엇을 포기할지 미리 정하는 일입니다. 공짜로 다 빠른 구조는 없습니다.

풀고 시작

스택은 되돌리기의 자료구조입니다

편집기에서 되돌리기를 누르면 방금 한 일이 취소됩니다. 그 다음을 누르면 그 전 일이 취소되죠. 가장 최근 것부터 꺼내는 이 동작이 스택(stack)입니다. 후입선출(LIFO)이고, 넣는 것을 push, 꺼내는 것을 pop이라고 부릅니다. 함수 호출도 스택으로 관리됩니다. 함수 안에서 함수를 부르면 새 프레임이 쌓이고, 끝나면 위에서부터 걷힙니다. 재귀 호출이 너무 깊어지면 나는 스택 오버플로가 그래서 생깁니다.

반대편에 큐(queue)가 있습니다. 선입선출(FIFO)이고, 줄 서기입니다. 프린터 대기열, 프로세스 스케줄링, 너비 우선 탐색이 모두 큐를 씁니다. 시험에서는 데크(deque)도 나오는데, 양쪽 끝에서 모두 넣고 뺄 수 있는 구조라 스택과 큐를 겸할 수 있습니다.

선형과 비선형의 구분도 자주 묻습니다. 배열, 연결 리스트, 스택, 큐, 데크는 요소가 한 줄로 이어지는 선형 구조입니다. 트리와 그래프는 한 요소가 여러 요소와 연결되는 비선형 구조입니다.

트리에서는 용어가 문제가 됩니다. 자식이 없는 노드가 단말(leaf), 한 노드에 달린 자식의 수가 차수(degree), 트리 전체의 차수는 그중 가장 큰 값입니다. 이진 트리의 순회는 셋인데, 루트를 언제 방문하느냐로 이름이 붙습니다. 전위는 루트-왼쪽-오른쪽, 중위는 왼쪽-루트-오른쪽, 후위는 왼쪽-오른쪽-루트입니다. 중위 순회가 이진 탐색 트리를 오름차순으로 훑는다는 사실은 알아 두시면 편합니다.

정렬은 성격이 다른 다섯 가지

정렬 알고리즘은 이름과 동작, 그리고 시간 복잡도를 묶어서 외워야 합니다.

시험이 파고드는 지점은 최악의 경우입니다. 퀵 정렬은 평균이 O(n log n)으로 가장 빠른 축에 들지만, 이미 정렬된 자료에 피벗을 맨 끝 값으로 잡으면 최악 O(n²)까지 떨어집니다. 반면 합병 정렬과 힙 정렬은 최악에도 O(n log n)을 지킵니다. 평균은 퀵이 빠르고 최악은 합병이 안전하다고 정리해 두시면 됩니다.

탐색과 해싱

이진 탐색은 정렬된 자료에서만 쓸 수 있습니다. 가운데 값과 비교해 절반씩 버리므로 O(log n)이죠. 정렬돼 있지 않으면 처음부터 훑는 순차 탐색뿐이고 O(n)입니다.

해싱(hashing)은 아예 계산으로 위치를 찾습니다. 키를 해시 함수에 넣으면 저장 위치가 바로 나오니 이상적인 경우 O(1)입니다. 해시 함수 방식으로는 나눗셈법, 중간 제곱법, 폴딩법, 숫자 분석법 등이 나옵니다.

문제는 서로 다른 키가 같은 자리를 가리키는 충돌(collision)입니다. 이때 몰린 상태를 오버플로라고 하고, 해결책은 둘로 나뉩니다. 개방 주소법(open addressing)은 비어 있는 다른 자리를 찾아 넣습니다. 선형 조사법이 대표적이죠. 체이닝(chaining)은 같은 자리에 연결 리스트를 매달아 줄줄이 잇습니다. 자리를 옮기지 않고 매단다는 점이 체이닝의 표지입니다.

정렬과 탐색은 4과목의 코드 읽기 문제로도 다시 나옵니다. 동작을 말로 설명할 수 있게 되면 코드도 따라 읽힙니다.

인출 문제

생각해볼 질문 (정답 없음)

평균이 빠른 알고리즘과 최악이 안정적인 알고리즘 중 하나를 골라야 한다면, 어떤 시스템에서 어느 쪽을 택하시겠습니까. 은행 거래와 게임 렌더링의 답이 같을까요.

이전: 1과목 5강 아키텍처와 디자인 패턴 · 다음: 2강 통합 구현과 형상 관리