WOONY's 인사이트

대망의 RB트리 주차가 끝나고 malloc 함수 구현 과제 주차에 들어섰다. (현재 6주차) 어제는 시원하게 블로그 TIL을 건너뛰었다. (그래도 github에 저번 주차에서 배운 것들을 정리했다! BST 먼저 정리하고 이번주 주말에 가능하면 RB트리 readme를 작성할 예정.) 시원하게 쉬었으니 오늘부터 다시 달립시다. malloc 개념은 CSAPP 책 9.9 장에 나온다. 그 전에 9장 전반적으로 정리를 할 필요가 있어 가장 큰 개념인 가상 메모리부터 정리. 가상 메모리(virtual memory) 가상 메모리를 쓰는 이유는 메모리를 더욱 효율적으로 & 더 적은 에러로 관리하기 위해서이다. 이와 관련해 아주 재밌게 설명한 영상이 있어 공유. 예를 들어, 어떤 식당이 있다고 하자. 이 식당은 예약제로..

지금 시간은 3시 3분..자그마치 6명의 집단 지성이 힘을 합쳐 겨우 디버깅을 완료하고 모든 테스트 케이스 통과!! 삭제 기능에 대해 빠르게 로직 정리하고 집 가야겠다.. 삭제(Deletion) 옮기거나 삭제하는 노드의 원래 색을 기억해뒀다가 옮기거나 지우려는 노드 색이 검정인 경우에만(=이중 흑색 노드) 트리를 고친다. 지우려는 노드 z 혹은 옮기려는 노드가 빨간색이면 rb트리 특성을 위반하지 않으니 고칠 필요가 없다. 지우려나 옮기려는 노드가 검정일 때는 경로 상의 검정 노드 개수가 변하므로 트리 특성을 위반한다. 이 경우에는 fixup 함수로 수정한다. 삭제 기능은 세 가지 케이스로 나눠서 구현한다. 1. 삭제하려는 노드(=z)의 왼쪽 자식만 있는 경우 (=오른쪽 자식이 NIL인 경우) 이때는 왼쪽..

요 며칠간 끊임없이 고통을 안겨줬던 레드블랙 트리(이하 RB트리)..그래도 계속 보다 보니까 얼추 감이 잡히기 시작한다. 아직 가장 큰 관문인 삭제가 남아있지만 그래도 삽입 구현 완료! RB트리 개념부터 시작해서 삽입까지 빠르게 정리하고 마무리할 예정. 오늘 풀었던 알고리즘 문제는 따로 포스팅해야겠다. Red-Black Tree(레드블랙 트리) 1. RB트리 정의 rb트리는 균형 이진 탐색 트리의 여러 버전 중 하나이다. 균형 이진 탐색 트리란, 이진 탐색 트리에 노드를 삽입/삭제하는 과정에서 어느 한 쪽으로 노드가 쏠리는 것을 방지하기 위해 규칙을 추가한 심화 버전 이진 탐색 트리라고 보면 되겠다. 왜 이런 짓을 하냐? 이진 탐색 트리를 만드는 이유는 특정 노드를 검색하는데 드는 시간 복잡도가 O(lo..

RB트리를 구현하기 전에 개념을 익힐 겸 연결 리스트로 이진 트리를 구현하는 연습(by C)을 진행한다. 공부자료는 이것을 참조함. 이진트리 with 연결리스트 1. 이진탐색트리(Binary Search Tree, BST)란? 원소를 특정한 조건에 따라 정렬해 놓은 이진 트리를 말한다. 2. 이진탐색트리 특징 모든 원소는 유일한 키값을 갖는다. (중복 내용을 갖는 항목은 없다.) 왼쪽 서브트리의 모든 원소들은 루트의 key보다 작은 값을 갖는다. 오른쪽 서브트리의 모든 원소들은 루트의 key보다 큰 값을 갖는다. 왼쪽/오른쪽 서브트리 역시 이진 탐색 트리이다.(재귀적으로 정의된다.) 3. 이진탐색트리에서 탐색 시 시간 복잡도 이진탐색트리에서 특정한 키값을 찾을 때, 그 값이 비교하려는 노드의 값보다 크면..

Ch.14 구조체(Struct) 배열에 여러 가지 정보를 매번 추가해야 한다고 생각해보자. 예컨대 도서 관리 프로그램을 만든다고 할때, i번째 책에 대한 정보를 저장한다. 책 이름, 저자, 출판사, 대출 횟수를 저장하려면 다음과 같은 i-1번째 순서에 다음과 같이 변수를 입력한다. book_name[i-1], auth_name[i-1], publ_name[i-1], borrow[i-1] 근데 더 적을 것도 없이 객체 개념을 떠올려보면 구조체가 왜 필요한지 생각하게 되는데, 이제까지 배웠던 C의 자료구조인 배열은 하나의 배열에 동일한 형만 담을 수 있다. 예를 들어, int 형 배열이면 int 값만, char 형이면 char만. 그런데 하나의 자료형에 여러 자료형을 담을 수 있다면 어떨까? 예를 들어 ch..

포인터의 덧셈/뺄셈 포인터에 1을 더하면 해당 포인터의 변수형 크기만큼 더해진다. 예컨대 pa라는 포인터가 int 형을 가리킨다고 하자. int 형의 바이트 크기는 4이므로 포인터 값에 +4만큼 더해진다. char형 변수를 가리키는 포인터라면 char의 크기가 1바이트이니 +1만큼 더해진다. 뺄샘 역시 마찬가지로 수행 가능하다. 덧셈과 뺄셈은 본질적으로 같은 개념이니 어느 정도 예상 가능. 다만, 이 역시도 해당 포인터가 가리키는 형의 크기만큼 주소값에서 빼진다. 그러면 두 포인터끼리 더할 수는 있을까? 놉. 포인터끼리의 덧셈은 의미가 없다. 두 변수의 메모리 주소값을 더하면 새로운 메모리의 주소값이 나올텐데 그 주소값과 기존에 더하려 했던 두 주소값 사이에는 아무런 연관이 없기 때문. 즉, 어떤 포인터..

Ch.4: 문자 입력 받기 scanf: 화면(키보드)으로부터 결과를 받아들이는 입력 함수 (파이썬에서 input에 해당). 출력은 printf. scanf 역시 printf처럼 각 변수의 타입에 따라 입력받는 포맷(%d, %f, %c 등)을 달리 해야 한다. 특이사항: scanf로 double 형 변수를 입력받으려면 %lf로 받아야! printf보다 좀 더 까다로운 점은, printf는 double이나 float 모두 %f로 출력하지만 float은 무조건 %f로 입력받아야 함. 버퍼 오버플로우: 허용된 메모리 이상에 데이터를 집어넣어 발생하는 오류. 보안 상 매우 취약. ex) 최대 1바이트를 차지하는 char형 변수인 ch에 한글을 치면 오류가 난다. printf("char 형 변수 입력: "); sc..

드디어 4주 간의 알고리즘 커리큘럼이 끝나는 날. 시원섭섭하다. 드디어 끝나서 후련한 마음 반, 지금부터 본격적으로 빡센 일정인 C언어 기반 커리큘럼이 다가왔다는 사실에 두려움 반. 하지만 그 알고리즘마저 해낸 마당에, 앞으로도 지금처럼 꾸역꾸역 하면 어떻게든 하겠지. 알고리즘 커리는 오늘로 끝이지만 앞으로 매일 한 문제씩 꼬박꼬박 풀 예정. 꾸준히 리뷰해야겠다. 이제 알고리즘 풀이 리뷰는 따로 카테고리를 만들어서 올릴 예정. 1. 계단 오르기(#2579) 마침 어제 풀었던 문제가 시험에 나와서 아주 기분 좋게 풀었더랬다. dp를 처음 계단을 오를 때 기점으로 생각하는 게 아니라 n번째 계단에 도착했을 때를 기점으로 거꾸로 생각하면 훨씬 간단하게 풀 수 있다. 아래 그림을 보자. n번째 계단에 도착하는 ..

1. 코치님 조언 1. 혹시 아직도 뭐가 뭔지 모르겠다? 내가 생각한 것을 프로그램으로 만들 수 있는지 자기 자신에게 질문해보기. 이 과정의 가장 근본적인 목표는 (코테 통과가 아니라) 내가 원하는 작업을 컴퓨터에게 시키는 능력을 키우는 것입니다. 일단, 내가 원하는 것을 컴퓨터에게 쉽게 시킬 수 있다면 잘 따라가고 있다고 생각합니다. 미래에 내가 원하는 것, 해내야 할 작업이 뭐가 될 지 모르기 때문에 정형화된 문제들로 연습하는 것이고 이왕이면 효율적으로 빠르게 컴퓨터에게 일을 시키기 위해 계산 복잡도를 고려하고, 문제 유형을 나누어 익히고, 정해진 시간 안에 프로그램을 짜는 연습을 하는 것입니다. 2. 이제까지 배운 것들 사이 상관관계 눈치 빠른 분들은 알고 계시겠지만 각 주의 keyword들은 서로..

1. 점프(#2253) 처음에 떠올렸던 아이디어는 출발지점에서 중간 도착지점을 저장하는 방식으로 DP 테이블을 짜는 방식이었다. 예를 들어 1번 돌에서 10번 돌까지 간다고 하면 1번 (+1)=> 2번 (+2)=> 4번 => 7번 => 10번이니까 D[1][2] = 1, D[2][4] = 2, D[4][7] = 3, D[7][10] = 3 이렇게 해서 최종적으로 D[1][10] = D[1][2] + D[2][4] + D[4][7] + D[7][10] 이런 식으로. 그런데 점화식을 짜려니 뭔가 꼬이기 시작하더라..가장 관건은 속도였는데, 나는 속도를 dp 테이블에 value로 저장했으나 이를 어떻게 점화식으로 풀어내야 할지 감이 잘 오지 않았다. 결국 풀지 못하고 풀이를 검색해서 찾아봤다. 풀이에서는 속도..