효율적 컴퓨팅 사고 : 자료에서 정보 찾기

1. 효율적인 자료의 표현과 검색

자료와 정보.. 어디서 들어보지 않았는가? 그렇다. 저번에 자료와 정보의 차이를 정리하며 자료의 단위에 대해 정리한 적이 있었다. 이 글(https://mspproject2023.tistory.com/625)을 참고 바란다.

자료들을 데이터 처리하면 정보가 된다.

이전 글에서는 자료는 단순한 사실이나 결과값이며, 정보는 자료(그 사실과 결과값)을 처리하여 인간에게 유용한 형태로 가공한 것이라고 했다. 그러나 여기선 자료와 정보를 새롭게 정의하겠다. 다만 위의 정의와 완전 다른 것은 아니며, 비슷한 의미가 될 것이다.

컴퓨팅 사고에서 자료(data)는 연구나 조사 등의 바탕이 되는 재료로써, 만들거나 이루는데 바탕이 되는 물자나 재료를 말한다. 그리고 정보(information)는 관찰이나 측정을 통해 수집한 자료를 실제 문제에 도움이 될 수 있도록 정리한 지식 또는 의미 자료를 말한다. 즉 자료는 재료고, 정보는 자료를 정리한 것을 말한다.

여기서 중요한 점은 자료는 많이 수집되고 많이 저장되어 있다고 좋은 것이 아니라 필요한 시점에, 필요한 목적에 따라 정보화될 수 있어야 비로소 의미를 가진다는 점이다. 이를 위해 컴퓨팅 사고에서는 대량의 자료를 효율적으로 관리할 수 있는 저장 방법과 모여진 자료 속에서 원하는 정보를 빠르게 찾아내는 여러 방법들을 구축했다.

 

특히 컴퓨터에서도 대량의 데이터를 처리할 때 표 구조를 자주 사용하는데, 같은 특성을 가진 자료끼리 분류해서 같은 열에 나열해 가독성을 높인다. 그리고 같은 행에 나열된 자료는 하나의 대상에 대한 정보를 의미하기에 정보 간의 연관성을 표현할 수 있다. 또한 표에서는 자료 삽입이나 삭제가 쉽기 때문에 기존의 자료에 새로운 자료를 추가하거나, 필요없는 정보를 삭제할 때 유용하다.

 

2. 변수와 리스트

컴퓨터에서 대량의 데이터를 처리할 때 표 구조를 자주 사용하는 것은 알겠는데, 이러한 정리된 내역을 어떤 방식으로 처리하는걸까?

 

하드디스크에 저장된 대량의 데이터를 컴퓨터 메모리로 불러들여 처리할 때 데이터를 저장하는 그릇의 역할을 하는 추상적 저장 공간(저장소)을 변수(variable)라고 한다. 변수는 각각의 이름을 가지고 있으며, 하나의 값을 저장할 수 있다.

그런데 수백 수천의 데이터를 처리하는 프로그램에서 모든 데이터에 변수명을 하나하나 붙이면서 저장해야 한다면  너무 복잡하고 고되고 반복적인 표현도 불가능하다. 이러한 문제를 해결하기 위해 시퀸스(sequence)라고도 불리는 리스트(list)가 만들어졌다.

 

이 리스트는 프로그램 내에 표 모양의 연속된 공간을 확보하여 그곳에 자료를 저장하고 처리할 수 있도록 하는 추상 자료형(추상적 자료구조)를 말한다. 리스트 또한 하나의 이름을 가지지만 리스트 내에서 여러 개의 항목을 관리하는 구조이므로 각 항목의 위치 값을 나타내는 항목번호(index)를 가진다. 즉, 하나의 이름으로 동일한 특성을 가지는 여러 개의 변수 값을 관리할 수 있다는 말이며, 데이터의 양이 너무 많아서 일일이 저장하기 힘든 경우에 쉽게 대량의 데이터를 저장할 수 있다는 말이기도 하다.

리스트의 형태

리스트는 고유한 이름(리스트명, 리스트 이름)을 가지며, 각각의 칸들은 리스트 항목이라고 부르며 해당 리스트 항목은 논리적 인덱스(논리적 항목 번호)로 구분된다. 따라서 리스트의 각 항목은 리스트의 이름과 항목 번호를 조합해서 명명한다.

표현 예시) 이름[2]는 돈까스다. 삼겹살은 이름[4]에 포함된다.

데이터베이스에서 세로 부분을 열(column, 필드), 가로 부분을 행(row, 레코드)이라고 부르는데, 이를 스프레드 시트에 시각화 한 것이 아래 그림이다. 아래 표의 이름을 <학생 정보>라고 정한 뒤 설명하겠다.

그렇게 되면 <학생 정보> 자체는 리스트 이름이 되며, [이름]란을 1행 1열이라고 정한다면, [서울특별시]는 3행 2열에 있는 변수가 된다. 이를 조금 더 컴퓨터화 시켜보면 '학생 정보 [4] [2]'는 '경기도 이천시'라는 항목 값을 가진다.

 

위와 같이 리스트를 이용하면 현실 세계에서 표형태로 표현할 수 있는 대부분의 자료를 프로그램으로 구현할 수 있다. 회사나 기관 등에서 사용하는 인사 정보 관리 시스템(위의 <학생 정보>표와 비슷한 형식), 각종 통계자료 검색 시스템, 금융 정보 조회 시스템 등도 모두 리스트를 활용해 만들어진 것이다. 이런 기본적인 표형식 리스트 뿐 아니라 조금 더 복잡한 시스템도 만들 수 있다.

 

분, 초단위로 발생하는 기록 정보를 모두 리스트에 저장한 후 원하는 시점에서 재생하는 것도 가능하기 때문에 히스토리(history) 혹은 로그(log) 관리 시스템에도 적용할 수 있으며, 리스트 기능을 확장 운용해 시멘틱 검색이나 빅데이터 분석과 같은 차세대 프로그램 제작도 가능해진다.

 

3. 큐와 스택

다양한 방면에서 쓰이는 리스트는 자료 처리 순서에 따라 큐(queue)와 스택(stack)의 구조로 응용할 수 있다.

큐 구조(좌측)와 스택 구조(우측)

컴퓨터 과학에서 큐(queue)는 시퀸스(리스트)의 한쪽 끝에 개체를 추가하고 다른 쪽 끝에서 개체를 제거함으로써 수정되는 방식을 가진 리스트에서 유지되는 개체(entity)의 집합을 말하며, 스택(stack)은 시퀸스(리스트)의 맨 위쪽에 개체를 추가하거나 제거함으로써 수정되는 방식을 가진 리스트에서 유지되는 개체(entity)의 집합을 말한다.

 

데이터 처리를 할 때 한쪽 방향으로만 데이터가 삽입되고 반대쪽 방향으로 데이터가 삭제되는 처리를 해야 할 경우에는 큐 구조를 사용한다. 이 연산 결과로 인해 데이터들은 먼저 삽입된 데이터가 먼저 삭제되는 선입선출(FIFO) 구조로 정리가 된다. 예를 들어 음식점의 키오스크를 보자. 음식 주문을 하는 사람이 특정 데이터를 입력하면 그 데이터는 조리사에게 출력된다. 이 때 두 정보는 같으며, 음식의 주문 순서에 따라 요리가 제공된다.

 

한편, 데이터의 삽입과 삭제가 같은 방향에서 일어나게 해야할 경우에는 스택 구조를 사용한다. 이 연산 결과로 인해 데이터들은 나중에 삽입된 데이터가 먼저 빠져나가는 후입선출(LIFO) 구조로 정리된다. 역순 문자열이나 최근 본 인터넷 페이지 열기, 실수로 닫은 인터넷 페이지 다시 열기와 같은 문제를 처리할 때 사용된다.

 

4. 정보 검색

리스트에 데이터를 하나씩 삽입하거나 삭제할 수도 있지만 외부에 저장된 파일을 한 번에 리스트로 불러올 수도 있다. 이렇게 불러들인 대량의 데이터는 추가적으로 데이터를 삽입, 삭제할 수 있을 뿐만 아니라 다양한 용도로 원하는 정보를 검색할 수도 있다.

 

주어진 대량의 데이터에서 조건에 맞는 정보를 찾아내는 작업을 검색(search)이라고 한다. 당연하겠지만 데이터가 저장된 방식에 따라 검색 방법도 달라질 것이다. 이러한 검색 방법에는 크게 순차 탐색(sequential search)과 이진 탐색(binary search)으로 나눌 수 있다.

	순차 탐색(sequential search)	이진 탐색(binary search)
다른 명칭	선형 검색(linear search)	반구간 검색(half-interval search) 로그 검색(logarithmic search)
정의	리스트 내에서 요소를 찾는 검색 알고리즘	정렬된 배열(array) 내에서 목표값의 위치를 찾는 검색 알고리즘
특징	다른 검색 알고리즘에 비해 시간이 오래 걸림	다른 검색 알고리즘에 비해 걸리는 시간이 적음 일정한 순서에 의해 항목을 반씩 나누며 탐색

만약 데이터들이 순서 없이 무작위로 저장되어 있다면 원하는 정보를 검색하기 위해 처음부터 끝까지 데이터를 일일이 살펴보는 식의 검색 알고리즘을 사용하는데 이 때 사용되는 방법이 순차 탐색이다. 또, 데이터들이 어떤 순서에 의해 저장되어 있다면 저장된 데이터의 가운뎃 값을 기준으로 반쪽씩만 살펴보다오 원하는 데이터를 쉽게 찾아낼 수 있다. 이 때 쓰는 검색 방법을 이진 탐색이라고 한다.

 

순차 탐색은 주어진 모든 데이터를 처음부터 끝까지 순차적으로 비교하면서 찾는 방식이기 때문에 다른 검색 알고리즘에 비해 시간이 오래 걸린다. 이를 보안하기 위해 등장한 이진 탐색은 일정한 순서에 의해 저장된 리스트 항목을 반씩 나눠 가면서, 되풀이해 그 한 부분을 버리고 남은 부분을 탐색하는 방식이기 때문에 찾고자 하는 항목을 빠르게 찾아낼 수 있다. 다만 자료를 정렬한 뒤 탐색을 할 수 있기 때문에, 수많은 데이터가 무작위로 나열된 경우에는 당장 사용하기 어렵다.