요즘 저것들 때문에 머리가 터질 거 같다. 용어를 완전히 이해하고 싶은데 다 그게 그거 같고, 검색만 하루 종일 한 결과 조금은 정리가 되어 기록해두려고 한다.

🗃️자료구조

🔹정의

데이터를 저장하고, 관리하고, 처리하기 위한 방법과 형식

EX : 데이터를 넣고, 꺼내고, 정렬하고, 검색하고, 삭제하고 등

목표 : 효율적으로 데이터를 사용하기 위해.

자료구조의 분류

✅ 1. 기본 자료구조 (선형 구조)

이름	구조 설명	특징
배열 (Array)	고정된 크기의 연속된 메모리 공간	인덱스로 접근 빠름, 크기 고정
연결 리스트 (Linked List)	노드들이 포인터로 연결	삽입/삭제 쉬움, 탐색 느림
스택 (Stack)	LIFO (후입선출)	push, pop
큐 (Queue)	FIFO (선입선출)	enqueue, dequeue
덱 (Deque)	양쪽에서 삽입/삭제 가능	양방향 큐
문자열 (String)	문자들의 배열	탐색, 처리 등

✅ 2. 비선형 자료구조

이름	구조 설명	특징
트리 (Tree)	계층적 구조 (부모-자식)	이진트리, 힙, 이진탐색트리 등
그래프 (Graph)	정점과 간선으로 구성	탐색 알고리즘과 함께 사용
힙 (Heap)	완전이진트리 + 우선순위 구조	우선순위 큐 구현에 사용

왜 배워야 할까?

문제마다 "적절한 자료구조"를 선택하면 코드가 간단하고 빠름

자료구조에 따라 🔹시간복잡도/공간복잡도가 다름
(예: 배열 vs 해시맵으로 탐색 시간 차이 큼)

코딩 테스트 문제는 대부분 "자료구조 + 알고리즘" 조합 문제

🔹시간 복잡도(Time Complexity)

• 알고리즘이 문제를 해결하는 데 걸리는 시간의 증가량을 입력 크기(n)에 따라 분석한 것.
  ➡️알고리즘이 얼마나 빨리 실행되는지를 나타냄
  
  
• 더 빠른 알고리즘 선택, 시간 초과 방지
  ➡️빠른 해결

🔹공간 복잡도(Space Complexity)

• 알고리즘이 문제를 해결하는 데 사용하는 메모리 공간의 양을 입력 크기(n)에 따라 분석한 것.
  ➡️ 알고리즘이 얼마나 많은 메모리를 사용하는지를 나타냄
  
  
• 메모리 초과 방지, 공간 효율적인 방식 선택
  ➡️메모리 최적화

➡️뭔가 복잡하지만 정리하자면 시간 복잡도와 공간 복잡도는 알고리즘의 효율성을 판단하는 기준(척도)이다.
더 나은 선택을 위해 필요!

💡 예를 들어:

두 알고리즘이 정답은 같아도
→ 하나는 O(n²) (느림), 하나는 O(n log n) (빠름)
→ 입력이 클수록 차이는 점점 커짐

그래서 우리는 알고리즘을 짤 때 항상 "시간 복잡도 vs 공간 복잡도"를 따져보고, 어떤 방식이 더 효율적인지 판단하는 것

코딩테스트에서 입력 제한이 있는 이유는 시간 복잡도랑 공간 복잡도를 선택할 때 힌트를 주기 위한 것임!

이거는 나중에 더 다뤄보도록 하자.

---

🧠알고리즘

🔹정의

알고리즘이란 컴퓨터가 따라 할 수 있도록 문제를 해결하는 절차나 방법.
이를 자세히 설명하면 컴퓨터를 활용한 문제 해결 과정에서 주어진 문제를 해결하는 일련의 방법 또는 절차이며, 문제해결 방법을 순서대로, 절차대로 나열한 것이라고 볼 수 있다.

왜 배워야 할까?

좋은 프로그램 = 프로그램을 수행하기 위해 꼭 필요한 자료구조 + 알고리즘

알고리즘과 자료구조의 관계

• 문제 해결법 = 알고리즘 (레시피)
• 재료와 도구 = 자료구조, STL, 표준 라이브러리
• 요리사 = 당신 (프로그래머!) 👩‍🍳👨‍🍳

• 자료구조는 데이터를 저장하고 조직하는 방법
• 알고리즘은 문제를 해결하는 절차 (이때 자료구조를 이용 할 수 있음)

예시 - 피자🍕

• 피자는 화덕 혹은 오븐과 같은 요리 도구를 필요로 하지만 이 피자를 만드는 방법은 언제나 비슷하다.
  • 재료를 씻어서 준비한다.
  • 반죽을 해서 소분을 한다.
  • 피자 주문이 들어오면 해당하는 양만큼의 반죽을 떼어내서 쓱쓱 밀어낸다.
  • 쓱쓱 밀어낸 반죽 위에 토핑을 올린다.
  • 오븐에 구워내고 슬라이스한다.
• 위와 같은 단계들을 묶어서 알고리즘이라 할 수 있다.
• 즉, 무언가 주어진 문제를 해결하는 과정 자체를 묶어서 알고리즘이라고 생각하면 된다.

---

🛠️STL(Standard Template Library)

C++ 표준 라이브러리의 한 부분으로, 자료구조(컨테이너), 알고리즘, 반복자(iterator)를 템플릿 기반으로 구현해 놓은 라이브러리이다.

쉽게 말해, “다양한 자료구조와 알고리즘을 ‘🔹템플릿’으로 미리 만들어 놓아 C++ 코드에서 쉽게 재사용할 수 있게 한 것”. => C++ 에서만 사용함.

예) 벡터(vector), 리스트(list), 스택(stack), 큐(queue) 같은 컨테이너와,
정렬, 탐색 같은 알고리즘이 STL에 포함돼 있다.

🔹템플릿(Template) 이란?

자료형(type)을 나중에 지정할 수 있게 미리 틀을 만들어두는 것.

➡️이해가 잘 안 된다면!

“템플릿은 일종의 ‘반복해서 쓰는 틀’ 같은 거.”
예를 들어, 당신이 친구들 이름을 넣는 상자를 만들고 싶다고 생각해보자

• 만약 상자를 만들 때, “이 상자는 이름(문자열)만 넣을 수 있어!”라고 정하면, 숫자나 다른 건 넣을 수 없음!
• 그런데 템플릿을 사용하면, “이 상자는 어떤 타입이든 넣을 수 있어!”라고 만들 수 있다.
• 즉, 상자를 만드는 설계도를 ‘템플릿’으로 작성해 두고, 나중에 상자를 만들 때 타입(문자열, 숫자 등)을 지정하는 것.

🖥️예시 코드

template <typename T> // T라는 타입을 나중에 정한다는 의미
class Box {
    T content;  // 내용물은 타입 T로 만든다
public:
    void put(const T& item) { content = item; }
    T get() { return content; }
};

Box<int> intBox; → 정수형 상자
Box<string> strBox;  → 문자열형 상자<br>

각각 따로 만들 필요 없이 하나의 코드로 다양한 타입 상자를 만들 수 있다.

이렇게 STL을 템플릿 기반으로 구현해 두었기 때문에 std::vector<int>
, std::vector<string> 등 다양한 타입에 사용할 수 있다.

---

STL의 주요 구성 요소 3가지

🔹컨테이너 (Containers)

데이터를 저장하는 역할을 하는 자료구조들의 집합

예 : vector, list, deque, stack, queue, set, map 등

🔹알고리즘 (Algorithms)

컨테이너에 저장된 데이터를 처리하는 다양한 함수들

예 : sort(), find(), accumulate(), binary_search() 등

🔹반복자 (Iterators)

컨테이너의 원소를 순회할 수 있도록 도와주는 객체

포인터처럼 작동하며, 알고리즘과 컨테이너를 연결해 줌

---

📚라이브러리(Library)란?

프로그래밍에서 자주 쓰이는 기능들을 미리 만들어 놓은 코드 모음.

➡️ “미리 만들어진 기능 모음집”

개발자가 직접 일일이 코드를 작성하지 않아도, 필요한 기능을 바로 가져다 쓸 수 있게 도와준다.

➡️ 개발자가 필요할 때 가져다 쓸 수 있는 도구 상자 같은 존재.

📌왜 쓰나요?

시간 절약 : 이미 잘 만들어진 코드를 사용하면 개발 속도가 빨라진다.

안정성 : 검증된 코드라 버그가 적고, 더 신뢰할 수 있다.

재사용성 : 여러 프로젝트에서 똑같이 사용할 수 있다.

📌종류

표준 라이브러리 : 프로그래밍 언어에서 기본 제공하는 라이브러리
➡️ C++ 표준 라이브러리(iostream, vector, algorithm 등), c 표준 라이브러리, Java 표준 라이브러리 등등 다양하게 있음!

서드파티 라이브러리 : 외부 개발자가 만든, 기능이 더 다양한 라이브러리 (예 : OpenCV, Boost 등)

---

⚙️C++ 표준 라이브러리

C++ 언어가 기본으로 제공하는 여러 유용한 기능과 도구들의 모음.
➡️ STL을 포함한 입출력, 문자열, 유틸리티, 수학, 시간 등을 포함한 라이브러리

❓그래서 STL 이랑 뭐가 다른데?

C++ 표준 라이브러리 안에 STL이 있다고 보면 된다.

"STL" = "C++ STL" = C++ 표준 라이브러리 중 자료구조·알고리즘 부분"

내용을 정리하며

이 내용들을 이해하기 좋은 코드를 하나 가져왔다.

이진 탐색 (Binary Search)

#include <iostream>
#include <vector>
#include <algorithm>  // sort 사용 위해

using namespace std;

int binarySearch(const vector<int>& arr, int target) {
  int left = 0;
  int right = (int)arr.size() - 1;

  while (left <= right) {
      int mid = left + (right - left) / 2;

      if (arr[mid] == target)
          return mid;  // 찾으면 인덱스 반환
      else if (arr[mid] < target)
          left = mid + 1;  // 오른쪽 절반 탐색
      else
          right = mid - 1;  // 왼쪽 절반 탐색
  }

  return -1;  // 못 찾으면 -1 반환
}

int main() {
  vector<int> data = {2, 4, 6, 8, 10, 12, 14};
  int target = 10;

  int result = binarySearch(data, target);

  if (result != -1)
      cout << "찾았다! 인덱스: " << result << "\n";
  else
      cout << "못 찾았다.\n";

  return 0;
}

• 정렬된 배열에서 특정 값을 빠르게 찾는 알고리즘.

• 배열을 반씩 나누면서 탐색해서 시간 복잡도는 O(log n)이다.