이것 저것 &

문제링크:www.acmicpc.net/status?user_id=gusdnr9875&problem_id=15918&from_mine=1

백트래킹 문제입니다. dfs를 통해 구현하는데 이때 문제 조건에 맞게 가지치기를 해주어야 합니다.

가지치기 

• 1. x,y가 주어지기 때문에 위치를 정할 수 있습니다. ex) x,y가 1,5라면 5 - 1 - 1 = 3. 즉 3이 x, y 위치에 고정됩니다.
• 2. 2*n개인 위치를 반복할때, arr[현재] 가 1이거나 arr[현재 + i + 1]이 이미 방문했을때는 탐색해줄 필요가 없습니다.
• 3. 2*n개인 위치를 반복할때, 현재 + i +1 > 2n 이면 탐색해줄 필요가 없습니다.

아래는 정답코드입니다. 위 조건 3개를 충족시키게 구현했습니다.

#include <iostream>
using namespace std;
int n, x, y;
int arr[26] = { 0, };
bool checked[25] = { 0, };
int result = 0;

void dfs(int cur) {
	if (cur == n*2) {
		result++;
		return;
	}
	if (arr[cur] == 0) {

		for (int i = 1; i <= n; i++) {
			if (checked[i] == 0) {
				if (cur + i + 1 <= 2 * n && !arr[cur+i+1]) {
					checked[i] = 1;
					arr[cur] = i;
					arr[cur + i + 1] = i;
					dfs(cur + 1);
					checked[i] = 0;
					arr[cur] = 0;
					arr[cur + i + 1] = 0;
				}
			}
		}
	}
	else
		dfs(cur + 1);
	return;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	cin >> n >> x >> y;
	
	arr[y] = y - x - 1;
	arr[x] = y - x - 1;
	checked[y - x - 1] = 1;
	dfs(1);
	cout << result << endl;
	return 0;
}

문제링크: www.acmicpc.net/problem/20208

n*n은 100이므로 각각의 좌표를 전부 검사해주는 행동은 당연히 시간초과

"민트초코우유의 총합은 10개를 넘지 않는다." 라는 조건을 사용하여야 합니다. 즉, 각 좌표들의 거리로 탐색해야 합니다.

이때, 조합이 아니라 순열구조이므로 10! 만큼 소모될수 있습니다. 시간적으로 괜찮을 것을 확인했다면 

바로 구현하면 됩니다.

정답코드입니다.

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

typedef struct MyStruct
{
	int y;
	int x;
	bool checked;
}val;

int n = 0, m = 0, h = 0;
int result = 0;
int arr[10][10] = { 0, };
val house;
vector <val> mint;

void dfs(int y, int x,int cur, int cnt, int hp) {
	if (cnt > result) {// 방문횟수가 더 많고
		if (abs(y - house.y) + abs(x - house.x) <= hp)
			result = cnt;
	}
	if (hp <= 0)
		return;
	for (int i = 0; i < mint.size(); i++) {
		
			int len = abs(mint[i].y - y) + abs(mint[i].x - x);
			if (len <= hp && mint[i].checked == 0) {
				mint[i].checked = 1;
				dfs(mint[i].y, mint[i].x, i+1, cnt + 1, hp - len + h);
				mint[i].checked = 0;
			}
			
	}

}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m >> h;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++){
			int temp = 0;
			cin >> temp;
			if (temp == 1)
				house.y = i, house.x = j;
			else if (temp == 2)
				mint.push_back({ i,j,0 });
		}
	}
	
	dfs(house.y,house.x,0, 0, m);
	cout << result  << endl;
	return 0;
}

간혹 조합과 수열 구현을 헷갈려 하시는데, 아래 링크 참고하시면 좋을 것 같습니다. 

paris-in-the-rain.tistory.com/35

특이하게 1월에 상반기 신입사원 공개채용을 했습니다.

서류합격하여 직무면접다녀왔습니다!

직무면접은 30분의 사전테스트와 1시간 30분 정도의 다대다 면접이었습니다. (아마 개발직군만 테스트가 있는것으로 알고 있습니다.)

사전테스트는 간단한 개발지식 문제들로 구성되어 있었습니다.

직무면접에서는 개발지식에 관한 질문들, 프로젝트 경험에 대해서 확인하셨고 

분위기는 편안한 분위기였습니다! 

딱딱한 느낌이 전혀 없고 답변들으시면서 고개를 끄덕여 주시면서 호응해주셨어요! 

개인적인 느낀점은 조금더 차분하게 말했으면 좋겠다는 것입니다. 질문에 대답을 하면 저 스스로가 기분이 좋아서 점점 템포가 업된 느낌입니다.

아프리카TV 오디오어플팀 TO인 것 같은데 너무 아프리카TV 서비스에 대한 어필만 해서 사실 붙을지 잘 모르겠습니다.. ㅠㅠ ㅋㅋㅋㅋㅋ

붙으면 추가 포스팅 진행하겠습니다.

모든 취준생분들 같이 화이팅입니다.!

--- 추가

2차 인성면접은 압박면접, 심층면접이었습니다.

하나의 질문에 꼬리 질문은 지속적으로 물어보셨습니다. 

준비한대로 이야기하기가 어려워서 그냥 꾸밈없이 솔직하게 답변하는게 좋을 것 같습니다.

저는 면접이후에 서버개발직무로 변경할 의향이 있는지 연락이 왔습니다.

c++, 리눅스, 네트워크 <<를 사용하는 직무인데, 경력직만 뽑는 직무를 추천해주셔서 처음에는 의아했습니다.

오히려 더 좋은 기회가 같아서 바로 수락하고 한번 더 면접을 보고왔습니다. (총 3번의 면접... ㅋㅋㅋㅋ)

서버개발직무 면접은 정말 편안한 분위기입니다. 면접보시는 현업 담당자분들이 엄청 장난끼가 많으시고 편하게 질문할 수 있도록 도와주십니다. 

결국 해당 직무로 합격했습니다.

회사다니더라도 블로그활동은 꾸준히 병행하겠습니다 : )

문제링크:www.acmicpc.net/problem/1941

백트래킹 문제입니다. 전체가 검색해주는 것이 아니라 임도연파 학생이 4이상이 될때 가지치기를 해주어야 합니다. (근데 제거 해주지 않아도 ac통과합니다.)

F 모양처럼 일반적인 방식의 dfs, bfs로는 구현할 수 없다는 것을 알게되었습니다.

모든 좌표를 탐색해야하는데 어떻게 구현할지 고민했습니다.

그리고 아래처럼 구현했습니다.

for (int i = y; i < 5; i++) {
		for (int j = (i == y ? x : 0); j < 5; j++) {
			if (chk[i][j] == 0) {
				chk[i][j] = 1;
				dfs(cnt + 1, i, j, arr[i][j] == 'S' ? som + 1 : som, arr[i][j] == 'Y' ? yim + 1 : yim);
				chk[i][j] = 0;
			}
		}
	}

y,x는 dfs에 넣어주는 값입니다. 모든 좌표중에 7개를 선택하는 경우입니다. 즉 25C7입니다.  480,700 가지의 경우의 수이므로 충분히 가능합니다. j = (i == y ? x : 0)는 처음에는 x좌표부터 시작하고 그이후점부터는 0으로 시작한다는 삼항연산자입니다.

• 1. 25개 좌표중에 7개 선택하기- dfs
• 2. 7개의 좌표들이 서로 연결되어 있는지 확인하기 - search
• 3. 결과도출

아래는 전체코드입니다.

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

int result = 0;
string arr[5];
bool chk[5][5] = { 0, };
bool temp[5][5] = { 0, };
int y_ar[4] = { 0,0,1,-1 };
int x_ar[4] = { 1,-1,0,0 };

void search(int y, int x) {
	temp[y][x] = 1;
	for (int i = 0; i < 4; i++) {
		int ny = y + y_ar[i];
		int nx = x + x_ar[i];
		if (chk[ny][nx] == 1 && temp[ny][nx] == 0)
			if (ny >= 0 && ny < 5 && nx >= 0 && nx < 5)
				search(ny, nx);
	}
}

void dfs(int cnt, int y, int x, int som, int yim) {
	if (yim >= 4)
		return;
	if (cnt == 7 && som >= 4) {
		int val_temp = 0;
		memset(temp, 0, sizeof(temp));
		for(int i=0;i<5;i++)
			for(int j=0; j<5;j++)
				if (chk[i][j] == 1&& temp[i][j]==0) {
					search(i, j);
					val_temp++;
				}

		if (val_temp == 1)
			result++;
		return;
	}


	for (int i = y; i < 5; i++) {
		for (int j = (i == y ? x : 0); j < 5; j++) {
			if (chk[i][j] == 0) {
				chk[i][j] = 1;
				dfs(cnt + 1, i, j, arr[i][j] == 'S' ? som + 1 : som, arr[i][j] == 'Y' ? yim + 1 : yim);
				chk[i][j] = 0;
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	for (int i = 0; i < 5; i++)
		cin >> arr[i];

	dfs(0, 0, 0, 0, 0);

	cout << result << endl;

	return 0;
}

문제풀이:programmers.co.kr/learn/courses/30/lessons/12952?language=cpp

n-queen 문제입니다.

아래 백준 문제와도 동일합니다.

https://www.acmicpc.net/problem/9663

gusdnr69.tistory.com/132

2차원배열이 아닌 1차원 배열로 구현할 수 있습니다.

1. row배열에 열값을 넣는다.

2. 넣으면 같은열에 있는 좌표가 있는지,

3. 대각선 상으로 일치하는 부분이 있는지 검사한다.

3가지 를 순서대로 구현해주면 되는 백트래킹 문제였습니다.

아래는 정답코드입니다.

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <cmath>
int N, result = 0;
int row[13] = { 0, }; //열값을 넣어줄 예정

bool checked(int r) {

	for (int i = 0; i < r; i++) {
		if (row[i] == row[r])
			return false;
		else if (abs(row[i] - row[r]) == r - i)
			return false;
	}
	return true;
}

void dfs(int r) {
	if (N == r) {
		result++;
		return;
	}

	for (int i = 0; i < N; i++) { //0열부터 n-1열까지 검사
		row[r] = i;
		if (checked(r)) {
			dfs(r + 1);
		}
		row[r] = 0;
	}
	return;
}

int solution(int n) {
	int answer = 0;
	N = n;
	dfs(0);
	answer = result;
	return answer;
}

문제링크:www.acmicpc.net/problem/1759

dfs문제입니다. 조건에 맞게 구현해주면 되는 간단한 문제였습니다.

주의할점은

• 1. 알파벳들을 정렬해주어야 한다는 것 
• 2. 모음 1자, 자음 2자 이상이어야 한다는 것

정답코드입니다.

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

int l, c;
string arr;
bool checked[17] = { 0, };

void dfs(int cnt, int current) {

	if (cnt == l) {

		int m=0, j=0;
		for (int i = 0; i < arr.size(); i++) {
			if (checked[i]) {
				if (arr[i] == 'a' || arr[i] == 'e' || arr[i] == 'i' || arr[i] == 'o' || arr[i] == 'u')
					m++;
				else
					j++;
			}
		}
		if (m >= 1 && j >= 2) {
			for (int i = 0; i < arr.size(); i++)
				if (checked[i])
					cout << arr[i];
			cout << endl;
		}
		return;
	}


	for (int i = current; i < arr.size(); i++) {
		if (checked[i] == 0) {
			checked[i] = 1;
			dfs(cnt + 1, i);
			checked[i] = 0;
		}
	}
	return;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> l >> c;
	for (int i = 0; i < c; i++) {
		char temp;
		cin >> temp;
		arr += temp;
	}
	sort(arr.begin(), arr.end());
	//cout << arr << endl;
	dfs(0, 0);
	return 0;
}

문제링크:www.acmicpc.net/problem/15686

간단한 dfs 문제였습니다. 

백트래킹의 요소는 잘 모르겠습니다. 단지 가까운 치킨 가게를 찾을때 bfs 탐색의 개념을 사용하지 말고, 각각의 치킨집과 집의 거리를  |r1-r2| + |c1-c2| 공식을 통해서 찾아주게끔만 구현해주면 맞는 간단한 문제입니다.

저는 치킨집 좌표를 구조체 벡터를 사용해서, 집 좌표는 pair사용해서 구현했습니다. 

아래는 정답 코드입니다. 

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

typedef struct a{
	int y;
	int x;
	bool checked;
}Chk;

vector <pair <int, int>> house;
vector <Chk> chicken;
int n = 0, m = 0;
int result = 2e9;

void dfs(int cnt, int current) {

	if (cnt == m) {
		/*
		for (int i = 0; i < chicken.size(); i++) {
			if (chicken[i].checked == true)
				cout << i << ' ';
		}
		cout << endl;*/

		int sum = 0;

		for (int i = 0; i < house.size(); i++) {
			int mined = 1000000000;
			for (int j = 0; j < chicken.size(); j++) {
				if (chicken[j].checked == false) continue;

				mined = min(mined, abs(house[i].first - chicken[j].y) + abs(house[i].second - chicken[j].x));
			}
			sum += mined;
		}

		if (result > sum)
			result = sum;

		return;
	}
	

	for (int i = current; i < chicken.size(); i++) {
		if (chicken[i].checked == false) {
			chicken[i].checked = true;
			dfs(cnt + 1, i);
			chicken[i].checked = false;
		}
	}
	return;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	// 1.
	cin >> n >> m;
	int num = 0;
	for(int i=1;i<=n;i++)
		for (int j = 1; j <= n; j++) {
			cin >> num;
			if (num == 1)
				house.push_back(make_pair(i, j));
			else if (num == 2)
				chicken.push_back({ i,j,0 });
		}
	//2.
	dfs(0, 0);

	cout << result << endl;
	return 0;
}

문제링크:www.acmicpc.net/problem/8911

간단한 시뮬레이션 문제입니다.

이동방향에 따라 이동시켜주면서 max y, x 값과 min y,x값을 찾아주면 되는 문제입니다.

이동할때는 4방향 배열을 사용해서 문제를 해결합니다.

바로 정답코드입니다.

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


int t = 0;
int y_arr[4] = { -1,0,1,0 }; //북 동 남 서 방향
int x_arr[4] = { 0,1,0,-1 };

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> t;

	while (t--) {
		int cy = 0, cx = 0, dir = 0;
		int minx = 0, miny = 0, maxx = 0, maxy = 0;

		string arr;
		cin >> arr;

		for (int i = 0; i < arr.size(); i++) {
			int ny, nx;
			if (arr[i] == 'F') {
				cy = y_arr[dir%4] + cy;
				cx = x_arr[dir%4] + cx;
			}
			else if (arr[i] == 'B') {
				cy = y_arr[(dir+2)%4] + cy;
				cx = x_arr[(dir+2)%4] + cx;
			}
			else if (arr[i] == 'R') {
				dir++;
			}
			else if (arr[i] == 'L') {
				dir--;
				if (dir < 0)
					dir += 4;
			}

		//	cout << i + 1<<"x y" << cx << ' ' << cy <<" dir "<<dir<<endl;
			if (maxx < cx)
				maxx = cx;
			if (maxy < cy)
				maxy = cy;
			if (minx > cx)
				minx = cx;
			if (miny > cy)
				miny = cy;
		}
		//cout << maxy << ' ' << maxx << ' ' << miny << ' ' << minx << endl;
		cout << ((maxy - miny)* (maxx - minx)) << "\n";

	}


	return 0;
}