공부정리 아카이브

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

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

#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
      }
    }
}

#include <iostream>
#include <stack>
#include <cstring>
using namespace std;

int main() {
	// your code goes here
	char arr[105];

	for(;;){
		cin.getline(arr, 105);
		if(!strcmp(arr, ".")) break;
		stack<char> brr;

		for(int i = 0 ; arr[i] ; i++){
			if(arr[i] == '(' || arr[i] == '[') brr.push(arr[i]);
			else if(arr[i] == ')'){
				if(brr.empty() || brr.top() == '[') brr.push(arr[i]);
				else if(brr.top() == '(') brr.pop();
			}
			else if(arr[i] == ']'){
				if(brr.empty() || brr.top() == '(') brr.push(arr[i]);
				else if(brr.top() == '[') brr.pop();
			}
		}

		if(brr.empty()) cout << "yes\n";
		else cout << "no\n";
	}

	return 0;
}

- 이것저것 많지만 결론은 괄호 짝 찾기 문제다. 스택을 이용하면 간편하게 해결 가능.
- 다만 공백을 포함한 문자열 입력을 못하면 좀 까다로운 문제였다.

- 예제 입력이 이런데 그냥 cin이나 scanf로 입력을 받으면 맨 마지막줄의 " ." 이 앞 공백이 빠져서 종료 코드로 인식을 해버린다.
- <string> 객체를 쓰면 더 편하게 처리가 가능하지만 아직 배우기 전이므로 사용 가능한 cin.getline(문자열, 크기)를 사용한다. 크기는 넉넉잡아도 개행("\n")이 들어오면 알아서 끊어주니 공백이 있는 입력 처리에는 상당히 간편할 듯하다.

- 그림으로 그려보니 풀이가 확실히 보였던 문제.

- 예제 입력 2를 푼다고 해보자. 원형으로 배치한 순열이 입력 n=10이기 때문에 1~10으로 입력된 숫자이고, m은 길이 3의 숫자를 찾을 것이고, 두번째 줄의 2,9,5를 순서대로 찾을 예정이라고 한다.

- 원형 순열을 원형 다이얼을 돌려가면서 찾는다고 하면 꽤 괜찮은 풀이법이 나온다고 본다. 이 다이얼을 시계/반시계 중 어느쪽으로 돌려야 빠르게 찾을 수 있는가를 생각해보자. 결국 한쪽으로 돌릴 때랑 반대쪽으로 돌릴 때 중 짧은 길이를 더해가며 계산하면 간단히 풀리는 문제이다.

- 바킹독 님의 알고리즘 https://blog.encrypted.gg/935?category=773649 강의를 참조하며 풀었기 때문에 deque 자료구조로 문제를 해결했다.

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

int main() {
	// your code goes here
	deque<int> a, b;
	int n, m;
	cin >> n >> m;
	for(int i = 0 ; i < n ; i++){
		a.push_back(i+1);
	}
	for(int i = 0 ; i < m ; i++){
		int k;
		cin >> k;
		b.push_back(k);
	}
	
	int cnt = 0;
	int front=0, back=0;
	while(!b.empty()){
		if(a.front() == b.front()){
			back = a.size() - front;
			cnt += front > back ? back : front;
			a.pop_front();
			b.pop_front();
			front=back=0;
		}
		else{
			a.push_back(a.front());
			a.pop_front();
			front++;
		}
	}
	
	cout << cnt;
	return 0;
}

출처 : 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을 호출 시 런타임 에러 주의