공부정리 아카이브

- DP, Dynamic Programming : 여러 하위 문제를 쌓아올려 주어진 문제를 해결
  - 점화식을 찾아내어 결과를 구현 Ex) 피보나치 수열

//재귀 : n번째 피보나치는 n-1과 n-2번째의 합
//O(1.618^n)
int fibo(int n){
	if(n <= 1) return 1;
    return fibo(n-1) + fibo(n-2);
}
//DP : 0, 1번째 수열부터 n번째까지의 값을 순서대로 계산
//O(n)
int fibo(int n){
	int f[20];
    f[0] = f[1] = 1;
    
    for(int i = 2 ; i <= n ; i++){
    	f[i] = f[i-1] + f[i-2];
    }
    return f[n];
}

- DP의 풀이과정
  1. 테이블 정의
  2. 점화식 찾기
  3. 초기값 정의

- 백트래킹 : 가능한 모든 후보군을 탐색하는 알고리즘

- 백트래킹의 구현 : 배열의 활용

#include <iostream>
using namespace std;

int n, m;
int arr[8];
bool used[8];

void func(int k){
	if(k == m){
		for(int i = 0 ; i < m ; i++){
			cout << 1 + arr[i] << ' ';
		}
		cout << "\n";
		return;
	}
	
	for(int i = 0 ; i < n ; i++){
		if(!used[i]){
			arr[k] = i;
			used[i] = 1;
			func(k+1);
			used[i] = 0;
		}
	}
}

int main(void){
	cin >> n >> m;
	func(0);
}

ex. 백준 15649 - N과 M

1. n, m은 입력 데이터
2. arr은 완성된 수열
3. used는 해당 숫자의 방문 여부를 확인
  - i번째 숫자에 방문하지 않은 경우 해당 숫자를 수열 맨 뒤에 추가
  - used에 방문 표시 후, k+1번째로 func 함수 호출
  - 함수 동작 후 used는 방문하지 않은것으로 수정
4. func 함수는 입력받은 수열 길이(m)를 만족할 경우(k), 수열을 출력

- 재귀 : 함수가 자기 자신을 다시 호출

//ex. 1부터 N까지의 합을 구하는 함수
int func(int N){
  if(N == 0) return 0
  return func(N-1) + N;
}

- 재귀의 풀이 - 수학적 귀납
  - ex. 도미노 : 1번 도미노는 쓰러진다 > k번 도미노가 쓰러지면 k+1번 도미노가 쓰러진다
  - 1부터 N까지의 계산
    - func(1)은 1을 출력한다
    - func(k)는 k ~ 1까지의 합을 출력
    - func(k+1)은 k+1 ~ 1까지의 합을 출력 : func(k+1)은 func(k)를 출력 - k+1과 k~1까지의 합

- 재귀 함수의 조건
  - 특정 입력(base condition)의 경우 종료
  - 모든 입력은 base condition으로 수렴해야 함
  - 재귀는 코드는 단순 / 메모리와 수행시간에는 손해

//ex. 1부터 N까지의 합을 구하는 함수
int func(int N){
  if(N == 0) return 0 // base condition
  return func(N-1) + N; //모든 N은 0으로 수렴
}

- 출처 : BaaaaaaaarkingDog | '강좌/실전 알고리즘' 카테고리의 글 목록 (encrypted.gg)

- DFS : 배열 접근 시 깊이를 우선하여 방문

- DFS의 구현
  - 시작 위치를 스택에 넣고, 방문 표시
  - 스택에서 원소를 꺼낸 후 상하좌우 인접 칸 확인
  - 방문하지 않은 경우 스택에 넣음
  - 스택이 빌 때까지 반복

- 출처 : BaaaaaaaarkingDog | '강좌/실전 알고리즘' 카테고리의 글 목록 (encrypted.gg)

- BFS(Breadth First Search)
  - 배열 방문 시 너비를 우선으로 방문
  - 그래프 순회 시 사용하는 알고리즘(DFS, BFS) 중 하나

- BFS의 구현(2차원 배열)
  1. 0,0좌표를 큐에 입력
  2. 큐의 맨 앞 데이터를 deque
  3. 해당 좌표의 접근 가능한 상/하/좌/우를 enque,
    - 조건을 만족하는 경우 해당 좌표에는 방문 표시
    - 이미 방문한 코드는 동작 생략
  4. 2~3을 반복
  5. 큐가 빌 경우 BFS 동작이 완료

- STL pair
  - <utility> 헤더에 존재
  - pair<자료형1, 자료형2>로 구현
  - 두개의 자료 구조를 동시에 사용할 때 사용
  - make_pair 혹은 중괄호(C++11이상)로 값 대입
  - pair간 비교시 앞의 데이터부터 순서대로 비교
    - ex. <1, 2>, <1, 3> : 앞의 1은 같고, 뒤의 2, 3 비교시 뒤가 더 크므로 뒤 자료가 더 크다고 확인
  - pair data는 pair.fist, pair.second로 앞/뒤의 데이터를 접근 가능

- 배열을 이용한 큐의 구현

#include<iostream>
#include<queue>
#include<utility>

int arr[100][100];
bool visit[100][100];

int dx[4] = {1, 0, -1, 0};
int dy[4] = {1, 0, -1, 0};

int main(void){
	ios::sync_with_stdio(0);
    cin.tie(0);
    
    queue<pair<int, int>> q;
    
    visit[0][0] = 1;
    q.push(make_pair(0, 0));
    
    while(!q.empty()){
      pair<int, int> cur = q.front();
      q.pop();
      
      for(int i=0; i<4 ; i++){ //상하좌우 좌표 접근
        int nx = cur.first + dx[dir];
        int ny = cur.second + dy[dir];
        
        if(nx < 0 || nx > 100 || ny < 0 || ny > 100) continue;
        if(visit[nx][ny] || arr[nx][ny] != 1) continue
        //상하좌우 좌표가 배열을 벗어나거나, 방문했거나, 조건을 불만족할 시 통과
        
        visit[nx][ny] = 1; // 방문 표시
        q.push(make_pair(nx, ny)); //새 좌표를 enque
      }
    }
}

출처 : BaaaaaaaarkingDog | '강좌/실전 알고리즘' 카테고리의 글 목록 (encrypted.gg)

- 덱(deque, double ended queue)

  - 양 끝에서 삽입/삭제가 가능한 자료구조

- 덱의 성질
  - 원소의 추가, 제거, 맨 앞/뒤 원소 확인 시 O(1)
  - 맨 앞/뒤 원소 외의 자료구조 확인이 불가

- 덱의 구현
  - 배열을 이용한 구현

const int MAX = 100000;
int data[2 * MAX + 1];
int head = MAX, tail = MAX;
//큐는 한 쪽으로만 데이터가 추가하므로 인덱스가 증가하는 방향으로만 구현
//덱의 경우 양쪽으로 데이터가 이동하므로 크기를 2배로 하고, 인덱스 시작점을 배열 중앙에 설정

//데이터 추가
int push_front(int x){
  data[--head] = x;
}
int push_back(int x){
  data[tail++] = x;
}
//데이터 제거
int pop_front(){
  head++;
}
int pop_back(){
  tail--;
}
//데이터 확인
int front(){
  return data[head];
}
int back(){
  return data[tail-1];
}

  - STL deque를 이용한 구현 - 벡터와 유사하게 동작

//https://github.com/encrypted-def/basic-algo-lecture-metarial/blob/master/0x07/deque_example.cpp
#include <deque>

int main(void){
  deque<int> DQ;
  DQ.push_front(10); // 10
  DQ.push_back(50); // 10 50
  DQ.push_front(24); // 24 10 50
  for(auto x : DQ)cout<<x;
  cout << DQ.size() << '\n'; // 3
  if(DQ.empty()) cout << "DQ is empty\n";
  else cout << "DQ is not empty\n"; // DQ is not empty
  DQ.pop_front(); // 10 50
  DQ.pop_back(); // 10
  cout << DQ.back() << '\n'; // 10
  DQ.push_back(72); // 10 72
  cout << DQ.front() << '\n'; // 10
  DQ.push_back(12); // 10 72 12
  DQ[2] = 17; // 10 72 17
  DQ.insert(DQ.begin()+1, 33); // 10 33 72 17
  DQ.insert(DQ.begin()+4, 60); // 10 33 72 17 60
  for(auto x : DQ) cout << x << ' ';
  cout << '\n';
  DQ.erase(DQ.begin()+3); // 10 33 72 60
  cout << DQ[3] << '\n'; // 60
  DQ.clear(); // DQ의 모든 원소 제거
}

수정 : 출처 : BaaaaaaaarkingDog | '강좌/실전 알고리즘' 카테고리의 글 목록 (encrypted.gg)

- 큐 : 한 쪽에서는 원소가 들어갈 수만 있고, 반대편에서 나올 수만 있는 자료구조
  - First In, First Out(FIFO) 형태의 자료 구조

- 큐의 특징
  - 원소의 추가, 제거, 맨 앞/뒤 원소 확인 시 O(1)
  - 앞/뒤 외의 원소 확인은 원칙적으로 불가

- 큐의 구현
  - 배열을 이용한 구현

const int MAX = 100000;
int data[MAX];
int head = 0, tail = 0;
//head : 제일 앞에 있는 원소 / tail : 비어 있는 원소의 인덱스

// 데이터가 추가되면 tail이 1 증가
// 데이터가 제거되면 head가 1 증가
// 큐의 크기 = tail - head

void push(int x){
  data[tail++] = x;
}//데이터 추가

void pop(){
  head++;
}// 데이터 제거

int front(){
  return data[head];
}//맨 앞 데이터 반환

int back(){
  return data[tail-1];
}// 맨 뒤 데이터 제거

  - STL queue를 이용한 구현

#include <queue>
using namespace std;

int main(void){
  queue<int> q;
  
  q.push(10); // 데이터 추가
  q.pop(); // 데이터 제거
  cout << q.size(); // 큐 크기 반환
  q.front();
  q.back(); // 큐의 맨 앞 / 뒤 데이터 반환
  cout << q.empty(); // 큐가 비었는지 여부
}

  - 큐가 빈 상태로 pop / front / back을 호출 시 런타임 에러 주의

출처 : BaaaaaaaarkingDog | '강좌/실전 알고리즘' 카테고리의 글 목록 (encrypted.gg)

- stack : 먼저 들어간 원소가 가장 나중에 나오는(First In, Last Out - FILO) 자료 구조

- 스택의 성질
  - 원소의 추가 / 제거에 O(1)
  - 제일 상단 원소 확인 시 O(1)
  - 원칙적으로는 제일 상단 외의 데이터 확인이 불가

- 스택의 구현
  - 배열을 이용한 구현

const int MAX = ...;
int data[MAX];
ins pos = 0; // 스택의 빈 공간의 인덱스를 가리킴 = 스택 원소의 수

void push(int x){
	data[pos++] = x;
} // 스택에 데이터 추가

void pop(int x){
	return data[pos--];
} // 스택의 데이터 제거 및 반환

void top(){
	return data[pos - 1];
}//최상단 데이터 반환

  - STL stack

#include <stack>

int main(void){
	stack<int> s;
    s.push(10); // 데이터 추가
    cout << s.size(); // 스택 크기 반환
    if(s.empty()) cout << "s is empty" // 스택의 비었는지 여부
    s.pop(); // 스택 최상단 데이터 제거
  	cout << s.top(); // 스택 최상단 데이터 확인
}

출처 : BaaaaaaaarkingDog | '강좌/실전 알고리즘' 카테고리의 글 목록 (encrypted.gg)

- 배열이란 : 연속된 메모리 주소 상에 데이터를 할당하는 자료 구조
- 배열의 시간 복잡도
  - 데이터의 조회 및 수정 : O(1)
  - 맨 끝 원소의 추가/제거 : O(1)
  - 임의 원소의 추가/제거 : O(n) - 해당 위치부터 배열 끝까지 1개씩 데이터 위치를 조정해주어야 하므로

- 배열의 특징
  - 원소의 조회 및 확인에 O(1)의 시간 복잡도 요구
  - overhead는 낮고, cache hit는 높다
  - 주소가 연속 할당되어야 하므로 다른 구조 대비 할당에 제약이 다소 있는 편

- 배열 임의 위치에 추가 및 제거

#include <iostream>
using namespace std;

void insert(int idx, int data, int arr[], int &len){
	// idx : 추가할 위치
    // data : 추가할 데이터
    // arr[] : 원본 배열
    // len : 배열 길이, reference로 호출하였으므로 수정시 원본 값도 수정된다.
	
	for(int i=len;i > idx;i--){
    	arr[i] = arr[i - 1];
    }
    arr[idx] = data;
    len++;
}
void delete(int idx, int arr[], int &len){
	// insert에서 data만 빠진 상태
    // 제거할 위치 뒤의 모든 데이터를 1칸씩 앞으로 옮긴다.
    for(int i = idx ; i < --len ; i++){
    	arr[i] = arr[i+1];
    }
}

- 배열의 초기화
  1. for문 순회
  2. <algorithm> 헤더 - fill함수

int a[21];
int b[21][21];

fill(a, a + 21, 0); //시작위치, 끝위치, 채울 값

for(int i = 0 ; i < 21 ; i++)
	fill(b[i], b[i] + 21, 0); // 2차원 배열 초기화

- <vector> 헤더
  - 배열과 동일한 기능
  - 크기 조정이 자유로움

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

int main(void){
	vector<int> v1(3, 5);
    // vector 선언 : vector<자료형>
    // 초기값 선언 : 배열이름(길이, 초기값);
    
    int size = v1.size(); // 벡터 길이
    int begin = v1.begin(); // 벡터 맨 앞 위치
    v1.push_back(1); // 벡터 맨 뒤에 데이터 추가
    v1.insert(begin, 3); // 임의 위치에 데이터 추가
    v1.erase(begin); //임의 위치의 데이터 제거
    
    int pop = v1.pop_back(); // 맨 뒤 데이터 제거 및 반환
    v1.clear(); // 벡터 초기화
    
    // insert, erase 시 O(n) 시간복잡도
    // push/pop_back은 O(1) - 맨 뒤 데이터이므로
    // 벡터 간 대입 시 deep copy - 한쪽이 바뀌어도 다른쪽은 유지
    
    //벡터 순회 - C++11 기준
    for(int v : v1) cout << v << ' ';
    // v1의 원소가 순서대로 v에 복사되어 들어감
    // 만약 int &v로 설정시 원본값이 들어감
    
    //for문으로 벡터 순회
    for(int i = 0 ; i < v1.size() ; i++) cout << v1[i] << ' ';
}

- C++의 <algorithm> 헤더에는 순열(permutation)을 구할 수 있는 next_permutation 함수가 있다.
완전 탐색 시의 코드를 상당히 간결하게 만들어준다.

- 코드 문제 풀이 시 입력받는 arr가 있다고 할 때, 해당 arr의 순열을 찾을 index의 배열을 별도로 선언한다.
- next_permutation(시작 주소, 끝 주소) 형태로 반환받으므로, next_permutation(배열 이름, 배열 이름 + 원소 개수) 형태로 while 반복문을 사용해주면, 다음 순열이 없을 때까지(false를 반환하다) 순열을 조합해준다.

int per[10] = {0,1,2,3,4,5,6,7,8,9};

do{
	//per에는
	//0,1,2,3,4,5,6,7,8,9 부터,
    //9,8,7,6,5,4,3,2,1,0 까지 모든 순열이 반환된다.
}while(next_permutation(per, per + 10));