자료구조

---

재귀

• 함수가 자기 자신을 호출 하는 것.
• 문제에 따라 전체를 같은 유형의 하위 작업으로 분할 하여 작은 문제부터 해결하는것이 효율적이기 때문에 사용.

---

자료구조

• 데이터를 조직하는 방법

• 자료 구조를 어떻게 조직하냐에 따라 프로그램은 더 빠르거나 느리게 실행될 수 있기 때문에 자료구조가 중요함.

• 선형 구조 : 리스트, 스택, 큐

• 비선형 구조 : 그래프, 트리

• 연산 : 자료 구조 내에서 동작함.

  • 읽기 : 특정 위치를 찾음.
  • 검색 : 특정 값을 찾음.
  • 삽입 : 새로운 값 추가.
  • 삭제 : 특정 값 삭제.

• 자료구조 구현 방법

  • 순차 자료구조
    • 구현할 자료들을 논리적인 순서대로 메모리에 연속하여 저장
  • 연결 자료구조
    • 노드라는 여러 개의 메모리 청크에 데이터 저장, 연결하여 구현.

• 알고리즘

  • 알고리즘의 분석

    • 자원을 분석하는 것, 자원을 적게 사용할수록 효율적

    • 알고리즘의 실행 시간은 하드웨어, 소프트웨어의 환경에 따라 달라, 객관적인 지표가 필요함.

    • 이것이 시간 복잡도이다.

      • 시간 복잡도

        • 알고리즘을 수행하는 데 필요한 연산이 몇 번 실행 되는지.
        • 실행 시간의 성장률 : 입력값이 커질수록 차이가 커짐.

      • 점근적 표기법

        • Big - O 표기법
          • 점근적 상한선 제공
          • 어떠한 카테고리가 다른 카테고리보다 빠르더라도 항상 빠른 것은 아님.
          • 한 알고리즘이 다른 알고리즘보다 실제로 빠르다고 하더라도 같은 방식으로 표현될 수 있다. (정확한 값은 시간 복잡도 함수를 사용해야함.)

      • 공간 복잡도

        • 알고리즘을 수행하는 데 메모리가 얼마나 필요한 지.
        • 보통 시간 복잡도와 공간 복잡도는 반비례.
        • 대개 시간의 가치가 공간의 가치보다 높음.

---

STL(Standard Template Library)

• 프로그래머의 편의성을 위하여 언어에서 제공하는 자료구조와 알고리즘

• 표준 템플릿 라이브러리

  • 컨테이너 라이브러리 : 임의 타입의 객체를 보관.

    • 컨테이너 : 자료구조의 구현체.

  • 반복자 라이브러리 : 컨테이너에 보관된 원소에 접근.

    • 반복자 : 컨테이너의 요소에 접근할 수 있는 포인터.
    • 반복자 패턴 : 반복자를 추가함으로써, 각 요소에 추상적 접근이 가능하게 되어 필요한 구현코드의 개수를 줄일 수 있다.

  • 알고리즘 라이브러리 : 반복자를 가지고 일련의 작업을 수행.

---

리스트

• 순서를 갖고 있는 자료구조
  • 순차 자료구조 : 선형 리스트
  • 연결 자료구조 : 단일 연결 리스트, 원형 연결 리스트, 이중 연결 리스트

선형 리스트

• 순서 리스트라고 하며, 임의 접근이 가능.

• 연산

  • 읽기 : 임의 접근이 가능하여, O(1)의 시간이 걸림.
    

  • 검색 : 원소를 각각 비교해가야 하므로, O(n) 의 시간이 소요된다. 정렬되어 있다면 이진 검색을 사용 가능하며, O(log n) 의 시간이 소요된다.

  • 삽입 : 삽입 위치에 따라 시간이 달라짐. 맨끝의 경우 O(1), 처음이나 중간에서는 모든 데이터를 이동해야하므로 O(n) 의 시간이 소요.

  • 삭제 : 삽입과 동일.

연결 리스트

• 연결 자료구조

• 선형 리스트와 연결 리스트는 모든 자료구조의 토대가 된다.

• 연산

  • 읽기 : O(n) , 처음과 끝이라면 구현에 따라 O(1)이 될 수 있음.

  • 검색 : O(n) , 선형 리스트와 다르게 이진 검색을 사용할 수 없다.

  • 삽입 : 검색해야 하므로 O(n), 정확한 위치를 알고있다면 O(1).

  • 삭제 : 검색해야 하므로 O(n), 정확한 위치를 알고 있다면 O(1).

단일 연결 리스트

• std::forward list
• 선형 리스트와 다르게 임의 접근이 불가능
  • 임의접근 : 원하는 주소값에 접근 하는 것. 주소 값을 알고 있어야 한다.
  • 임의 접근이 가능 하다는 것 -> 주소값이 연속적이어서 주소연산을 해서 위치를 알 수 있다.
  • 메모리가 연속적이지 않게 할당됨.

이중 연결 리스트

• 이전 원소로도 이동할 수 있다.

• 원형 연결 리스트(Circular Linked List)

  • std::list
  • 마지막 원소와 첫 번째 원소를 연결한 형태다.
  • std::list가 이중 원형 연결 리스트에 해당한다.

스택(Stack)

• 리스트의 일종, 한 쪽 끝에서만 연산이 이루어짐.

• 괄호가 올바른지 검사, 후위 표기식, DFS 등에 사용됨.

  • LIFO (Last-In First-Out) : 후입선출, 가장 나중에 들어온 것이 가장 먼저 나감.
  • 위(Top) : 스택의 끝
  • 밑(Bottom) : 스택의 시작

• 컨테이너 어댑터