Archive

02 Array & Structures

10 min read

1. 배열(C)

1.1. 배열의 개념 및 1차원 배열

  • 배열(Array)

    • 같은 자료형의 변수를 여러 개 묶어서 사용하는 자료구조
    • <인덱스, 요소>의 쌍으로 구성

  • 선언 및 메모리

    • 선언: 자료형 배열이름[크기]; (예: int A[6];)
    • 인덱스는 0부터 시작
    • 배열의 이름(A)은 첫 번째 요소(A[0])의 메모리 주소(base address)를 가리킨다.
    • 주소 계산: base + 인덱스 * sizeof(자료형)

  • 크기 확인

    • sizeof() 연산자를 통해 배열 전체 크기와 요소의 크기를 확인할 수 있다.

  • 초기화

    • 선언과 동시에 초기화 가능 (int A[6] = {1, 2, ...};)
    • 값을 적게 넣으면 나머지는 0으로 채워진다.

1.2. 2차원 배열

  • 구조: 행(Row)과 열(Col)로 구성된 격자 형태의 데이터
  • 메모리 저장: 논리적으로는 격자 형태이나, 물리적 메모리에는 1차원(선형)으로 순서대로 저장
  • 선언: int A[2][3] = {{1, 2, 3}, {4, 5, 6}};

1.3. 문자열(String)

  • 특징: 문자의 배열(char array)로 표현

  • NULL 문자

    • 문자열의 끝을 알리기 위해 항상 마지막에 \0 (NULL)이 포함
    • 따라서 “Hello”를 저장하려면 최소 6칸의 배열이 필요

  • 함수: strcpy (복사), strlen (길이 계산) 등을 사용

1.4. 함수와 배열

  • 전달 방식

    • 배열을 함수의 매개변수로 넘길 때, 배열의 이름(주소값)이 전달
    • (Call-by-Reference와 유사한 효과)

  • 주의점

    • 배열의 크기 정보는 함께 전달되지 않으므로,
    • 배열의 크기(길이)를 별도의 매개변수로 함께 넘겨주어야 한다.

2. 배열(자료구조)

2.1. Time Complexity

ArraySearchBestAverageWorst
UnsortedLinear Search
SortedBinary Search
SortedInterpolation Search

  • Binary Search의 Best Case는 탐색의 관점에서 , 탐색 차수의 관점에서

  • Interpolation Search는 직선 형태의 균등 분포에서 , 불균등 분포에서

  • Insert/Delete:

2.2. Features

  • 연속된 메모리 공간에 저장됨

    • → Random Access(임의 접근): 빠른 인덱스 접근 가능
    • → 메모리 접근 패턴이 일정해 캐시 친화적

  • (동적 배열 제외) 크기 고정

    • → 메모리 낭비 가능성
    • → 삽입/삭제 시 데이터 이동 발생 (삽입/삭제가 빈번하면 부적합)

2.3. Applications

  • 기본적인 자료구조 구현
  • 다차원 데이터 처리
  • 인덱스 접근을 활용하는 비디오 프레임 버퍼
  • 자주 변경되지 않는 정적 데이터 저장

3. 배열의 탐색

  • 탐색: 테이블(레코드의 집합)에서 원하는 탐색키를 가진 레코드를 찾는 작업

  • 테이블 구성 방법: 배열, BST, 해시 테이블 등

    • 테이블 구조에 따라 탐색·삽입·삭제 성능이 달라짐

  • 순차 탐색(선형 탐색): 일렬로 늘어선 레코드를 앞에서부터 순차적으로 비교하며 탐색

    • 배열이나 연결 리스트로 구성

  • 동작: 배열의 left부터 right까지 순서대로 탐색키와 비교

    • 같으면 성공(인덱스 반환), 끝까지 없으면 실패(-1 반환)
    • 시간 복잡도: 최선 O(1), 평균/최악 O(n)
    • 분석: 비효율적이지만, 비정렬 테이블이라면 별다른 대안은 없음
for (int i = left; i <= right; i++)
	if (A[i] == key) {
		// if (i != left) { i -= int; swap(A[i], A[i+1])} // 교환 전략
		return i;
	]
return -1;
  • 개선 - 자기 구성 순차 탐색: 자주 탐색되는 레코드를 테이블의 앞쪽으로 옮겨 탐색 효율 증가
    • move to front: 찾은 레코드를 맨 앞으로 이동
    • transpose: 찾은 레코드를 한 칸씩 앞쪽으로 교환
    • count-based: 탐색 횟수 집계 후 빈도 순으로 재배치
int binary_search(int A[]. int key, int low, int high) {
	while (low <= high) {
		int mid = (low + high) / 2;
		if (key == A[mid]) return mid; // 탐색키와 레코드가 같으면 반환
		else if (key < A[mid]) high = mid - 1; // 레코드가 크면 왼쪽으로
		else low = mid + 1; // 레코드가 작으면 오른쪽으로
	}
	return -1;
}

  • 이진 탐색: 정렬된 배열에서 가운데 요소와 비교하여 탐색 범위를 절반씩 줄여 나가는 방법

    • 구현: 재귀(recursive) 또는 반복(iterative) 구조

  • 분석

    • 삽입/삭제: O(n), 탐색: O(log n) (매 단계마다 범위를 절반으로 축소)
    • 삽입/삭제가 빈번하면 AVL 트리
    • 탐색 연산만 주로 처리하면 효율적

  • 보간 탐색(Interpolation Search)
    • 탐색키가 존재할 위치를 예측하여 탐색하는 방법
    • 래코드의 키값과 탐색키의 비율을 고려해 탐색 위치 계산

4. 구조체

4.1. 구조체의 개념 및 정의

  • 구조체(Structures)

    • 서로 다른 자료형의 데이터를 하나로 묶은 모임
    • (배열은 ‘같은’ 자료형의 모임)

  • 선언

    • struct 키워드 사용
    • typedef를 사용하면 매번 struct를 쓰지 않고 새로운 자료형처럼 사용할 수 있어 편리

  • 접근

    • 멤버 접근 연산자 . (점)을 사용 (예: student.id)

4.2. 구조체의 연산

  • 대입

    • 대입 연산자(=)를 통해 구조체 변수 간 복사는 가능

  • 비교

    • 비교 연산자(==, !=)는 사용 불가
    • 비교하려면 내부 멤버들을 일일이 비교하는 함수를 직접 만들어야 한다.

4.3. 구조체 응용

  • 중첩 구조체: 구조체 안에 다른 구조체를 멤버로 포함할 수 있다.
  • 구조체 배열: 구조체를 요소로 가지는 배열을 만들 수 있다. (예: Friend list[45];)

4.4. 구조체와 함수

  • 전달 방식: 기본적으로 Call-by-Value(값에 의한 호출)
    • 함수에 구조체를 넘겨서 내용을 변경하더라도, 원본에는 영향을 주지 않는다. (복사본이 전달됨)
    • 원본을 수정하려면 포인터를 사용해야 한다.

Lab. 희소 행렬 표현

  • 희소 행렬(Sparse Matrix): 대부분의 항이 0인 행렬
  • 효율적 표현: 2차원 배열 전체를 저장하는 대신, 0이 아닌 요소만 <행, 열, 값>의 구조체 배열로 저장하여 메모리를 절약

5. 배열과 구조체의 응용 : 다항식 프로그램

5.1. 다항식의 표현 방법

다항식 을 컴퓨터로 표현하는 두 가지 방법을 비교

  • 방법 1: 모든 계수 저장 (배열)

    • 배열의 **인덱스를 차수(지수)**로, 값을 계수로 사용
    • 장점: 구현이 간단함
    • 단점: 처럼 차수는 높은데 항이 적은 경우, 0인 계수들을 위해 많은 메모리가 낭비됨

  • 방법 2: 0이 아닌 항만 저장 (구조체 배열)

    • 구조체에 (계수, 차수) 쌍을 저장하고, 이 구조체들의 배열로 다항식을 표현
    • 장점: 희소 다항식의 경우 메모리 공간을 훨씬 절약할 수 있음
    • 단점: 덧셈 등의 연산 구현이 방법 1보다 조금 더 복잡함

5.2. 다항식 덧셈 알고리즘

  • 두 다항식 A와 B의 최고차항부터 비교하며 덧셈을 수행하여 새로운 다항식 C를 만든다.
    1. A의 차수 > B의 차수: A의 항을 C에 추가
    2. A의 차수 < B의 차수: B의 항을 C에 추가
    3. A의 차수 == B의 차수: 계수를 더해서 C에 추가 (단, 계수의 합이 0이면 추가하지 않음)

그래프 뷰