본문 바로가기

부스트코스

 (11)
<알고리즘> 삽입정렬과 병합정렬 1. 삽입정렬과 병합정렬 * 삽입 정렬(Insetion Sort) - 선택정렬과 버블정렬과 마찬가지로 제자리 정렬(in-place sorting) 알고리즘이다. - 삽입 정렬은 마치 카드게임에서 손 안의 패를 정렬하는 것과 같다. 카드를 새로 받으면 기존에 정렬시켜둔 카드 사이에 삽입시켜 정렬시킨다. 이에 따라 동일한 값에 대해 순서가 유지되는 안정정렬방식을 보장한다. - 삽입 정렬을 알아보기 위해 10 5 7 1 3 이라는 5개의 숫자를 오름차순으로 정렬시켜보자. - 삽입 정렬은 두 번째 값부터 정렬을 시작하며, 해당 값과 그 앞의 값들과만 비교한다. - 먼저 5와 10을 비교한다. 5가 더 작으므로 10을 뒤로 이동시키고 5를 그자리에 삽입한다. 5 > 10 7 1 3 5 10 7 1 3 - 다음은 ..
<자료구조> 해시 테이블과 트라이 * 해시 테이블 - 연결리스트와 트리구조에서 검색시간이 O(n)과 O(log n)이 걸렸다. 그러나 컴퓨터 공학자들은 이 시간을 더 단축시켜서 O(1)에 가깝게 만들기를 원했다. - 위를 가능하게 해주는 구조 중 하나가 바로 해시 테이블이다. - 해시테이블은 연결리스트를 원소로 가지는 배열이다. - 이름표를 바구니에 담는다고 가정하자. 단순히 바구니 하나에 여러 이름표를 담으면 사람들이 찾는 데 오랜 시간이 걸릴 것이다. - 그렇다면 바구니를 여러개로 한다면 어떨까. 이 때 바구니를 무슨 기준으로 나누는 것이 좋을까. - 이 때의 기준이 해시 함수이다. 이름표이므로 해시함수를 이름의 가장 첫 글자로 시도해보자. 알파벳이라면 총 16개의 포인터들이 생기고, 그 알파벳은 각각 연결리스트를 가리키게 된다. -..
<알고리즘> 버블정렬과 선택정렬 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..
<C언어 기초> 04. 자료형과 연산자 1. 자료형 * 데이터 타입 - 변수의 데이터 타입형식들은 다음과 같다. - bool : 불리언 표현으로써 True, False를 의미한다. (때에 따라 1,0, yes, no 포함) - char : 문자 하나를 의미한다. (ex. 'A', '?') - string : 문자열 - int : 정수 (약 40억 미만까지만 저장 가능) - long : 더 큰 크기의 정수 - float : 부동소수점을 갖는 실수 - double : 부동소수점을 갖는 더 큰 실수 * CS50라이브러리의 get 함수 - 지금까지 우리는 문자열을 받기위해 cs50라이브러리의 get_string함수를 사용했으나 다른 데이터 타입을 받아오는 함수들도 존재한다. - get_char, get_double, get_float, get_ing..
<C언어 기초> 03. 루프 1. 정수인 변수 - 우리는 지난 시간에 문자열 변수를 string으로 지정한다는 것을 배웠다. 그렇다면 정수는 어떻게 지정할까. int counter = 0; - 위는 counter라는 변수를 0으로 할당한 코드이다. 정수(integer)는 int를 사용한다. - 이름이 카운터이므로 1을 추가하는 코드를 작성해보자. counter = counter + 1; - 위처럼 작성하면 간단하게 1이 추가되어 counter에 새로 할당된다. 하지만 1씩 추가할일은 매우 많은 경우에서 발생하는데 이 때마다 저렇게 길게 작성할 필요는 없다. counter += 1; counter++; - 위의 두가지 코드 모두 같은 기능을 수행한다. 2. 반복문(loop) * while문 - 루프는 어떤 일을 계속 반복하는 것을 말..
<C언어 기초> 02. 조건문 · 조건문 * if - x와 y의 크기를 비교해서 x가 y보다 큰지 작은지를 출력하는 프로그램을 만든다고 가정하자. - x가 y보다 작을 경우 "x is less than y"를 출력해보자. if (x < y) { printf("x is less than y\n"); } - if 문으로 조건을 시작하고 괄호안에 조건을 적는다. - 위는 x가 y보다 작으면 출력문이 실행되는 구조이다. - 참고로 조건문의 끝에는 ;(세미콜론)을 굳이 붙이지 않는다. 세미콜론은 주로 함수의 끝에 넣는다. * else - 위를 좀더 보완하여보자. x가 y보다 작지 않으면 "x is not less than y"를 출력하자. if (x < y) { printf("x is less than y\n"); } else { printf..
<C언어 기초> 01 출력과 문자열 1. 출력 - 프로그래밍의 시작은 역시 출력이다. C언어로 "hello, world"를 출력하려면 어떻게 해야할지 천천히 살펴보자. #include int main(void) { printf("hello, world\n"); } - 가장 첫줄의 include 는 출력과 관련된 C언어의 표준라이브러리인 stdio.h를 불러온다는 의미이다. - int main(void){} 는 코드의 시작을 알린다고 보면된다. 앞으로 작성할 코드 모두 이 괄호안에 작성하게 된다. - printf()는 출력함수이며 괄호 안에 쌍따옴표로 문장을 적을 수 있다. 이 때 \n 은 개행문자로써 출력후 문단을 넘기는 역할, 즉 엔터를 쳐주는 역할이다. - 그리고 끝에 ;(세미콜론)은 우리가 문장을 작성할 때 .(마침표)로 끝을 내는 ..
<컴퓨터 구조> 하드웨어의 한계 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이다. 특수 문자도 있으니 자세한 내용은 직접 찾아보는 것도 좋을 것 같다..

티스토리툴바