본문 바로가기

Computer Science

 (45)
<메모리> 문자열과 메모리 1. 문자열 * 문자열 - cs50수업을 듣는 동안 string 자료형을 사용하기 위해서 cs50라이브러리를 사용했다. - 이 때의 문자열은 문자의 배열이므로 다음과 같이 메모리에 저장된다. (종단문자포함) - 실제로 c언어에는 string이라는 별도의 자료형은 존재하지 않으며, cs50라이브러리에서는 string을 다음과 같이 정의해두었다. typedef char *string - 따라서 string타입의 정의 없이 문자열을 출력하려면 다음과 같이 작성한다. #include int main(void) { char *s = "HARRY"; printf("%s\n", s); // HARRY printf("%p\n", s); // 0x402002 } - 이 때 포인터를 출력하면 문자열의 가장 첫 값인 H에 ..
<메모리> 메모리와 포인터 1. 16진수 - 컴퓨터 과학에서는 숫자를 16진수로 표현하는 일이 많다. 그 이유는 16진수가 10진수에 비해 2진수를 훨씬 더 간단하게 나타낼 수 있어서 컴퓨터 친화적이기 때문이다. - 예를 들어, 11110000(2) 이라면 16진수는 4자리씩 끊어서 f0이라고 나타낸다. 즉 4비트씩 간단하게 나눠진다. - 주로 16진수를 나타낼 때에는 앞에 0x를 붙여서 0xf0과 같이 구분하여 나타낸다. - 16진수는 정보를 훨씬 더 짧게 표현할 수 있다는 장점도 있다. 2. 메모리 주소 * 메모리 주소 - 정수형 변수 n에 24라는 값을 저장하고 출력한다고 가정하자. - n은 int 자료형이므로 메모리 어딘가에서 4바이트 만큼 자리를 차지한다. - n은 메모리상에서의 주소값을 갖고 있다. 메모리 상에서의 주소..
<알고리즘> 버블정렬과 선택정렬 1. 버블 정렬 - 버블 정렬은 두 개의 인접한 데이터를 비교하면서 서로의 위치를 교환하며 정렬해나간다. - 임의의 숫자의 나열 7 5 6 8 1 3 을 보자. - 오름차순으로 나열하기 위해 버블정렬을 한다면 가장 먼저 7과 5가 비교된다. - 7 5 6 8 1 3 => 5 7 6 8 1 3 - 7이 더 크므로 5와 위치가 교환된다. 다음은 두 번째 위치값과 세 번째 위치값이 비교된다. - 5 7 6 8 1 3 => 5 6 7 8 1 3 - 7과 6중 7이 더 크므로 위치가 교환된다. - 마찬가지로 진행하면 세 번째와 네 번째, 네 번째와 다섯 번째, 다섯 번째와 여섯 번째를 비교하면 다음과 같이 교환된다. - 5 6 7 8 1 3 => 5 6 7 8 1 3 => 5 6 7 1 8 3 => 5 6 7 1..
<컴퓨터 구조> 컴파일링과 디버깅 1. 컴파일링 - 우리는 C언어를 작성하면서 clang 명령어로 c파일을 컴퓨터가 이해할 수 있는 머신코드를 만들어 보았었다. 그 때 cs50라이브러리를 이용했었기 때문에 다음과 같이 명령어를 입력했었다. clang -o hello hello.c -lcs50 - 위는 clang에게 cs50 라이브러리에 있는 코드들까지 0 과 1로 만들어서 연결하라는 의미이다. 물론 위 명령어를 make로 단순하게 만들수도 있지만 기본적으로 거치는 단계는 동일하다. - 컴파일이 되는 과정은 전처리, 컴파일링, 어셈블링, 링킹 의 네 단계를 거친다. * 전처리 - 전처리 단계는 가장 처음에 일어나는 단계로써 우리가 처음에 선언한 라이브러리들을 읽고 가져오는 역할을 한다. - 예를 들면 stdio.h 라이브러리를 #inclu..
<컴퓨터 구조> 하드웨어의 한계 1. 메모리 한계 * RAM의 한계 - 컴퓨터는 RAM이라는 저장장치를 갖고 있다. 우리가 작성한 코드도 RAM에 저장되고 실행된다. - RAM은 당연히 유한한 크기만 저장할 수 있다. 필자의 RAM은 현재 12GB이므로 이 이상은 실행되지 못할 것이다. - 많은 이용자들이 이미 겪어 봤겠지만 한 컴퓨터로 동영상을 보면서 게임을 하는 등의 무거운 프로그램 여러개를 돌리면 흔히 말하는 렉이 걸리는 것을 알 수 있다. 이러한 것이 주로 RAM에서 오는 문제이다. * 부동 소수점 부정확성 - 1을 10으로 나누면 0.1이라는 것은 모두가 알 것이다. - 이 때 소수점이 아무리 길더라도 0.1 뒤는 0이 반복됨을 알 수 있다. - 이를 코드로 작성해보자. #include #include int main(void..
<컴퓨팅 사고> 알고리즘 * 알고리즘 - 지난 강의에서 컴퓨터가 이해할 수 있는 2진법으로 숫자뿐만아니라 글자나 색 등을 입력할 수 있음을 배웠다. 우리는 이러한 입력을 통해 원하는 출력(output)을 얻기를 원한다. 이 때 input을 output으로 만드는 일련의 과정을 알고리즘이라 한다. - 즉 알고리즘은 우리의 명령을 수행하는 규칙들을 나열한 것과 같다. 하지만 규칙을 어떻게 나열하느냐에 따라 다양한 알고리즘이 존재할 수 있다. 그리고 같은 결과가 나오더라도 얼마나 짧은 시간이 걸리는지, 얼마나 정확한지 그리고 얼마나 효율적인지도 다를 것이다. * 정확한 알고리즘 - 요즘은 보기 힘들지만 책으로 된 1,000페이지의 전화번호부가 있다고 가정하자. 여기서 윤해리를 찾는 작업을 해보자. - 우리는 첫페이지부터 한 장씩 넘겨..
<컴퓨터 구조> 정보의 표현 1. 문자의 표현 * 문자의 표현 지난 장에서 2진법으로 0,1 외에 더 큰 숫자를 표현하는 것을 보았다. 그렇다면 우리가 쓰고있는 문자는 어떻게 표현하는 것일까. 이 또한 숫자로 표현이 가능하다. 이 때 표준으로 정해진 부호가 바로 ASCII(아스키)코드이다. 미국정보교환표준부호(American Standard Code for Information Interchange)의 약자 답게 모든 영어가 숫자와 대응되어있다. * 아스키코드 각 알파벳에 대응되는 숫자는 아스키코드 표를 찾아보면 쉽게 알 수 있다. 아스키코드는 128개의 부호가 있다. 그 중 십진법으로 65부터 대문자A가 시작된다. 참고로 소문자a는 97이며, 숫자 1은 49이다. 특수 문자도 있으니 자세한 내용은 직접 찾아보는 것도 좋을 것 같다..
<컴퓨터 구조> 컴퓨터 과학과 2진법 1. 컴퓨터 과학 컴퓨터과학(Computer Science)는 CS라 불리며, 이는 단순히 문제 해결에 초점을 맞춘 하나의 학문이다. 여기서 문제 해결은 입력(input)을 전달받아서 출력(output)을 만들어내는 과정이다. 이 때 입력과 출력 사이에 존재하는 과정자체가 컴퓨터과학이다. 입력과 출력을 표현하기 위해서는 모두가 동의하는 표준이 필요한데, 그래서 알아보고자 하는 것이 컴퓨터의 표현 방법이다. 2. 2진법 2진법이라는 개념은 대부분의 사람들이 중학교 과정에서 이미 배웠기 때문에 알고 있다. 흔히 사용하는 10진법과 달리 모든 숫자를 0과 1로만 표현하는 진법이다. 컴퓨터는 이 0과 1로 우리가 아는 모든 숫자를 표현할 수 있을 뿐만아니라 문자부터 사진까지 게다가 영상과 소리도 표현할 수 있다..
<알고리즘> 재귀 알고리즘 (1) 1. 재귀 알고리즘의 기본 * 재귀란 - 재귀 : 어떤 사건에서 자기 자신을 포함하고 다시 자신을 사용하여 정의되는 것. * 팩토리얼 구현 - n! 정의 ① 0! = 1 ② n > 0 이면 n! = n x (n-1)! 이 경우 n이 0이 아닌 수일 경우 ②를 실행하고 이는 또 다시 그 보다 1작은 수의 ②를 시행함을 알 수 있다. def factorial(n: int) -> int : if n > 0: return n * factorial(n - 1) else: return 1 x = int(input()) print(factorial(x)) # 5 # 120 : 매개 변수 5를 먼저 받고, 5 * factorial(4)을 계산해야한다. 이 때 이 곱셈을 위해 factorial(4)를 호출한다. 차례로 ..
<자료구조> 스택과 큐(2) 1. 큐란 * 큐 - 스택과 같이 데이터를 임시 저장하는 자료구조이지만 가장 먼저 넣은 데이터를 가장 먼저 꺼낸다는 차이가 있다. (선입선출구조) - 인큐(enqueue) : 큐에 데이터를 추가하는 행위 - 디큐(dequeue) : 큐에서 데이터를 꺼내는 행위 - 프론트(front) : 데이터가 빠지는 가장 앞쪽 부분 - 리어(rear) : 데이터를 넣는 부분 2. 배열과 큐 - 인큐 : 맨 끝 데이터의 다음 인덱스에 원소를 저장하여 처리의 복잡도는 O(1)이고 cost가 적다. - 디큐 : que[0]에 저장된 원소를 꺼내면서 이후의 원소를 모두 앞쪽으로 옮겨야한다. 따라서 복잡도는 O(n)이고 매우 비효율적이다. ※ 우선순위 큐 : 인큐할 때 데이터에 우선순위를 부여하고 디큐할 때 우선순위대로 꺼내는..

티스토리툴바