• exe파일이므로 마찬가지로 윈도우에서 실행하자.
• 사용 도구는 x32dbg
• 실행하면

와 같이 이름을 먼저 묻고 시리얼을 묻는다.
조건을 만족하지 않는 값을 넣으면 Wrong이 출력된다.

같이 첨부된 리드미 파일을 열어보면

Find the Name when the Serial is 5B134977135E7D13
라고 한다. 시리얼이 주어져있고, 이름을 찾아내면 되는듯하다

ida를 열어, 메인함수를 디컴파일하면

int __cdecl main(int argc, const char **argv, const char **envp)
{
  signed int v3; // ebp
  int i; // esi
  int v6; // [esp+0h] [ebp-13Ch]
  int v7; // [esp+0h] [ebp-13Ch]
  int v8; // [esp+Ch] [ebp-130h]
  char v9[100]; // [esp+10h] [ebp-12Ch] BYREF
  char Buffer[197]; // [esp+74h] [ebp-C8h] BYREF
  __int16 v11; // [esp+139h] [ebp-3h]
  char v12; // [esp+13Bh] [ebp-1h]

  memset(v9, 0, sizeof(v9));
  memset(Buffer, 0, sizeof(Buffer));
  v11 = 0;
  v12 = 0;
  LOWORD(v8) = 8208;
  BYTE2(v8) = 48;
  sub_4011B9(aInputName, v6);
  scanf("%s", v9);
  v3 = 0;
  for ( i = 0; v3 < (int)strlen(v9); ++i )
  {
    if ( i >= 3 )
      i = 0;
    sprintf(Buffer, "%s%02X", Buffer, v9[v3++] ^ v9[i - 4]);
  }
  memset(v9, 0, sizeof(v9));
  sub_4011B9(aInputSerial, v7);
  scanf("%s", v9);
  if ( !strcmp(v9, Buffer) )
    sub_4011B9(aCorrect, v8);
  else
    sub_4011B9(aWrong, v8);
  return 0;
}

위와 같다.
사용자가 입력한 name을 받아 v9에 저장하고, 반복문 내 연산을 수행한 후 Buffer에 저장하는 것으로 보인다. 그 후 v9와 Buffer 를 비교하여 일치 여부에 따라 Correct, Wrong이 나타나는 듯하다.
리드미에 있는 시리얼 값을 이용하여 name을 역연산하면 해결할 수 있을 것이다.

x32dbg를 열어서 확인해보면

브레이크 포인트가 걸린 곳은 scanf로 name을 받는 곳이고, 계속 한줄씩 실행하다보면 해당 지점으로 계속 돌아온다. 이 부분이 위의 반복문임을 확인할 수 있다.

전체 뷰를 확인하면 위와 같다.

# 키값으로 이름 찾는 알고리즘 
# find name algorithm using key value
# 5B134977135E7D13
hexx = ['5b','13','49','77','13','5e','7d','13']
count = 1
full = ''

for x in hexx:
    for i in range(0,200):
        a = (16 * count) ^ i
        a = hex(a)
        a = a[2:]

        if a == x:
            print('원래값:',i,"hexx값:",x,'count값체크:',count)
            full = full + chr(i)

            if count == 3:
                count = 1                
                break

            else:
                count = count + 1                
                break
print(full)

원래값: 75 hexx값: 5b count값체크: 1
원래값: 51 hexx값: 13 count값체크: 2
원래값: 121 hexx값: 49 count값체크: 3
원래값: 103 hexx값: 77 count값체크: 1
원래값: 51 hexx값: 13 count값체크: 2
원래값: 110 hexx값: 5e count값체크: 3
원래값: 109 hexx값: 7d count값체크: 1
원래값: 51 hexx값: 13 count값체크: 2
K3yg3nm3

exe파일이므로 윈도우에서 실행하면
input를 묻고

IDA를 키면

input을 묻는 부분을 바로 찾을 수 있다.

메인함수를 디컴파일해보니 위와 같다.
추정컨대 sub_140011B0으로 인풋 메시지를 출력하고
sub_14001210으로 값을 받아서 저장하는 것으로 보인다.

우리가 알아야 하는것은 Correct가 뜨는 조건인데 그 조건과 관련된 함수는
sub_14001000으로 보인다.

그 함수도 디컴파일했는데 결과가 위와 같다. 인풋값을 ac배열과 비교하는 로직이다.
따라서 ac배열을 조사해볼 필요가 있다.

ac배열을 클릭해서 들어가보면
Comp4re_the_arr4y를 확인할 수 있다.

• 탐색 알고리즘이란
• 순차 탐색
• 이진 탐색

탐색 알고리즘

탐색 알고리즘이란 어떤 데이터셋에서 특정한 요소를 찾아내는 것이다. 여기서 말하는 데이터셋은 배열이나 리스트나, 트리나 무엇이든 될 수 있으나, 특정 알고리즘은 링크드 리스트나 이진 트리에만 사용할 수 있는 등 제약이 있을 수 있다.

순차 탐색(Linear Search)

처음부터 끝까지 모든 요소를 비교하여 원하는 데이터를 찾는 탐색 알고리즘이다. 어느 한 방향으로만 탐색할 수 있는 알고리즘이므로 선형 탐색(linear search)라고 하기도 한다.

절차는 매우 단순한데, 정리하자면
처음부터 시작해서->찾을 값과 해당 위치 값 비교->같으면 찾은 것, 아니면 이동해서 다시 찾기

예시를 들어 살펴보자.
30을 {10, 50, 30, 70, 80, 60, 20, 90, 40} 배열에서 찾을 것이다.

• 30은 10과 같지 않다. 넘어가서,

• 마찬가지로 50도 30과 같지 않다.

• arr[2]의 값은 30과 같다. 찾았다.

순차 탐색의 구현

간단한 알고리즘인만큼 구현도 매우 간단한 편이다.

#include <stdio.h>

int linearSearch(int arr[], int N, int x) {
  for (int i = 0; i < N; i++)
    if (arr[i] == x)
      return i;
  return -1;
}

int main(void) {
  int arr[] = {2, 3, 4, 10, 40};
  int x = 10;
  int N = sizeof(arr) / sizeof(arr[0]);

  int result = linearSearch(arr, N, x);
  (result == -1) ? printf("찾지못함\n") : printf("arr[%d]\n", result);
  return 0;
}

순차 탐색의 분석

시간 복잡도

• Best Case: 첫번째에서 바로 찾으면 $O(1)$
• Worst Case: $O(N)$
• Average: $O(N)$

장점

• 말그대로 그냥 하나하나 처음부터 비교하는 것이므로 데이터셋이 어떤 상태이든지 상관없다. 정렬이 되어있든, 되어있지 않든

단점

• 하나하나 처음부터 찾을 때까지 비교해가는 것이므로 비효율적이고, 데이터셋이 크면 쓰기 어렵다.

이진 탐색(Binary Search)

이진 탐색은 정렬된 배열에서 쓸 수 있는 탐색 알고리즘이다.

과정은 다음과 같다.

• 데이터셋을 가운데 인덱스를 기준으로 반으로 나눈다.
• 가운데 인덱스의 요소와 찾을 값(key)를 비교한다.
• 정확히 가운데에서 찾았다면 탐색을 종료하고, 그렇지 않다면
• 키가 앞쪽 반에 있다면 뒤쪽 반을 버리고 뒤쪽에 있다면 앞쪽 반을 버린다.
• 키의 후보 구역에서 위 과정을 반복해서 찾는다.

예를 들어,

위 그림과 같은 배열에서 23을 찾는다고 가정해보자.
위 배열의 가운데 인덱스는 arr[4], 16이다.

23은 16보다 크다. 따라서 뒤쪽(오른쪽) 반을 탐색하자.

다시, 뒤쪽 반의 가운데 요소는 56이다. 23은 이보다 작다. 그러면 이제 앞쪽 반을 탐색하자.

구역을 좁혀나가는 방식으로 23을 찾는 데에 성공했다.

이진 탐색의 구현

#include <stdio.h>

int binarySearch(int arr[], int low, int high, int x) {
  while (low <= high) {
    int mid = low + (high - low) / 2;
    //가운데 인덱스가 키일때
    if (arr[mid] == x)
      return mid;
    //일치하지 않는 경우 값을 비교하여 구역을 좁힘
    else if (arr[mid] < x)
      low = mid + 1;
    else
      high = mid - 1;
  }
  //배열 내에 없음.
  return -1;
}

int main(void) {
  int arr[] = {2, 3, 4, 5, 6, 7, 8, 9};
  int n = sizeof(arr) / sizeof(arr[0]);
  int x = 10;
  int result = binarySearch(arr, 0, n - 1, x);
  if (result == -1)
    printf("없음\n");
  else
    printf("arr[%d]\n", result);
}

이진 탐색 분석

시간복잡도:

• Best case: $O(1)$
• Average case: $O(logN)$
• Worst Case: $O(log N)$

장점

• 순차 탐색보다 빠르다.
• 따라서 더 큰 데이터셋에 사용하기 적합하다.

단점

• 배열이 정렬되어있어야한다.
• 찾으려는 값이 비교할 수 있는 값이어야한다. 순차 탐색에서는 일치 여부만 찾으면 되므로 크고 작음을 비교할 수 없어도 된다.

• 버블 정렬
• 선택 정렬
• 삽입 정렬

정렬 알고리즘

정렬(sorting)이란 기준에 따라 데이터를 순서대로, 체계적으로 정리하는 것이다. 정렬에도 여러 가지 방법들이 있는데 대표적으로 버블 정렬, 선택 정렬, 삽입 정렬이 있다.

버블 정렬(Bubble sort)

버블 정렬은 가장 간단한 정령 알고리즘 중 하나이다.
간단하게, 옆에 위치한 두 개끼리 비교하여 정렬하는 것을 반복하는 것이다.

예시를 들어

arr[] = {6,0, 3, 5}
이면

• 1. 가장 큰 element가 끝으로 위치하게 된다.

• 2. 두 번째 큰 element도 제 위치를 찾아가게 된다.

• 3. 세 번째 큰 element도 제 자리를 찾아가므로, element개수가 총 4개인 이 배열은 정렬이 완료되었다.

버블 정렬의 구현

#include <stdbool.h>
#include <stdio.h>

void swap(int *xp, int *yp) {
  int temp = *xp;
  *xp = *yp;
  *yp = temp;
}

// 버블 정렬
void bubbleSort(int arr[], int n) {
  bool swapped;
  for (int i = 0; i < n - 1; i++) {
    swapped = false;
    for (int j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(&arr[j], &arr[j + 1]);
        swapped = true;
      }
    }
    // 이 경우 처음부터 정렬되어있었음
    if (swapped == false)
      break;
  }
}

// 배열 출력
void printArray(int arr[], int size) {
  for (int i = 0; i < size; i++)
    printf("%d ", arr[i]);
}

int main(void) {
  int arr[] = {64, 34, 25, 12, 22, 11, 99};
  int n = sizeof(arr) / sizeof(arr[0]);
  bubbleSort(arr, n);
  printArray(arr, n);
  return 0;
}

위와 같이 구현할 수 있다.
실행 시 작은 값부터 출력된다.

버블 정렬 분석

이중반복문을 돌기 때문에 시간복잡도는 $$ O(N^2) $$

장점

• 가장 간단한 정렬 알고리즘 중 하나이다.
• 추가적인 메모리 공간이 필요없다.
• stable하다.

단점

• $O(N^2)$의 시간복잡도
• comparison operator가 요구됨.

stable

크기가 같은 값이 있을 때, 예를 들어 12가 두 개면 하나를 a1, 남은 하나를 a2라 하자.
정렬은 크기를 기준으로 하기 때문에 값이 같은 a1과 a2는 경우에 따라 서로 위치가 a2, a1처럼 바뀔 수도 있는데, 바뀌지 않는 경우를 stable하다고 한다.

선택 정렬(Selection Sort)

선택 정렬도 마찬가지로 간단하고 효과적인 정렬 알고리즘 중 하나이다. 선택 정렬은 계속해서 가장 작은 값 또는 가장 큰 값을 뽑아내서 끝의 위치로 옮겨준다.

마찬가지로 예시를 보면
arr = {64, 25, 12, 22, 11}

• 1. 최솟값을 탐색한다. 가장 작은 값은 11이다.

• 2. 11을 64의 자리로 옮긴다. 11은 정렬되었으니 건드리지 말고 다음 작은 값을 찾는데 이건 12이다.

• 3. 과정은 계속 같다...이번에는 22가 가장 작다. 22를 25와 교환해준다.

• 4. 25가 최솟값이고, 이미 4번째 자리에 있어서 교환해줄 필요는 없다.

• 5. 이미 위에서 3번 시점에서 이 배열은 정렬된 상태이지만, 이러한 과정을 통해 최종적으로 가장 큰 값이 자동적으로 맨 뒤에 오게되면서 정렬이 완료된다.

선택 정렬의 구현

#include <stdio.h>

void swap(int *xp, int *yp) {
  int temp = *xp;
  *xp = *yp;
  *yp = temp;
}

void selectionSort(int arr[], int n) {
  int min_idx;
  for (int i = 0; i < n - 1; i++) {
    min_idx = i;
    for (int j = i + 1; j < n; j++)
      if (arr[j] < arr[min_idx])
        min_idx = j;
    if (min_idx != i)
      swap(&arr[min_idx], &arr[i]);
  }
}

void printArray(int arr[], int size) {
  for (int i = 0; i < size; i++)
    printf("%d ", arr[i]);
  printf("\n");
}

int main(void) {
  int arr[] = {190, 90, 120, 1, 3, 2};
  int n = sizeof(arr) / sizeof(arr[0]);
  selectionSort(arr, n);
  printArray(arr, n);
  return 0;
}

선택 정렬 분석

시간복잡도는 이중반복문을 돌게 되므로
$$O(N^2)$$

장점

• 간단하다. 버블정렬과 마찬가지로..
• 작은 데이터셋에서 잘 작동한다.

단점

• 시간복잡도.
• 큰 데이터셋에서는 좋지 못하다.
• stable하지 않다.

삽입 정렬(Insertion Sort)

삽입 정령은 자료구조를 순차적으로 순회하면서 순서에 어긋나는 element를 찾고, 그 element를 올바른 위치에 다시 삽입해나가는 정렬 알고리즘이다.

1. 첫 번째 요소가 정렬이 되어있다고 가정하고 두 번째 요소부터 살펴본다.
2. 첫 번째 요소와 두 번째 요소를 비교한다. 비교 후 swap으로 정렬
3. 세 번째 요소와 두 번째 요소를 비교하고, 다음으로 첫 번째 요소와 비교한다. 그리고 세 번째 요소를 맞는 위치에 끼워넣는다.
4. 이런 식으로 완전히 정렬되기 전까지 반복한다.

사진의 예시를 살펴보고 위 절차대로 수행해보자.

23이 정렬되어있다고 가정하고 1과 23을 비교
-> 1을 23 앞에 끼워넣기
-> 10과 23 비교, 10과 1 비교. 1과 23 사이에 끼워넣음
-> 5도 마찬가지로 비교해서 끼워넣음.
-> 2도 순차적으로 비교해서 맞는 위치에 끼워넣음.
-> 정렬 완료

삽입 정렬의 구현

#include <stdio.h>

void insertionSort(int arr[], int n) {
  for (int i = 0; i < n; i++) {
    int key = arr[i];
    int j = i - 1;

    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
}

void printArray(int arr[], int n) {
  for (int i = 0; i < n; i++)
    printf("%d ", arr[i]);
  printf("\n");
}

int main(void) {
  int arr[] = {12, 11, 13, 5, 6};
  int n = sizeof(arr) / sizeof(arr[0]);
  insertionSort(arr, n);
  printArray(arr, n);
  return 0;
}

삽입 정렬 분석

• Best Case: $O(N)$
• Average Case: $O(N^2)$
• Worst Case: $O(N^2)$

이미 전부 정렬되어 있는 경우 O(N)이지만 랜덤하게 되어있거나, 역순으로 되어있는 최악의 경우일 때는 $O(N^2)$

장점

• 간단하다.
• stable
• 작은 크기의 리스트에 적합하다.

단점

• 큰 크기에서는 적합하지 않음
• 위 두 알고리즘에 비교한 단점은 아니나 일반적으로 머지 소트나 퀵 소트가 더 효율적이다.

• exe 파일이므로 윈도우에서 실행해보자.
• 실행하면 패스워드를 받는 구조인데,

비밀번호를 현재는 모르니 아무거나 입력하면 아래와 같은 메시지박스를 출력한다.

따라서 Incorrect Password를 검색하여 그 전후로 비밀번호를 검증하는 로직을 찾을 수 있을 것이다.
틀린 경우에 위와 같은 메시지박스를 출력할 것이고, 맞을 때는 현재는 알 수 없다

.

x32dbg에서 Incorrect Password를 찾으면 아래와 같은 위치에 있다.

조금 올려보면 Congratulation이 있다. Congratulation이 되는 조건을 찾으면 될 것으로 보인다. 입력 방식을 보아 Congratulations 위로 문자열을 비교하는 로직들을 확인하면 될 것 같다.
그 위로 esp+4와 E(코멘트로 45:E)를 비교하는 로직이 있다.

더 더 위로 올려보면

위와 같이 어떤 문자열과 비교하는 과정들이 있다.
주석처리를 통해 저것들이 무엇인지 알 수 있으며, 플래그가 저기 적힌 a, 5y, R3versing과 관련이 있을 것으로 보인다.

Ea5yR3versing을 입력하게 되면

파일을 다운받고, 압축을 해제하면 ch2.bin이 나온다.
제목에서도 예상했지만 32비트 ELF파일이다.

file ch2.bin
ch2.bin: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), statically linked, for GNU/Linux 2.6.8, with debug_info, not stripped

프로그램을 미리 실행해보면, username을 먼저 받고 username이 틀리면 그 이후로 넘어가지 않는다.
여기까지만 보고 예상해 보건대 username과 password를 모두 맞춰야 통과되는 것 같다.

그런데,
이걸 IDA로 열면 사실 굉장히 직관적으로 답이 보인다...
아이다를 열면 성공적으로 메인함수로 바로 보여준다.

열자마자 john, the ripper라는 문자열이 보인다.
그리고 아래에 아까 봤던 익숙한 시작 화면 문자열이 보인다. username을 받고 분기점을 보니 username이 맞을 때 password를 입력할 수 있도록 넘어가는 것이다.

usename에 john을, password에 the ripper를 넣으면

./ch2.bin
############################################################
##        Bienvennue dans ce challenge de cracking        ##
############################################################

username: john
password: the ripper
Bien joue, vous pouvez valider l'epreuve avec le mot de passe : 987654321 !

플래그가 987654321이라고 한다. 대충지었군..

What integer does this program print with arguments 266134863 and 1592237099? File: chall.S Flag format: picoCTF{XXXXXXXX} -> (hex, lowercase, no 0x, and 32 bits. ex. 5614267 would be picoCTF{0055aabb})

[WRITEUP]

파일을 다운받고

file chall.S
chall.S: assembler source, ASCII text

확인해보면 어떤 어셈블리 소스코드임을 확인할 수 잇다.

cat chall.S

로 내용을 출력해보면

cat chall.S          
    .arch armv8-a
    .file    "chall.c"
    .text
    .align    2
    .global    func1
    .type    func1, %function
func1:
    sub    sp, sp, #16
    str    w0, [sp, 12]
    str    w1, [sp, 8]
    ldr    w1, [sp, 12]
    ldr    w0, [sp, 8]
    cmp    w1, w0
    bls    .L2
    ldr    w0, [sp, 12]
    b    .L3
.L2:
    ldr    w0, [sp, 8]
.L3:
    add    sp, sp, 16
    ret
    .size    func1, .-func1
    .section    .rodata
    .align    3
.LC0:
    .string    "Result: %ld\n"
    .text
    .align    2
    .global    main
    .type    main, %function
main:
    stp    x29, x30, [sp, -48]!
    add    x29, sp, 0
    str    x19, [sp, 16]
    str    w0, [x29, 44]
    str    x1, [x29, 32]
    ldr    x0, [x29, 32]
    add    x0, x0, 8
    ldr    x0, [x0]
    bl    atoi
    mov    w19, w0
    ldr    x0, [x29, 32]
    add    x0, x0, 16
    ldr    x0, [x0]
    bl    atoi
    mov    w1, w0
    mov    w0, w19
    bl    func1
    mov    w1, w0
    adrp    x0, .LC0
    add    x0, x0, :lo12:.LC0
    bl    printf
    mov    w0, 0
    ldr    x19, [sp, 16]
    ldp    x29, x30, [sp], 48
    ret
    .size    main, .-main
    .ident    "GCC: (Ubuntu/Linaro 7.5.0-3ubuntu1~18.04) 7.5.0"
    .section    .note.GNU-stack,"",@progbits

와 같이 나오는 것을 볼 수 있다. (코드가 짧아서 전체를 집어넣었다.)

func1 함수

func1:
    sub    sp, sp, #16
    str    w0, [sp, 12]
    str    w1, [sp, 8]
    ldr    w1, [sp, 12]
    ldr    w0, [sp, 8]
    cmp    w1, w0
    bls    .L2
    ldr    w0, [sp, 12]
    b    .L3

위에서 핵심은 cmp w1, w0이다.
w0이 w1보다 작으면 L2로 분기한다고 한다.

L2, L3

.L2:
    ldr    w0, [sp, 8]
.L3:
    add    sp, sp, 16
    ret
    .size    func1, .-func1
    .section    .rodata
    .align    3
.LC0:
    .string    "Result: %ld\n"
    .text
    .align    2
    .global    main
    .type    main, %function

main

main:
    stp    x29, x30, [sp, -48]!
    add    x29, sp, 0
    str    x19, [sp, 16]
    str    w0, [x29, 44]
    str    x1, [x29, 32]
    ldr    x0, [x29, 32]
    add    x0, x0, 8
    ldr    x0, [x0]
    bl    atoi
    mov    w19, w0 
    ldr    x0, [x29, 32]
    add    x0, x0, 16
    ldr    x0, [x0]
    bl    atoi 
    mov    w1, w0
    mov    w0, w19
    bl    func1 ; func1호출
    mov    w1, w0 
    adrp    x0, .LC0
    add    x0, x0, :lo12:.LC0
    bl    printf
    mov    w0, 0
    ldr    x19, [sp, 16]
    ldp    x29, x30, [sp], 48
    ret
    .size    main, .-main
    .ident    "GCC: (Ubuntu/Linaro 7.5.0-3ubuntu1~18.04) 7.5.0"
    .section    .note.GNU-stack,"",@progbits

결과적으로 들어오는 인자 중 더 큰 값이 반환된다.
따라서 위 인풋에서 들어오는 값 중 더 큰 것은 1592237099 이므로,
플래그 형식에 맞게 32비트 16진수로 바꾼 플래그는
picoCTF{5ee79c2b}

1. 헤더파일이란?

• 헤더파일: c프로그램에서 .h가 붙는 파일들로, 여러 소스코드 파일에 공통적으로 필요한 것을 저장하는 파일이다.

• #include를 통해 .c파일에서 헤더파일의 내용을 가져다 쓸 수 있다.

• 헤더파일의 필요성: 유지보수와 재사용에 용이하다. 겹치는 내용은 한 번 적어서 include해서 공통적으로 쓸 수 있고, 유지보수할 때도 보기 편하다.

• 컴파일 시 헤더파일을 따로 처리할 필요는 없으며 .c파일을 처리하면서 처리된다.

2. 코드 살펴보기

hacker.h

//hacker.h  
#pragma once  
#include <string.h>  
#include <stdio.h>  
#include <unistd.h>  
#include <stdlib.h>  

//hacker 구조체 정의  
typedef struct hacker{  
    char name[50];  
    unsigned int age;  
    char** skill_list;  
    int skill_num;  
    int level;  
}hacker;  

int input_name(hacker*);  
int input_age(hacker*);  
int input_new_skill(hacker*);  

//new_hacker함수  
hacker* new_hacker() {  
    hacker* new_ptr = (hacker*)malloc(sizeof(hacker));  

    memset(new_ptr->name, '\0', sizeof(new_ptr->name));  
    new_ptr->skill_num = 0;  
    new_ptr->level = 1;  

    new_ptr->skill_list = (char**)malloc(sizeof(char*));  

    input_name(new_ptr);  
    input_age(new_ptr);  
    input_new_skill(new_ptr);  

    return new_ptr;  
}  

//input_name함수  
int input_name(hacker* ptr){  
    write(1,"Input the name : ",17);  
    return scanf("%s",ptr->name);  
}  

int input_age(hacker* ptr){  
    printf("Input the age : ");  
    return scanf("%u",&ptr->age);  
}  

void increase_size(char***);  
int input_new_skill(hacker* ptr){  
    write(1, "Input new Skill : ", 18);  

    char buf[50] = {0,};  
    scanf("%s",buf);  

    char* tmp = (char*)malloc(strlen(buf)+1);  
    strcpy(tmp,buf);  

    ptr->skill_num++;  
    increase_size(&(ptr->skill_list));  


    ptr->skill_list[ptr->skill_num-1] = tmp;  
    return ptr->skill_num;  
}  

void increase_size(char*** skill_list) {  
    if (*skill_list == NULL) {  
        *skill_list = (char**)malloc(sizeof(char*));  
        (*skill_list)[0] = NULL;  
        return;  
    }  
    int org_size = sizeof(*skill_list) / sizeof(char*);  

    char** new_ptr = (char**)malloc(sizeof(char*) * (org_size + 1));  

    for (int i = 0; i < org_size; i++) {  
        new_ptr[i] = (*skill_list)[i];  
    }  
    free(*skill_list);  
    *skill_list = new_ptr;  
}

헤더파일 hacker.h의 전체 코드는 위와 같다.

저 부분들을 하나하나 떼어서 보자면

header files

#pragma once
#include <string.h>
#include <stdio.h> 
#include <unistd.h> 
#include <stdlib.h>

• #pragma once: 컴파일러에게 해당 헤더파일이 한번만 빌드되도록 하는 역할. 여러 곳에서 include되면 정의가 추가되어 중첩될 수 있는데 이를 방지한다.

hacker 구조체

typedef struct hacker{
    char name[50];
    unsigned int age;
    char** skill_list;
    int skill_num;
    int level;
}hacker;

new_hacker 함수

//new_hacker함수  
hacker* new_hacker() {  
    hacker* new_ptr = (hacker*)malloc(sizeof(hacker));  
    // 해커 구조체 크기만큼 메모리 동적 할당
    memset(new_ptr->name, '\0', sizeof(new_ptr->name));  
    //new_ptr->name배열의 모든 바이트를 널로 초기화 
    new_ptr->skill_num = 0;  
    new_ptr->level = 1;  

    new_ptr->skill_list = (char**)malloc(sizeof(char*)); 
    // 스킬 목록을 저장할 포인터 배열을 동적 할당, 초기에는 스킬이 없으므로 char* 

    input_name(new_ptr);  
    input_age(new_ptr);  
    input_new_skill(new_ptr);  
  // input함수들을 통해 사용자의 정보 입력
    return new_ptr;  
    // 초기화된 해커 구조체 포인터를 반환
} 

입력 함수들

hacekr 구조체 포인터를 받아 스킬 입력

• input_name

• input_age

• input_new_skill

int input_new_skill(hacker* ptr){
    write(1, "Input new Skill : ", 18);
    // write함수를 사용해 위 메시지를 표준출력
    char buf[50] = {0,};
    // 임시 저장 버퍼를 50바이트 크기로 선언, 모든 바이트를 0으로 초기화
    scanf("%s",buf);
    // 입력을 버퍼에 저장

    char* tmp = (char*)malloc(strlen(buf)+1);
    // 입력받은 기술명의 길이만큼 메모리 동적 할당
    strcpy(tmp,buf);
    // buf에 저장된 기술명을 동적 할당된 메모리 공간 tmp에 복사

    ptr->skill_num++;
    // 기술 개수 증가
    increase_size(&(ptr->skill_list));
    // 함수 호출, 하단에 있음
    ptr->skill_list[ptr->skill_num-1] = tmp;
    // 새로운 기술명을 기술 목록 배열의 마지막 위치에 추가
    return ptr->skill_num;
    // 기술 개수 반환
}

increase_size 함수

void increase_size(char*** skill_list) {
    if (*skill_list == NULL) {
        *skill_list = (char**)malloc(sizeof(char*));
        (*skill_list)[0] = NULL;
        return;
    }

    int org_size = sizeof(*skill_list) / sizeof(char*);

    char** new_ptr = (char**)malloc(sizeof(char*) * (org_size + 1));

    for (int i = 0; i < org_size; i++) {
        new_ptr[i] = (*skill_list)[i];
    }

    free(*skill_list);
    *skill_list = new_ptr;
}

위 헤더파일의 내용을 받아서 쓰면

//다음과 같은 코드를 이해하고, 작성해봅시다.
//main.c
#include "hacker.h"

int main(){
    hacker* qwertyou = new_hacker();
    printf("%s's age is %d\n",qwertyou->name, qwertyou->age);
    printf("%s's level is %d\n",qwertyou->name, qwertyou->level);


    printf("\n\n-----qwertyou's skill list-----\n");
    for(int i=0;i<qwertyou->skill_num;i++){
        printf("%s's skill%d : %s\n",qwertyou->name, i, qwertyou->skill_list[i]);
    }
}

메인함수에 위 함수들과 다른 헤더파일들도 따로 더 적을 필요가 없다.

• 트리의 개념
• 트리의 순회 방법
• 이진 트리, 완전 이진 트리
• 이진 탐색 트리

1. 트리의 개념

• 나무를 닮은 자료구조

1-1. 트리의 구성 요소

트리의 구성 요소: 뿌리, 가지, 잎 모두 똑같은 노드이나 위치에 따라 명칭이 다르다.

구성 요소

• 뿌리(Root): 가장 위에 있는 노드
• 가지(Branch): 뿌리와 잎 사이
• 잎(Leaf): 끝에 있음(단말:terminal)이라고 하기도 함.

• 부모(parents): A는 B,C,D의 부모
• 자식(Children): B,C,D는 A의 자식
• 형제(Sibling): B,C,D는 형제

경로

• 경로: 한 노드에서 다른 한 노드까지 이르는 길 사이에 있는 노드들의 순서
  example) A에서 K까지의 경로: A,B,E,K
• 경로의 길이(length): 출발 노드에서 목적 노드까지 거쳐야 하는 노드의 개수
  ex) A-K: 3
• 깊이(Depth): 뿌리 노드에서 해당 노드까지 이르는 경로의 길이
  ex) K: 3
• 레벨(level): 깊이가 같은 노드의 집합
  ex) level 3: K, L, M
• 높이(height): 가장 깊은 곳에 있는 잎 노드까지의 깊이
  ex) 3
• 차수(Degree): 노드의 차수->그 노드의 자식 노드 개수, 트리의 차수->트리 내에 있는 노드들 가운데 자식 노드가 가장 많은 노드의 차수

2. 트리의 기본 연산

2-2. 노드 선언

Left Child, Right Sibling 형태 표현법(LCRS)에서
노드 구조체는

typedef char ElementType;
typedef struct tagLCRSNode {
  struct tagLCRSNode *LeftChild;
  struct tagLCRSNode *RightSibling;
  ElementType Data;
} LCRSNode;

와 같이 데이터 필드와 Left Child, Right Sibling 두 개 포인터로 구성된다.

2-3. 노드 생성/소멸

//노드 생성
LCRSNode *LCRS_CreateNode(ElementType NewData) {
  LCRSNode *NewNode = (LCRSNode *)malloc(sizeof(LCRSNode));
  NewNode->LeftChild = NULL;
  NewNode->RightSibling = NULL;
  return NewNode;
}
//노드 소멸
void LCRS_DestroyNode(LCRSNode *Node) { free(Node); }

• 노드 생성: 자유 저장소에 LCRSNode 구조체의 크기만큼 메모리를 할당하고 매개변수 NewData를 Data에 저장한 후 노드 메모리 주소 반환
• 노드 소멸: 자유 저장소에서 할당했던 메모리만 해제하면 됨

2-4. 자식 노드 연결

void LCRS_AddChildNode(LCRSNode *Parent, LCRSNode *Child) {
//자식 노드가 있는지 검사
  if (Parent->LeftChild == NULL)
  //자식 노드가 없으면 왼쪽노드에 바로 저장
    Parent->LeftChild = Child;
  else {
  //자식 노드가 있는 경우
    LCRSNode *TempNode = Parent->LeftChild;
    while (TempNode->RightSibling != NULL)
    //RightSibling을 이용해 가장 오른쪽의 자식 노드를 찾고 Child를 가장 오른쪽 자식 노드의 RightSibling노드에 대입
      TempNode = TempNode->RightSibling;
    TempNode->RightSibling = Child;
  }
}

위 함수 과정을 통해 부모 노드는 자식을 하나 추가한다.

2-5. 트리 출력

void LCRS_PrintTree(LCRSNode *Node, int Depth) {
//들여쓰기
  for (int i = 0; i < Depth - 1; i++) {
    printf("   ");
    if (Depth > 0) //자식 노드 여부
      printf("+--");
      //노드 데이터 출력
    printf("%c\n", Node->Data);
    if (Node->LeftChild != NULL)
      LCRS_PrintTree(Node->LeftChild, Depth + 1);
    if (Node->RightSibling != NULL)
      LCRS_PrintTree(Node->RightSibling, Depth);
  }
}

구성된 트리를 출력하는 코드

3. 이진 트리

앞쪽 코드에서 구현한 트리는 노드의 자식 노드 개수에 제한이 없었으나 이진트리는 하나의 노드가 자식 노드를 2개까지만 가질 수 있다.

3-1. 이진 트리의 종류

• 포화 이진 트리
• 완전 이진 트리
• 이진 탐색 트리

포화 이진 트리

위 사진처럼 잎 노드를 제외한 모든 노드가 자식을 2개씩 갖고 있으면 포화 이진 트리라고 한다.

완전 이진 트리

모든 노드가 자식 2개를 갖고 있진 않아도 잎 노드들이 왼쪽부터 차곡차곡 채워져있으면 완전 이진 트리라고 한다.
B처럼 중간에 노드가 빈 트리는 완전 이진 트리가 아니다.

높이 균형 트리

뿌리 노드를 기준으로 왼쪽 하위 트리와 오른쪽 하위 트리의 높이가 2이상 차이 나지 않는 이진 트리

완전 높이 균형 트리

왼쪽 하위 트리와 오른쪽 하위 트리의 높이가 완전히 같은 이진 트리

• 트리의 성능과 모양: 가능한 완전한 모습으로 유지해야 높은 성능을 낼 수 있다. 이진 트리는 컴파일러나 검색과 같은 알고리즘의 뼈대가 되는 특별한 자료구조이므로, 이러한 모양이 중요하다.

3-4. 이진 탐색 트리

• 한마디로 탐색을 위한 이진 트리(이진 탐색)

이진 탐색은 배열에만 사용 가능하기 때문에 링크드 리스트에서 탐색을 위해서 이진 탐색 트리를 쓸 수 있다.

이진 탐색 트리의 특징

• 부모 노드 입장에서 왼쪽 자식 노드는 나보다 작고 오른쪽 자식 노드는 나보다 크다.

위와 같은 특징을 통해 탐색이 작동한다.
중앙 요소를 찾아 좌우의 대소르 비교하여 탐색 범위를 정하고 다시 중앙 요소를 찾아 좌우의 요소를 비교하는 것을 반복하여 탐색한다.

예시) 위 트리에서 5를 찾는다고 해보자.
5는 8보다 작으니 왼쪽 노드로, 다시 5는 3보다 크니 오른쪽 노드로 이동하는 것이다.