침대 밖은 위험해!

1. 그래프 표현과 정의

1) 그래프의 정의와 종류

- G(V, E)로 정점(Vertex)과 간선(Edge)의 집합으로 구성된 자료구조

- 속성에 따른 분류

  방향 그래프(directed graph) / 무향 그래프(undirected graph) / 가중치 그래프(weighted graph)

- 형태에 따른 분류

  다중 그래프(multigraph) : 정점들 간에 두 개 이상의 간선이 있을 수 있는 그래프

  단순 그래프(simple graph) : 정점간 최대 한 개의 간선만 있는 그래프

  트리 혹은 루트 없는 트리(unrooted tree) : 부모자식 관계가 없을 뿐 형태는 무향 그래프

  이분 그래프(bipartite graph) : 겹치지 않는 두 개의 그룹으로 나눠서 서로 다른 그룹에 속한 정점들 간에 간선을 갖는 그래프

- 두 가지 이상의 속성을 가질 수 있음

  방향 가중치 그래프 / 이분 가중치 그래프 / 사이클이 없는 방향 그래프(Directed Acyclic Graph : DAG) = 의존 그래프

2) 암시적 그래프 구조들

- 그래프 같은 형태를 갖는 구조가 아니라도 그래프를 통해서 표현하면 쉽게 해결할 수 있는 문제

  서로 의존 관계를 갖는 그래프에서 순서를 결정하는 위상 정렬, 의존 그래프는 사이클이 없음(DAG)

  그래프의 크기는 아주 큰데 실제로는 그 중 일부만 사용 : 15-퍼즐

  2^N

3) 그래프의 표현 방법

- 그래프는 트리에 비해 훨씬 정적인 용도로 사용

※ 정적? : 새로운 정점이나 간선을 추가, 삭제 하는 경우가 적은 것

  그래프는 정적이므로 구조의 변경이 어렵더라도 메모리를 적게 차지하는 방법으로 구현함

- 간선의 정보를 어떤 식으로 저장하느냐에 따라 두 가지로 나눔

  인접 리스트 표현(adjacency list) : 그래프의 각 정점마다 해당 정점에서 나가는 간서의 목록을 저장해서 그래프를 표현

vector<list<int>> adj;

  인접 행렬 표현(adjacency matrix) : 2차원 배열을 이용하여 간선의 정보를 저장

vector<vector<bool>> adj;
bool adj[v][v];

- 인접 리스트와 인접 행렬 비교

                     특정 간선을 찾기 위한 탐색 시간         공간

인접 리스트                      V * V                            V+E

인접 행렬                           1                              V * V

※ 벡터 생성자 : 테케 여러개 돌려야 하는 경우에 초기화를 따로 해줄 필요가 없어서 좋음

vector<int> a;
vector<vector<int>> b;

a = vector<int>(할당 갯수, 초기값);
b = vector<vector<int>>(26, vector<int>(26, 0));

2. DFS

1) DFS ?

- 탐색 알고리즘 중 하나

- 깊이 우선 탐색

- 시간복잡도

  인접리스트 : 정점의 수 V + 간선의 수 E = O(|V| + |E|)

  인접행렬    : 정점의 수 V * 정점의 수 V = O(|V|^2)

2) dfs의 예제

- 두 정점이 서로 연결되어 있는가 확인

- 연결된 부분집합의 개수 세기

- 위상정렬 : dfs가 종료될 때 저장, 결과를 뒤집으면 위상정렬

                문제를 풀때는 사이클이 생성될 가능성이 있는 그래프는 위상정렬된 결과가 사이클을 갖는지 확인해줘야 함.

예제. 문제 : DICTIONARY

https://algospot.com/judge/problem/read/DICTIONARY

1, 2) 문제를 읽고 이해하기 및 재정의

- 어떤 고대사전에 단어가 적혀있는데 순서가 그 시대의 사전순

- 단어 목록이 주어 질 때, 알파벳 간의 상대적 순서를 출력

- 단어의 수 : 1 <= n <= 1,000

- 각 단어의 길이 : 1 <= L <= 20

- 순서에 모순이 있다면 "INVALID HYPOTESIS" 출력

- 없다면 알파벳 순서를 출력

3) 계획 세우기

- 단어에서 알파벳 간의 순서도 즉, 그래프를 만듦

- dfs로 그래프를 돌면서 가장 깊이 들어가는 알파벳이 순서상으로 가장 뒤이므로

  dfs가 끝날때 마다 알파벳을 추가

4) 계획 검증하기

- 시간복잡도 : 1000개의 단어 입력 시간 + => 싱크맞추는거 없이 cin 쓰면 오래 걸리지만 시간 초과 나진 않을 것 같음

                   그래프 생성시간 +            => 모든 단어를 다 봐야하므로 NL

                   위상정렬 시간 +               => 각 알파벳을 한번씩만 방문하면 되므로 26

                   사이클 검사 시간              => 한 알파벳이 사이클을 생성하는지 확인해야 하므로 26 * 26

  => O(NL)

5, 6) 계획 수행하기 및 회고하기

- 처음에 예제출력 결과를 이해하지 못해서 "위상정렬된 알파벳 + 위상정렬에 사용되지 않은 알파벳" 을 출력함.

  => ogklh abcdefijmnpqrstuvwxyz 무조건 이런식으로만 출력해야 되는지 암.

- 알고보니 그럴필요 없이 그래프를 만들고 있는 알파벳 간의 순서만 정렬하면 됨.

  zyxwvutsrqp  o  nmji  gklh  fedcba  이렇게 그래프를 형성하고 있지 않은 단어들은 순서가 상관없음. ogklh만 순서가 맞으면 됨.

- 그래서 처음에는 그래프를 이루고 있는 알파벳들만 dfs 재귀를 돌림

- 나중에는 그래프를 이루고 있지 않은 알파벳들은 순서가 상관없으므로 모든 알파벳을 dfs 재귀 돌림

- 위상정렬 결과가 사이클을 가지는지 하나씩 확인해봐야 하나???? 으흠...

- dfs를 돌리면서 사이클을 가지는지 확인하기에는 이전 루트를 다 기억하면서 비교해야 하므로 으흠...

- 배열을 하나 만들어서 dfs가 끝나는 시점에 해당 정점이 끝났다는 표시를 해줌.

  방문은 했지만, 끝나지 않은 정점을 방문한 경우 역방향 간선 즉, 사이클

  bool check[n], end[n];

  void dfs(int c){

     check[c] = true;

     for(int i = 0; i < n; i++){

         if(!check[i])

              dfs(i);

         else if(!end[i])

              // cycle

     }

     end[c] = true;

     // 위상정렬 추가

  }

소스코드

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

int t, n;
vector<char> ans;
vector<bool> check;
vector<vector<int> > graph;

int min(int a, int b){
	return ((a < b) ? a : b);
}

bool make_cycle(){
	for (int i = 0; i < (int)ans.size() - 1; i++)
		for (int j = i + 1; j < ans.size(); j++)
			if (graph[ans[i] - 'a'][ans[j] - 'a'])
				return true;
	return false;
}

void dfs(int node){
	check[node] = true;

	for (int i = 0; i < 26; i++)
		if (!check[i] && graph[node][i])
			dfs(i);

	ans.push_back((char)(node + 'a'));
}

int main(void){
	cin >> t;
	while (t--){
		cin >> n;
		vector<string> temp(n);
		// 정점의 갯수를 정확하게 알 수 없기에 알파벳 갯수인 26개로 잡음.
		graph = vector<vector<int> >(26, vector<int>(26, 0));
		check = vector<bool>(26, false);
		for (int i = 0; i < n; i++)
			cin >> temp[i];

		// make graph
		for (int i = 0; i < n - 1; i++)
			for (int j = 0; j < min(temp[i].size(), temp[i + 1].size()); j++)
				if (temp[i][j] != temp[i + 1][j]){
					graph[temp[i][j] - 'a'][temp[i + 1][j] - 'a'] = 1;
					break;
				}

		// make topolgotical sorting
		for (int i = 0; i < 26; i++)
			if (!check[i])
				dfs(i);

		// 위상정렬 결과에 사이클이 있는가?
		if (make_cycle()){
			cout << "INVALID HYPOTHESIS";
		}
		else{
			for (int i = ans.size(); i > 0; i--)
				cout << ans[i - 1];
		}
		cout << "\n";

		ans.clear();
	}
	return 0;
}

- 알고리즘 문제 해결전략 2편 중 -

- 저작권 문제시 삭제하겠습니다 -

3. 최적화 문제

- 경우의 수 문제와 같이 답이 여러개인 문제에서 '어떤 기준'에 따라 '좋은' 답을 찾는 문제를 '최적화 문제(Optimization Problem)'

※ 최적화 문제를 해결하는 방법

- 완전 탐색

- 동적 계획법

- 조합 탐색

- 결정 문제로 치환

=> 완전 탐색은 최적화 문제를 풀기 위한 가장 직관적인 방법

예제. 문제 : CLOCKSYNC

https://algospot.com/judge/problem/read/CLOCKSYNC

1) 문제를 읽고 이해하기

- 시간 제한 10ms / 메모리 제한 2^16kb

- 테스트 케이스의 개수 <= 30

2) 문제 재정의

- 16개의 시계, 3, 6, 9 12 만 가리킬 수 있음

- 10개의 스위치로 시간 조작 가능

- 각각의 스위치는 3~5개의 시계와 연결되어 있어서 해당 스위치를 누르면 연결된 시계들이 +3 씩 움직임

- 모두 12시를 가리키기 위해 눌러야 할 최소 스위치의 횟수

- 불가능할 경우 -1 출력

3) 계획 세우기

계획1.

- 최소 스위치 횟수 이기에 bfs를 고민함.

- 스위치를 몇 번 눌러야 할지 정해지지 않았기에 모든 상태를 저장하고 하나의 상태를 방문할 때 마다 저장된 상태와 비교하려고 함.

- 시계 하나는 3, 6, 9, 12 4가지 상태를 나타낼 수 있으므로 2bit로 표현 가능.

  16개의 시계 이므로 32bit 즉, int 하나로 16개 시계의 한 가지 상태를 저장 할 수 있음

  하지만, 메모리가 너무 크고 시간 예측이 안됨.

  큐 0회 : 4byte

  큐 1회 : 0 ~ 9번 버튼을 각각 눌렀을 때 10가지의 상태 : 40byte

  큐 2회 : 큐 1회에서 각각 10가지 경우가 또 발생 하므로 : 400byte

  큐 3회 : 4,000byte

  ... 큐 1회를 돌 때마다 10배가 늘어나므로 65,536,000 byte < 4 * 10^N => N이 8이면 메모리 초과

계획2.

- 시계가 3, 6, 9, 12로 회전 하므로 하나의 시계가 4회 이상 돌아갈 필요가 없음.

- '0번 버튼 -> 1번 버튼' 이나 '1번 버튼 -> 0번 버튼' 이나 결과는 똑같음

   012012나 001122는 결과가 같음

- 즉, 각각의 버튼은 0 ~ 3회만 누르면 되고 순서에 상관없음.

- 버튼을 누르는 횟수의 경우의 수는 4, 총 버튼의 개수가 10이므로 모든 경우의 수는 4^10

4) 계획 검증하기

- '계획1'은 이미 메모리 초과

- '계획2'는 4^10 == 2^20 ≒ 1억번

5, 6) 계획 수행하기 및 회고하기

- 문제 풀이 원리 : 다시 되돌아 오는 특징과 버튼의 순서가 중요하지 않다는 점이 버튼을 누르는 횟수를 제한 시킴

- 사실 아직도 4번 이상 누를 필요가 없는지에 대해서는 확신이 없음

- 나중에 내가 다시 풀 수 있을까?

- 비슷한 문제를 찾아봐야 겠음. 전구인가 색칠하기 인가 한칸 누르면 인접 4칸 색이 바뀌는 문제가 있었던거 같은데

- 구현 시 배열이라면 길이를 확인 또 확인....

- "Run-Time Check Failure#2 - Stack around the variable was corrupted" 에러는 포인터로 지역변수를 넘겼을 때 실제로 선언된 사이즈를 넘어선 인덱스로 입력을 시도할 때 발생함.

소스코드

#include<iostream>
using namespace std;

#define INF 987654321

int b[10][5] = { { 0, 1, 2, 16, 16 },   // 0
				 { 3, 7, 9, 11, 16 },   // 1
				 { 4, 10, 14, 15, 16 }, // 2
				 { 0, 4, 5, 6, 7 },     // 3
				 { 6, 7, 8, 10, 12 },   // 4
			 	 { 0, 2, 14, 15, 16 },  // 5
				 { 3, 14, 15, 16, 16 }, // 6
				 { 4, 5, 7, 14, 15 },   // 7
				 { 1, 2, 3, 4, 5 },     // 8
				 { 3, 4, 5, 9, 13 } };  // 9
int ans;

void dfs(int *clock, int button, int cnt){	
	int i = 0;
	for (; i < 16; i++)
		if (clock[i] != 0)
			break;
	// 아 이거..... 15가 아니라 16이었군
	if (i == 16){
		ans = ans < cnt ? ans : cnt;
		return;
	}
	if (button == 10)
		return;

	for (int j = 0; j < 4; j++){
		dfs(clock, button + 1, cnt + j);
		// 4번 돌리니까 dfs를 호출 하기 전의 시계 상태로 돌아감
		// 4번 회전하면 호출 하기 전의 시계상태로 돌아가므로 이전 상태를 따로 저장할 필요가 없음
		for (int k = 0; k < 5; k++)
			if (b[button][k] < 16)
				clock[b[button][k]] = (clock[b[button][k]] + 3) % 12;
	}

	return;
}

int main(void){
	ios::sync_with_stdio(false);
	freopen("Text.txt", "r", stdin);
	int T;
	cin >> T;
	while (T--){
		// clock를 15로 선언함....이거때문에 "Run-Time Check Failure#2 - Stack around the variable was corrupted" 떠서 당황했네
		int clock[16];
		ans = INF;
		for (int i = 0; i < 16; i++){
			cin >> clock[i];
			clock[i] %= 12;
		}
		dfs(clock, 0, 0);
		cout << ((ans == INF) ? -1 : ans) << "\n";
	}
	return 0;
}

4. 많이 등장하는 완전 탐색 유형

1) 모든 순열 만들기

- 가능한 모든 경우 : N!

- 실제로 만드는 방법은 다른 블로그 많으니 참고

- C++ 은 next_permutation(), prev_permutation()이 있음

2) 모든 조합 만들기

- 재귀

- nCr => 1개를 뽑고 n-1Cr-1을 재귀

- 코드 6.2 참고

3) 2^n가지 경우 만들기

- 'Yes / No' 의 경우 => 재귀 2^N

- Bit Mask를 이용하면 for문 하나로 모든 경우를 다 돌 수 있음

- 알고리즘 문제 해결전략 1편 중 -

- 저작권 문제시 삭제하겠습니다 -

예제. 문제 : BOARDCOVER

https://algospot.com/judge/problem/read/BOARDCOVER

1) 문제를 읽고 이해하기

- 시간제한 2ms / 메모리제한 2^16kb

- 1 <= h, w <= 20 / 흰칸의 수 <= 50

2) 문제 재정의

- 게임판의 흰칸( . )을 'ㄱ' 모양을 회전시킨 모양으로 전부 덮을 수 있는 경우의 수

3) 계획 세우기

- 경우의 수 문제이기에 일단 다해보는 '브루트 포스'

  : 블럭을 채워야 할 칸을 선택 후 적절한 블럭을 채움

  : 아직 채우지 않은 칸을 대상으로 위 과정을 반복함

  => '한 블럭'과 '나머지 칸'으로 문제를 분할 => 재귀

- 한 지점에서 시작하여 채우는 모양의 경우의 수가 16개

  최대 칸의 개수가 400개 이므로 중복되는 경우를 줄일 필요가 있음

- 재귀 호출 시 마다 젤 왼쪽 윗칸을 채우도록 순서를 강제함

  그럼 어떤 칸을 채우려고 할 때, 그 칸보다 왼쪽 윗칸은 다 차있다고 가정할 수 있음

            <fig 1>                                          <fig 2>                                           <fig 3>                                          <fig 4>

- 위 그림처럼 현재칸( * )을 채우는 경우의 수는 4가지

4) 계획 검증하기

- 시간복잡도 : 한 칸에서 선택할 수 있는 블럭 모양이 4가지 이므로

                   4 ^ 16(흰칸의 개수가 최대 50개라고 했으니 3개짜리 블럭은 최대 16개를 넣을 수 있음)

                   ≒ 4000 억

                   하지만, 재귀가 4000억을 다 돌지 않음. 그 이유는 한개의 블럭이 결정 되면 다음에 결정될 블럭의 경우의 수는 줄어듬

ex) 2*3 모두 하얀칸인 경우 

    <fig 1>을 선택하면 재귀 1 --- 경우의 수 0

    <fig 2>를 선택하면 재귀 2 --- 경우의 수 1

    <fig 3>을 선택하면 재귀 2 --- 경우의 수 1

    <fig 4>를 선택하면 재귀 0 --- 경우의 수 0

    즉, 실제로 재귀 5번 --- 모든 칸을 채울수 있는 경우의 수는 2

        2개의 블럭을 놓는 이론적인 경우의 수는 4^2 = 16가지

        2개의 블럭을 놓는 경우의 수에서 재귀가 도는 횟수가 많이 줄어듬

※ 실제로는 12칸일 경우 재귀는 23번

                 48칸일 경우 재귀는 68655번

※ 줄어드는건 알 수 있지만 그래도 어떻게 저 경우의 수가 시간 내에 들어오리라는 확신을 할 수가 있을까?

   확신을 해야만 브루트 포스로 풀텐데

- 공간복잡도 : global variable : int * 2 + int * 12 * 2 = 104byte

                   local variable : int * 400 = 1600byte(int나, bool 변수들은 무시)

                   즉, 1804byte < 2^16kb

5, 6) 계획 수행하기 및 회고하기

- 솔직히 아직도 재귀가 시간내에 들어오리란 확신을 가지지 못하겠음...

- 4가지 경우의 수를 줄일 때 처음에 '중심'을 가지고 줄였음

  하지만, 다음 중심을 찾기가 너무 어렵고, 중심이 들어가지 않는 경우가 발생한다면 그 부분에서 계속 무한루프를 돌게됨

  알고스팟 예제에서 첫 번째 흰칸을 중심이 들어갈 경우로 판단한다면 아무것도 넣을 수가 없음. 만약 건너뛰게 한다 하더라도

  다음번 시작점을 찾을 때도 (0, 0) 에서 시작하기에 저 부분을 계속 거치게 됨

  그래서 왼쪽 위를 무조건 채운다는 강제를 부여하게 되면 위 그림과 같은 4가지 경우가 생김

소스코드

#include<iostream>
using namespace std;

int h, w;
int dr[4][3] = { { 1, 0, 0 }, { 1, 1, 0 }, { 0, 1, 1 }, { 0, 0, 1 } };
int dc[4][3] = { { 0, 0, 1 }, { -1, 0, 0 }, { 0, 0, 1 }, { 0, 1, 1 } };

int dfs(char(*map)[21]){
	// 블럭을 채울 공간을 찾음
	int row, col, ret = 0;
	bool isWhiteBlock = false;

	for (int i = 0; i < h; i++){
		for (int j = 0; j < w; j++){
			if (map[i][j] == '.'){
				row = i; col = j;
				isWhiteBlock = true;
				break;
			}
		}

		if (isWhiteBlock)
			break;
	}

	// 하나의 경우의 수를 찾음
	if (!isWhiteBlock)
		return 1;

	// 4개의 경우를 찾음
	int i = 0;
	for (; i < 4; i++){
		bool isCover = true;
		for (int j = 0; j < 3; j++){
			int nrow = row + dr[i][j];
			int ncol = col + dc[i][j];

			if (nrow < 0 || nrow >= h || ncol < 0 || ncol >= w || map[nrow][ncol] != '.'){
				isCover = false;
				break;
			}
		}

		if (isCover){
			cnt += 1;
			map[row + dr[i][0]][col + dc[i][0]] = '#';
			map[row + dr[i][1]][col + dc[i][1]] = '#';
			map[row + dr[i][2]][col + dc[i][2]] = '#';
			ret += dfs(map);
			map[row + dr[i][0]][col + dc[i][0]] = '.';
			map[row + dr[i][1]][col + dc[i][1]] = '.';
			map[row + dr[i][2]][col + dc[i][2]] = '.';
		}
	}

	return ret;
}

int main(void){
	freopen("Text.txt", "r", stdin);
	int T;
	cin >> T;
	while (T--){
		cnt = 0;
		cin >> h >> w;
		char map[21][21];
		int white_block = 0;
		for (int i = 0; i < h; i++){
			for (int j = 0; j < w; j++){
				cin >> map[i][j];
				if (map[i][j] == '.') white_block++;
			}
		}

		if (white_block == 0)
			cout << '1' << "\n";
		else if (white_block % 3 == 0){
			cout << dfs(map) << "\n";
			cout << "cnt : " << cnt << "\n";
		}
		else
			cout << '0' << "\n";
	}
	return 0;
}

- 알고리즘 문제 해결전략 1편 중 -

- 저작권 문제시 삭제하겠습니다 -

오늘도 여전히 줍줍

std::ios::sync_with_stdio(false)

cout << ... << "\n";

http://gooddaytocode.blogspot.kr/2016/07/cin-scanf.html

https://algospot.com/forum/read/2496/

https://www.acmicpc.net/board/view/20309

1. 무식하게 풀기(brute-force)

- 가장 많이 하는 실수 중 하나가 쉬운 문제를 어렵게 푸는 것

- 공부를 열심히 할수록 복잡하지만 우아한 답안에 집착하기에..

- 부르트포스 문제는 빠르면서도 정확한 구현능력을 요구함

- 부르트포스는 더 빠른 알고리즘의 근간이 되기에 잘 익혀둘 필요가 있음

2. 재귀 호출과 완전 탐색

1) 재귀 호출

※ tail recursion 이라는 것도 있긴하지만 여기서 설명은 하지 않음

- 큰 조각을 반복되는 유사한 작은 조각들로 나누어 접근하는 것

- 작은 조각들 중 하나를 자신이 해결하고 나머지 조각들을 자기 자신을 호출해서 해결

예) 1 ~ n까지 합

int recursum(int n){
	if(n == 1) return 1;
	return n + recursum(n-1);
}

  n 과 1 ~ n-1 까지의 합으로 구분 => n-1과 1~ n-2 까지의 합으로 다시 구분 ... => 2와 1 ~ 1 까지의 합으로 마지막 구분

  n 의 합을 스스로 처리하고 나머지 1 ~ n-1 까지의 합을 자기자신을 호출하여 처리함

- 재귀는 크게 두 부분으로 구성됨

  base case : 더이상 쪼개지지 않는 작업, 최소 입력에 대한 작업, 답이 없을 경우에 대한 작업

  general case : base case를 제외한 재귀를 호출할 작업

예제. 문제 : PICNIC

- 절차적 접근

https://algospot.com/judge/problem/read/PICNIC

1) 문제를 읽고 이해하기

  : 시간제한 1000ms

  : 메모리제한 2^16kb

  : 2 <= n <= 10

2) 문제 재정의

  : 서로 친구인 학생 끼리 짝을 짓는 경우의 수

3) 계획 세우기

  : 짝이 지어지지 않은 학생을 골라서 친구사이인 다른 학생과 짝을 지어줌

  : 아직 짝이 지어지지 않은 학생을 대상으로 위 과정을 반복

  => "한쌍" 과 "짝이 지어지지 않은 학생" 으로 문제를 분할 => 재귀

4) 계획 검증하기

  : 시간복잡도 : 첫 짝이 없는 친구를 고르는 경우(1)(0 학생이 무조건 처음이므로) * 0학생과 친구인 관계(N-1) * 0과 0 친구를 제외한 다음 짝이 없는 친구를 고르는 경우(N-2) * 두 번째 고른 학생과 친구인 관계(N-3) * ... * 1 = 9! ≒ 360,000 

   즉, 1억번 내에 들어옴

  : 공간복잡도 : global variable - int * 3 = 12byte

                    local variable - bool * 100 + bool * 10 = 110byte

                    ≒ 122byte

   즉, 2^16kb 이내

5, 6) 계획 수행하기 및 회고하기

실패한 소스코드

- 중복처리를 안해줌

- 해당 코드에서는 (0, 1) (2, 3) 과 (2, 3) (0, 1) 이 다른 경우로 판단함.

#define LOCAL_TEST

#include<iostream>
using namespace std;

int n, m, cnt;

// isfriend : 두 명이 친구인지 여부
// check : 친구랑 짝이 지어졌는지 여부
// remain : 짝지을 학생이 몇명 남아있는지 여부
void dfs(bool isfriend[][10], bool check[10], int remain){
	// 짝지을 학생이 없으면 하나의 경우를 찾았으므로 cnt++
	if (remain == 0){
		cnt++;
		return;
	}

	// 짝을 지을 첫번째 학생 선택
	for (int i = 0; i < n; i++){
		if (!check[i]){

			// i 번째 학생과 친구인 학생
			for (int j = 0; j < n; j++){
				// i와 j가 친구이고 j가 다른 친구와 짝짓지 않은 경우, 친구임을 check 배열에 없데이트하고 재귀
				if (isfriend[i][j] && !check[j]){
					check[i] = check[j] = true;
					dfs(isfriend, check, remain - 2);
					check[i] = check[j] = false;
				}
			}
		}
	}

	return;
}

int main(void){
#ifdef LOCAL_TEST
	freopen("input.txt", "r", stdin);
#endif
	int T;
	cin >> T;

	while (T--){
		n = m = cnt = 0;
		cin >> n >> m;

		bool isfriend[10][10] = { false };
		bool check[10] = { false };
		for (int i = 0; i < m; i++){
			int a, b;
			cin >> a >> b;
			isfriend[a][b] = true;
		}

		dfs(isfriend, check, n);

		cout << cnt << "\n";
	}

#ifdef LOCAL_TEST
	fclose(stdin);
#endif
	return 0;
}

성공한 소스코드

- 중복처리는 시작점을 고정하는게 제일 좋음

- 단, 이 방법은 a와 b가 친구이면 isfriend[a][b] = isfriend[b][a] = true로 해줘야 (1,2) (3,0) 같은 경우를 골라낼 수 있음

- 아니면 0과 3이 친구가 아니므로 경우의 수가 빠지게 됨

※ 시간복잡도 : 학생 하나 고르는데 걸리는 시간(1) * 고른 학생과 친구인 학생 고르는데 걸리는 시간(N-1) * 두명을 제외한 학생 한명과 그 친구를 고르는데 걸리는 시간(N-3) * ... * 1= 9 * 7 * 5 * 3 * 1 = 945

   공간복잡도 : 위 공간복잡도 + 각 재귀마다 int student가 추가됨(int * (9 * 7 * 5 * 3 * 1) = 3780byte

   즉, 3920byte

#define LOCAL_TEST

#include<iostream>
using namespace std;

int n, m, cnt;

// isfriend : 두 명이 친구인지 여부
// check : 친구랑 짝이 지어졌는지 여부
// remain : 짝지을 학생이 몇명 남아있는지 여부
void dfs(bool isfriend[][10], bool check[10], int remain){
	// 짝지을 학생이 없으면 하나의 경우를 찾았으므로 cnt++
	if (remain == 0){
		cnt++;
		return;
	}

	// 짝을 지을 첫번째 고정학생 선택
	int student = 0;
	for (int i = 0; i < n; i++){
		if (!check[i]){
			student = i;
			break;
		}
	}

	// student 학생과 친구인 학생
	for (int j = 0; j < n; j++){
		// student와 j가 친구이고 j가 다른 친구와 짝짓지 않은 경우, 친구임을 check 배열에 없데이트하고 재귀
		if (isfriend[student][j] && !check[j]){
			check[student] = check[j] = true;
			dfs(isfriend, check, remain - 2);
			check[student] = check[j] = false;
		}
	}

	return;
}

int main(void){
#ifdef LOCAL_TEST
	freopen("input.txt", "r", stdin);
#endif
	int T;
	cin >> T;

	while (T--){
		n = m = cnt = 0;
		cin >> n >> m;

		bool isfriend[10][10] = { false };
		bool check[10] = { false };
		for (int i = 0; i < m; i++){
			int a, b;
			cin >> a >> b;
			isfriend[a][b] = isfriend[b][a] = true;
		}

		dfs(isfriend, check, n);

		cout << cnt << "\n";
	}

#ifdef LOCAL_TEST
	fclose(stdin);
#endif
	return 0;
}

※ 왜 종만북의 코드와 속도는 동일하지만 종만북 코드로 제출한 사람들의 코드는 0ms도 있음

   무슨 차이일까 코드를 보았더니

   눈에 띄는 차이는 cin, cout과 scanf, printf

   나중에 입출력 속도에 대해 정리된거 줍줍해와야겠음

- 알고리즘 문제 해결전략 1편 중 -

- 저작권 문제시 삭제하겠습니다 -

1. 왜 필요한가

- 알고리즘의 수행 속도를 대략적으로 측정하기 위해서

- A 알고리즘이 B 알고리즘 보다 빠르다 느리다 얼마만에 수행이 된다 등

※ 왜 프로그램 수행 속도가 아닌 알고리즘의 수행 속도를 사용하는가?

- 프로그램 수행 속도는 하드웨어, OS, 컴파일러, 언어 등에 따라 바뀔 수 있기 때문

- 위의 외적인 이유를 같게 하더라도 어떤 STL을 썼는가, 파라미터, 반복문 내 수행되는 명령문의 개수 등에 따라도 바뀔 수 있기 때문

- 프로그램 수행 속도는 다양한 입력에 대한 실행 시간을 반영하지 못함(입력이 커지면 수행 속도도 달라지기 때문)

2. 속도 측정 기준

- 반복문이 돌아가는 횟수를 기준으로 함

※ 반복문을 제외한 나머지는?

- 입력의 크기가 충분히 크다면 반복문을 제외한 나머지 명령문의 수행 횟수는 전체 명령문의 수행 횟수에서 비율이 점점 줄어들 것이기 때문

- 입력의 크기에 따라 알고리즘 내 반복문의 수행 횟수가 달라지기 때문에 "입력의 크기에 대한 함수"로 표현 =>시간 복잡도 표현의 시작

3. 알고리즘 "시간 복잡도"의 표현과 예제

- Big-O Notation

※구술로 말할때는 Order 라고도 함

- Big-Ω

- Big-Θ

- Big-O 계산 방법 : 가장 큰 항만 남김, 상수 제외

※ 단, 알고리즘 문제를 풀면서 상수가 중요한 경우도 있으니 복잡하지 않으면 상수도 포함하여 계산하는 것도 나쁘지 않음

- 예제 : selection sort, insertion sort

1) selection sort

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

void selectionSort(vector<int>& arr){
	for (int i = 0; i < (int)arr.size(); i++){
		int minIndex = i;

		for (int j = i; j < (int)arr.size(); j++){
			if (arr.at(minIndex) > arr.at(j))
				minIndex = j;
		}

		swap(arr[i], arr[minIndex]);
	}
}

int main(void){
	vector<int> a(10, 0);
	
	for (int i = 0; i < (int)a.size(); i++)
		a[i] = (rand() % 10);

	for (int i = 0; i < (int)a.size(); i++)
		cout << a.at(i) << " ";
	cout << "\n";

	selectionSort(a);
	for (int i = 0; i < (int)a.size(); i++)
		cout << a.at(i) << " ";
	cout << "\n";
	return 0;
}

<src 1 : selection sort>

  : (N-1) + (N-2) + ... + 1 = ½N(N-1) = ½N^2 - ½N => O(N^2)

2) insertion sort

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

void insertionSort(vector<int>& arr){
	for (int i = 0; i < (int)arr.size(); i++){
		int j = i;
		while (j > 0 && arr[j] < arr[j-1]){
			swap(arr[j], arr[i]);
			j--;
		}
	}
}

int main(void){
	vector<int> a(10, 0);
	
	for (int i = 0; i < (int)a.size(); i++)
		a[i] = (rand() % 10);

	for (int i = 0; i < (int)a.size(); i++)
		cout << a.at(i) << " ";
	cout << "\n";

	insertionSort(a);
	for (int i = 0; i < (int)a.size(); i++)
		cout << a.at(i) << " ";
	cout << "\n";

	return 0;
}

<src 2 : insertion sort>

  : 1 + 2 + ... + N-2 + N-1 => O(N^2)

4. 시간 복잡도 어림짐작

- 대충 때려 맞추기(개인적으로 가장 많이 이용하는 방법) => 반복의 횟수가 약 1억번(2^20, 10!) 이면 1초에 실행 된다고 판단

  (단, 반복문 안이 길면 그보다 더 걸리고 짧으면 그보다 더 적게 걸림)

  : 1개가 끝나는데 걸리는 시간 * 총 개수

  : selection sort에서 1개가 정렬되려면 최악 N * 총 배열 개수가 N = N^2

  : insertion sort에서 1개가 정렬되려면 최악 N * 총 배열 개수가 N = N^2

  : Map에서 중복되지 않고 모든 칸을 가는 경우 = N^2

  : 선택 하고 안하고의 문제 = 2^N (선택의 경우가 3, 4... 이라면 3^N, 4^N 즉, 경우의 수)

                      (fig 1)

- fig 1 에 있는건 연산 결과 1억번이 나오는 N의 입력 크기

  ex) 1만^2 = 1억

공간복잡도 분석

- 알고리즘 문제 해결전략 1편 중 -

- 저작권 문제시 삭제하겠습니다 -

문제를 풀면서 무엇이 부족한지 모르기에 좀 더 절차적으로 접근

1. 알고리즘 문제 해결을 위한 전략

1) 문제를 읽고 이해하기

- 문제가 원하는 바를 완전히 이해

- 사소한 제약조건, N값의 범위, 메모리 크기

2) 문제를 익숙한 용어로 재정의 = 재정의와 추상화

- 문제를 직관적으로 이해하기 위한 발판

- 문제의 본질만 남기고 축약 => 어떤 부분을 추상화할 것인를 선택하는 작업, 문제를 재정의하는 방법들에 대한 고찰

3) 계획 세우기

- 문제를 어떤 방식으로 해결할지, 사용할 알고리즘과 자료구조 선택

※ 문제 해결 전략 => 체계적인 접근

- 비슷한 문제를 풀어본 적이 있는가? => 원리를 이해하고 변형할 수 있는 능력

  문제의 목적을 보고 적절한 접근법을 선택하기 위해서는 문제를 분류(최적화, 경우의 수, 검색 등)하고, 각 알고리즘들이 어느 경우에 사용될 수 있는지

- 단순한 방법 => 점진적으로 개선점을 찾아가는 방법

- 수식화

- 문제를 단순화

- 그림으로

- 문제를 분해

- 뒤에서 부터 시작

- 순서를 강제

- 특정 형태의 답만 고려(답이 여러개가 나올 수 있는 경우)

4) 계획 검증하기

- 빅오, 메모리

5) 계획 수행하기

- 구현에서 유의점과 좋은 프로그램 작성

※ 좋은 코드 짜기

- 간결한 코드 - 전역변수(대회 한정)

- 코드 재사용 - 모듈화 : 항상 깔끔하게 작성하고 그것이 습관이 되도록 노력

- 표준 라이브러리 공부

- 항상 같은 형태로 프로그램 작성 - 행열, 범위, for 등

- 일관적이고 명료한 명명법 사용

- 자료를 정규화 - 각도, 시간, 분수 등 : 정규화는 프로그램이 자료를 입력 받거나 계산하자마자 바로 시행하는 것이 좋음

- 코드와 데이터 분리

  fig1 코드 처럼 데이터를 코드 안에 넣기 보다는 fig2 처럼 논리와 상관없는 데이터는 상수화

string getMonthName(int month){
   if (month == 1) return "January";
   if (month == 2) return "February";
   ...
   return "December";
}

<fig1>

const string monthName[] = { "January", "Fabruary", ..., "December" };

<fig2>

코드와 상관없는 데이터 부분은 따로 분리. 맵에서 움직일 수 있는 위치 보다 움직일 수 있는 상대좌표를 이용하는 것이 좋음

단, 오타 조심

※ 자주하는 실수

- 산술 오버플로우

  int를 벗어나는 큰 결과 또는 중간값 : 자료형을 변경, 중간값의 수식을 변경하여 초과하지 않도록 함

  무한대 - 987654321 : 2^30에 가까운 수로 어느 정도의 수가 더해지더라도 오버플로우가 안생김

  자료형의 프로모션 - 보통 부호있는 값과 없는 값이 계산될 때 : 특히 벡터의 사이즈는 부호없는 size_t를 반환함

  실수 연산 - 안쓰는게 제일 좋음. 써야 한다면 값을 늘려서 정수형으로 변환. 그것도 안되면 그냥 크게 잡는게 좋음(부동 소수점의 유효숫자)

- Out of Index

- 상수 오타

- 스택 오버플로우 - C++의 경우 지역 변수로 선언한 배열이나 클래스 인스턴스가 스택을 사용하기 때문에 조심. 그냥 전역이 제일 좋음

- 다차원 배열 인덱스 바꿔쓰기

- 최대, 최소 예외

- 연산자 우선순위

- 변수 초기화 - 입력 예제를 똑같은걸 두번 쓰면 어느 정도 피할 수 있음

- 계산 중간 결과를 출력하는 것이 디버깅을 덜 돌리게 함

6) 회고하기

- 문제를 풀 때마다 코드와 함께 자신의 경험을 기록

- 문제의 간단한 해법 + 어떤 방식으로 접근했는지 + 문제 해결을 위한 결정적 깨달음

- 오답 원인

=> 나중에 읽으면서 그때 뭘 배웠는지 되새김. 문제들 간의 공통 해법 등 파악하는데 좋음

- 다른 사람의 코드

다음 2편은 빅오에 대해

- 해당 내용은 종만북에서 가져옴 -

- 알고리즘 문제 해결 전략 1편 중 -

- 저작권 문제시 삭제하겠습니다 -

지극히 주관적이고 공부한거 안까먹고 어디서든 보고 싶은 마음에 블로그를 시작함

17년 2월 쯤 알고리즘을 시작함

백준 오프라인 강의로 시작함

저 밑바닥 구렁텅이에서 인간계로 넘어오기 위해 발버둥 치는 중임

17년 11월 현재까지 이래저래 제대로 공부한건 4개월 정도

지금부터는 종만북과 BOJ, COCI 위주로 공부할 계획

1. 종만북 - 

2. BOJ, COCI는 종만북에서 공부한 알고리즘 위주로만 풀 예정