mirror of
https://github.com/krahets/hello-algo.git
synced 2026-11-01 10:45:21 +08:00
Yudong Jin
2f561d3d51
* feat(ko): add the complete Korean online edition * Use UTF-8 for Python CI output on Windows * Remove print-book promotion from the Korean site * fix(ko): preserve emphasis before Korean particles
87 lines
5.0 KiB
Markdown
87 lines
5.0 KiB
Markdown
# 연습 문제
|
|
|
|
## 개념 확인
|
|
|
|
### 일상 속 데이터의 관계
|
|
|
|
데이터 사이의 관계를 바탕으로 다음 세 상황에 대해 ‘선형 구조, 트리 구조, 네트워크 구조’ 중 하나를 고르고 이유를 설명하라.
|
|
|
|
<!-- numbered-subquestions -->
|
|
|
|
1. 학생들이 한 줄로 서 있고, 각자 바로 앞과 뒤에 있는 사람만 신경 쓴다.
|
|
2. 학교를 ‘학교 → 학년 → 학급’의 계층으로 나누어 관리한다.
|
|
3. 도시의 도로가 여러 교차로를 연결한다. 한 교차로에서 여러 다른 교차로로 갈 수 있으며 순환하는 경로도 생길 수 있다.
|
|
|
|
??? success "참고 답안"
|
|
|
|
1. 선형 구조다. 맨 앞과 맨 뒤에 선 사람을 제외하면 각 사람은 앞뒤로 한 사람씩만 이웃하며, 관계가 하나의 선을 따라 이어진다.
|
|
|
|
2. 트리 구조다. 각 학급은 한 학년에 속하고 각 학년은 학교에 속하므로, 관계가 위에서 아래로 계층적으로 펼쳐진다.
|
|
|
|
3. 네트워크 구조다. 한 교차로가 여러 교차로와 연결될 수 있고 경로들이 순환을 이룰 수도 있으므로, 하나의 순서나 엄격한 계층으로 나열할 수 없다.
|
|
|
|
구조를 판단할 때는 메모리에서 차지하는 공간보다 원소 사이의 관계를 먼저 살펴보아야 한다.
|
|
|
|
### 논리적 순서를 메모리에 저장하는 방법
|
|
|
|
논리적 순서 `A → B → C`를 저장하기 위해 다음과 같이 단순화한 두 메모리 배치 방식을 생각해 보자.
|
|
|
|
- 방법 가: `A, B, C`를 각각 번호가 `20, 21, 22`인 메모리 칸에 저장한다.
|
|
- 방법 나: `A, B, C`를 각각 번호가 `20, 7, 31`인 메모리 칸에 저장하고, `A`에 `B`의 위치를, `B`에 `C`의 위치를 기록한다.
|
|
|
|
<!-- numbered-subquestions -->
|
|
|
|
1. 어느 방법이 연속 공간 저장이고, 어느 방법이 분산 공간 저장인가?
|
|
2. 두 방법은 각각 배열과 연결 리스트 중 어느 쪽에 더 가까운가?
|
|
3. 방법 나는 메모리 칸의 번호가 크기순으로 정렬되어 있지 않은데, 어떻게 `A → B → C`의 논리적 순서를 나타낼 수 있는가?
|
|
|
|
??? success "참고 답안"
|
|
|
|
1. 방법 가는 연속된 메모리 칸을 사용하므로 연속 공간 저장이다. 방법 나는 노드가 여러 위치에 흩어져 있으므로 분산 공간 저장이다.
|
|
|
|
2. 방법 가는 배열에, 방법 나는 연결 리스트에 더 가깝다.
|
|
|
|
3. 논리적 순서는 메모리 칸 번호의 크기가 아니라 노드 사이에 기록된 연결 관계로 결정된다.
|
|
`A`에 기록된 위치에서 `B`를 찾고, 다시 `B`에 기록된 위치에서 `C`를 찾을 수 있으므로 `A, B, C`에 차례대로 접근할 수 있다.
|
|
|
|
이는 논리적 구조와 물리적 구조가 같은 데이터 집합을 바라보는 서로 다른 두 관점임을 보여 준다.
|
|
|
|
### 과제 기록의 자료형과 구조
|
|
|
|
한 학습 모임에서 학생 4명의 과제 제출 여부를 좌석 순서대로 기록한 결과가 다음과 같다.
|
|
|
|
`[true, false, true, true]`
|
|
|
|
<!-- numbered-subquestions -->
|
|
|
|
1. 각 원소에는 어떤 기본 자료형이 적합한가?
|
|
2. 이 4개 원소를 좌석 순서대로 한 줄에 나열한 것은 어떤 논리적 구조인가?
|
|
3. 나중에 각 학생의 과제 점수 `[90, 0, 85, 100]`를 기록하도록 바꾼다면, 달라지는 것은 데이터의 ‘내용 유형’인가, ‘조직 방식’인가? 이유를 설명하라.
|
|
|
|
??? success "참고 답안"
|
|
|
|
1. 각 원소는 ‘예’ 또는 ‘아니요’만 나타내므로 불리언 자료형 `bool`이 적합하다.
|
|
|
|
2. 원소들이 좌석 순서대로 나열되어 선형 구조를 이루며, 배열에 저장할 수 있다.
|
|
|
|
3. 달라지는 것은 내용 유형이다. 원소가 불리언 값에서 정수로 바뀐다. 조직 방식은 바뀌지 않는다.
|
|
데이터는 여전히 좌석 순서대로 한 줄에 나열되어 있으므로 배열이라는 선형 구조를 사용할 수 있다.
|
|
|
|
기본 자료형은 ‘무엇을 저장하는가’를, 자료 구조는 ‘데이터를 어떻게 구성하는가’를 설명한다.
|
|
|
|
## 프로그래밍 연습
|
|
|
|
### 이진수 표현에서 1의 개수 세기
|
|
|
|
음이 아닌 정수 `n`이 주어질 때, 이진수 표현에 포함된 1의 개수를 구하라.
|
|
|
|
비트 연산을 사용해야 하며, 이진수 표현을 문자열로 변환하거나 1의 개수를 바로 세어 주는 내장 함수를 사용해서는 안 된다.
|
|
|
|
??? tip "풀이 힌트"
|
|
|
|
1. n & 1로 n의 가장 오른쪽 비트를 얻어 그 비트가 1인지 확인할 수 있다.
|
|
2. 오른쪽으로 한 비트 이동하면 현재 가장 오른쪽 비트가 제거된다. 대부분의 언어에서는 >> 연산자를 사용한다.
|
|
3. 비트를 하나씩 확인하고 오른쪽으로 이동하는 방법을 완성한 뒤, n & (n - 1)이 n의 가장 오른쪽 1을 0으로 바꾼다는 점도 살펴보자.
|
|
|
|
[LeetCode](https://leetcode.com/problems/number-of-1-bits/){ .rounded-button .exercise-button target="_blank" rel="noopener noreferrer" }
|