WEEK05

yeopto·2022년 5월 8일
CCSAPPSW사관학교 정글sw정글자료구조
0

SW사관학교 정글

목록 보기
7/14
post-thumbnail

22.04.28

C언어

  1. 배열 포인터

    • 배열에서 배열의 이름은 배열의 첫 번째 원소의 주소값을 나타내고 있다.
    • 그렇다면 배열의 이름이 배열의 첫 번째 원소를 가리키는 포인터라고 할 수 있을까? → 아니다!
    #include <stdio.h>
int main() {
  int arr[6] = {1, 2, 3, 4, 5, 6};
  int* parr = arr;

  printf("Sizeof(arr) : %d \n", sizeof(arr));
  printf("Sizeof(parr) : %d \n", sizeof(parr));
}

/*
Sizeof(arr) : 24
Sizeof(parr) : 8
*/
    • sizeof를 arr 자체에 그대로 썻을 경우 배열의 실제 크기가 나온다.
    • 하지만 parr의 sizeof를 구하면 그냥 포인터 크기를 알려줌. → 즉 배열의 이름과, 첫 번째 원소의 주소값은 엄밀히 다른 것
    • C 언어 상에서 배열의 이름이 sizeof 연산자나 주소값 연산자(&)와 사용될 때 경우를 빼면, 배열의 이름을 사용시 암묵적으로 첫 번째 원소를 가리키는 포인터로 타입이 변환되기때문!
    #include <stdio.h>

int main() {
  int arr[3] = {1, 2, 3};
  int (*parr)[3] = &arr;

  printf("arr[1] : %d \n", arr[1]);
  printf("parr[1] : %d \n", (*parr)[1]);
}
    • 그래서 &arr 은 주소값 연산자가 앞에 붙었기때문에 암묵적 변환이 일어나지 않는다. 그래서 더블포인터가 아님. arr이 크기가 3인 배열이기 때문에 &arr 을 보관할 포인터는 크기가 3인 배열을 가리키는 포인터가 되어야함.
    • int(*parr)[3] 는 배열 포인터다.
    • parr 은 크기가 3인 배열을 가리키는 포인터이기 때문에 배열을 직접 나타내기 위해서는 * 연산자를 통해 원래의 arr을 참조해야함. 따라서 (*parr)[1] 과 arr[1]은 같은게 된다.

22.04.29

C언어

  1. 함수

    • 특정한 타입의 변수의 값을 바꾸려면, 특정한 타입을 가리키는 포인터로 인자를 취해야한다.
    • 함수포인터
      • int (*pmax)(int, int); → 함수 포인터 pmax의 정의 → ‘이 함수 포인터 pmax는 함수 리턴값이 int형이고, 인자 두 개가 각각 int인 함수를 가리킨다. (인자가 없으면 괄호 안을 비워두면 됨)
      • 특정한 함수의 시작 주소값을 알려면 그냥 함수 이름을 넣어주면 된다. pmax = max

  2. 문자열

  • getchar() : stdin 에서 한개의 문자를 읽어와서 그 값을 리턴한다. → scanf() 에서 %c 형식으로 사용하게 될때(권장 하진 않지만, 간혹 써야할 때) 다음 scanf() 를 쓰기 위해 버퍼를 비워줄때 쓴다.(이전 scanf() 에서 엔터때문에 개행이 버퍼에 남아있음)
  • 리터럴이란, 소스 코드 상에서 고정된 값을 가지는 것을 일컫는다. 특히 C에서는 큰 따옴표(”)로 묶인 것들을 문자열 리터럴이라 부른다. → 즉, 실제 프로그램 실행 중에서도 리터럴의 값은 절대로 변경 되서는 안된다.
  • 리터럴을 가리키기 위해서는 char* 가 아닌 const char *로 가리켜야한다.

  1. 전역변수

    • 지역 변수는 함수가 종료 될때 파괴 되는데, 전역 변수는 프로그램이 시작할 때 만들어 졌다가 프로그램이 종료 될 때 파괴된다. 전역 변수는 지역변수와 달리 메모리의 데이터 영역에 할당 됨.
    • 전역 변수들은 정의 시 자동으로 0으로 초기화 된다.

  2. 정적변수(static)

    • 정적 변수는 자신이 선언된 범위를 벗어나더라도 절대로 파괴되지 않음.
    • 전역변수와 마찬가지로 데이터 영역에 저장되고 프로그램이 종료될 때 파괴된다.
    • 전적 변수도 정의시 특별한 값을 지정해 주지 않는 한 0으로 자동으로 초기화 됨.

  3. 동적할당(malloc)

    • malloc은 자신이 할당한 메모리의 시작 주소를 리턴함.
    • 리턴형이 void * 형이다. 그래서 자료형 * 형변환 해주면 된다.
    • free() 는 할당받은 메모리를 다 쓰고 난 후에 메모리 영역을 다시 컴퓨터에게 돌려주는 역할.
    • free() 를 제대로 하지 않아 발생되는 문제를 메모리 누수라고 한다.
    • 예를 들어 malloc이 돗자리를 깔아 주는데 free를 안해주면 돗자리를 두고오는 것 그러다보면 공원에는 돗자리 놓을 수 있는 공간이 없다.
    • malloc으로 할당된 메모리는 heap영역에 위치함.
    • 2차원 배열을 할당할때는 배열 포인터로 선언하는 방법이 더 좋음. malloc은 상당히 느린 함수들 중 하나이기에 malloc의 호출 횟수를 최소한으로 하는 것이 좋다. 또 컴파일러가 다이렉트로 2차원배열 메모리에 접근할 수 있음. 메모리가 연속적으로 있기 때문에 접근이 더 빠름.

22.05.01

자료구조

  1. 이진 탐색 트리

    • 이진탐색트리란 다음과 같은 특징을 갖는 이진트리를 말한다. (이진트리 - 각 노드의 자식 노드가 최대 2개인 트리)

      • 각 노드에 중복되지 않는 키가 있다.
      • 루트노드의 왼쪽 서브 트리는 해당 노드의 키보다 작은 키를 갖는 노드들로 이루어져 있다.
      • 루트노드의 오른쪽 서브 트리는 해당 노드의 키보다 큰 키를 갖는 노드들로 이루어져 있다.
      • 좌우 서브트리도 모두 이진 탐색 트리여야 한다.

    • 이진 탐색 트리는 기존 이진트리보다 탐색이 빠르다. 이진 탐색 트리의 탐색 연산은 트리의 높이가 h이라면 O(h)의 시간 복잡도를 갖는다.

    • 이진 탐색 트리의 탐색 과정

      • 루트 노드의 키와 찾고자 하는 값을 비교한다. 찾고자 하는 값이라면 탐색을 종료한다.
      • 찾고자 하는 값이 루트 노드의 키보다 작다면 왼쪽 서브 트리로 탐색을 진행한다.
      • 찾고자 하는 값이 루트노드의 키보다 크다면 오른쪽 서브 트리로 탐색을 진행한다.
      • 위 과정을 찾고자 하는 값을 찾을 때까지 반복해서 진행한다. 만약 값을 찾지못하면 그대로 종료함.

    • 이진 탐색 트리 삽입 과정

      • 삽입할 값을 루트 노드와 비교해 같다면 오류를 발생한다.(중복 값 허용 X)
      • 삽입할 값이 루트 노드의 키보다 작다면 왼쪽 서브 트리를 탐색해서 비어있으면 추가하고, 비어있지 않다면 다시 값을 비교한다.
      • 삽입할 값이 루트노드의 키보다 크다면 오른쪽 서브트리를 탐색해서 비어있다면 추가하고, 비어있지 않다면 다시 값을 비교한다.

    • 이진 탐색 트리 삭제 과정

      • 삭제하려는 노드가 단말 노드일 경우
        • 삭제할 노드의 부모 노드가 있다면 부모 노드의 자식 노드를 NULL로 만들고, 삭제할 노드를 삭제 해주면 된다.
      • 삭제하려는 노드의 서브 트리가 하나인 경우(왼쪽 혹은 오른쪽 서브 트리)
        • 삭제할 노드의 자식노드를 삭제할 노드의 부모노드가 가리키게 하고 해당 노드를 삭제하면 된다.
      • 삭제하려는 노드의 서브 트리가 두 개인 경우
        • 삭제할 노드 인쪽 서브 트리의 가장 큰 자손을 해당 노드의 자리에 올린다. → 삭제할 노드의 왼쪽 서브 트리에서 가장 큰 자손을 해당 노드의 자리에 올리면 이진 탐색 트리의 조건을 만족하면서 트리가 유지된다.

  2. Red-Black-Tree

    • 개념

      • 이진 탐색 트리(BST)의 한 종류
      • 스스로 균형 잡는 트리
      • BST의 worst case의 단점을 개선
      • 모든 노드는 red 혹은 black

    • 속성

      1. 모든 노드는 red 혹은 black
      2. 루트 노드는 black
      • nil 노드
        • 존재하지 않음을 의미하는 노드
        • 자녀가 없을 때 자녀를 nil 노드로 표기
        • 값이 있는 노드와 동등하게 취급
        • RB 트리에서 leaf 노드는 nil 노드
      1. 모든 nil 노드는 black
      2. red의 자녀들은 black이다. 또, red는 연속적으로 존재할 수 없다.
      3. 임의의 노드에서 자손 nil 노드들까지 가는 경로들의 black 수는 같다. (자기 자신은 카운트에서 제외)
      • 노드 x의 black height
        • 노드 x에서 임의의 자손 nil 노드까지 내려가는 경로에서의 black수 (자기 자신은 카운트에서 제외)
        • 5번 속성을 만족해야 성립하는 개념
        • rbtree가 바로 위의 속성을 만족하고 있고 두 자녀가 같은 색을 가질 때 부모와 두 자녀의 색을 바꿔줘도 5번 속성은 여전히 만족한다.

    • rb트리 균형잡는 법

      • 삽입/삭제 시 주로 4번, 5번 속성을 위반하며 이들을 해결하려고 구조를 바꾸다 보면 자연스럽게 트리의 균형이 잡히게 됨.

    • rb트리 삽입 방식

      1. 삽입 전 rb트리 속성 만족한 상태
      2. 삽입 방식은 일반적인 BST와 동일
      3. 삽입 후 rb트리 위반 여부 확인
      4. 위반 했다면 재조정
      5. rb트리 속성을 다시 만족

      • 삽입되는 노드는 항상 red다. → why? 삽입 후에도 5번 속성을 만족하기 위해

      • 노드를 삽입할 때 두 nil노드의 색은 black으로 고정한다. → 그러면 자연스럽게 3번 속성을 만족

      • red로 삽입했기 때문에 2번 속성 위반한다. → 그래서 루트 노드를 black으로 바꾸면 해결

      • case 3 : 4번 속성(노드가 red라면 자녀들은 black)을 위반할 때 → 구조를 바꿔준 뒤에 BST 특징 또한 유지되어야 한다. → 구조를 바꾸면서도 BST의 특징을 유지시키는 방법은 회전이다.

        회전을 어떻게 사용할까? → 20과 50의 색깔을 바꿔준다 → 50을 기준으로 오른쪽으로 회전한다. → 해결 → rbtree 조건 모두 해결

      • case2 : 꺾인 부분을 펴줘서 case3과 같은 형태로 만들고 case3와 같은 방식으로 해결 가능

        20기준으로 왼쪽으로 회전한다. → 회전 후 case3형태가 됨 → 40과 50의 색을 바꾸고 → 50기준으로 오른쪽 회전한다. → rbtree 조건 모두 해결

      • case1 : red 삽입 후 4번 속성을 위반했을 때 → 삽인된 red 노드의 부모도 red & 삼촌(부모의 형제)도 red라면 부모와 삼촌을 black으로 바꾸고 할아버지를 red로 바꾼 뒤 할아버지에서 다시 확인을 시작한다. → 할아버지 색깔이 레드였는데 루트면 블랙으로 바꿔주어야한다.

22.05.02

자료구조

  • rbtree의 삭제방식

    1. 삭제 전 rb트리 속성 만족한 상태

    2. 삭제 방식은 일반적은 BST와 동일

    3. 삭제 후 rb 트리 속성 위반 여부 확인

    4. rb 트리 속성을 위반했다면 재조정

    5. rb 트리 속성을 다시 만족

      cf) rb트리에서 노드를 삭제할 때 어떤 색이 삭제 되는지가 속성 위반 여부를 확인할 때 매우 중요

  • rbtree의 삭제에서 속성 위반 여부 확인은 삭제되는 색을 통해 알수 있다. (여기서 자녀는 유효한 값을 가진 자녀)

    • 삭제하려는 노드의 자녀가 없거나 하나라면?
      • 삭제되는 색은 삭제되는 노드의 색
    • 삭제하려는 노드의 자녀가 둘이라면?
      • 삭제되는 노드의 successor의 색

  • 속성 위반 여부 확인

    • 삭제되는 색이 red라면 어떠한 속성도 위반하지 않는다.
    • 삭제되는 색이 black이라면, 2번, 4번, 5번(특수한 상황을 제외하면 항상) 속성을 위반할 수 있다.

  • 위반 해결하기

    • 삭제되는 색이 black일때 2번 속성 해결하기
      • 루트 노드를 black으로 바꾸면 된다.
    • 삭제되는 색이 black일때 5번 속성 해결하기
      • 속성을 다시 만족시키기 위해 삭제된 색의 위치를 대체한 노드에 extra black을 부여한다.
      • 경로에서 black 수를 카운트 할 때 extra black은 하나의 black으로 카운트 된다.
      • 자녀가 없을 때
        • 삭제한 노드의 위치를 대체한 노드인 nil 노드에 extra black을 부여한다.
        • doubly black: extra black이 부여된 black 노드
      • 자녀가 하나일 때 → 자녀가 하나인 노드가 black이고 삭제하면 black이 삭제된거라 5번속성을 위반 그리고 바로 연결되면서 4번도 위반
        • 삭제된 노드의 위치를 대체한 노드에 extra black을 부여한다. → 5번 해결
        • red-and-black : extra black이 부여된 red노드
        • red-and-black 해결 → red-and-black을 black으로 바꾸면 해결 → 4번 해결
      • 자녀가 둘일 때
        • 삭제된 노드의 위치를 대체한 nil노드에 extra black 부여
        • doubly black
    • doubly black 해결하기 - 네가지 케이스
      • 기준은 doubly black의 형제의 색과, 그형제의 자녀들의 색
      • case4
        • doubly black의 오른쪽 형제가 black & 그 형제의 오른쪽 자녀가 red일 때
          • 그 red를 doubly black 위로 옮기고 옮긴 red로 extra black을 전달해서 red-and-black으로 만들면 red-and-black을 black으로 바꿔서 해결
          • 오른쪽 형제는 부모의 색으로, 오른쪽 형제의 오른쪽 자녀는 black으로, 부모는 black으로 바꾼 후에 부모를 기준으로 왼쪽으로 회전하면 해결
          • 오른쪽을 왼쪽으로 바꾸어도 성립
      • case3
        • doubly black의 오른쪽 형제가 black & 그 형제의 왼쪽 자녀가 red일 때 & 그 형제의 오른쪽 자녀는 black일 때
          • doubly black의 형제의 오른쪽 자녀가 red가 되게 만들어서 이후에 case4를 적용하여 해결
          • 오른쪽 왼쪽을 바꿔도 성립
      • case2
        • doubly black의 형제가 black & 그 형제의 두 자녀 모두 black일 때
          • doubly black과 그 형제의 black을 모아서 부모에게 전달해서 부모가 extra black을 해결하도록 위임한다.
      • case1
        • doubly black의 형제가 red일 때
          • doubly black의 형제를 black으로 만든 후 case 2,3,4 중에 하나로 해결
          • 부모와 형제의 색을 바꾸고 부모를 기준으로 왼쪽으로 회전한 뒤 doubly black을 기준으로 case 2,3,4 중에 해결

22.05.03

자료구조

22.05.04

코드리뷰

  • 류석영 교수님 코드 리뷰 강의
    • 코드리뷰 가장 중요한 2가지
      • 이해하기 쉬운 코드
      • 유지보수하기 쉬운 코드
        • 이해하기 쉬워야 유지보수가 편하다.
        • 유지보수가 편해야 디버깅할 일이 없다.
        • 클린한 코드에서는 버그가 숨을 곳이 없다.
    • 코드리뷰에서 제일 중요한 것
      • 구현해야 할 요구사항과 구현을 분리하는 것
        • 구현하기 전에 test부터 짠다.
          • edge case를 생각해야한다 (코드부터 짜면 이걸 잡기 힘듬)
        • test는 실행 가능한 문서다.
        • No source code without tests
          • code commit 전에 항상 test를 돌려야함.
          • 조금씩 commit을 해 놓아야 문제가 발생했을 때 범인을 찾기 쉽다.
        • Pair-programming
          • 제일 빨리 배우는 방법은 선배 어깨너머로 배우는 것이다.
          • 둘이 나란히 앉아서 한다(컴퓨터 하나)
    • Code Refactoring
      • 정의 : Refactoring은 SW의 동작을 바꾸지 않으면서 내부 구조를 개선하는 것 (즉, 코드의 구조를 잘 정해진 규정대로 수정하는 기술)
      • 왜 하는가?
        • sw 설계 개선 (항상 새로운게 나오기 때문에 그걸 배워서 적용해야 함)
          • 설계가 좋지 않은 코드는 보통 같은 일을 하는데 코드가 길고, 같은 일을 여러 곳에서 함.
        • 이해하기 쉬움
        • 프로그램 속도 향상

이번 주엔 드디어 C언어가 시작되었다. RED-BLACK-TREE 자료구조를 구현해보면서 익숙하지 않다는 걸 느꼈다. 구조체에 대한 개념이 많이 부족했었는데, BST, RB-TREE를 하면서 확실히 익숙해진 것 같다. 과제 테스트 케이스는 통과했는데 제출용 테스트 케이스를 통과하지 못해서 당황했다. 그래서 kantwang님과 함께 어디서 잘못된건지 찾아보면서 오류를 잡았다. 오류를 찾는 재미도 있었고 찾으면서 헷갈렸던 malloc, calloc에 대해서도 복기하게 되었다. 사실 RB-TREE 개념에 대해서는 RB-TREE 구조를 유지하면서 노드를 삽입, 삭제하려면 RB-TREE를 유지하기 위한 규칙들이 위반되는 케이스들이 있는데 이 위반 케이스들을 해결하려면 이런 방법들이 있구나 정도만 이해하고 넘어갔다. 왜냐하면 내가 생각한 이번과제의 목표는 기계친화적인 C언어를 하면서 컴퓨터와 친해지는 것이라 생각했기 때문이다. RB-TREE 구조를 완벽히 이해하는 것 보다 복잡한 자료구조를 구현해보면서 malloc-lab, 웹 프록시, pintos프로젝트들을 하기위해 이번주 과제를 하는 것이라 생각했다. 확실히 C언어가 익숙해졌다!

단체 회식이 이번주에 있었는데, 코치님과 많은 대화를 할 수 있었다. 대화를 하며 내가 정글이 목표로 하는 방향으로 잘 가고 있다는 생각이 들었다. 어제 몰랐던걸 오늘은 알게되며 매일 성장중이다. 성장속도가 빠르진 않지만 확실히 어제보단 나은 오늘을 실천하며 살고있다. 오늘에 최선을 다하면 분명 내일은 오늘보다 나을 것이다. 조바심을 갖지말고 꾸준함이 중요하다라는걸 어느때보다 크게 느낀 한 주였다.

WEEK05 구현 소스코드 - https://github.com/yeopto/rbtree-lab/blob/main/src/rbtree.c

profile
yeopto
https://yeopto.github.io로 이동했습니다.
이전 포스트

WEEK04

다음 포스트

WEEK06

0개의 댓글