모두를 위한 컴퓨터 과학(하버드CS50 2019)(2)

 

 

자료형과 메모리 크기

C 프로그래밍에서는 모든 데이터는 메모리에 저장되고, 자료형(Data Type) 에 따라 필요한 메모리 크기가 결정된다.

bool	1 byte	참/거짓 값
char	1 byte	하나의 문자 (예: ‘A’)
int	4 bytes	정수
float	4 bytes	소수점 수 (정밀도 낮음)
long	8 bytes	아주 큰 정수
double	8 bytes	더 높은 정밀도의 소수
string	? bytes	문자들의 집합 (문자 배열)

string은 문자(char)의 배열이기 때문에, 크기는 문자열 길이에 따라 달라진다. (문자 수 + 1(널 문자 ‘\0’) 만큼 바이트를 사용)

---

컴퓨터 메모리와 바이트 개념

• RAM은 컴퓨터에서 프로그램을 실행할 때 데이터를 저장하는 임시 기억장치이다.
• RAM은 수십억 개의 비트(bit) 들로 구성되어 있다.
  • 예) 1GB = 약 10억 개의 비트.
• 메모리는 1바이트(8비트) 단위로 관리된다.
• 각 바이트는 순서대로 번호(주소) 가 붙어 있다.
  • 0번 주소, 1번 주소, 2번 주소, …

→ 컴퓨터는 이 메모리 주소를 이용해서 데이터를 저장하고 읽는다.

---

자료형에 따른 메모리 할당

• 예를 들어 int 하나를 선언하면, 컴퓨터는 연속된 4바이트를 예약한다. 그리고 안에 0과 1로 구성된 데이터가 저장된다.

• 변수의 자료형에 따라 메모리 공간이 다르게 할당된다.
• 자료형은 메모리 사용량을 결정하는 중요한 요소이다.

---

문자(char) 저장과 출력

#include <stdio.h>

int main(void)
{
    char c1 = 'H';
    char c2 = 'I';
    char c3 = '!';
}

• char는 항상 홑따옴표(’ ’) 를 사용해서 한 문자를 저장한다.
• 큰따옴표(” “)는 문자열(string)에서 사용된다.

출력해보기

printf("%c %c %c\n", c1, c2, c3);

• %c는 문자(char) 를 출력한다.
• 결과:

H I !

 

숫자로 출력하기 (형변환)

printf("%i %i %i\n", (int)c1, (int)c2, (int)c3);

• %i는 정수(int) 를 출력한다.
• (int)c1처럼 (int) 를 붙여주면 형변환(casting) 이 일어난다.
• 결과:

72 73 33

• 사실 현대 clang 컴파일러에서는 char를 직접 %i로 출력해도 암묵적으로 형변환된다. 반대로도 가능하다.

printf("%i %i %i\n", c1, c2, c3);

• 위처럼 해도 같은 결과가 나온다.

---

추상화(Abstract)

• 사실 메모리에는 0과 1만 저장되지만,
• 우리는 char, int, float 같은 추상화된 형태로 데이터를 다룬다.
• 프로그래밍 언어 덕분에
• 01001000 같은 비트를 신경쓰지 않고도 문자나 숫자를 쉽게 다룰 수 있는 것이다.

---

 

#include <stdio.h>
#include <cs50.h>

int main(void)
{
    int score1 = 72;
    int score2 = 73;
    int score3 = 33;

    printf("Average: %i\n", (score1 + score2 + score3) / 3);
}

• 평균을 구하는 프로그램이다.
• 하지만 학생 수가 많아지면 코드가 비효율적이 된다.
• 복사/붙여넣기가 필요하다는 것은 비효율적인 코드라는 것이고,
• 비효율적이라는 것은 코드 디자인을 개선할 여지가 있다는 것이다.

 

배열 사용

배열을 쓰면 같은 타입의 변수를 연속적으로 저장할 수 있다.

#include <stdio.h>
#include <cs50.h>

int main(void)
{
    int scores[3];       // 크기 3의 int 배열 선언
    scores[0] = 72;
    scores[1] = 73;
    scores[2] = 33;

    printf("Average: %i\n", (scores[0] + scores[1] + scores[2]) / 3);
}

• int scores[3];
  • 정수형 3칸짜리 배열을 만들었다.
  • 배열 선언 시에는 공간을 의미하기 때문에 3개의 공간을 만드려면, [3]을 선언해야한다.
• scores[0], scores[1], scores[2]
  • 배열의 인덱스는 0부터 시작한다.
• 배열을 사용하면 같은 타입의 값을 깔끔하게 관리할 수 있다.

---

위 코드도 여전히 비효율적인 부분이 존재한다.

#include <stdio.h>
#include <cs50.h>

// 함수 선언 (프로토타입)
float average(int length, int array[]);

int main(void)
{
    // 사용자로부터 점수 개수 입력받기
    int n = get_int("Number of scores: ");

    // 가변 크기 배열(VLA, Variable Length Array) 선언
    int scores[n];

    // 점수 입력받아 배열에 저장
    for (int i = 0; i < n; i++)
    {
        scores[i] = get_int("Score: ");
    }

    // 평균 계산 후 출력
    printf("Average: %.1f\n", average(n, scores));
}

// 평균 계산 함수
float average(int length, int array[])
{
    int sum = 0;
    
    // 배열의 모든 원소를 합산
    for (int i = 0; i < length; i++)
    {
        sum += array[i];
    }

    // 형변환 후 평균 계산 (float로 반환)
    return (float) sum / (float) length;
}

 

코드 설명

float average(int length, int array[])	길이와 배열을 매개변수로 받아 평균을 계산하는 함수 선언
int n = get_int("Number of scores: ");	점수 개수 입력
int scores[n];	n 크기의 정수 배열 선언
for (int i = 0; i < n; i++)	배열에 점수 입력 반복
sum += array[i];	배열 원소를 하나씩 합산
return (float) sum / (float) length;	합을 길이로 나누어 평균을 계산 (형변환 필수)

 

추가 개념

(1) 배열을 함수에 전달할 때

• 함수 매개변수 int array[]는 사실 포인터처럼 동작한다.
• 배열 이름은 배열의 시작 주소를 의미한다.

→ 배열을 함수에 넘길 때 복사되는 것이 아니라 주소(참조) 가 넘어간다. (성능에 유리)

---

(2) 가변 크기 배열 (VLA)

int scores[n];

• n이 사용자 입력에 따라 변하므로,
• 크기가 고정되지 않은 배열을 만든다.
• C99 표준 이후 가변 길이 배열(VLA, Variable Length Array)이 허용되었다.

→ 하지만 주의: 너무 큰 n을 입력하면 메모리 초과(segmentation fault)가 날 수 있다.

---

(3) 형변환 (Casting)

return (float) sum / (float) length;

• sum과 length 모두 int 타입이라서 그냥 나누면 int 결과만 나온다.
• 둘 중 하나라도 float로 바꾸면 결과가 소수점까지 나오는 부동소수점 연산이 된다.

추가 설명:

• (int + float) → float
• (int / float) → float
• → 연산 시 자료형이 다르면 더 큰 타입(float)으로 자동 승격된다.

---

sizeof 연산자로 배열 크기 알아내기

sizeof는 데이터의 크기(바이트 수) 를 알려주는 연산자입니다.

배열에서 sizeof를 사용하면:

• sizeof(배열) → 배열 전체의 크기(바이트 단위)
• sizeof(배열[0]) → 배열 한 칸(원소 하나)의 크기

→ 이 둘을 나누면 배열 안에 몇 개의 원소가 있는지 알 수 있습니다.

배열 크기 자동 계산하기

#include <stdio.h>

int main(void)
{
    int scores[] = {72, 73, 33};

    int length = sizeof(scores) / sizeof(scores[0]);

    printf("Length of array: %i\n", length);

    for (int i = 0; i < length; i++)
    {
        printf("Score %i: %i\n", i, scores[i]);
    }
}

출력:

Length of array: 3
Score 0: 72
Score 1: 73
Score 2: 33

배열 선언 + 초기화	int scores[] = {72, 73, 33};
배열 크기 구하기	sizeof(scores) / sizeof(scores[0])
배열 반복 처리	for문을 이용해 순서대로 접근

---

string은 사실 char 배열

• C 표준 언어에는 string 자료형이 없습니다.
• CS50에서 string은 typedef char *string;로 정의된 char 포인터입니다.

즉, 문자열(string)은 문자(char)들의 배열입니다.

C 표준 언어에는 string 자료형이 없습니다.

• C에서는 기본적으로 문자 하나를 저장하는 char 타입만 존재합니다.
• 그래서 문자열(string)을 표현하려면 char 배열을 사용합니다.

그렇다면 string은 뭘까?

• 우리가 CS50 수업이나 몇몇 라이브러리에서 사용하는 string은교육용으로 따로 정의된 별명(alias) 입니다.
• 실제 C 표준에 있는 타입이 아니라,
• CS50에서는 string을 사실 다음처럼 정의해놨습니다:

typedef char *string;

• typedef는 “새로운 이름을 붙여주는 문법“입니다.
• 그래서 string은 사실 char * (char 포인터) 를 의미합니다.

즉, CS50의 string은 “문자(char)들의 시작 주소”를 가리키는 포인터입니다.

---

문자열을 사용할 때는 큰따옴표(””) 사용

• 한 문자: 작은따옴표 'A'
• 문자열: 큰따옴표 "Alice"

string name = "Alice";

"Alice"는 메모리에 다음처럼 저장됩니다: Alice\0

• 마지막에는 항상 \0 (널 문자)가 들어가서
• 문자열의 끝을 표시합니다.

\0은 1바이트이고, 모든 비트가 0(00000000)입니다.

---

string 배열 만들기

#include <stdio.h>
#include <cs50.h>

int main(void)
{
    string names[4];
    names[0] = "EMMA";
    names[1] = "RODRIGO";
    names[2] = "BRIAN";
    names[3] = "DAVID";

    printf("%s%c%i\n", names[0], names[0][1], names[0][400]);
}

• names는 string 타입(즉, char *)의 배열이다.
• names[0]은 "EMMA"라는 문자열을 가리킨다.

출력:

EMMAM0

• %s → names[0] → “EMMA” 출력
• %c → names[0][1] → ‘M’ 출력
• %i → names[0][400] → 0 출력

names[0]	“EMMA” 문자열 출력
names[0][1]	두 번째 문자 ‘M’ 출력
names[0][400]	메모리 400칸 뒤를 참조하는데, 거기에 우연히 0(널 문자)이 있어서 0 출력됨

C에서는 배열의 범위를 벗어난 접근(Out-of-Bounds Access)을 막아주지 않기 때문에,ㅠ names[0][400] 같이 엉뚱한 메모리 접근도 가능하지만, 이는 정상적이지 않은 동작입니다. (심각한 경우 프로그램이 강제 종료될 수도 있습니다.)

---

 

기본 흐름: 문자열 반복하기

#include <stdio.h>
#include <cs50.h>
#include <string.h>

int main(void)
{
    string s = get_string("Input: ");

    printf("Output:");

    // 방법 1: 널 문자('\0')를 만날 때까지 반복
    for (int i = 0; s[i] != '\0'; i++)
    {
        printf("%c", s[i]);
    }

    // 방법 2: strlen()을 이용해서 문자열 길이만큼 반복
    int n = strlen(s);
    for (int i = 0; i < n; i++)
    {
        printf("%c", s[i]);
    }

    printf("\n");
}

 

추가 설명

• s[i] != '\0'
  • 문자열 끝을 표시하는 널 문자를 만날 때까지 반복한다.
  • ’\0’은 문자 하나이므로 홑따옴표(’’) 를 사용한다.
• strlen(s)
  • string.h 라이브러리 함수.
  • 문자열의 길이를 계산해준다.
• strlen(s)를 for문 안에서 매번 호출하면 비효율적이다.
  • 문자열 길이는 고정되어 있으니까, 미리 n에 저장하고 사용하는 것이 좋다.

---

소문자를 대문자로 바꾸기 (ASCII 수치 조작)

#include <cs50.h>
#include <stdio.h>
#include <string.h>

int main(void)
{
    string s = get_string("Before: ");

    printf("After:");

    for (int i = 0, n = strlen(s); i < n; i++)
    {
        if (s[i] >= 'a' && s[i] <= 'z')
        {
            printf("%c", s[i] - 32);  // 소문자 → 대문자 (ASCII 코드 차이: 32)
        }
        else
        {
            printf("%c", s[i]);
        }
    }

    printf("\n");
}

• ASCII (American Standard Code for Information Interchange) 는
  • 미국에서 만든 문자 인코딩 표준입니다.
  • 7비트(0~127) 범위를 사용합니다.
• C에서는 char 타입이 바로 ASCII 코드값을 저장하는 데 사용됩니다.
• printf("%c", 65); → 출력: A
• printf("%i", 'A'); → 출력: 65

---

ctype.h 라이브러리를 활용해서 깔끔하게

아래 사이트에서 C++ 및 C의 다양한 라이브러리를 확인할 수 있다.(https://cplusplus.com/)

https://cplusplus.com/

 

#include <cs50.h>
#include <stdio.h>
#include <string.h>
#include <ctype.h> // 문자 검사와 변환 함수 제공

int main(void)
{
    string s = get_string("Before: ");

    printf("After:");

    for (int i = 0, n = strlen(s); i < n; i++)
    {
        printf("%c", toupper(s[i]));
    }

    printf("\n");
}

 

• toupper(c)
  • 문자 c를 대문자로 변환해준다.
  • 이미 대문자면 그대로 반환하고, 소문자면 대문자로 바꿔준다.
• ctype.h
  • 문자 처리 관련 함수를 모아놓은 표준 라이브러리이다.
  • (예: tolower(), isupper(), islower(), isdigit(), isalpha() 등)

 

---

Command-line Argument (명령줄 인자)와 C의 main 함수

• Command-line argument는
• 프로그램을 실행할 때 프로그램 이름 뒤에 추가로 주는 입력값입니다.

./program hello world

• ./program → 프로그램 이름
• hello, world → 명령줄 인자(argument)

---

C의 main 함수: void 대신 인자를 받을 수 있다

기본형

int main(void)

• 인자 없이 프로그램을 실행하는 기본 구조입니다.

명령줄 인자 받기

int main(int argc, string argv[])

• argc: Argument Count (인자의 개수)
• argv: Argument Vector (인자의 배열)

특징:

• argv[0]: 항상 프로그램 이름 (./program)
• argv[1], argv[2], …: 프로그램에 전달된 실제 인자들

argc와 argv는 관행적으로 쓰는 이름입니다. (다른 이름을 써도 되지만 관습적으로 이렇게 씁니다.)

간단한 예제

#include <cs50.h>
#include <stdio.h>

int main(int argc, string argv[])
{
    if (argc == 2)
    {
        printf("hello, %s\n", argv[1]);
    }
    else
    {
        printf("hello, world\n");
    }
}

실행 예시

./argv	hello, world
./argv Emma	hello, Emma

설명:

• 인자가 1개(프로그램 이름만 있을 때)는 “hello, world” 출력.
• 인자가 2개(프로그램 이름 + 이름)일 때는 “hello, (이름)” 출력.

---

명령줄 인자 검사와 프로그램 종료

더 나은 예제

#include <cs50.h>
#include <stdio.h>

int main(int argc, string argv[])
{
    if (argc != 2)
    {
        printf("missing command-line argument\n");
        return 1; // 비정상 종료를 나타냄
    }

    printf("hello, %s\n", argv[1]);
    return 0; // 정상 종료
}

주요 포인트

• return 0: 프로그램이 정상적으로 끝났다는 뜻.
• return 1 (또는 다른 값): 에러가 발생했음을 운영체제에 알려준다.

C에서 main() 함수는 항상 int를 반환하고, 그 값은 프로그램 실행 결과(exit code)를 의미합니다.

더 알아보기“exit”만 치고 실행되게 하려면?

방법 1: 프로그램을 PATH에 등록된 디렉토리에 복사 // 리눅스, macOS에서는 보통(/usr/bin, /bin, /usr/local/bin)같은 곳이 PATH에 등록되어 있습니다. // exit 프로그램을 컴파일해서 만들고 PATH에 포함된 디렉토리에 복사하면 됩니다.

방법 2: 현재 폴더(.)를 PATH에 추가 (추천은 안 함, 보안 상 좋지 않음)

---

프로그램 이름이 argv[0]이다

// 예를 들어 ./exit Emma 로 실행하면
argv[0] == "./exit"
argv[1] == "Emma"

• 프로그램 이름도 명령줄 인자에 포함되기 때문에
• 실제 데이터는 argv[1]부터 시작합니다.

---

명령줄 인자 활용 예시: 간단한 암호화 프로그램

명령줄 인자를 통해 암호화 키(key) 를 입력받을 수 있습니다.

개념 요약:

• 문자를 ASCII 숫자로 변환한다.
• 키 값을 더해서 암호화한다.
• 복호화할 때는 키 값을 빼준다.

(이건 유명한 고전 암호법인 시저 암호(Caesar Cipher) 와 연결됩니다.)

---

컴퓨터는 배열의 내용을 하나하나 읽어야 한다

• 메모리에 저장된 배열은 물리적으로 연속된 메모리 공간에 나열되어 있다.
• 따라서 컴퓨터는 순서대로 각 원소를 읽을 수 있다.

선형 탐색 (Linear Search)

 

선형 탐색이란?

• 배열을 처음부터 끝까지 차례대로 살펴보면서 원하는 값을 찾는 방법이다.
• 배열이 정렬되어 있지 않아도 사용할 수 있다.

 

선형 탐색 의사코드 (pseudocode)

for i from 0 to n-1
    if i번째 요소가 50이면
        return true
return false

• 배열의 0번째 원소부터 n-1번째 원소까지 하나씩 살펴본다.
• 찾고자 하는 값(50)이 나오면 true 반환.
• 끝까지 찾지 못하면 false 반환.

 

선형 탐색 특징

장점	정렬이 필요 없음, 간단함
단점	최악의 경우 배열 전체를 다 봐야 함 (시간 오래 걸림)
시간 복잡도	O(n) (n은 배열 크기)

 

---

이진 탐색 (Binary Search)

 

이진 탐색이란?

• 배열이 미리 오름차순(또는 내림차순) 정렬되어 있을 때 사용할 수 있다.
• 매번 배열의 가운데 원소를 기준으로탐색 범위를 반으로 줄여나가는 방법이다.
• 찾고자 하는 값이 왼쪽에 있는지, 오른쪽에 있는지를 판단하고 탐색 범위를 반으로 줄여나가는 방법이다.

이진 탐색 의사코드 (pseudocode)

if 배열에 아무것도 없다면
    return false

중간 요소를 확인한다
if 중간 요소가 50이면
    return true
else if 50 < 중간 요소라면
    왼쪽 절반을 대상으로 다시 이진 탐색
else if 50 > 중간 요소라면
    오른쪽 절반을 대상으로 다시 이진 탐색

• 배열 가운데 값을 본다.
• 찾는 값이 가운데 값보다 작으면 왼쪽 절반을 다시 탐색한다.
• 크면 오른쪽 절반을 다시 탐색한다.
• 이 과정을 찾을 때까지 또는 찾을 수 없을 때까지 반복한다.

 

이진 탐색 특징

장점	탐색 범위를 매번 반으로 줄이기 때문에 빠름
단점	배열이 반드시 정렬되어 있어야 함
시간 복잡도	O(log n)

---

컴퓨터 과학자들이 문제를 분석하는 방법: Big-O, Big-Ω, Big-Θ

• 알고리즘 분석 시에 n/2와 n을 구분하지 않는데, 숫자가 커질수록 거의 같은 그래프 형태가 되기 때문이다.
• Big-O(빅오)는 항상 “최악”을 기준으로 봅니다. 최악의 경우 시간이고 실행시간 상한으로 볼 수 있다.
• Big-Ω(빅오메가)는 “최선”을 본다. 최선의 경우 시간이고 실행식간 하한으로 볼 수 있다.
• Big-Θ(빅세타)는 “평균적이고 일관된” 경우를 본다. 최선 = 최악 (대체로 이 시간 걸림)

---

 

Big-O (빅오 표기법)

Big-O는 “최악의 경우(가장 오래 걸릴 때) 얼마나 걸리는지” 를 나타냅니다.

형식:

O(함수)

 

• O(1) → 입력 크기에 관계없이 항상 고정 시간
• O(n) → 입력 크기에 비례해서 시간 증가
• O(log n) → 입력이 커져도 천천히 증가 (이진 탐색)

Big-O 특징

최악의 경우 시간 측정	가장 오래 걸리는 경우를 기준
보수적 평가	안전하게 시스템을 설계할 수 있다
성능 한계 예측	시스템이 얼마나 큰 문제를 처리할 수 있을지 계산 가능

 

Big-O 간단 예시

알고리즘Big-O

선형 탐색	O(n)
이진 탐색	O(log n)
버블 정렬	O(n²)
병합 정렬(Merge Sort)	O(n log n)
해시 테이블 검색	O(1)

 

---

Big-Ω (빅 오메가 표기법)

Big-Ω(오메가)는 “최선의 경우(가장 빨리 끝나는 경우) 얼마나 빠른지” 를 나타냅니다.

형식:

Ω(함수)

• 선형 탐색의 경우, 찾는 값이 첫 번째에 있다면 → Ω(1)
• 버블 정렬이 이미 정렬된 배열을 받을 때 → Ω(n)

Big-Ω 특징

최선의 경우 시간 측정	가장 빠르게 끝날 때 기준
운이 좋으면 더 빠를 수 있다	하지만 항상 이만큼 빠르다고 보장할 수는 없음

 

---

Big-Θ (빅 세타 표기법)

Big-Θ(세타)는 “최선과 최악이 같은 속도로 성장할 때” 를 나타냅니다.

형식:

Θ(함수)

• 이진 탐색은 항상 Θ(log n) 이다. (최선도 최악도 log n)
• 단순 합산(모든 원소 더하기)은 항상 Θ(n) 이다. (입력 크기에 정확히 비례)

Big-Θ 특징

최선 = 최악	입력 크기에 대해 항상 비슷한 시간 소요
알고리즘 분석의 이상적인 형태	“이 알고리즘은 대략 이 정도 걸립니다.“라고 정확히 예측 가능

 

 

---

선형 탐색 (Linear Search)

• 설명: 배열 처음부터 끝까지 차례로 찾기
• Big-O: O(n)
• Big-Ω: Ω(1) (처음에 찾으면)
• Big-Θ: Θ(n) (일반적으로)

---

이진 탐색 (Binary Search)

• 설명: 정렬된 배열에서 반씩 잘라가며 찾기
• Big-O: O(log n)
• Big-Ω: Ω(1) (운 좋으면 첫 번째 시도에 찾음)
• Big-Θ: Θ(log n)

 

---

버블 정렬 (Bubble Sort)

// 의사코드
Repeat (n - 1) times:
    For i from 0 to n - 2:
        If element i > element i+1:
            Swap element i and element i+1

• 설명: 인접한 두 수를 비교해가며 정렬
• Big-O: O(n²) (최악: 완전 뒤죽박죽)
• Big-Ω: Ω(n) (최선: 거의 정렬되어 있음)
• Big-Θ: Θ(n²)

#include <stdio.h>

void bubble_sort(int array[], int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = 0; j < n - i - 1; j++)
        {
            if (array[j] > array[j + 1])
            {
                // swap
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
}

int main(void)
{
    int arr[5] = {5, 3, 1, 4, 2};
    bubble_sort(arr, 5);

    for (int i = 0; i < 5; i++)
    {
        printf("%i ", arr[i]);
    }
    printf("\n");
}

 

---

 

선택 정렬 (Selection Sort)

// 의사코드
Repeat n - 1 times:
    Find the smallest element in the unsorted part
    Swap it with the first element of the unsorted part

• 설명: 최솟값을 찾아서 맨 앞에 놓기 반복
• Big-O: O(n²)
• Big-Ω: Ω(n²)
• Big-Θ: Θ(n²)

 

#include <stdio.h>

void selection_sort(int array[], int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        int min_index = i;
        for (int j = i + 1; j < n; j++)
        {
            if (array[j] < array[min_index])
            {
                min_index = j;
            }
        }

        // swap
        int temp = array[i];
        array[i] = array[min_index];
        array[min_index] = temp;
    }
}

int main(void)
{
    int arr[5] = {5, 3, 1, 4, 2};
    selection_sort(arr, 5);

    for (int i = 0; i < 5; i++)
    {
        printf("%i ", arr[i]);
    }
    printf("\n");
}

---

재귀 정렬(Recursive Sort)

재귀 이해하기

#include <cs50.h>
#include <stdio.h>

void draw(int);

int main(void)
{
  int height = get_int("Height: ");

  draw(height);
}

void draw(int h)
{
  if(h == 0)
  {
    return;
  }

  draw(h - 1);

  for (int i = 0; i < h; i++)
  {
    printf("#");
  }
  printf("\n");
}

• 먼저 draw(h - 1)을 호출한다.
• → 즉, 아직 그리지 않고 더 작은 문제를 해결하려고 한다.
• 그러다가
• h == 0이 되면 아무 것도 하지 않고 return 한다.
• 그 후에각각의 h에 대해 #을 출력한다.
• 하나씩 돌아오면서 (stack unwind)

→ “재귀는 문제를 작게 나누고, 나중에 거꾸로 작업한다.”

메모리(Stack) 흐름

draw(3)	→ draw(2) 호출 대기
draw(2)	→ draw(1) 호출 대기
draw(1)	→ draw(0) 호출 대기
draw(0)	바로 종료
draw(1) 복귀	# 출력
draw(2) 복귀	## 출력
draw(3) 복귀	### 출력

---

1. 퀵 정렬 (Quick Sort)

// 의사코드
If array has 0 or 1 elements:
    return (already sorted)

Choose a pivot element
Partition array into two subarrays:
    Left subarray: elements less than pivot
    Right subarray: elements greater than pivot

Recursively apply quick sort to left subarray
Recursively apply quick sort to right subarray

• 설명: 배열을 반으로 나누고 합치면서 정렬
• Big-O: O(n²) (불균형 분할 시)
• Big-Ω: Ω(n log n)
• Big-Θ: Θ(n log n)

#include <stdio.h>

// 요소들을 정렬하기 위해 두 값을 swap하는 함수
void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 파티션을 수행하는 함수 (피벗 기준으로 분할)
int partition(int array[], int low, int high)
{
    int pivot = array[high]; // 피벗을 배열의 마지막 요소로 선택
    int i = low - 1;

    for (int j = low; j < high; j++)
    {
        if (array[j] < pivot)
        {
            i++;
            swap(&array[i], &array[j]);
        }
    }
    swap(&array[i + 1], &array[high]);
    return i + 1;
}

// 퀵 정렬 함수 (재귀 호출)
void quick_sort(int array[], int low, int high)
{
    if (low < high)
    {
        int pi = partition(array, low, high);

        // 왼쪽 부분 재귀 정렬
        quick_sort(array, low, pi - 1);
        // 오른쪽 부분 재귀 정렬
        quick_sort(array, pi + 1, high);
    }
}

int main(void)
{
    int arr[5] = {5, 3, 1, 4, 2};
    int n = 5;

    quick_sort(arr, 0, n - 1);

    for (int i = 0; i < n; i++)
    {
        printf("%i ", arr[i]);
    }
    printf("\n");
}

---

2. 병합 정렬 (Merge Sort)

// 의사코드
If n < 2:
    return

Split the array into two halves
Recursively sort the left half
Recursively sort the right half
Merge the two sorted halves into a single sorted array

• 설명: 배열을 반으로 나누고 합치면서 정렬
• Big-O: O(n log n)
• Big-Ω: Ω(n log n)
• Big-Θ: Θ(n log n)

#include <stdio.h>

void merge(int array[], int left, int mid, int right)
{
    int n1 = mid - left + 1;
    int n2 = right - mid;

    int L[n1], R[n2];

    // 왼쪽 배열 복사
    for (int i = 0; i < n1; i++)
        L[i] = array[left + i];

    // 오른쪽 배열 복사
    for (int j = 0; j < n2; j++)
        R[j] = array[mid + 1 + j];

    // 병합
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j])
        {
            array[k++] = L[i++];
        }
        else
        {
            array[k++] = R[j++];
        }
    }

    // 왼쪽 남은 것 복사
    while (i < n1)
    {
        array[k++] = L[i++];
    }

    // 오른쪽 남은 것 복사
    while (j < n2)
    {
        array[k++] = R[j++];
    }
}

void merge_sort(int array[], int left, int right)
{
    if (left < right)
    {
        int mid = left + (right - left) / 2;

        merge_sort(array, left, mid);
        merge_sort(array, mid + 1, right);

        merge(array, left, mid, right);
    }
}

int main(void)
{
    int arr[5] = {5, 3, 1, 4, 2};
    merge_sort(arr, 0, 4);

    for (int i = 0; i < 5; i++)
    {
        printf("%i ", arr[i]);
    }
    printf("\n");
}

---

 

struct (구조체)란?

struct(구조체) 는 여러 가지 다른 타입의 데이터를 한 덩어리로 묶어 저장할 수 있게 해주는 C의 데이터 구조입니다.

“관련된 값들을 하나로 묶어주는 박스” 라고 이해하면 됩니다.

struct 기본형

struct person
{
    string name;
    string number;
};

• struct person은 이름(name)과 전화번호(number)를 가지는 구조입니다.
• 각각의 요소를 멤버(member) 라고 부릅니다.

 

typedef란?

typedef(타입 정의) 는 기존 타입에 새로운 이름(alias) 을 붙여주는 기능입니다.

“긴 이름을 짧게 부를 수 있게 해주는 별명 만들기” 입니다.

 

typedef struct를 함께 쓰는 이유

C에서는 원래 struct person 이렇게 써야 하지만, typedef를 이용하면 struct를 생략하고 바로 person만 쓸 수 있습니다.

typedef struct
{
    string name;
    string number;
} person;

• 이렇게 하면 나중에 struct 키워드를 생략하고
• 그냥 person 타입으로 선언할 수 있습니다.

person people[4];

• 훨씬 코드가 깔끔해지고 읽기 쉬워집니다.

---

 

typedef struct
{
    string names;
    string numbers;
} person;

• person이라는 새로운 타입을 정의했습니다.
• 이 타입은 names (이름)numbers (전화번호)를 한 묶음으로 가지게 됩니다.

구조체 배열 사용

person people[4];

• 사람(person) 정보를 저장하는 배열을 만들었습니다.

각 사람에 대한 데이터 입력

people[0].names = "Emma";
people[0].numbers = "617-223-1234";

• people[0] → 첫 번째 사람
• people[0].names → 이름
• people[0].numbers → 전화번호

 

검색

for (int i = 0; i < 4; i++)
{
    if (strcmp(people[i].names, "Emma") == 0)
    {
        printf("%s\n", people[i].numbers);
        return 0;
    }
}
printf("Not Found\n");
return 1;

• 배열을 순회하면서 strcmp()로 이름 비교 일치하면 해당 사람의 번호 출력

왜 struct를 사용하는가?

#include <cs50.h>
#include <stdio.h>
#include <string.h>

int main(void)
{
  string names[4] = {"Emma", "Rodrigo", "Brian","David"};
  string numbers[4] = {"617-234-0111", "617-234-0112", "617-234-0113", "617-234-0131"};
  for (int i = 0; i < 4; i++)
  {
    if(strcmp(names[i], "Emma") == 0)
    {
      printf("%s\n", numbers[i]);
      return 0;
    }
  }
  printf("Not Found\n");
  return 1;
}

처음 코드 문제점 (string 배열 2개 사용)

• names[i]와 numbers[i]를 별도로 관리해야 해서
• 정렬하거나 수정할 때 동기화 문제가 생긴다.
• 실수할 가능성이 매우 높다.

구조체(struct)를 쓰면

• 이름과 전화번호를 항상 함께 다룰 수 있다.
• 정렬, 검색, 추가 작업이 훨씬 안전하고 깔끔해진다.

• 구조체를 함수에 전달하고 다루는 방법
• 구조체 배열을 정렬(예: 이름순, 번호순)하는 방법

#include <cs50.h>
#include <stdio.h>
#include <string.h>

typedef struct
{
  string names;
  string numbers;
}
person;


int main(void)
{
  person people[4];

  people[0].names = "Emma";
  people[0].numbers = "617-223-1234";
  
  people[1].names = "David";
  people[1].numbers = "617-243-1134";

  people[2].names = "Brian";
  people[2].numbers = "617-233-1234";

  people[3].names = "Tom";
  people[3].numbers = "617-113-1234";


  for (int i = 0; i < 4; i++)
  {
    if(strcmp(people[i].names, "Emma") == 0)
    {
      printf("%s\n", people[i].numbers);
      return 0;
    }
  }
  printf("Not Found\n");
  return 1;
}