[ Section 1. 개요 ]

1. 자료구조와 알고리즘이란?

• 프로그램은 자료구조와 알고리즘으로 이루어진다.

• 프로그램 작성 시 적절한 자료구조를 선택하여 데이터를 저장하고, 자료구조에 맞는 알고리즘을 사용해 데이터를 가공하여 원하는 결과를 도출한다.

1) 자료구조

자료구조란?

• 데이터가 어떤 구조로 저장되고 어떻게 사용되는지를 나타낸다.

• 단순한 자료구조 : 변수, 배열

• 자료구조에 따라 처리방법이 달라지며 데이터의 변경시 코드가 더 단순해질 수도 있다.

2) 알고리즘

알고리즘이란?

• 어떤 문제를 해결하기 위한 확실한 방법

• 데이터가 어떤 자료구조를 하고 있는지에 따라 알고리즘이 달라진다.

• 알고리즘은 자료구조에 많은 영향을 받는다.

• 한가지 자료구조에 대해서도 여러가지 알고리즘이 있을 수 있다.

2. 시간복잡도

1) 시간복잡도

• 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간의 효율성을 나타내는 척도를 말한다.

• 알고리즘의 성능을 평가할 때 처리 속도를 중요한 기준으로 사용하지만, 컴퓨터의 사양에 따라 실제 속도는 달라질 수 있다.

• 따라서, 실제 시간을 측정하는 것보다 알고리즘에서 성능에 영향을 미치는 핵심 연산을 기반으로 실행 시간을 예측하는 방식으로 시간복잡도를 평가한다.

2) 시간복잡도 평가시 점근 표기법(Asymptotic Notation)의 사용

• 3가지 종류의 표기법이 사용된다.

  • Big-Ω, Big-O, Big-Θ

• 표기법중 Big-O와 Big-Θ를 주로 사용하며, 가장 많이 사용되는것은 Big-O 이다.

1) 빅 오메가 표기법 (Big-Ω, Big-Omega Notation, Ω)

• 최선의 경우를 나타내는 표기법

2) 빅 오 표기법 (Big-O, Big-O Notation, O)

• 최악의 경우를 나타내는 표기법

3) 빅 세타 표기법 (Big-Θ, Big-Theta Notation, Θ)

• 평균적인 경우 또는 정확한 시간 복잡도를 나타낸다.

3) 시간복잡도 분류

(1) 선형시간 알고리즘 O(n)

• 입력량이 많아지는 경우 계산량이 증가하므로 O(n)의 알고리즘은 선형시간 알고리즘이라고 부른다.

(2) 상수시간 알고리즘 O(1)

• 입력량의 크기에 상관없이 상수의 시간이 걸린다는 의미로 계산량이 꼭 한 번일 필요는 없다.

4) 빅 오(Big-O) 표기법의 특징

• 빅 오(Big-O) 표기법은 입력의 크기에 따라 알고리즘의 계산량이 어떻게 변하는지를 나타내는 척도를 제공한다.

• 빅 오(Big-O) 표기법에서는 성능에 가장 큰 영향을 미치는 항만 표기한다.

  • ex) n**²** + 2n + 100 이라는 성능을 가진 알고리즘의 빅 오 표기법은 O(n**²**) 이다.

• 빅 오(Big-O) 표기법에서 상수는 성능에 큰 영향을 미치지 않으므로 제거한다.

  • ex) 3n**²** + 100n 성능의 알고리즘을 빅 오 표기법으로 나타내면 O(n**²**) 이다.

  ---

  [ Section 2. 자료구조 ]

  1. 배열

  (1) 배열의 특징

  • 일반적으로 프로그래밍 언어에서 배열을 선언할 때 크기를 지정해야 하며, 운영체제는 크기에 맞는 연속된 메모리 공간을 할당한다.

  • 운영체제는 배열의 시작 주소만 기억하며, 인덱스를 이용해 O(1)의 성능으로 데이터를 참조할 수 있다.

  • 배열을 읽기/쓰기 와 같은 참조에서 빠른 성능을 보인다.

  • 배열의 크기를 확장할 수 없기 때문에 데이터 추가/제거 시 성능 저하가 발생한다.

    • 배열을 확장하려면 새로운 메모리 공간을 할당하고 기존 데이터를 복사해야 함.

  • 배열을 미리 크게 선언하거나 사용하지 않는 공간이 있을 경우 메모리 공간이 낭비될 수 있다.

  (2) 배열의 장단점

  • 장점 : 인덱스 접근에서 빠른 성능(O(1))을 제공한다.

  • 단점 : 크기를 미리 정해야 하며, 삽입/삭제가 비효율적이고, 메모리 낭비 가능성이 있다.

2. 연결 리스트 (Linked List)

연결 리스트 (Linked List)

• 연결 리스트는 노드(Node)라는 것을 만들어서 수행한다.

• 첫 노드의 주소만 알고 있으면 다른 모든 노드에 접근할 수 있다.

(1) 장점

• 배열처럼 초기 크기를 알아야 하는 단점이 없다

  • 빈 메모리 공간 아무 곳에 데이터를 생성하고 연결만 해주면 됨

• 데이터 삽입시 다음 가리키는 노드만 바꿔주면 되기 때문에 배열보다 작업이 간단함

(2) 단점

• 데이터를 찾을때 연속된 노드를 순회하여 데이터를 참조해야 함

  • 연결 리스트에서 데이터 참조는 O(n)의 성능

3. 스택 (Stack)

• 스택은 마지막에 삽입된 데이터가 먼저 제거(LIFO, Last In First Out)되는 구조를 가진다.

• 데이터의 삽입과 제거는 항상 맨 앞(head/top)에서만 이루어진다.

• 스택은 LIFO 규칙만 충족하면 어떤 자료구조로도 구현할 수 있다.

FILO (First In Last Out)

• 먼저 들어간 데이터가 나중에 나오는 규칙

4. 큐 (Queue)

• 먼저 들어온 데이터가 먼저 나가는(FIFO, First In First Out) 구조를 가진다.

• 데이터의 삽입은 tail(rear)에서, 제거는 head(front)에서 이루어진다.

FIFO (First In First Out)

• 먼저 들어간 데이터가 먼저 나오는 규칙

• 운영체제에서 FIFO 스케줄링이 사용된다.

  • 운영체제가 프로세스의 작업 요청을 들어온 순서대로 큐에 넣고 CPU가 순서대로 꺼내어 처리한다.

5. 덱 (Deq)

• 데이터의 삽입과 제거를 head와 tail 두 군데서 자유롭게 할 수 있는 자료구조

• 덱을 이용하여 스택과 큐를 전부 구현할 수도 있다.

• 덱 (Deq)의 추상 자료형

  • printAll -

    모든 데이터 출력

  • addFirst -

    head에 데이터 삽입하는 함수

     

  • removeFirst -

    head에서 데이터 제거하는 함수

     

  • addLast -

    tail에 데이터 삽입하는 함수

     

  • removeLast -

    tail에서 데이터 제거하는 함수

     

  • isEmpty -

    리스트가 비었는지를 알려주는 함수

6. 해시테이블 (Hash Table)

• Key를 Hash 함수를 통해 특정 위치에 매핑하여 데이터를 저장하는 자료구조이다.

  • 해시와 테이블이 결합된 형태로, 해시 함수를 사용하여 테이블의 인덱스를 생성한다.

• 프로그래밍 언어에 따라 다양한 이름으로 불린다.

  • 예 : 해시(Hash), 맵(Map), 해시맵(HashMap), 딕셔너리(Dictionary)

• 데이터 읽기, 삽입, 수정, 삭제를 평균적으로 O(1)의 성능으로 처리할 수 있다.

해시 테이블에서의 충돌 (Collision)

여러 Key가 동일한 Hash 값으로 매핑될 경우 충돌이 발생한다.

해시 테이블의 장단점

(1) 장점

• 빠른 데이터 읽기, 삽입, 삭제 성능을 제공한다.

(2) 단점

• 공간의 효율성이 떨어질 수 잇다.

  • 미리 할당해야 하는 메모리 공간이 많다.

  • 해시 함수에 따라 메모리 낭비가 발생할 수 있다.

• 해시 함수의 품질에 따라 성능에 큰 영향을 미치므로 좋은 해시 함수의 구현이 필수적이다.

7. 셋 (Set)

• 데이터의 중복을 허용하지 않는 자료구조

  • 중복되지 않는 값 저장시 유용함

• 해시 테이블을 이용하기 때문에 해시 셋(Hash Set) 이라고도 불리며 쉽게 구현 가능

• 해시 테이블의 value 값은 사용하지 않고 key 만 사용해서 구현한다.

  • key 가 key 임과 동시에 데이터로 사용됨

셋 (Set)의 추상자료형

• add(data) - 셋에 데이터를 추가하는 기능

  • 매개변수로 전달되는 data는 key이자 데이터

• isContain(data) - 셋에 해당 데이터가 있는지 체크하는 기능

  • 해당 데이터가 셋에 있다면 true, 없다면 false를 리턴한다.

• remove(data) - 셋에 데이터를 제거하는 기능

  • 제거할 data를 매개변수로 전달하며 해시 테이블에서 해당 key를 제거

• clear() - 셋을 비우는 기능

• isEmpty() - 셋이 비었는지 검사하는 기능

• printAll() - 테스트를 위해 셋의 모든 데이터를 출력하는 기능