[알고리즘/코딩테스트👩‍💻] Do it! 알고리즘 코딩테스트 C++ 3장 자료구조

교재 : Do it! 알고리즘 코딩테스트 c++ (김종관, 이지스퍼블리싱)
공부 깃허브 : https://github.com/yeonjae02/algorithmStudy_cpp

GitHub - yeonjae02/algorithmStudy_cpp: Do it! 알고리즘 코딩테스트 C++ 을 공부하며 작성한 코드 저장소

---

3.1 배열과 리스트 그리고 벡터

1) 배열

- 메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조
- 인덱스를 통해 배열의 값을 참조할 수 있으며  선언한 자료형의 값만 저장할 수 있다.
- 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어렵다. (값을 삽입하거나 삭제하려면 해당 인덱스 주변에 있는 값을 이동시키는 과정이 필요하다.)
- 배열의 크기는 선언할 때 지정할 수 있으며, 한 번 선언하면 크기를 늘리거나 줄일 수 없다.
 

2) 리스트

- 값과 포인터를 묶은 노드를 포인터로 연결한 자료구조
- 인덱스가 없으므로 값에 접근하려면 Head 포인터부터 순서대로 접근해야 한다. (값의 접근 속도가 느림.)
- 포인터로 연결되어 있으므로 데이터를 삽입하거나 삭제하는 연산 속도가 빠르다.
- 선언할 때 크기를 별도로 지정하지 않아도 된다. (크기가 정해져 있지 않음.)
- 포인터를 저장할 공간이 필요하므로 배열보다 구조가 복잡하다.
 

3) 벡터

- C++표준 라이브러리(STL)에 있는 자료구조 컨테이너 중 하나
- 기존의 배열과 같은 특징을 가지면서도 배열의 단점을 보완한 동적 배열의 형태
- 동적으로 원소를 추가할 수 있다.
- 맨 마지막 위치에데이터를 삽입하거나 삭제할 때는 문제가 없지만 중간 데이터의 삽입 삭제는 배열과 같은 매커니즘으로동작한다.
- 배열과 마찬가지로 인덱스를 이용하여 각 데이터에 직접 접근할 수 있다.
- 기본적인 벡터 사용

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    // 선언
    vector <int> v;
    
    //삽입
    v.push_back(1); // 마지막에 1 삽입
    v.insert(v.begin(), 7); // 맨 앞에 7 삽입
    v.insert(v.begin()+2, 9); // index 2 위치에 10 삽입
    
    // 값 변경
    v[2] = 11;
    
    // 삭제 연산
    v.pop_back(); // 마지막 값 삭제
    v.erase(v.begin()+1); // index 1 위치에 해당하는 값 삭제
    v.clear();  // 모든 값 삭제
    
    // 정보
    v.size(); // 데이터 개수
    v.front(); // 처음 값
    v.back(); // 마지막 값
    v.begin(); // 첫 번째 데이터 위치
    v.end(); // 마지막 데이터 다음 위치
    v[3]; // index 3 위치에 해당하는 값 == v.at(3);
    
    return 0;
}

 
*  C++에서의 형 변환
- string형 → 숫자형(int, long, double, float)

#include <string>

string s = "1234";
int inum = stoi(s);
long lnum = stol(s);

string sd = "1234.567";
double dnum = stod(sd);
float fnum = stof(sd);

-  숫자형(int, long, double, float) → string형

#include <string>

int inum = 1234;
long lnum = 1234;
double dnum = 1234.56;
float fnum = 1234.56f;

string intToString = to_string(inum);
string longToString = to_string(lnum);
string doubleToString = to_string(dnum);
string floatToString = to_string(fnum);

 
 

3.2 구간 합

- 배열을 이용하여 시간복잡도를 줄이기 위해 사용하는 특수한 목적의 알고리즘
- 합 배열 S의 정의 : A[0] + A[1] + ... + A[i] //  A[0]~A[i]의 합 
- 합 배열 S를 만드는 공식 : S[i] = S[i-1] + A[i]
- 구간 합을 구하는 공식 : S[j] - S[i-1] // A[i]~A[j]까지의 합
 
* C++에서의 시간단축을 위한 구문
: 멀티스레드 환경이나 화면 출력 부분에서 의도와 다르게 동작할 수 있기 때문에 실제 프로젝트나 시스템 구축 시에 잘 사용하는 구문은 아니다.

ios::sync_with_stdio(false);

• C의 stdio와 C++의 iostream의 동기화 비활성화 
• C++ 독립버퍼 사용으로 속도가 빨라짐.

cin.tie(NULL);
cout.tie(NULL);

• 하나로 묶인 두 스트림을 푼다.
• 기본적으로 cin, cout은 하나로 묶여 있는데 한 스트림이 다른 스트림에서 각 IO 작업을 진행하기 전 자동으로 버퍼를 비워주는 것을 보장한다.
• 특히 cin을 수행하기 전 기본적으로 cout 출력 버퍼를 지우는 작업을 수행하는데, 이 작업을 생략하기 때문에 속도가 빨라진다.

 
 

3.3 투 포인터

- 두 개의 포인터로 알고리즘의 시간 복잡도를 최소화한다.
- 투 포인터 이동 원칙 (연속된 자연수의 합이 n이 되는 가짓수 구하기)

• start_idx = 1, end_idx = 1, count=0; // 초기화
• sum > n : sum += sum-start_idx;, start_idx++;
• sum < n : end_idx++;, sum += end_idx;
• sum == n :end_idx++; sum += end_idx;, count++;

- 투 포인터 이동 원칙 (오름차순으로 정렬된 배열에서 두 수의 합이 n이 되는 가짓수 구하기)

• start_idx = 0, end_idx = (배열의 크기)-1, count=0; // 초기화
• arr[start_idx] + [end_idx] > m : end_idx--;
• arr[start_idx] + [end_idx] < m : start_idx++;
• arr[start_idx] + [end_idx] == m : start_idx++,  end_idx-- , count++;

 

3.4 슬라이딩 윈도우

- 2개의 포인터로 범위를 지정한 다음, 범위(window)를 유지한 채로 이동(sliding)하며 문제를 해결한다.
- 슬라이딩 윈도우를 덱으로 구현하여 정렬 효과를 볼 수 있다. -> BOJ 11003
 
 

3.5 스택과 큐

1) 스택 (stack)

- 삽입과 삭제 연산이 후입선출(LIFO; Last-in First-out)로 이루어지는 자료구조
- 삽입과 삭제가 한 쪽에서 일어난다.
- 깊이 우선 탐색(DFS; Depth First Search), 백트래킹 종류의 코딩테스트에 효과적이다.
- 용어

• 위치
  • top : 삽입과 삭제가 일어나는 위치
• 연산
  • push : top 위치에 새로운 데이터를 삽입하는 연산
  • pop : top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산
  • top : top 위치에 현재 있는 데이터를 단순 확인하는 연산

 
 

2) 큐 (queue)

- 삽입과 삭제 연산이 선입선출(FIFO; First-in First-Out)로 이루어지는 자료구조
- 먼저 들어온 데이터가 먼저 나간다. (삽입과 삭제가 양방향에서 일어남.)
- 너비 우선 탐색(BFS; Breadth First Search)에서 자주 사용한다.
- 용어

• 위치
  • back : 큐에서 가장 끝 데이터를 가리키는 영역
  • front : 큐에서 가장 앞의 데이터를 가리키는 영역
• 연산
  • push : back 부분에 새로운 데이터를 삽입하는 연산
  • pop : front 부분에 있는 데이터를 삭제하고 확인하는 연산

 
 

3) 우선순위 큐 (priority queue)

- 값이 들어간 순서와 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조
- 설정에 따라 front에 항상 최솟값이나 최댓값이 위치한다.
- 힙(heap)을 이용해 구현