3.6 연습 문제¶

3.6.1 개념 확인¶

데이터 사이의 관계를 바탕으로 다음 세 상황에 대해 ‘선형 구조, 트리 구조, 네트워크 구조’ 중 하나를 고르고 이유를 설명하라.

참고 답안

선형 구조다. 맨 앞과 맨 뒤에 선 사람을 제외하면 각 사람은 앞뒤로 한 사람씩만 이웃하며, 관계가 하나의 선을 따라 이어진다.
트리 구조다. 각 학급은 한 학년에 속하고 각 학년은 학교에 속하므로, 관계가 위에서 아래로 계층적으로 펼쳐진다.
네트워크 구조다. 한 교차로가 여러 교차로와 연결될 수 있고 경로들이 순환을 이룰 수도 있으므로, 하나의 순서나 엄격한 계층으로 나열할 수 없다.

구조를 판단할 때는 메모리에서 차지하는 공간보다 원소 사이의 관계를 먼저 살펴보아야 한다.

논리적 순서 A → B → C를 저장하기 위해 다음과 같이 단순화한 두 메모리 배치 방식을 생각해 보자.

방법 가: A, B, C를 각각 번호가 20, 21, 22인 메모리 칸에 저장한다.
방법 나: A, B, C를 각각 번호가 20, 7, 31인 메모리 칸에 저장하고, A에 B의 위치를, B에 C의 위치를 기록한다.

참고 답안

방법 가는 연속된 메모리 칸을 사용하므로 연속 공간 저장이다. 방법 나는 노드가 여러 위치에 흩어져 있으므로 분산 공간 저장이다.
방법 가는 배열에, 방법 나는 연결 리스트에 더 가깝다.
논리적 순서는 메모리 칸 번호의 크기가 아니라 노드 사이에 기록된 연결 관계로 결정된다. A에 기록된 위치에서 B를 찾고, 다시 B에 기록된 위치에서 C를 찾을 수 있으므로 A, B, C에 차례대로 접근할 수 있다.

이는 논리적 구조와 물리적 구조가 같은 데이터 집합을 바라보는 서로 다른 두 관점임을 보여 준다.

한 학습 모임에서 학생 4명의 과제 제출 여부를 좌석 순서대로 기록한 결과가 다음과 같다.

[true, false, true, true]

각 원소에는 어떤 기본 자료형이 적합한가?
이 4개 원소를 좌석 순서대로 한 줄에 나열한 것은 어떤 논리적 구조인가?
나중에 각 학생의 과제 점수 [90, 0, 85, 100]를 기록하도록 바꾼다면, 달라지는 것은 데이터의 ‘내용 유형’인가, ‘조직 방식’인가? 이유를 설명하라.

참고 답안

각 원소는 ‘예’ 또는 ‘아니요’만 나타내므로 불리언 자료형 bool이 적합하다.
원소들이 좌석 순서대로 나열되어 선형 구조를 이루며, 배열에 저장할 수 있다.
달라지는 것은 내용 유형이다. 원소가 불리언 값에서 정수로 바뀐다. 조직 방식은 바뀌지 않는다. 데이터는 여전히 좌석 순서대로 한 줄에 나열되어 있으므로 배열이라는 선형 구조를 사용할 수 있다.

기본 자료형은 ‘무엇을 저장하는가’를, 자료 구조는 ‘데이터를 어떻게 구성하는가’를 설명한다.

음이 아닌 정수 n이 주어질 때, 이진수 표현에 포함된 1의 개수를 구하라.

비트 연산을 사용해야 하며, 이진수 표현을 문자열로 변환하거나 1의 개수를 바로 세어 주는 내장 함수를 사용해서는 안 된다.

풀이 힌트