자료구조 1주차 - 자료구조와 시간복잡도 총정리

1. 자료구조란?

 (1) 자료의 저장과 표현

 컴퓨터에서 자료는 정수, 실수, 문자, 문자열 등의 형태로 저장됩니다. 아래는 각 자료형의 예입니다.

 

분류 - 예시 - 설명

정수	0, 1000, -100	소수점 없는 수
실수	3.14, 0.01	소수점 있는 수
문자	'A', '1', '가'	한 글자 문자, '로 표현
문자열	"Hello", "가나다"	여러 문자의 조합, "로 표현

 

 (2) 선형 자료구조와 비선형 자료구조

 

- 선형 자료구조

• 리스트: 자유로운 데이터 삽입/삭제 가능
• 스택: 마지막에 넣은 것부터 꺼냄 (LIFO)
• 큐: 먼저 넣은 것부터 꺼냄 (FIFO)
• 덱: 양쪽에서 삽입/삭제 가능

- 비선형 자료구조

• 트리: 계층 구조 (ex. 회사 조직도)
• 그래프: 복잡한 관계 구조 (ex. SNS 친구 관계)

 2. 알고리즘이란?

 (1) 정의

알고리즘은 컴퓨터로 문제를 해결하기 위한 절차를 의미합니다. 데이터 → 처리 → 결과로 이어지는 구조죠.

예) 시험 성적 중 가장 높은 점수를 찾는 프로그램

 (2) 알고리즘의 조건

조건 - 설명

입력	최소 0개 이상의 입력 존재
출력	최소 1개 이상의 출력 존재
명확성	모호하지 않고 정확한 명령어 사용
유한성	제한된 단계 후 종료해야 함
유효성	각 명령어는 실행 가능한 것이어야 함

 

 (3) 알고리즘 표현 방법

1. 자연어: 누구나 쉽게 이해 가능하지만 명확하지 않음
2. 흐름도: 순서도를 통한 시각적 표현
3. 유사코드(Pseudo Code): 코드와 일반언어의 중간
4. 프로그래밍 언어: 실제 코드로 작성

대부분은 유사코드로 알고리즘을 설계하고, 이후 실제 코드로 구현합니다.

 

 3. 추상 자료형 (ADT: Abstract Data Type)

 ADT는 데이터와 그에 관련된 연산을 정의한 것입니다.
 구현 방법은 숨기고 '무엇을 할 수 있는가'에만 집중합니다.

 (1) Bag ADT 예시

• 중복 허용, 순서 없음
• 연산:
  • Bag() → 빈 가방 생성
  • insert(e) → e 추가
  • remove(e) → e 제거
  • contains(e) → e 포함 여부 반환
  • count() → 항목 개수 반환

 (2) Bag ADT의 파이썬 구현 예시

def insert(bag, e):
    bag.append(e)

def remove(bag, e):
    bag.remove(e)

def contains(bag, e):
    return e in bag

def count(bag):
    return len(bag)

 

 4. 알고리즘의 시간복잡도

 (1) 복잡도 분석

1. 실행시간 측정
   • 실제 코드 실행
   • 현실적으로 정확하지 않음
2. 복잡도 분석 (이론)
   • 연산 횟수로 시간 추정
   • 입력 크기 n에 대한 함수 T(n)으로 표현

 

(2) n²을 구하는 세 가지 알고리즘 비교

알고리즘	연산횟수 분석	시간복잡도
A	2	O(1)
B	2n + 1	O(n)
C	2n² + n + 1	O(n²)

 

 5. 빅오(Big-O) 표기법

• 함수의 성장을 차수(가장 큰 항) 기준으로 비교

f(n) = 5	O(1)
f(n) = 3n + 1	O(n)
f(n) = 6n² + 100	O(n²)
f(n) = 7·2ⁿ + n²	O(2ⁿ)

 6. 그 외 시간 복잡도 개념

O(g(n))	최악의 경우 상한
Ω(g(n))	최선의 경우 하한
Θ(g(n))	평균적으로 상하한이 일치

 

실무에서는 최악의 경우 (Worst Case)를 중심으로 분석합니다.

 

 7. 순환(재귀)과 반복

 예) 팩토리얼

방식	코드 형태	시간복잡도
재귀	n! = n × (n-1)!	O(n)
반복	for i in range()	O(n)

재귀는 자연스럽지만, 함수 호출 오버헤드가 있으므로 반복이 더 빠를 수도 있어요.

 

마무리 요약

 

자료구조	데이터를 효율적으로 저장하고 사용하는 방식
알고리즘	문제를 해결하는 절차, 명확하고 유한해야 함
ADT	구현은 숨기고 기능만 정의한 구조
시간복잡도	알고리즘의 효율성을 수치적으로 표현 (O(n), O(n²) 등)
재귀 vs 반복	대부분의 재귀는 반복으로 변경 가능, 반복이 빠름

 

고생하셨습니다. 2주차에서 뵙겠습니다.