컴퓨터에서 이름 목록을 검색하는 프로그램을 실행한다고 생각해 보겠습니다. 파일에 저장한 프로그램과 이름 목록이 있고, 사용자는 찾을 이름을 입력합니다. 컴퓨터는 무엇을 어디에 보관하고 어떤 순서로 처리할까요? 이 작은 작업 안에 운영체제, 자료구조, 알고리즘의 기본 문제가 함께 들어 있습니다.
명령과 데이터
프로그램은 컴퓨터가 실행할 명령과 그 명령이 다룰 데이터로 이루어집니다. CPU는 명령을 실행하고, 실행 중인 값은 레지스터나 메모리 등에 놓입니다. 디스크에 저장된 파일과 실행 중 사용하는 메모리는 역할과 수명이 다릅니다. 파일에 저장하지 않은 변경은 프로그램이 종료되면 사라질 수 있습니다.
문자열도 결국 정해진 인코딩으로 표현한 바이트입니다. 같은 화면 글자라도 표현이 다를 수 있으므로, 비교 전에 어떤 단위와 규칙을 사용할지 정해야 합니다. 사람이 보는 이름과 컴퓨터가 비교하는 저장 표현은 처음부터 같은 것이 아닙니다.
프로그램·프로세스·스레드
디스크의 프로그램 파일을 실행하면 운영체제가 실행에 필요한 주소 공간과 자원 등을 관리합니다. 이 실행 단위를 프로세스라고 합니다. 같은 프로그램을 두 번 실행해 서로 다른 프로세스를 만들 수 있습니다.
스레드는 그 프로세스 안에서 명령을 실행하는 흐름입니다. 같은 프로세스의 스레드는 메모리와 자원을 공유할 수 있지만 각각의 호출 스택과 실행 위치를 가집니다. 따라서 검색 담당 스레드와 목록 수정 스레드를 나누면, 같은 목록을 동시에 접근하는 문제도 새로 생깁니다.
CPU 코어보다 실행할 스레드가 많으면 운영체제는 실행 기회를 나눕니다. 파일 읽기를 기다리는 스레드가 있다고 다른 모든 프로그램도 멈춰야 하는 것은 아닙니다. 실행 중, 실행 가능하지만 대기 중, 입출력을 기다리는 상태를 구별하는 이유입니다.
그림을 글로 읽기
- 사용자 · 검색 이름
- 프로세스 · 명령과 이름 목록
- CPU · 비교·분기
- 운영체제 · 파일·실행 자원
- 사용자 · 검색 이름 → 프로세스 · 명령과 이름 목록: 입력
- 프로세스 · 명령과 이름 목록 → CPU · 비교·분기: 명령 실행
- 프로세스 · 명령과 이름 목록 → 운영체제 · 파일·실행 자원: 자원 요청
자료구조와 알고리즘
이름을 입력 순서대로 배열에 넣으면 이름 하나를 찾을 때 처음부터 비교할 수 있습니다. 이것이 순차 탐색입니다. 목록이 정렬돼 있다면 가운데 값을 비교해 후보 구간을 절반씩 줄이는 이진 탐색을 사용할 수 있습니다. 데이터의 배치가 가능한 탐색 방법을 바꿉니다.
1024개 목록의 순차 탐색은 최악에 1024개를 확인합니다. 이진 탐색은 정렬과 무작위 위치 접근이라는 전제 아래 후보 구간을 약 10번 반으로 줄일 수 있습니다. 그러나 매 입력마다 다시 정렬해야 한다면 그 비용도 포함해야 합니다. 검색 한 번의 속도만 보고 전체 프로그램이 빠르다고 판단하지 않습니다.
| 구분 | 검색 프로그램의 선택 |
|---|---|
| 자료구조 | 이름을 배열·해시 테이블·트리 중 어디에 저장할지 |
| 알고리즘 | 저장한 이름을 어떤 순서로 확인할지 |
| 운영체제 | 파일·메모리·CPU 실행을 어떻게 제공할지 |
| 동시성 | 검색과 수정이 겹쳐도 어떤 상태를 허용할지 |
계산량과 실제 시간
O(n), O(log n)은 입력 크기가 커질 때 연산량이 어떻게 증가하는지를 설명합니다. 밀리초를 직접 나타내지는 않습니다. 같은 비교 횟수라도 긴 문자열을 비교하거나 디스크에서 데이터를 읽으면 시간이 달라집니다.
메모리 사용량도 원소 개수만으로 정해지지 않습니다. 문자열 본문, 포인터, 자료구조의 빈 공간과 임시 버퍼가 함께 들어갑니다. 작은 연습으로 1,024개 정렬 목록을 준비하고 같은 이름을 순차 탐색과 이진 탐색에 넣어 비교 횟수를 세어 봅니다. 순차 탐색은 최악에 1,024회까지 늘고 이진 탐색은 정렬·무작위 접근 전제에서 약 10회의 구간 축소를 보입니다. 목록을 매번 정렬하도록 바꾼 뒤에는 검색 함수만의 비교 횟수와 전체 요청 시간을 따로 기록해야 자료구조 선택의 효과와 준비 비용을 구분할 수 있습니다.
세부 학습 경로
프로세스·스레드에서 실행 단위를, 주소 변환에서 프로그램의 주소와 물리 메모리를 살펴볼 수 있습니다. 데이터 저장은 배열·리스트, 탐색은 이진 탐색으로 이어집니다. 이 장의 모델을 실제 문제에 적용할 때는 “입력은 어디에 있고, 누가 실행 기회를 주며, 어떤 상태를 공유하고, 실패 후 무엇이 남는가”를 순서대로 질문합니다. 이 네 가지 답이 정리되면 프로세스·스레드, 주소 변환, 컨테이너, 탐색 같은 다음 학습 항목이 단절된 용어가 아니라 하나의 검색 프로그램에서 이어지는 선택으로 보입니다.