힙 오버플로우/ 스택 오버플로우

• 힙 영역에서는 malloc 에 의해 메모리가 더 할당될수록, 점점 사용하는 메모리의 범위가 아래로 늘어남
• 마찬가지로 스택 영역에서도 함수가 더 많이 호출 될수록 사용하는 메모리의 범위가 점점 위로 늘어남
• 이렇게 점점 늘어나다 보면 제한된 메모리 용량 하에서는 기존의 값을 침범하는 상황도 발생
• 이를 힙 오버플로우 또는 스택 오버플로우라고 한다.

사용자에게 입력 받기

스택은 우리가 여태껏 많이 써왔던 get_int나 get_string 과 같은 함수에서도 사용된다. 만약 이런 함수들을 직접 구현한다면 아래와 같은 코드가 될 것

[get_int 코드]

[get_string 코드]

• 위 코드들에서 scanf라는 함수는 사용자로부터 형식 지정자에 해당되는 값을 입력받아 저장하는 함수
• get_int 코드에서 int x를 정의한 후에 scanf에 s가 아닌 &x로 그 주소를 입력해주는 부분을 유의하기
• scanf 함수의 변수가 실제로 스택 영역 안에 x가 저장된 주소로 찾아가서 사용자가 입력한 값을 저장하도록 하기 위함
• 반면 get_string 코드에서는 scanf에 그대로 s를 입력해줬다.
• 그 이유는 s를 크기가 5인 문자열, 즉 크기가 5인 char 자료형의 배열로 정의하였기 때문
• clang 컴파일러는 문자 배열의 이름을 포인터처럼 다룹니다. 즉 scanf에 s라는 배열의 첫 바이트 주소를 넘겨주는 것

파일 쓰기

사용자로부터 입력을 받아 파일에 저장하는 프로그램도 작성하기

• fopen이라는 함수를 이용하면 파일을 FILE이라는 자료형으로 불러올 수 있다.
• fopen 함수의 첫번째 인자는 파일의 이름, 두번째 인자는 모드로 r은 읽기, w는 쓰기, a는 덧붙이기를 의미
• 사용자에게 name과 number라는 문자열을 입력 받고, 이를 fprintf 함수를 이용하여 printf에서처럼 파일에 직접 내용을 출력할 수 있다.
• 작업이 끝난 후에는 fclose함수로 파일에 대한 작업을 종료해줘야 한다.

파일 읽기

파일의 내용을 읽어서 파일의 형식이 JPEG 이미지인지를 검사하는 프로그램을 작성하기

• 위 코드에서 main 함수를 보면 사용자로부터 입력을 받는 것을 알 수 있다. 여기서는 파일의 이름을 입력으로 받을 예정
• 만약 argc가 2가 아니라면, 파일명이 입력되지 않았거나 파일명 외의 다른 인자가 입력되었기 때문에 1(오류)을 리턴하고 프로그램을 종료
• 만약 argc가 2라면 프로그램이 그대로 진행
• 입력받은 파일명(argv[1])을 ‘읽기(r)’ 모드로 불러옴
• 만약 파일이 제대로 열리지 않으면 fopen 함수는 NULL을 리턴하기 때문에 이를 검사해서 file을 제대로 쓸 수 있는지를 검사하고 아니라면 역시 1(오류)를 리턴하고 프로그램을 종료
• 만약 파일이 잘 열렸다면, 프로그램이 계속 진행
• 그 후 크기가 3인 문자 배열을 만들고, fread 함수를 이용해서 파일에서 첫 3바이트를 읽어옴
• fread 함수의 각 인자는 (배열, 읽을 바이트 수, 읽을 횟수, 읽을 파일)을 의미
• 그리고 마지막으로 읽어들인 각 바이트가 각각 0xFF, 0xD8, 0xFF 인지를 확인
• 이는 JPEG 형식의 파일을 정의할 때 만든 약속으로, JPEG 파일의 시작점에 꼭 포함되어 있어야 함
• 따라서 이를 검사하면 JPEG 파일인지를 확인할 수 있다.

※ 디지털 포렌식에서 쓰이는 매직 넘버들
.jpg는 FFD8 / .gif는 47 49 46 38 [GIF89] / .png는  89 50 4E 47 .PNG
사진파일 확장자 뿐만아니라 .mp3 49 44 33 [ID3] / .avi 52 49 46 46 [RIFF] / .zip 50 4B 03 04 [PK]
등이 있다.

메모리 누수

• malloc 함수를 이용하여 메모리를 할당한 후에는 free라는 함수를 이용하여 메모리를 해제해줘야 한다.
• 그렇지 않은 경우 메모리에 저장한 값은 쓰레기 값으로 남게 되어 메모리 용량의 낭비가 발생하게 되기 때문
• 이러한 현상을 ‘메모리 누수’라고 한다.

※ valgrind라는 프로그램을 사용하면 우리가 작성한 코드에서 메모리와 관련된 문제가 있는지를 쉽게 확인할 수 있다. 

다음과 같은 명령어를 사용하면 filename 파일에 대한 valgrind의 검사 내용을 쉽게 확인할 수 있다.

• f 함수를 살펴보면 먼저 포인터 x에는 int형의 사이즈(4바이트)에 10배에 해당하는 크기의 메모리, 즉 40바이트를 할당한다.
• 그리고 x의 10번째 값으로 0을 할당한다.
• 그리고 main 함수에서 f를 실행하게 되는데,
• 이 코드를 valgrind 로 검사해보면 버퍼 오버플로우와 메모리 누수 두 가지 에러를 확인할 수 있다.
• 먼저 버퍼 오버플로우는 x[10] = 0; 코드로 인해 발생한다.
• 우리는 10개의 int형의 배열을 만들었는데 배열의 인덱스가 0부터 시작한다는 점을 감안하면 인덱스 10은 11번째 인덱스에 접근하겠다는 의미이고, 이는 정의되지 않은 것이기 때문에 버퍼 오버플로우가 발생하는 것
• 따라서 이 오류는 0에서 9 사이의 인덱스를 사용하면 해결할 수 있다.
• 또한 메모리 누수는 x라는 포인터를 통해 할당한 메모리를 해제하기 위해 free(x) 라는 코드를 추가해줌으로써 해결할 수 있다.

메모리 교환, 스택, 힙

① 예제 1 swap 함수

• 함수 swap은 정수 a와 b를 입력받아 그 값을 바꾸는 일을 수행한다. 
• main 함수에서는 x에 1, y에 2를 입력하고 swap 함수를 통해 그 두 값을 바꾸려고 하고 있다.
• 그러나 위 코드를 컴파일하고 출력해보면 의도와는 다르게 swap 함수를 거친 후에도 x와 y의 값이 바뀌지 않은채 그대로 출력된다.
• 사실 swap 함수는 교환 작업을 제대로 수행하고 있는데, 문제는 교환하는 대상이 x, y 그 자체가 아닌 함수 내에서 새롭게 정의된 a, b라는 것
• a와 b는 각각 x와 y의 값을 복제하여 가지게 된다. 서로 다른 메모리 주소에 저장되는 것.

② 데이터 저장 구역

• 그림에서와 같이 메모리 안에는 데이터 저장되는 구역이 나뉘어져 있다.
• 머신 코드 영역에는 우리 프로그램이 실행될 때 그 프로그램이 컴파일된 바이너리가 저장
• 글로벌 영역에는 프로그램 안에서 저장된 전역 변수가 저장
• 힙 영역에는 malloc으로 할당된 메모리의 데이터가 저장
• 스택에는 프로그램 내의 함수와 관련된 것들이 저장

• 이를 바탕으로 다시 생각해보면, 위의 코드에서 a, b, x, y, tmp 모두 스택 영역에 저장되지만
• a와 x, b와 y는 그 안에서도 서로 다른 위치에 저장된 변수!
• 따라서 a와 b를 바꾸는 것은 x와 y를 바꾸는 것에 아무런 영향도 미치지 않는 것
• 따라서 아래 그림 및 코드와 같이 a와 b를 각각 x와 y를 가리키는 포인터로 지정함으로써 이 문제를 쉽게 해결할 수 있다.

문자열

우리는 문자열을 저장하기 위해 CS50 라이브러리에 포함된 string 자료형을 사용했다.

아래와 같이 s에 “EMMA”라는 값을 저장한다고 생각해 보면,

문자열은 결국 문자의 배열이고, s[0], s[1], s[2], … 와 같이 하나의 문자가 배열의 한 부분을 나타낸다.

( ※ 가장 마지막의 \0은 0으로 이루어진 바이트로, 문자열의 끝을 표시하는 약속 )

여기서 변수 s는 결국 이러한 문자열을 가리키는 포인터

더 상세히는 문자열의 가장 첫번째 문자, 즉 주소 0x123에 있는 s[0]를 가리키게 된다.

실제 CS50 라이브러리를 보면 string 자료형은 아래와 같이 정의되어 있다.

여기서 typedef는 새로운 자료형을, char *은 문자에 대한 포인터를, string은 자료형의 이름을 의미

따라서 아래 두 코드는 동일하게 동작할 것

① string 자료형을 이용하여 “EMMA” 출력

② char 포인터를 이용하여 “EMMA” 출력

2번 코드의 char *s에서 s라는 변수는 문자에 대한 포인터가 되고, “EMMA”라는 문자열의 가장 첫 번째 값을 저장하기 때문

// 내가 이해한 바 : string = char*, 즉 문자열 첫 주소에대한 포인터

 문자열 비교

위 코드를 실행하면, s라는 포인터의 값, 즉 “EMMA”라는 문자열의 가장 첫 값인 “E”에 해당하는 메모리 주소를 출력하게 될 것

그렇다면 아래 코드들은 무엇을 출력할까?

s가 가리키는 곳을 시작으로 “EMMA”라는 문자열로 이루어진 문자들의 배열이 있으니, 각각

s라는 문자열의 첫 번째 문자에 해당하는 주소값,

s라는 문자열의 두 번째 문자에 해당하는 주소값,

s라는 문자열의 세 번째 문자에 해당하는 주소값,

s라는 문자열의 네 번째 문자에 해당하는 주소값을 출력

( &s[0]는 “E”의 주소값을, &s[1]은 “M”의 주소값을,  &s[2]은 “M”의 주소값을,  &s[3]은 “A”의 주소값을 의미 )

문자열은 첫번째 문자를 시작으로 메모리상에서 바로 옆에 저장되어 있다.

다시 말해, 가장 첫 번째 문자에 해당하는 주소값을 하나씩 증가시키면 바로 옆에 있는 문자의 값을 출력할 수 있는 것

따라서 아래 코드는 E M M A를 순서대로 출력할 것

문자열을 비교할 때도 아래 코드와 같이 문자열이 저장된 변수를 바로 비교하게 되면

그 변수가 저장되어 있는 주소가 다르기 때문에 다르다는 결과가 나올 것

정확한 비교를 위해서는 실제 문자열이 저장되어 있는 곳으로 이동하여, 각 문자를 하나하나씩 비교해야 한다.

문자열 복사

문자열을 복사하기 위해 아래 코드를 실행하면?

• 사용자에게 입력값을 받아 string s에 저장하고, string t를 s로 정의
• 그리고 t의 첫 번째 문자를 toupper 함수를 이용하여 대문자로 바꾼다면 s와 t는 각각 어떻게 출력 될까?
• 입력값으로 “emma”를 주게 된다면, 단순한 예상과는 다르게 s와 t 모두 “Emma”라고 출력이 된다.
• 그 이유는  s라는 변수에는 “emma”라는 문자열이 아닌 그 문자열이 있는 메모리의 주소가 저장되기 때문
• string s 는 char *s 와 동일한 의미
• 따라서 t도 s와 동일한 주소를 가리키고 있고, t를 통한 수정은 s에도 그대로 반영이 되게 되는 것

그렇다면 두 문자열을 실제로 메모리상에서 복사하려면 어떻게 해야 할까?

아래 코드와 같이 메모리 할당 함수를 사용하면 됩니다

• 위의 코드와 다른 점은 malloc이라는 함수를 이용해서 t를 정의한다는 것
• malloc 이라는 함수는 정해진 크기 만큼 메모리를 할당하는 함수
• 즉 s 문자열의 길이에 널 종단 문자(\0)에 해당하는 1을 더한 만큼 메모리를 할당
• 그리고 루프를 돌면서 s 문자열 배열에 있는 문자 하나 하나를 t 배열에 복사해준다.
• 이 코드를 컴파일 후 실행시키고 입력값으로 “emma”를 주면 우리가 예상한 대로 s는 “emma”가, t는 “Emma”가 성공적으로 출력

메모리 주소

① 16진수 

• 컴퓨터과학에서는 데이터를 처리하기 위해 숫자를 10진수나 2진수 대신 16진수(Hexadecimal)로 표현하는 경우가 많다.
• 16진수를 사용하면 10진수보다 2진수를 간단하게 나타낼 수 있는 장점이 있기 때문

② 10진수를 16진수로 바꾸어보기

JPG 이미지 파일은 항상 255 216 255 로 시작되고 이것은 10진수다. 하지만 실제 컴퓨터 내에서는 10진수를 사용하지 않는다. 컴퓨터는 0과 1만을 이해할 수 있기 때문.

 

• 먼저 255 216 255를 2진수로 나타내보면 <그림 1>과 같다.
• 2진수로 모든 데이터를 표현하기에는 너무 길어지기 때문에 16진수로 바꾸어 보면,
• 2^4(2의 4제곱)이 16이기 때문에 4bits씩 두 덩어리로 나누어 보면 0000 부터 1111까지는 16진수로 표현할 수 있다.
• 그렇다면 16진수에서 10부터 15까지는 어떻게 표기할까? 10은 a, 11은 b, …, 15는 f를 대입하여 사용
• 4bits씩 16진수로 변환 후 0x를 붙혀 뒤에 오는 문자들이 16진수임을 알려준다.

 

③ 16진수의 유용성

 

• ASCII 코드에 의해 “A, B, C”는 10진수로 65, 66, 67에 해당
• 컴퓨터는 10진수를 이해할 수 없으므로 2진수로 표현해보면  "01000001 01000010 01000011＂이 된다.
• 하지만 16진수로 표현하면 2진수로 표현했을 때 보다 훨씬 간단해 진다.
• 컴퓨터는 8개의 비트가 모인 바이트 단위로 정보를 표현는데,
• 2개의 16진수는 1byte의 2진수로 변환되기 때문에 정보를 표현하기 매우 유용

 

 

⑤ 메모리 주소

• 정수형 변수 n에 50이라는 값을 저장하고 출력한다고 생각해 보자.
• n 이라는 값은 int 타입이므로, 우리 컴퓨터의 메모리 어딘가에 4바이트 만큼의 자리를 차지하며 저장되어 있을 것 
• C에서는 변수의 메모리상 주소를 받기 위해 ‘&’이라는 연산자를 사용할 수 있다.

• 예를 들어, 위와 같은 코드를 실행하면 ‘0x7ffe00b3adbc’와 같은 값을 얻을 수 있고, 이는 변수 n의  16진법으로 표현된 메모리의 주소이다.
• 반대로 ‘*’를 사용하면 그 메모리 주소에 있는 실제 값을 얻을 수 있다.

• 위 코드는 먼저 n의 주소를 얻고, 또 다시 그 주소에 해당하는 값을 얻어와 출력한 것이므로 결국 ‘50’이라는 값이 출력된다.

포인터

• 지난 강의에서 배웠던 ‘*’ 연산자는 어떤 메모리 주소에 있는 값을 받아오게 해준다.
• 이 연산자를 이용해서 포인터 역할을 하는 변수를 선언할 수도 있다.

• 위 코드를 보면 정수형 변수 n에는 50이라는 값이 저장되어 있다.
• 그리고 *p라는 포인터 변수에 &n 이라는 값, 즉 변수 n의 주소를 저장한다.
• int *p 에서 p앞의 *는 이 변수가 포인터라는 의미이고, int 는 이 포인터가 int 타입의 변수를 가리킨다는 의미
• 따라서 첫 번째 printf문과 같이 포인터 p의 값, 즉 변수 n의 주소를 출력하거나, 두 번째 printft문과 같이 포인터 p가 가리키는 변수의 값, 즉 변수 n의 값을 출력할 수도 있다.

실제 컴퓨터 메모리에서 변수 p는 아래와 같이 저장될 수 있다.

하지만 아래 그림과 같이 실제로 p의 값, 즉 n의 주소값을 생각하지 않고, 추상적으로 단지 p가 n을 가리키고 있다는 것만 생각해도 된다.

실행시간의 상한

• O(n^2): 선택 정렬, 버블 정렬
• O(n log n) 병합 정렬
• O(n): 선형 검색
• O(log n): 이진 검색
• O(1)

실행시간의 하한

• Ω(n^2): 선택 정렬, 버블 정렬
• Ω(n log n) 병합 정렬
• Ω(n) 버블 정렬
• Ω(log n)
• Ω(1): 선형 검색, 이진 검색

버블 정렬을 좀 더 잘 할 수 있는 방법

만약 정렬이 모두 되어 있는 숫자 리스트가 주어진다면?

원래 의사 코드는 아래와 같다.

여기서 안쪽 루프에서 만약 교환이 하나도 일어나지 않는다면 이미 정렬이 잘 되어 있는 상황일 것

따라서 바깥쪽 루프를 ‘교환이 일어나지 않을때’까지만 수행하도록 다음과 같이 바꿀 수 있다.

따라서 최종적으로 버블 정렬의 하한은 Ω(n)이 된다. 상황에 따라서는 선택 정렬보다 더 빠른 방법이 되는 것

재귀

• 함수가 본인 스스로를 호출해서 사용할 수 있는지? 이에 대한 대답은 할 수 있다 이며, 이러한 것을 재귀(Recursion)라고 부른다.

아래와 같이 피라미드 모양을 출력하기 위해 다음과 같은 코드를 작성할 수 있다.

#

##

###

####

• 높이를 입력 받아 중첩 루프를 통해 피라미드를 출력해주는 draw 함수를 정의
• 여기서 꼭 중첩 루프를 써야만 할까? 사실 바깥 쪽 루프는 안 쪽 루프에서 수행하는 내용을 반복하도록 하는 것일 뿐
• 따라서 바깥 쪽 루프를 없앤 draw함수를 만들고, 이를 ‘재귀적으로’ 호출하도록 해서 똑같은 작업을 수행할 수 있다.
• 즉, draw 함수 안에서 draw 함수를 호출 하는 것. 아래 코드와 같이 수정할 수 있다.

• draw 함수 안에서 draw 함수를 다시 호출 하는 부분을 유의
• h라는 높이를 받았을 때, h-1 높이로 draw 함수를 먼저 호출하고, 그 후에 h 만큼의 #을 출력.
• 여기서 내부적으로 호출된 draw 함수를 따라가다 보면 h = 0인 상황이 오게 된다.
• 따라서 그 때는 아무것도 출력을 하지 않도록 하는 조건문을 추가해줘야 한다.
• 이렇게 재귀를 사용하면 중첩 루프를 사용하지 않고도 하나의 함수로 동일한 작업을 수행할 수 있다.

※ 반복문을 쓸 수 있는데도 재귀를 사용하는 이유는 ? 루프를 중첩하게 되면 가독성이 떨어질 수 있고 변수도 더 많이 선언 해줘야 한다. 하지만 재귀를 사용하면 변수도 줄일 수 있고 가독성도 늘어나 메모리 공간도 아끼고 심미적으로 보기 괜찮다. 코드를 좀 더 간결하게 만들 수 있다.

병합 정렬

• 병합 정렬은 원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가며 정렬을 하는 방식
• 그리고 이 과정은 재귀적으로 구현되기 때문에 나중에 재귀를 학습하면 더 이해하기 쉽다.

----------------------------------------------------------------------------------------------------------------------
마찬가지로 다음 숫자들을 오름차순으로 정렬해 보겠습니다.

7 4 5 2 6 3 8 1

먼저 숫자들을 반으로 나눕니다.

7 4 5 2 | 6 3 8 1

그리고 나눠진 부분 중 첫번째를 한번 더 반으로 나눠봅니다.

7 4 | 5 2 | 6 3 8 1

마지막으로 한 번 더 나눠봅니다.

7 | 4 | 5 2 | 6 3 8 1

이제 숫자가 두 개 밖에 남지 않았으므로 더 이상 나누지 않고, 두 숫자를 다시 병합합니다.

단, 이 때 작은 숫자가 먼저 오도록 합니다. 4와 7의 순서를 바꿔서 병합하는 것이죠.

4 7 | 5 2 | 6 3 8 1

마찬가지로 5 2 부분도 반으로 나눈 후에 작은 숫자가 먼저 오도록 다시 병합할 수 있습니다.

4 7 | 2 5 | 6 3 8 1

그럼 이제 4 7과 2 5 두 개의 부분들을 병합하겠습니다.

각 부분들의 숫자들을 앞에서 부터 순서대로 읽어들여 비교하여 더 작은 숫자를 병합되는 부분에 가져옵니다.

즉, 4와 2를 먼저 비교해서 2를 가져옵니다. 그 후에 4와 5를 비교해서 4를 가져옵니다.

그리고 7과 5를 비교해서 5를 가져오고, 남은 7을 가져옵니다.

2 4 5 7 | 6 3 8 1

이제 남은 오른쪽 4개의 숫자들도 위와 동일한 과정을 거칩니다. 

2 4 5 7 | 1 3 6 8

마지막으로 각각 정렬된 왼쪽 4개와 오른쪽 4개의 두 부분을 병합합니다.

2와 1을 비교하고, 1을 가져옵니다. 2와 3을 비교하고, 2를 가져옵니다. 4와 3을 비교하고, 3을 가져옵니다.

4와 6을 비교하고… 이 과정을 병합이 끝날때까지 진행하면 아래와 같이 정렬이 완료됩니다.

1 2 3 4 5 6 7 8

전체 과정을 요약해서 도식화해보면 아래와 같습니다.

7 | 4 | 5 | 2 | 6 | 3 | 8 | 1 → 가장 작은 부분 (숫자 1개)으로 나눠진 결과입니다.

4   7 | 2   5 | 3   6 | 1   8 → 숫자 1개씩을 정렬하여 병합한 결과입니다.

2   4   5   7 | 1   3   6   8 → 숫자 2개씩을 정렬하여 병합한 결과입니다.

1   2   3   4   5   6   7   8 → 마지막으로 숫자 4개씩을 정렬하여 병합한 결과입니다. 

이러한 방법을 ‘병합 정렬’ 이라고 합니다.

----------------------------------------------------------------------------------------------------------------------

병합 정렬 실행 시간의 상한은 O(n log n)

숫자들을 반으로 나누는 데는 O(log n)의 시간이 들고, 각 반으로 나눈 부분들을 다시 정렬해서 병합하는 데 각각 O(n)의 시간이 걸리기 때문! 

실행 시간의 하한도 역시 Ω(n log n). 숫자들이 이미 정렬되었는지 여부에 관계 없이 나누고 병합하는 과정이 필요하기 때문.

※ 병합 정렬을 선택 정렬이나 버블 정렬과 비교했을 때 장점과 단점은 무엇이 있을까요? 가장큰 장점은 무엇보다 실행시간이 다른 두 정렬에 비해 빠르다는 것이고 단점이라면 이미 정렬이 되어있다면 버블정렬의 하한선이 병합정렬보다 더 빠르다는 것 즉, 더 빠르게는 할 수 없다는 얘기.