- 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
15649번: N과 M (1)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해
www.acmicpc.net
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)
[실전 알고리즘] 0x0A강 - DFS
드디어 01 02 03 이렇게 숫자를 넘어서 0A강에 도달했습니다. 아직 완결까지는 한참 남았지만 아무튼 힘을 내서 계속 잘 해봅시다. 아, 참고로 저번 단원보다는 내용이 많지 않아
blog.encrypted.gg
- DFS : 배열 접근 시 깊이를 우선하여 방문
- DFS의 구현
- 시작 위치를 스택에 넣고, 방문 표시
- 스택에서 원소를 꺼낸 후 상하좌우 인접 칸 확인
- 방문하지 않은 경우 스택에 넣음
- 스택이 빌 때까지 반복
- 출처 : BaaaaaaaarkingDog | '강좌/실전 알고리즘' 카테고리의 글 목록 (encrypted.gg)
'강좌/실전 알고리즘' 카테고리의 글 목록
blog.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)
'강좌/실전 알고리즘' 카테고리의 글 목록
blog.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을 호출 시 런타임 에러 주의
STL 연습겸 STL stack으로 풀긴 했지만 배열이 더 효율적일 듯한 문제.
1부터 n까지의 숫자가 순서대로 들어온다고 하니, 크게 답변 출력을 위한 문자 stack과 값 저장을 위한 int형 stack 두개를 선언한다.
int형 변수를 하나 선언해서 그거보다 큰 값이 들어오면 같아질때까지 stack에 push 후, 같아지면 pop하는 식으로 구현한다.
들어온 숫자가 int변수보다 작은 경우는 두가지일 것이다. top에 있어서 수열로 만들 수 있거나, 아니면 top에 없으므로 수열로 구현 불가능하거나.
#include <iostream>
#include <stack>
using namespace std;
int main() {
// your code goes here
stack<int> in;
stack<char> ans, ans_;
int a;
cin >> a;
for(int i = 0, j = 0 ; i < a ; i++){
int b;
cin >> b;
if(b > j){
while(b != j){
in.push(++j);
ans.push('+');
}
}
if(b == in.top()){
in.pop();
ans.push('-');
}
else{
cout << "NO";
return 0;
}
}
while(!ans.empty()){
ans_.push(ans.top());
ans.pop();
}
while(!ans_.empty()){
cout << ans_.top() << "\n";
ans_.pop();
}
return 0;
}