TIL 2026-03-03

3/3 - 코딩테스트 강의 (이론 복습)

챕터 3-2 배열

학습 목표

• 배열의 개념과 필요성 이해: 같은 타입 데이터를 인덱스로 빠르게 관리.
• C++에서 1차원/2차원 배열 선언 및 초기화 패턴 숙지.
• 배열 원소 접근, 반복문 처리, 기본 활용 예제를 통해 실전 감각 확보.

  1) 배열의 특징

• 연속 메모리 할당: arr[0]~arr[n-1]가 메모리 상에 연속 배치됨.
• 임의 접근(Random Access): arr[i] 형태로 원하는 위치를 즉시 접근 가능.
• 고정 크기 구조(정적 배열): 선언 시 크기 결정, 런타임 동적 확장은 불가.
• 반복문 친화적: for 루프로 전체 원소 순회/가공이 단순하고 빠름.

  2) 배열 선언/초기화 (1차원/2차원)

1차원 배열

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

• 인덱스 범위: 0 ~ 4, 범위 초과 접근은 UB 위험.

  2차원 배열

int board[3][4] = {0};
board[1][2] = 7;

• 행/열 인덱스 모두 경계 체크 필요: 0<=r<R, 0<=c<C

  3) 메모리 구조와 접근 패턴

for (int i = 0; i < 5; i++) {
    cout << "arr[" << i << "] = " << arr[i] 
         << ", 주소: " << &arr[i] << endl;
}

• 주소 간격이 일정하게 증가하면 연속 메모리 특성 확인 가능.
• 이 특성은 순차 처리 시 캐시 효율 향상으로 이어짐.

  5) 코드 요약

A. 연속 메모리 확인

• 의도: 배열 원소가 연속 주소에 놓인다는 사실을 주소 출력으로 확인.

  B. 인덱스 기반 접근

cout << arr[0] << endl;
cout << arr[2] << endl;
arr[1] = 99;

• 의도: 순차 접근 없이도 특정 원소 조회/수정이 O(1)로 가능함을 확인.

  6) 코딩테스트 유의점 (기초 제외, 실전 중심)

• 입력 크기 N이 크고 중간 삽입/삭제가 많으면 배열 단독 사용은 시간초과 위험.
• 배열 문제의 첫 단계는 연산 패턴 분류(조회 중심 vs 구조 변경 중심).
• 오프바이원(off-by-one) 방지를 위해 경계 테스트(N=1, 마지막 인덱스) 필수.
• 2차원 배열은 행/열 순서와 범위 검증을 먼저 고정하고 구현.

  강의 3-3 정렬

학습 목표 요약

• 정렬 알고리즘의 동작 원리와 시간복잡도 비교 역량 강화.
• 정렬을 통해 탐색 효율 개선 및 이진탐색 전제 충족.

  핵심 알고리즘

• 삽입 정렬: key 삽입 방식, 역순 입력에서 최악 O(N^2).
• 병합 정렬: 분할 정복, 안정적 O(N log N).
• 계수 정렬: O(N+K), 값 범위 K가 작을 때 효과적.
• 힙 정렬: max_heapify/build_heap 기반 O(N log N).

  삽입 정렬 코드 포인트

for (int i = 1; i < n; i++) {
  int key = arr[i], j = i - 1;
  while (j >= 0 && arr[j] > key) { arr[j+1] = arr[j]; j--; }
  arr[j+1] = key;
}

정렬 효율성 비교

알고리즘	시간복잡도	유의점
삽입 정렬	평균/최악 O(N^2)	거의 정렬된 입력에서 유리
병합 정렬	O(N log N)	안정적 성능, 대용량 적합
계수 정렬	O(N+K)	범위 K 크면 비효율
힙 정렬	O(N log N)	힙 구성/유지 로직 실수 주의

코테 유의점

• 정렬 기준(오름/내림/커스텀)과 안정성 요구를 먼저 확인.
• 정렬 후 이분탐색 결합 가능 여부를 우선 판단.
• 값 범위가 좁으면 계수 정렬 고려, 아니면 비교 정렬 선택.

  3/3 - C/C++의 8.동적할당 + 9.구조체

8) 동적할당 핵심 정리

• 힙 메모리는 런타임에 크기/수명을 직접 제어할 수 있는 영역이며, 스택의 고정 크기·수명 한계를 보완한다.
• 동적할당 3단계: 할당(malloc/calloc) → 사용 → 해제(free). 해제를 누락하면 메모리 누수 발생.
• 핵심 함수: malloc, calloc, realloc, free / 보조 함수: memset, memcpy, memcmp.
• 중요 습관: malloc 직후 free 위치를 먼저 설계하고, 원본 시작 주소를 잃지 않게 사본 포인터로 연산한다.
• 힙은 유연하지만 할당/해제 비용이 스택보다 크고, 소유권 관리 실수(이중해제/누수) 위험이 있다.

  int* nums = (int*)malloc(n * sizeof(int));
  if (!nums) return -1;
  /* use nums */
  free(nums);
  nums = NULL;
  

9) 구조체 핵심 정리

• 구조체는 여러 자료형을 묶어 사용자 정의 자료형을 만든다(도메인 모델링의 시작점).
• 멤버 접근: 변수는 . 연산자, 구조체 포인터는 -> 연산자 사용.
• typedef를 사용하면 struct 키워드 반복을 줄이고 가독성을 높일 수 있다.
• 구조체는 함수 인자/반환형/배열 원소로 활용 가능하여 다중 값 전달에 유리하다.
• 포인터 멤버를 가진 구조체는 얕은 복사/깊은 복사 이슈를 반드시 구분해야 한다. ```c typedef struct Date { int Year, Month, Day; } Date_t;

Date_t d = {2026, 3, 3}; Date_t* p = &d; printf(“%d\n”, p->Year); ```

코딩테스트 관점 체크포인트

주제	자주 나오는 실수	실전 대응
동적할당	free 누락, 시작 주소 유실, 이중 해제	소유권 1개 원칙 + 해제 후 NULL
구조체	값/참조 전달 혼동, 포인터 멤버 얕은 복사	복사 정책 명시(깊은복사 필요 시 직접 구현)
구조체+함수	큰 구조체 값 복사 비용	읽기 전용은 const 포인터 인자 우선