// 선언
int arr[5];

// 선언과 동시에 초기화
int arr[5] = {10, 20, 30, 40, 50};

// 부분 초기화 (나머지는 0)
int arr[5] = {10, 20};  // {10, 20, 0, 0, 0}

// 모두 0으로 초기화
int arr[5] = {0};

// 크기 생략 (컴파일러가 자동 계산)
int arr[] = {10, 20, 30};  // 크기: 3

int arr[5] = {10, 20, 30, 40, 50};

// 읽기
int value = arr[2];  // 30

// 쓰기
arr[2] = 100;  // {10, 20, 100, 40, 50}

// 시간복잡도: O(1) ✔ (인덱스로 직접 접근)

// 선형 탐색 (Linear Search)
int search(int arr[], int size, int key) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == key) {
            return i;  // 찾은 인덱스 반환
        }
    }
    return -1;  // 못 찾음
}

// 시간복잡도: O(N)

int arr[10] = {10, 20, 30, 40, 50};
int size = 5;

// 맨 뒤에 60 삽입
arr[size] = 60;
size++;

// 결과: {10, 20, 30, 40, 50, 60}
// 시간복잡도: O(1) ✔

void insertAt(int arr[], int *size, int index, int value) {
    // 뒤에서부터 한 칸씩 이동
    for (int i = *size; i > index; i--) {
        arr[i] = arr[i - 1];
    }
    
    arr[index] = value;
    (*size)++;
}

// 시간복잡도: O(N) ✘

int arr[10] = {10, 20, 30, 40, 50};
int size = 5;

// 맨 뒤 삭제
size--;

// 결과: {10, 20, 30, 40} (50은 무시됨)
// 시간복잡도: O(1) ✔

void deleteAt(int arr[], int *size, int index) {
    // 앞으로 한 칸씩 이동
    for (int i = index; i < *size - 1; i++) {
        arr[i] = arr[i + 1];
    }
    
    (*size)--;
}

// 시간복잡도: O(N) ✘

int findMax(int arr[], int size) {
    int max = arr[0];
    
    for (int i = 1; i < size; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    
    return max;
}

int findMin(int arr[], int size) {
    int min = arr[0];
    
    for (int i = 1; i < size; i++) {
        if (arr[i] < min) {
            min = arr[i];
        }
    }
    
    return min;
}

// 시간복잡도: O(N)

void reverse(int arr[], int size) {
    int temp;
    
    for (int i = 0; i < size / 2; i++) {
        // 양 끝을 교환
        temp = arr[i];
        arr[i] = arr[size - 1 - i];
        arr[size - 1 - i] = temp;
    }
}

// 시간복잡도: O(N)

int removeDuplicates(int arr[], int size) {
    if (size == 0) return 0;
    
    int newSize = 1;  // 첫 원소는 항상 포함
    
    for (int i = 1; i < size; i++) {
        int isDuplicate = 0;
        
        // 이전 원소들과 비교
        for (int j = 0; j < newSize; j++) {
            if (arr[i] == arr[j]) {
                isDuplicate = 1;
                break;
            }
        }
        
        // 중복이 아니면 추가
        if (!isDuplicate) {
            arr[newSize] = arr[i];
            newSize++;
        }
    }
    
    return newSize;
}

// 시간복잡도: O(N²)

// 선언
int arr[3][4];  // 3행 4열

// 초기화
int arr[3][4] = {
    {1, 2, 3, 4},
    {5, 6, 7, 8},
    {9, 10, 11, 12}
};

// 일괄 초기화
int arr[3][4] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};

int arr[3][4] = {
    {1, 2, 3, 4},
    {5, 6, 7, 8},
    {9, 10, 11, 12}
};

// 행 우선 순회
for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 4; j++) {
        printf("%d ", arr[i][j]);
    }
    printf("\n");
}

// 출력:
// 1 2 3 4
// 5 6 7 8
// 9 10 11 12

typedef struct Node {
    int data;           // 데이터
    struct Node* next;  // 다음 노드 포인터
} Node;

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    
    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        return NULL;
    }
    
    newNode->data = data;
    newNode->next = NULL;
    
    return newNode;
}

void insertFront(Node** head, int data) {
    Node* newNode = createNode(data);
    
    newNode->next = *head;  // 새 노드가 현재 head를 가리킴
    *head = newNode;         // head를 새 노드로 변경
}

// 시간복잡도: O(1) ✔

void insertBack(Node** head, int data) {
    Node* newNode = createNode(data);
    
    // 리스트가 비어있으면
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    
    // 마지막 노드 찾기
    Node* current = *head;
    while (current->next != NULL) {
        current = current->next;
    }
    
    current->next = newNode;
}

// 시간복잡도: O(N) ✘ (마지막까지 순회)

void insertAt(Node** head, int position, int data) {
    Node* newNode = createNode(data);
    
    // 맨 앞 삽입
    if (position == 0) {
        newNode->next = *head;
        *head = newNode;
        return;
    }
    
    // 이전 노드 찾기
    Node* current = *head;
    for (int i = 0; i < position - 1 && current != NULL; i++) {
        current = current->next;
    }
    
    if (current == NULL) {
        printf("Invalid position\n");
        free(newNode);
        return;
    }
    
    newNode->next = current->next;
    current->next = newNode;
}

// 시간복잡도: O(N)

void deleteFront(Node** head) {
    if (*head == NULL) {
        printf("List is empty\n");
        return;
    }
    
    Node* temp = *head;
    *head = (*head)->next;
    free(temp);
}

// 시간복잡도: O(1) ✔

void deleteBack(Node** head) {
    if (*head == NULL) {
        printf("List is empty\n");
        return;
    }
    
    // 노드가 1개만 있을 때
    if ((*head)->next == NULL) {
        free(*head);
        *head = NULL;
        return;
    }
    
    // 마지막 이전 노드 찾기
    Node* current = *head;
    while (current->next->next != NULL) {
        current = current->next;
    }
    
    free(current->next);
    current->next = NULL;
}

// 시간복잡도: O(N) ✘

void deleteValue(Node** head, int value) {
    if (*head == NULL) {
        return;
    }
    
    // 첫 노드가 삭제 대상
    if ((*head)->data == value) {
        Node* temp = *head;
        *head = (*head)->next;
        free(temp);
        return;
    }
    
    // 삭제할 노드의 이전 노드 찾기
    Node* current = *head;
    while (current->next != NULL && current->next->data != value) {
        current = current->next;
    }
    
    // 못 찾음
    if (current->next == NULL) {
        printf("Value not found\n");
        return;
    }
    
    // 삭제
    Node* temp = current->next;
    current->next = current->next->next;
    free(temp);
}

Node* search(Node* head, int key) {
    Node* current = head;
    
    while (current != NULL) {
        if (current->data == key) {
            return current;  // 찾음
        }
        current = current->next;
    }
    
    return NULL;  // 못 찾음
}

// 시간복잡도: O(N)

void display(Node* head) {
    Node* current = head;
    
    printf("List: ");
    while (current != NULL) {
        printf("%d → ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

void deleteAll(Node** head) {
    Node* current = *head;
    Node* next;
    
    while (current != NULL) {
        next = current->next;
        free(current);
        current = next;
    }
    
    *head = NULL;
}

typedef struct DNode {
    int data;
    struct DNode* prev;  // 이전 노드
    struct DNode* next;  // 다음 노드
} DNode;

// 배열: O(1)
int value = arr[100];  // 바로 접근

// 링크드 리스트: O(N)
Node* current = head;
for (int i = 0; i < 100; i++) {
    current = current->next;  // 100번 이동
}
int value = current->data;

int main() {
    int arr[5] = {10, 20, 30, 40, 50};
    int i;
    
    for (i = 0; i < 5; i++) {
        arr[i] = arr[i] + 5;
    }
    
    printf("%d %d", arr[2], arr[4]);
    
    return 0;
}

typedef struct Node {
    int data;
    struct Node* next;
} Node;

int main() {
    Node* head = NULL;
    
    // 노드 생성 및 연결
    Node* n1 = createNode(10);
    Node* n2 = createNode(20);
    Node* n3 = createNode(30);
    
    head = n1;
    n1->next = n2;
    n2->next = n3;
    n3->next = NULL;
    
    // 맨 앞에 5 삽입
    Node* newNode = createNode(5);
    newNode->next = head;
    head = newNode;
    
    // 출력
    printf("%d %d", head->data, head->next->next->data);
    
    return 0;
}

// 배열에서 최댓값 찾기
int findMax(int arr[], int size) {
    int max = arr[0];
    
    for (int i = 1; i < size; i++) {
        if (arr[i] ______ max) {  // 빈칸 1
            max = ______;          // 빈칸 2
        }
    }
    
    return max;
}

if (arr[i] > max) {      // 빈칸 1: >
    max = arr[i];         // 빈칸 2: arr[i]
}

// 맨 뒤에 노드 삽입
void insertBack(Node** head, int data) {
    Node* newNode = createNode(data);
    
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    
    Node* current = *head;
    while (current->______ != NULL) {  // 빈칸 1
        current = current->next;
    }
    
    current->next = ______;             // 빈칸 2
}

while (current->next != NULL) {  // 빈칸 1: next
    current = current->next;
}

current->next = newNode;          // 빈칸 2: newNode

// 배열을 왼쪽으로 1칸 회전
// {10, 20, 30, 40} → {20, 30, 40, 10}

void rotateLeft(int arr[], int size) {
    int temp = arr[0];  // 첫 원소 저장
    
    // 왼쪽으로 이동
    for (int i = 0; i < size - 1; i++) {
        arr[i] = arr[i + 1];
    }
    
    arr[size - 1] = temp;  // 마지막에 저장
}

// 시간복잡도: O(N)

// arr1과 arr2를 result에 합치기
void mergeArrays(int arr1[], int size1, 
                 int arr2[], int size2, 
                 int result[]) {
    int i, j;
    
    // arr1 복사
    for (i = 0; i < size1; i++) {
        result[i] = arr1[i];
    }
    
    // arr2 복사
    for (j = 0; j < size2; j++) {
        result[i + j] = arr2[j];
    }
}

// 시간복잡도: O(N + M)

// 링크드 리스트를 역순으로 변경
Node* reverse(Node* head) {
    Node* prev = NULL;
    Node* current = head;
    Node* next = NULL;
    
    while (current != NULL) {
        next = current->next;    // 다음 노드 저장
        current->next = prev;     // 방향 전환
        prev = current;           // prev 이동
        current = next;           // current 이동
    }
    
    return prev;  // 새로운 head
}

// 시간복잡도: O(N)

// 리스트의 중간 노드 찾기 (Fast & Slow Pointer)
Node* findMiddle(Node* head) {
    if (head == NULL) return NULL;
    
    Node* slow = head;
    Node* fast = head;
    
    // fast는 2칸, slow는 1칸씩 이동
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    
    return slow;  // slow가 중간 지점
}

// 시간복잡도: O(N)

// 리스트에 순환(Cycle)이 있는지 확인
bool hasCycle(Node* head) {
    if (head == NULL) return false;
    
    Node* slow = head;
    Node* fast = head;
    
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        
        // 만나면 순환 있음
        if (slow == fast) {
            return true;
        }
    }
    
    return false;  // 순환 없음
}

// 시간복잡도: O(N)

// 배열에서 합이 target인 두 수의 인덱스 찾기
// arr[] = {2, 7, 11, 15}, target = 9
// 답: [0, 1] (2 + 7 = 9)

void twoSum(int arr[], int size, int target) {
    for (int i = 0; i < size - 1; i++) {
        for (int j = i + 1; j < size; j++) {
            if (arr[i] + arr[j] == target) {
                printf("[%d, %d]\n", i, j);
                return;
            }
        }
    }
    printf("Not found\n");
}

// 시간복잡도: O(N²)

// 배열을 오른쪽으로 k칸 회전
// arr[] = {1, 2, 3, 4, 5}, k = 2
// 결과: {4, 5, 1, 2, 3}

void reverse(int arr[], int start, int end) {
    while (start < end) {
        int temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
        start++;
        end--;
    }
}

void rotateRight(int arr[], int size, int k) {
    k = k % size;  // k가 size보다 클 경우 대비
    
    // 1. 전체 역순
    reverse(arr, 0, size - 1);
    
    // 2. 앞 k개 역순
    reverse(arr, 0, k - 1);
    
    // 3. 나머지 역순
    reverse(arr, k, size - 1);
}

// 시간복잡도: O(N)

// 정렬된 두 리스트를 병합하여 정렬된 하나의 리스트로
// list1: [1] → [3] → [5]
// list2: [2] → [4] → [6]
// 결과: [1] → [2] → [3] → [4] → [5] → [6]

Node* mergeSortedLists(Node* l1, Node* l2) {
    // 더미 노드 생성
    Node dummy;
    Node* tail = &dummy;
    dummy.next = NULL;
    
    while (l1 != NULL && l2 != NULL) {
        if (l1->data <= l2->data) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }
    
    // 남은 노드 연결
    if (l1 != NULL) {
        tail->next = l1;
    } else {
        tail->next = l2;
    }
    
    return dummy.next;
}

// 시간복잡도: O(N + M)

// 뒤에서 N번째 노드 삭제
// 리스트: [1] → [2] → [3] → [4] → [5], N = 2
// 결과: [1] → [2] → [3] → [5] (4 삭제)

Node* removeNthFromEnd(Node* head, int n) {
    Node dummy;
    dummy.next = head;
    
    Node* first = &dummy;
    Node* second = &dummy;
    
    // first를 n+1칸 앞서게 이동
    for (int i = 0; i <= n; i++) {
        if (first == NULL) return head;
        first = first->next;
    }
    
    // 둘 다 이동 (간격 유지)
    while (first != NULL) {
        first = first->next;
        second = second->next;
    }
    
    // 삭제
    Node* temp = second->next;
    second->next = second->next->next;
    free(temp);
    
    return dummy.next;
}

// 시간복잡도: O(N)

int arr[5];  // 인덱스: 0, 1, 2, 3, 4

arr[5] = 10;  // ✘ 범위 초과 (Undefined Behavior)
arr[4] = 10;  // ✔ 올바름

Node* head = NULL;  // ✔ 반드시 초기화

if (head == NULL) {  // NULL 체크 습관화
    // 처리
}

Node* temp = head;
head = head->next;
free(temp);  // ✔ 반드시 해제

void insertFront(Node** head, int data) {
    // *head를 수정하려면 **head 필요
    *head = newNode;
}

// 빈 리스트
if (head == NULL) { ... }

// 노드 1개
if (head->next == NULL) { ... }

// 배열 범위
if (index < 0 || index >= size) { ... }