이것 저것 &

문제풀이:https://www.acmicpc.net/problem/1436

666을 포함하는 값의 위치를 탐색하는 탐색문제였습니다.

별 다른 알고리즘기법이 포함되지 않기 때문에 구현문제라고도 생각할 수 있습니다.

666부터 수를 탐색하면서 666을 포함하는지 확인해주고 카운트값을 1씩 올려주면 탐색하면 되는 문제였습니다.

시간초과를 조심해야 하는데,  해당 문제는 10000까지 밖에 되지 않기 때문에 풀이가 가능했습니다. 

정답코드입니다.

#include <iostream>
using namespace std;
int n = 0;
int arr_index = 0;
int val[15]; //자리수들을 저장할 배열 

int main() {
	cin >> n;

	for (int i = 666; arr_index != n; i++) {
		int num = i;
		int num_size = 0;
		bool jud = false;

		while (num) { // 10이면 2자리수 이런식 
			val[num_size] = num % 10;
			num /= 10;
			num_size++;	
		}
		num = i; // 다시 num은 i 
		for (int j = 0; j <= num_size - 3; j++) {
			if (val[j] == 6 && val[j + 1] == 6 && val[j + 2] == 6) {
				jud = true;
				break;
			}
		}
		if (jud == true)
			arr_index++;
		if (arr_index == n) {
			cout << i << '\n';
			return 0;
		}
	}
}

문제링크:https://www.acmicpc.net/problem/1021

실제 데큐를 사용해서 문제에서의 조건을 실행하며 결과값을 얻는 시뮬레이션 문제였습니다. 

저는 c++의 deque를 사용해서 구현하였습니다. 

숫자를 탐색할때 왼쪽으로 빼는게 빠른지, 오른쪽으로 빼는게 빠른지 

index와 arr.size()를 이용해 위치를 비교하였습니다. 

비교적 쉬운 문제 였습니다. 

정답코드입니다. 

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

deque <int> arr;
int n = 0, m = 0;
int cnt = 0;
int arr_m[51];
int main() {
	cin >> n >> m;

	for (int i = 1; i <= n; i++)
		arr.push_back(i);
	for (int i = 0; i < m; i++)
		cin >> arr_m[i];

	for (int i = 0; i < m; i++) {
		
		int num = arr_m[i];
		int num_index = -1;
		for (int i = 0; i < arr.size(); i++) {
			if (num == arr[i])
				num_index = i;
		}

		// 왼쪽으로 가는게 빠른지 오른쪽으로 가는게 빠른지
		
		//1.왼쪽이 이동하는게 빠를때
		if (num_index <= arr.size() - num_index) {
			for (int i = 0; i < num_index; i++) {
				int val = arr.front();
				arr.push_back(val);
				arr.pop_front();
				cnt++;
			}
			arr.pop_front();
		}
		// 2. 오른쪽으로 이동하는게 빠를때 
		else {
			for (int i = arr.size() - 1; i >= num_index; i--) {
				int val = arr.back();
				arr.push_front(val);
				arr.pop_back();
				cnt++;
			}
			arr.pop_front();
		}
	}
	cout << cnt << '\n';
}

문제 링크:https://www.acmicpc.net/problem/1012

dfs, bfs 를 사용하는 완전 탐색 문제였습니다. 

1인 위치의 상하좌우를 이동하며 해당위치가 1인지, 방문 한적 있는지 판단하는 문제였습니다.

bfs 보다는 dfs 로 구현하는게 좋은 문제였습니다.

저는 큐를 탐색하는 형태인 bfs로 탐색하며 dfs를 추가로 사용해서 구현하였습니다.

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

int t = 0, k = 0, m = 0, n = 0;
int	arr[51][51];
bool visited[51][51];
int que[2500][2];
int started = 0, ended = 0;
int result = 0;

int x_ar[4] = { -1,1,0,0 };
int y_ar[4] = { 0,0,1,-1 };
void dfs(int y, int x);
void bfs() {

	while (started != ended) {
		
		int x = que[started][0];
		int y = que[started++][1];
		if (visited[y][x] == 1) continue;
		
		result++;

		dfs(y, x);

	}
}
void dfs(int y, int x) {
	visited[y][x] = 1;

	for (int i = 0; i < 4; i++) {
		int yy = y + y_ar[i];
		int xx = x + x_ar[i];
		if (yy >= 0 && yy < n && xx >= 0 && xx < m) {
			if(arr[yy][xx] == 1 &&visited[yy][xx] == 0)
				dfs(yy, xx);
		}
	}

}

int main() {

	cin >> t;

	while (t--) {

		cin >> m >> n >> k;
		started = 0, ended = 0;
		result = 0;
		memset(arr, 0, sizeof(arr));
		memset(que, 0, sizeof(que));
		memset(visited, 0, sizeof(visited));
		int x, y;

		for (int i = 0; i < k; i++) {
			cin >> que[ended][0] >> que[ended][1];
			arr[que[ended][1]][que[ended][0]] = 1;
			ended++;

		}
		
		bfs();
		
		cout << result << endl;
	}
}

더욱 최적화 된 코드입니다.

다시 풀어본 문제인데, 1년전에 풀었던 코드가 훨씬 효율이 좋아서 현타가 왔습니다... 

굳이 큐를 사용할 필요 없는 문제였습니다. ( 위의 코드는 사실 큐라고 하기에도 애매한 배열의 사용형태입니다..)

#include <iostream>
#include <string.h>
using namespace std;
 
int dy[4]={1,-1,0,0};
int dx[4]={0,0,1,-1};
int M,N,K;
int arr[50][50]={0};
int visited[50][50]={0};
 
void dfs(int y,int x){
    
    for(int i=0;i<4;i++){
        int ny=y+dy[i];
        int nx=x+dx[i];
        
        if(ny<0 || ny>=N || nx<0 || nx>=M)
            continue;
        
        if(arr[ny][nx] && !visited[ny][nx]){
            visited[ny][nx]++;
            dfs(ny,nx);
        }
    }
}
int main(){
    int T,x,y;
    cin>>T;
    
    for(int testCase=0;testCase<T;testCase++){
        scanf("%d %d %d",&M,&N,&K);
        
        memset(arr,0,sizeof(arr));
        memset(visited,0,sizeof(visited));
        
        int ans=0; //지렁이 개수
        
        for(int i=0;i<K;i++){
            scanf("%d %d",&x,&y);
            arr[y][x]=1;
        }
        
        for(int i=0;i<N;i++)
            for(int j=0;j<M;j++)
                if(arr[i][j] && !visited[i][j]){
                    
                    ans++;
                    visited[i][j]++;
                    dfs(i,j);
                    
                }
        
        cout<<ans<<endl;
    }
    return 0;
}

꼭 직접 작성하면서 풀어보세요! 화이팅 :)

문제링크:https://www.acmicpc.net/problem/11502

에라토스테네스의 체 알고리즘을 알고있어야합니다.

아래코드입니다.

for (int i = 2; i <= 1000; i++) {
		if (arr[i] == 1) continue;
		for (int j = i + i; j <= 1000; j += i)
			arr[j] = 1;
	}
	

소수의 배수는 소수가 아닌 것을 이용해서 소수에는 0 비소수에는 1을 넣어놓습니다. 

그이후 O(n^3)만큼 삼중포문으로 반복하면서 값을 판별해주는 완전탐색문제 (브루트 포스) 였습니다. 

구현이 너무 쉽기때문에  나머지 설명은 생략하겠습니다.

정답코드입니다. 

#include <iostream>
using namespace std;
int t = 0, n = 0;
int arr[1001] = { 0 };


int main() {
	for (int i = 2; i <= 1000; i++) {
		if (arr[i] == 1) continue;
		for (int j = i + i; j <= 1000; j += i)
			arr[j] = 1;
	}
	
	cin >> t;
	while (t--) {
		bool jud = false;
		cin >> n;
		for (int i = 2; i <= n; i++) {
			if (arr[i] == 1) continue;
			for (int j = 2; j <= n; j++) {
				if (arr[j] == 1) continue;
				for (int k = 2; k <= n; k++) {
					if (arr[k] == 1) continue;

					if ((i + j + k) == n) {
						cout << i << ' ' << j << ' ' << k << endl;
						jud = true;
						break;
					}
				}
				if (jud == true)
					break;
			}
			if (jud == true)
				break;
		}
	
	}
}

문제링크:https://www.acmicpc.net/problem/2661

정답률에 비해서 어려운 문제였습니다.

우선, 규칙성이 있는지 확인하셔야 합니다. 하지만 수가 늘어남에 따라 규칙성이 변화하는 형태로 별다른 규칙이 없었습니다. 그렇다면 완전탐색을 고려해보아야 합니다. 마침 n도 1 이상 80이하로 비교적 적은 수 입니다. 단순히 모든 수를 넣어보고 비교한다면 시간초과가 날 것입니다. 백트래킹에 대한 개념을 아셔야 합니다.

백트래킹이란?

주로 dfs에서 사용되는 개념입니다. 가지치기라고 생각하면 됩니다. 완전탐색시에 모든 경우의 수 를 고려해서 결과를 도출합니다. 하지만 완탐은 시간이 어마어마하게 들어가는 비효율적인 방법입니다. 

백트래킹은 완전탐색시에 가능성이 있는 경우의 수들만 추려내면서 탐색을 하는 방법입니다.  

이번 문제는 직접 코드를 보시는게 이해가 빠릅니다. 

#include <iostream>
#include <string>
using namespace std;
int n = 0;
bool ended = 0;
bool isValid(string val) {
	
	int len = val.size();
	int ended = val.size() - 1;

	for (int i = 1; i <= len / 2; i++) {
		string first = val.substr(ended - i, i);
		string second = val.substr(ended, i);
		if (first.compare(second) == 0) return false;
		ended--;
		
	}
	return true;
}

void dfs(int cnt, string val) {
	if (ended == 1)
		return;
	if (!isValid(val))  return;
	if (cnt == n) {
		cout << val <<"\n";
		ended = 1;
		return;
	}

	dfs(cnt + 1, val + '1');

	dfs(cnt + 1, val + '2');

	dfs(cnt + 1, val + '3');

}
int main() {
	cin >> n;
	dfs(0, "");
}

dfs 함수입니다.

void dfs(int cnt, string val) {
	if (ended == 1)
		return;
	if (!isValid(val))  return;
	if (cnt == n) {
		cout << val <<"\n";
		ended = 1;
		return;
	}

	dfs(cnt + 1, val + '1');

	dfs(cnt + 1, val + '2');

	dfs(cnt + 1, val + '3');

}

보시는 것 처럼 전형적인 dfs 재귀 함수입니다. 

종료되는 시점은 cnt == n 일때 입니다. ( 1부터 2, 3번 순서로 탐색하기에 가장먼저 도착한 친구가 가장 값이 작습니다.)

하지만 추가된 ended == 1, isValid()  2조건이 포함되기때문에 백트래킹입니다.  ended는 출력초과를 막기위해 당연히 필요한 함수입니다. (겸사겸사 가지치기도 하게됩니다.)

그리고 isValid 함수를 통해서  해당 문자열이 유효한지 확인하고 유효할 경우에만 더 진행되는 구조입니다.

전형적인 백트래킹 문제였지만, 구현난이도가 낮지 않아서 저도 valid 함수에서 막혔던 문제입니다.

안보고 코드를 직접 입력하면서 꼭 손으로 풀어보세요!

문제링크:https://www.acmicpc.net/problem/11051

이항계수를 출력하는 문제입니다. 

당연히 팩토리얼을 계산해서 푸는 방식이 아닙니다. 팩토리얼 방식으로 하면, 곱하기 과정에서 아주 큰 값이 나오게 되기 때문에 오버플로우가 발생합니다. (int, longlong 둘다) 

중간중간에 나머지를 해주는 방식도 생각해보았지만, 어떠한 규칙을 적용해야할지 모르겠네요..

dp문제입니다.

dp란? 순차적인 결과물에서 특정 점화식에 의해서 값이 도출되는 형태를 의미합니다.

아래 그림은 파스칼 삼각형입니다. 이항계수를 구할 때 사용됩니다. 

감이 오시나요?

dp알고리즘의 핵심은 점화식 구하기 입니다. 

dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] << 라는 점화식을 구하실 수 있을거에요

아래는 정답코드입니다. 아마 구현하는데 어려움은 없을실 겁니다. 

#include <iostream>
using namespace std;

int n = 0, k = 0;
int dp[1002][1002] = { 0 };

int main() {
	cin >> n >> k;

	for (int i = 1; i <= n + 1; i++) {
		dp[i][1] = 1, dp[i][i] = 1;
		for (int j = 2; j <= i - 1; j++) {
			dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
			dp[i][j] %= 10007;
		}
	}
	cout << dp[n + 1][k + 1] << '\n';
}

문제링크:https://www.acmicpc.net/problem/8061

전형적인 bfs 문제입니다. d(p1,p2)=|i1-i2|+|j1-j2| 을 만족하는 최단 경로 탐색문제입니다.

너무 쉬워서 설명은 생략하겠습니다.

#include <iostream>
#include <cstring>
#include <string>
using namespace std;
int n = 0, m = 0;
int arr[183][183] = { 0 };
int visited[183][183] = { 0 };
int que[40000][2] = { 0 };
int started = 0, ended = 0;
int x_go[4] = { 0,0,1,-1 };
int y_go[4] = { 1,-1,0,0 };

void bfs() {
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (arr[i][j] == 1)
				que[ended][0] = i, que[ended++][1] = j, visited[i][j] = 1;

	while (started != ended) {
		int y = que[started][0];
		int x = que[started++][1];

		for (int i = 0; i < 4; i++) {
			int yyy = y + y_go[i];
			int xxx = x + x_go[i];
			if (yyy >= 0 && yyy < n && xxx >= 0 && xxx < m)
				if (!visited[yyy][xxx]) {
					visited[yyy][xxx] = visited[y][x] + 1;
					que[ended][0] = yyy, que[ended++][1] = xxx;
				}
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		string arg;
		cin >> arg;
		for (int j = 0; j < m; j++) {
			arr[i][j] = arg[j] - '0';

		}
	}

	bfs();
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++)
			cout << visited[i][j] - 1 << ' ';
		cout << '\n';
	}
}

 그리고 조금더 오래걸리지만 브루트포스의 형식으로도 solve를 받을 수 있습니다.

장점: 쉬운 문제풀이 단점: 시간 

#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
using namespace std;
int n = 0, m = 0;
int arr[183][183] = { 0 };
int visited[183][183] = { 0, };
int que[40000][2] = { 0 };
int ended = 0;

void func() {
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (arr[i][j] == 1)
				que[ended][0] = i, que[ended++][1] = j;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) {
			int y = i, x = j;

			for (int k = 0; k < ended; k++) {
				if (arr[y][x] == 0) {
					int val = abs(y - que[k][0]) + abs(x - que[k][1]);
					if (visited[y][x] > val) {
						visited[y][x] = val;
					}
				}
			}

		}

}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		string arg;
		cin >> arg;
		for (int j = 0; j < m; j++) {
			arr[i][j] = arg[j] - '0';
			if (arr[i][j] == 0)
				visited[i][j] = 1000;
		}
	}

	func();
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++)
			cout << visited[i][j] << ' ';
		cout << '\n';
	}
}

문제링크:https://www.acmicpc.net/problem/15666

dfs연습문제입니다. 

• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다

두가지 조건을 만족시켜야 합니다. 

중복 수를 제거하고 sort 함수를 통해 오름차순 배열로 정렬시켰습니다.

그 이후 재귀식을 통해서 count값을 올리며 진행했습니다. 

void dfs(int cnt) {
	if (cnt == m) {
		for (int i = 0; i < cnt; i++)
			cout << result[i] << ' ';
		cout << endl;
		return;
	}

	for (int i = 0; i < arr_index; i++) {
		bool jud = true;

		for (int j = 0; j < cnt; j++)
			if (result[j] > arr[i]) {
				jud = false;
				break;
			}


		if (jud == true)
		{
			result [cnt] = arr[i];
			dfs(cnt + 1);
		}
	}
}

위 처럼 구현하였습니다.

정답코드입니다.

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

int n = 0, m = 0,arr_index=0,num;
int arr[8] = { 0 };
int result[8];
bool visited[8] = { 0 };
void dfs(int cnt) {
	if (cnt == m) {
		for (int i = 0; i < cnt; i++)
			cout << result[i] << ' ';
		cout << endl;
		return;
	}

	for (int i = 0; i < arr_index; i++) {
		bool jud = true;

		for (int j = 0; j < cnt; j++)
			if (result[j] > arr[i]) {
				jud = false;
				break;
			}


		if (jud == true)
		{
			result [cnt] = arr[i];
			dfs(cnt + 1);
		}
	}
}
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		bool jud = true;
		cin >> num;
		for (int j = 0; j < arr_index; j++) {
			if (arr[j] == num) {
				jud = false;
				break;
			}
		}
		if (jud == true)
			arr[arr_index++] = num;
	}
	sort(arr, arr + arr_index);
	
	dfs(0);
}