본문 바로가기

C언어

 (11)
<자료구조> 해시 테이블과 트라이 * 해시 테이블 - 연결리스트와 트리구조에서 검색시간이 O(n)과 O(log n)이 걸렸다. 그러나 컴퓨터 공학자들은 이 시간을 더 단축시켜서 O(1)에 가깝게 만들기를 원했다. - 위를 가능하게 해주는 구조 중 하나가 바로 해시 테이블이다. - 해시테이블은 연결리스트를 원소로 가지는 배열이다. - 이름표를 바구니에 담는다고 가정하자. 단순히 바구니 하나에 여러 이름표를 담으면 사람들이 찾는 데 오랜 시간이 걸릴 것이다. - 그렇다면 바구니를 여러개로 한다면 어떨까. 이 때 바구니를 무슨 기준으로 나누는 것이 좋을까. - 이 때의 기준이 해시 함수이다. 이름표이므로 해시함수를 이름의 가장 첫 글자로 시도해보자. 알파벳이라면 총 16개의 포인터들이 생기고, 그 알파벳은 각각 연결리스트를 가리키게 된다. -..
<자료구조> 트리구조 * 연결리스트의 장단점 - 연결리스트는 배열과 달리 새로운 값을 추가하면 메모리를 추가하지 않아도 되었다. - 그러나 배열과 달리 임의 접근이 불가능하다. - 위와 같은 단점은 값의 추가, 검색에서 손실을 가져온다. 추가와 검색을 위해 연결리스트의 각 node를 하나하나 이동해야하기 때문이다. - 배열의 경우에는 정렬만 되어 있다면 임의 접근이 가능하여 이진검색을 이용하면 O(log n)의 실행시간을 갖는다. 그러나 위와 같은 단점때문에 연결리스트는 O(n)이 된다. * 트리구조의 등장 - 트리는 연결리스트를 기반으로 한 새로운 데이터 구조이다. - 연결리스트에서 노드의 연결이 1차원이었다면 트리에서의 노드의 연결은 2차원이다. - 위에서 언급되었던 단점을 해결한 '이진 검색 트리' 를 살펴보자. - 가..
<자료구조> 연결리스트와 노드 * 연결리스트 소개 - 배열에선 각 인덱스 값들이 메모리 상에서 연이어 저장되어있다. 그렇다면 배열에 새로운 값을 추가하려면 어떻게 해야 할까 - 기존 배열 바로 뒤에 다른 값이 있을 수 있으므로 배열의 길이를 늘리려면 새로운 메모리를 할당해서 값을 하나하나 복사하여 옮겨야한다. - 위의 방식은 너무 번거롭다. 각 값을 메모리의 다른 곳에 저장하더라도 배열처럼 사용할 수 있다면 어떨까. 각 값에 다음 값의 메모리 주소를 기억하게 하는 것이다. 이를 연결리스트라 한다. (Linked List) - 이제 첫 값인 1은 2의 주소를 갖고, 2는 3의주소를, 3은 Null을 갖게 된다. * 노드 - 연결리스트를 C언어 코드로 구현하면 다음과 같은 구조체로 정의한다. typedef struct node { int..
<메모리> 문자열과 메모리 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에 ..
<C언어 기초> 07. 문자열 · 문자열 * 문자열과 문자 - 우리는 지금까지 문자열을 사용하기 위해서 string자료형을 사용하였다. 문자열(string)은 실제로는 문자(char)자료형 데이터들의 배열이다. - string s = "HI!"; 와 같은 문자열 s가 정의 되어있다고 한다면 메모리 상에 다음과 같이 저장될 것이다. - s는 문자의 배열이므로 s[0] 과 같은 방법으로 문자에 접근할 수 있다. - \0은 문자열의 끝을 나타내는 널 중단 문자이다. 이는 모튼 비트가 0인 1바이트이다. - 이번에는 여러 문자열의 배열을 보자. string names[3]; names[0] = "HARRY"; names[1] = "IU"; names[2] = "SUZY"; printf("%s\n", names[0]); printf("%c%c..
<C언어 기초> 06. 배열 * 배열 - 배열은 같은 자료형의 데이터를 메모리상에 연이어서 저장하고 그것을 하나의 변수로 관리하고 싶을 때 사용한다. - 72점 73점 33점이라는 점수를 scores라는 변수 하나로 관리하고 싶다고 하자. #include #include int main(void) { // Scores int scores[3]; scores[0] = 72; scores[1] = 73; scores[2] = 33; // Print average printf("Average: %i\n", (scores[0] + scores[1] + scores[2]) / 3); } - 위와 같이 배열 안의 자료형과 원소의 갯수를 이용하여 변수를 선언한다. - 그리고 0부터 차례로 인덱스값을 대괄호[]에 입력하여 점수를 넣어 주었다. -..
<C언어 기초> 05. 사용자 정의 함수 · 사용자 정의 함수 * 사용자 정의 함수 - 우리는 자주 사용하는 기능을 함수로 직접 만들어서 관리할 수 있다. - 지금 까지 사용했던 printf 와 같은 함수도 과거에 누군가가 만들어 둔 함수이다. - 사용자에게 5번 인사하는 프로그램을 만든다고 생각해보자. #include int main(void) { for (int i = 0; i < 3; i++) { printf("hello\n") } } - 지금까지 배운 내용으로 위를 간단하게 만들 수 있다. - 하지만 다른 구문들을 떠나 인사를 하는 행위자체에 집중을 하고 싶고, 더 효율적으로 코드를 관리하고 싶을 수 있다. 그래서 위를 함수로 만들어보자. #include void hello(void) { printf("hello\n") } int mai..
<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..

티스토리툴바