1-1) 전산학개론 정리

1. 컴퓨터과학(CS)의 정의

많은 사람들이 컴퓨터과학을 "컴퓨터를 공부하는 학문" 또는 "프로그램을 짜는 학문"이라고 생각하지만, 이는 오해다.

컴퓨터과학(Computer Science)은 알고리즘(Algorithm)을 연구하는 학문이다.

알고리즘의 연구에는 다음 네 가지 영역이 포함된다:

• 알고리즘의 수학적·형식적 성질 (이론적 분석)
• 알고리즘의 하드웨어 구현 (컴퓨터 하드웨어)
• 알고리즘의 언어적 구현 (프로그래밍 언어)
• 알고리즘의 응용 (실제 문제 해결)

2. 알고리즘이란?

기본 정의

알고리즘이란 어떤 작업을 수행하기 위한 단계별 방법(step-by-step method)이다.

좀 더 엄밀하게 정의하면 다음과 같다:

알고리즘은 잘 정렬된(well-ordered), 모호하지 않은(unambiguous), 효과적으로 계산 가능한(effectively computable) 연산들의 모음으로, 실행하면 결과를 생성하고 유한한 시간 안에 종료된다.

알고리즘의 세 가지 핵심 요소

1. 모호하지 않아야 한다 — "다시 해"라는 지시는 모호하다. 무엇을 다시 하는지 명확해야 한다.
2. 효과적으로 계산 가능해야 한다 — 연산을 이해하는 것만으로는 부족하고, 실제로 수행할 수 있어야 한다.
3. 유한한 시간 안에 끝나야 한다 — 영원히 도는 무한 루프(infinite loop)가 있으면 알고리즘이 아니다.

알고리즘을 구성하는 세 가지 연산

왜 알고리즘이 중요한가?

어떤 문제를 풀기 위한 알고리즘을 명확하게 기술할 수 있으면, 그 해결 과정을 자동화(automate)할 수 있다. 여기서 알고리즘의 단계를 실행하는 주체를 컴퓨팅 에이전트(computing agent)라고 부른다. 이는 컴퓨터일 수도 있고, 로봇이나 사람이 될 수도 있다.

알고리즘 예시: 샴푸하기

이 예시에는 순차, 조건, 반복 연산이 모두 포함되어 있다.

1. 알고리즘의 표현: 의사코드(Pseudocode)

왜 자연어(한국어, 영어)로 알고리즘을 쓰면 안 되는가?

• 너무 장황하다 (verbose)
• 구조가 없어서 특정 부분을 찾기 어렵다
• 해석이 여러 가지로 가능하여 모호하다

의사코드란?

의사코드(Pseudocode)는 자연어와 프로그래밍 언어의 중간 형태로, 알고리즘을 설계하고 표현하는 데 사용된다. 정확한 문법 규칙을 외울 필요 없이, 핵심 로직을 명확하게 전달하는 것이 목적이다.

의사코드의 기본 구성 요소

① 순차 연산 (Sequential)

• 계산: Set the value of "변수" to "수식"
• 입력: Get a value for "변수" — 외부에서 값을 받아온다
• 출력: Print the value of "변수" — 결과를 바깥에 보낸다

② 조건 연산 (Conditional)

If "조건" is true then
    참일 때 실행할 명령들
Else
    거짓일 때 실행할 명령들

③ 반복 연산 (Iterative)

While ("조건") do
    반복할 명령들
End of the loop

반복문의 두 가지 유형

• Pretest loop: 반복 시작 전에 조건을 검사한다 (while문)
• Posttest loop: 반복 본문을 한 번 실행한 후에 조건을 검사한다 (do-while문)

2. 알고리즘 설계 예시

예시 1: 반복 덧셈으로 곱셈 구현하기

문제: 두 음이 아닌 정수 a, b가 주어졌을 때, a를 b번 더하여 a × b를 구한다.

Get values for a and b
If (a = 0 or b = 0) then
    Set product to 0
Else
    Set count to 0
    Set product to 0
    While (count < b) do
        Set product to (product + a)
        Set count to (count + 1)
    End of loop
Print product
Stop

a=100, b=5이면 → product = 100+100+100+100+100 = 500이 된다.

예시 2: 순차 검색 (Sequential Search)

문제: 이름 목록에서 특정 이름을 찾아 전화번호를 출력한다.

첫 번째 시도 (비효율적): 10,000개의 if문을 일일이 나열하는 방법. 모든 항목을 하나씩 비교해야 하므로 매우 비효율적이다.

최종 알고리즘:

Get values for NAME, N₁...N₁₀₀₀₀, T₁...T₁₀₀₀₀
Set i to 1, Found to NO
While (Found = NO) and (i ≤ 10,000) do
    If NAME = Nᵢ then
        Print Tᵢ
        Set Found to YES
    Else
        Add 1 to i
If (Found = NO) then
    Print 'Sorry, this name is not in the directory'
Stop

핵심은 Found 플래그를 사용해서 찾으면 즉시 멈추고, 끝까지 못 찾으면 안내 메시지를 출력하는 것이다.

예시 3: 최댓값 찾기 (Find Largest)

문제: n개의 숫자 리스트에서 가장 큰 값과 그 위치를 찾는다.

Get n, A₁, A₂, ..., Aₙ
Set largest to A₁
Set location to 1
Set i to 2
While (i ≤ n) do
    If Aᵢ > largest then
        Set largest to Aᵢ
        Set location to i
    Add 1 to i
End of loop
Print largest, location
Stop

예를 들어 A = [2, 7, 1, 9, 3]이면, largest = 9, location = 4가 출력된다.

예시 4: 패턴 매칭 (Pattern Matching)

문제: 텍스트 T₁T₂...Tₙ에서 패턴 P₁P₂...Pₘ이 나타나는 모든 위치를 찾는다.

핵심 아이디어 — 슬라이딩 윈도우(Sliding Window):

1. 패턴을 텍스트의 현재 위치에 정렬한다
2. 한 글자씩 비교하면서 전체 패턴이 일치하는지 확인한다
3. 일치하면 위치를 출력한다
4. 패턴을 한 칸 오른쪽으로 밀고 다시 비교한다

예: T = "AAGCCTGA", P = "CCT" → 위치 4에서 매칭 발견

Get n, m, T₁...Tₙ, P₁...Pₘ
Set k to 1
While (k ≤ n - m + 1) do
    Set i to 1
    Set Mismatch to NO
    While (i ≤ m) and (Mismatch = NO) do
        If Pᵢ ≠ T_{k+(i-1)} then
            Set Mismatch to YES
        Else
            Add 1 to i
    End of loop
    If Mismatch = NO then
        Print 'Match at position', k
    Add 1 to k
End of loop
Stop

이 알고리즘에는 이중 while 루프가 사용된다. 바깥 루프는 시작 위치 k를 이동시키고, 안쪽 루프는 해당 위치에서 패턴을 한 글자씩 비교한다.

3. 알고리즘 설계의 핵심 원칙

추상화(Abstraction)

복잡한 연산을 높은 수준의 명령어로 표현하는 것이다. 예를 들어 "리스트를 오름차순으로 정렬하라"는 한 줄로 쓰되, 구체적인 구현은 나중에 세분화(top-down design)한다.

하향식 설계(Top-Down Design)

문제를 큰 틀에서 먼저 설계한 후, 세부 사항을 점진적으로 구체화해 나가는 방식이다. 패턴 매칭 알고리즘에서 "텍스트 끝까지 비교"라는 큰 틀을 먼저 잡고, 이후에 구체적인 비교 로직을 채워 넣은 것이 좋은 예시다.

알고리즘 설계 시 확인할 것

1. 정확성(Correctness) — 올바른 결과를 내는가?
2. 효율성(Efficiency) — 비교 횟수 등 자원을 얼마나 사용하는가?

1. 효율성(Efficiency)이란?

효율성이란 알고리즘이 자원(시간, 공간)을 얼마나 아껴서 사용하는지를 나타내는 용어다. 같은 문제를 푸는 알고리즘이 여러 개 있을 때, 어떤 것이 더 빠르고 메모리를 적게 쓰는지 비교하는 것이 핵심이다.

벤치마크(Benchmark)란 서로 다른 알고리즘(또는 기계)의 성능을 비교·평가하기 위한 기준이다. 입력이 달라질 때 알고리즘이 얼마나 민감하게 반응하는지도 벤치마크를 통해 측정할 수 있다.

2. 시간 복잡도 기본 개념

시간 복잡도는 입력 크기 n이 커질 때 알고리즘의 작업량이 어떻게 변하는지를 나타낸다.

핵심 포인트: n이 작을 때는 Θ(n²)이 Θ(n)보다 빠를 수도 있다. 하지만 n이 충분히 커지면 Θ(n²)은 항상 Θ(n)보다 느려진다. 상수 계수(constant factor)와 상관없이 이 관계는 변하지 않는다.

3. 주요 알고리즘 분석

순차 탐색 (Sequential Search)

리스트의 처음부터 끝까지 하나씩 비교하면서 원하는 값을 찾는 알고리즘이다.

선택 정렬 (Selection Sort)

무작위 리스트를 오름차순(또는 내림차순)으로 정렬하는 알고리즘이다. 매 단계마다 남은 원소 중 가장 작은 값을 찾아서 앞으로 보내는 방식이다.

입력이 이미 정렬되어 있든 아니든, 항상 n²에 비례하는 비교를 수행한다는 것이 특징이다.

4. 데이터 정리(Data Cleanup) 알고리즘 비교

리스트에서 0을 제거하는 세 가지 방법을 비교한다.

① Shuffle-Left 알고리즘

왼쪽에서 오른쪽으로 훑으면서 0이 발견되면 그 뒤의 값들을 왼쪽으로 한 칸씩 밀어서 0을 제거하는 방식이다.

② Copy-Over 알고리즘

0이 아닌 값만 골라서 새로운 리스트에 복사하는 방식이다.

③ Converging-Pointers 알고리즘

왼쪽 포인터와 오른쪽 포인터가 중간에서 만날 때까지 이동하면서, 왼쪽에서 0을 발견하면 오른쪽의 값과 교환하는 방식이다.

세 알고리즘 비교 요약

→ Converging-Pointers가 시간과 공간 모두에서 가장 효율적이다. 다만 원래 순서가 보존되지 않는다는 단점이 있다.

5. 이분 탐색 (Binary Search)

"정렬된" 리스트에서 원하는 값을 찾는 알고리즘이다. 매번 탐색 범위를 절반으로 줄여 나가기 때문에 매우 빠르다.

동작 방식

1. 리스트의 중간값(mid)을 확인한다
2. 찾는 값과 같으면 → 탐색 종료
3. 찾는 값이 중간값보다 작으면 → 왼쪽 절반만 탐색한다
4. 찾는 값이 중간값보다 크면 → 오른쪽 절반만 탐색한다
5. 범위가 없어질 때까지 1~4를 반복한다

성능

비교: 10,000개의 리스트에서 순차 탐색은 최대 10,000번 비교하지만, 이분 탐색은 최대 약 14번(log₂10,000 ≈ 13.3)만 비교하면 된다. 엄청난 차이다!

주의: 이분 탐색은 반드시 리스트가 미리 정렬되어 있어야 사용할 수 있다.

6. 패턴 매칭 (Pattern Matching)

텍스트 T(길이 n)에서 패턴 P(길이 m)가 나타나는 모든 위치를 찾는 알고리즘이다. 슬라이딩 윈도우 방식으로 동작한다.

동작 방식

1. 패턴을 텍스트의 위치 1에 맞추고, 한 글자씩 비교한다
2. 불일치가 발견되면 패턴을 한 칸 오른쪽으로 밀고 다시 비교한다
3. 모든 글자가 일치하면 해당 위치를 출력한다
4. 텍스트 끝까지 반복한다

성능

이에 대해 시간복잡도가 O(n+m)으로 해결 가능한 알고리즘이 있다. 궁금하다면 → KMP 알고리즘

1. 사람 vs 컴퓨터: 데이터 표현 방식

사람은 10진수와 문자를 사용하지만, 컴퓨터는 2진수(0과 1)만 사용한다. 컴퓨터가 이진법을 사용하는 이유는 신뢰성 때문이다. 전자 회로는 두 가지 상태(on/off)를 안정적으로 유지할 수 있는데, 이를 Bistable system이라고 한다. 외부 입력에 따라 두 상태 중 하나로 전환되는 방식이다.

2. 숫자의 표현

2진수의 맨 왼쪽 비트(bit)는 부호(sign)를 나타낸다. 0이면 양수, 1이면 음수다.

3. 문자의 표현

ASCII는 표현할 수 있는 문자 수가 제한적이라서, 더 많은 문자를 담기 위해 Unicode가 만들어졌다.

4. 소리(Sound)의 디지털 변환

소리와 이미지는 원래 아날로그(analog) 신호다. 컴퓨터가 처리하려면 디지털(digital)로 변환해야 하는데, 이 과정을 digitize라고 한다.

소리의 기본 용어

샘플링(Sampling)

연속적인 소리 파형을 일정 간격으로 끊어서 값을 저장하는 방식이다. 저장된 값들(samples)을 이용해 원래 소리의 근사치를 구해서 재생한다.

소리 품질을 결정하는 두 가지 요소

예를 들어 CD 음질은 44,100Hz(sampling rate) × 16bit(bit depth)로 저장된다.

5. 이미지(Image)의 디지털 변환

이미지도 샘플링 방식으로 디지털화된다. 각 픽셀의 색상과 강도가 이미 고정되어 저장된다.

색상을 표현할 때는 RGB 인코딩 방식을 사용한다. 빨강(Red), 초록(Green), 파랑(Blue) 세 가지 색의 조합으로 모든 색을 표현하는 방식이다.

6. 데이터 압축 (Data Compression)

데이터 압축이란 데이터를 축소된 크기로 저장하여 공간과 시간을 절약하는 기법이다.

압축률 (Compression Ratio)

압축률 = 압축 전 데이터 크기 ÷ 압축 후 데이터 크기

위 예시에서는 19/10 ≈ 2, 즉 약 2배 압축된 것이다.

압축 방식의 두 가지 종류

Lossy 압축이 가능한 이유는, 사람의 귀나 눈에는 감지 한계가 있어서 버려진 데이터를 느끼지 못하기 때문이다.

7. 트랜지스터 (Transistor)

트랜지스터는 컴퓨터가 기가바이트(GB) 단위의 데이터를 처리할 수 있게 해주는 초소형 전자 장치다. Control line의 신호에 따라 on/off가 결정된다. 이 on/off가 바로 1과 0을 나타내는 것이다.

8. 불리언 논리와 게이트 (Boolean Logic & Gates)

불리언 논리 (Boolean Logic)

참/거짓을 나타내기 위한 하드웨어 및 논리 설계의 기초다. 1과 0만을 사용하여 참/거짓을 표현한다.

세 가지 기본 연산

게이트 (Gates)

게이트는 입력 값을 받아 불리언 연산을 수행한 후 출력 값을 내보내는 전자 장치다.

NAND는 AND의 결과를 반전시킨 것이고, NOR는 OR의 결과를 반전시킨 것이다.

9. 컴퓨터 회로 (Computer Circuits)

회로(Circuit)란?

회로는 입력(input), 게이트(gate), 출력(output)으로 구성된 논리 게이트들의 모임이다. 출력은 게이트들의 연결 방식에 의해 결정된다.

제어 회로 (Control Circuits)

산술적 계산이 목적이 아니라, 값을 골라내거나 어떤 연산을 사용할지 결정하는 회로다.

디코더 회로 (Decoder Circuit)

여러 개의 입력 중 하나의 출력을 선택하는 논리 회로다.

예를 들어 입력이 2개면 출력은 4개(2²), 입력이 3개면 출력은 8개(2³)가 가능하다.

멀티플렉서 회로 (Multiplexor Circuit)

여러 개의 데이터 입력 중에서 하나를 선택하여 출력하는 회로다.

예를 들어 8개의 입력(2³)이 있으면 3개의 선택 라인으로 그 중 1개를 골라서 출력한다.

디코더 vs 멀티플렉서 비교

디코더는 N개 입력으로 2ⁿ개 출력 중 하나를 활성화하는 것이고, 멀티플렉서는 2ⁿ개 데이터 입력 중 하나를 선택하여 통과시키는 것이다.

1. 폰 노이만 구조 (Von Neumann Architecture)

폰 노이만 구조는 현대 컴퓨터의 기본 설계다. 다음 4개의 주요 하위 시스템으로 구성된다:

2. 메모리와 캐시 (Memory & Cache)

메모리는 명령어와 실행 중인 데이터를 저장하고 검색하는 컴퓨터의 기능 유닛이다.

RAM vs ROM

메모리의 기본 동작

메모리의 기본 기능은 가져오기(Fetch)와 저장(Store) 두 가지다.

이 작업을 수행하기 위해 두 개의 특수 레지스터가 사용된다:

예를 들어 메모리 주소 5번에서 데이터를 가져오려면, MAR에 5를 넣고 fetch 명령을 내리면, 해당 데이터가 MDR에 담기는 방식이다.

3. 연산 논리 장치 (ALU)

ALU는 덧셈, 뺄셈, 비교 등의 연산을 수행하는 하위 시스템이다.

구성 요소

ALU는 레지스터에서 값을 가져와 연산을 수행하고, 결과를 다시 레지스터에 저장한다. 각 부품 간의 데이터 이동은 버스를 통해 이루어진다.

4. 제어 장치 (Control Unit)

저장 프로그램 (Stored Program)

저장 프로그램이란 메모리에 이진값으로 저장된 기계어 명령어 시퀀스를 말한다. 컴퓨터는 이 명령어들을 하나씩 가져와서 실행한다.

제어 장치의 세 가지 작업

1. Fetch (가져오기) — 메모리에서 다음 명령어를 가져온다
2. Decode (디코딩) — 명령어가 무엇을 의미하는지 해석한다
3. Execute (실행) — 해석된 명령어를 실행한다

이 세 단계를 반복하는 것을 폰 노이만 사이클 (Von Neumann Cycle)이라고 한다.

5. 기계어 (Machine Language)

기계어는 컴퓨터의 제어 장치가 직접 디코딩하고 실행할 수 있는 명령어다. 사람이 읽기 어려운 0과 1의 나열로 되어 있다.

기계어 명령어의 구성

명령어 집합 (Instruction Set)

Instruction set이란 해당 프로세서가 실행할 수 있는 모든 연산의 집합이다. 프로세서마다 지원하는 명령어 집합이 다를 수 있다.

6. 프로그램 실행 단계 요약

1. Fetch   → 메모리에서 명령어를 가져온다
2. Decode  → 명령어를 해석한다
3. Execute → 명령어를 실행한다
→ 다음 명령어로 돌아가서 1번부터 반복 (폰 노이만 사이클)

7. 폰 노이만 구조의 한계

폰 노이만 구조는 단순하고 효과적이지만, 몇 가지 한계가 있다:

• 크기와 복잡성 증가: 컴퓨터가 커질수록 회로가 복잡해진다
• 속도 향상 제한: 칩에 게이트를 더 가까이 배치하는 데 물리적 한계가 있다
• 성능 증가율 둘화: 새로운 기계의 성능 향상 폭이 점점 줄어들고 있다
• 폰 노이만 병목 현상 (Von Neumann Bottleneck): 메모리와 CPU 사이의 데이터 전송이 병목이 된다. 현대의 대규모 문제를 처리하기에 부족할 수 있다

8. 비-폰 노이만 구조 (Non-Von Neumann Architecture)

폰 노이만 구조의 한계를 극복하기 위해 병렬 처리(Parallel Processing) 방식이 등장했다. 한 번에 여러 작업을 동시에 수행하여 속도를 향상시킨다.

SIMD vs MIMD

SIMD는 예를 들어 이미지의 모든 픽셀에 같은 처리를 적용하는 경우에 유리하고, MIMD는 완전히 다른 작업을 동시에 수행해야 하는 경우에 적합하다.

1. 명령어 포맷 (3가지)

모든 명령어는 16비트로 구성된다. 상위 3비트가 opcode다.

2. 8가지 명령어

연산 명령어

메모리 명령어

분기 명령어

쉽게 정리하면

• add / addi / nand → 계산용
• lw / sw → 메모리 읽기/쓰기
• beq → if문 (조건 분기)
• jalr → goto (무조건 점프, 함수 호출)
• lui → 큰 숫자를 레지스터에 넣을 때 사용

3. 의사 명령어 (Pseudo-instructions)

의사 명령어는 프로그래머의 편의를 위해 제공되는 명령어로, 어셈블러가 실제 명령어로 변환해 준다.

기출 :

다음 코드가 어떻게 동작하는지 서술하시오.

답 : The following is an assembly-language program that count down from 5, stopping when it hits 0.