Search

'알고리즘/algospot'에 해당되는 글 6건

  1. 2016.12.11 카쿠로
  2. 2016.08.01 회전초밥
  3. 2016.08.01 블록게임
  4. 2016.07.25 조합게임
  5. 2015.02.21 ASYMTLING
  6. 2015.02.21 NUMB3RS

카쿠로

알고리즘/algospot 2016.12.11 16:49 Posted by 아는 개발자 아는 개발자

스도쿠나 N-Queens 문제들을 마주할 때면 가슴이 답답하다. 냅색이나 LIS 처럼 차곡차곡 상황들을 쌓아 갈 수 없을 뿐더러 두더지 게임 처럼 하나의 조건을 해결하면 또 다른 문제가 튀어나오니 도대체 어떻게 풀어야 할 지 감을 잡을 수 없었다. 이러한 유형의 문제를 보면 정말 머리 좋은 친구들이 푸는건가보다 하고 그냥 넘어 갔던 것 같다.


알고리즘 해결 전략에서는 스도쿠, N-Queen 그리고 가쿠로 문제처럼 특정한 제약에 해당하는 답을 찾는 문제를 제약 충족 문제라고 한다. 조합 탐색 문제들 중에 하나인데 먼저 조합 탐색은 기존에 사용했던 알고리즘(DP, 탐욕법 등등)을 사용 할 수 없고 가지치기를 통해 검사 할 필요가 없는 경우들을 미리 쳐내는 방법이다. 제약 충족 문제는 조합 문제에서 한 발 더 나아간다. 주어진 조건에서 제약을 스스로 만들고 다른 조각에 그 제약을 전파 하는 것이다. 다르게 말하면 답의 일부를 생성한 뒤 거기서 얻을 수 있는 정보를 최대한 많이 찾아내는 것이라 할 수 있다.


한가지 더 생각해볼 것은 채울 순서를 고르는 것이다. 스도쿠 문제를 풀 때 빈 칸중에서 제일 만만히 입력 할 수 있는 빈칸은 가로 또는 세로가 많이 채워져 있는 칸일 것이다. 최대한 가지의 순서를 줄이려면 어느 것을 먼저 채울지 선택하는것 또한 중요하다.


카쿠로 문제에서도 동일하다. 먼저 채울 순서는 오른쪽 또는 세로의 줄에 칸이 적은 것들 부터 골라야 할 것이다. 즉 빈칸에 들어갈 숫자 후보의 수가 가장 작은 곳 부터 먼저 채워가야 한다. 그래야지 빈칸을 채우는 전체 경우의 수가 줄어들어 시간내에 풀 수 있다.


이 문제의 해설 을 볼 때 감탄을 했던 부분이 여러 군데 였던 것 같다. 첫 번째는 각 빈칸에 놓을 수 있는 숫자들의 잡합을 비트로 표현했다는 것이다. 각 칸마다 가능한 숫자 후보자는 가로쪽 힌트와 세로쪽 힌트의 교집합인데, 비트마스크는 그 힌트를 가장 간단히 표현 해주었다.


두번째는 모든 후보 경우의 수들을 전처리해준 것이다. 후보 집합에 영향을 미치는 값들이 길이, 총합 인데 중복 계산을 방지 하기 위해 모든 경우에 대해서 전처리 해줬다. 가능한 숫자로 0을 빼기 위해 비트 연산을 넣은 센스도 감탄 스러웠다.


책에서 본 내용을 토대로 작성한 코드는 이렇다.


 
#include<iostream>
#include<cstdio>
#include<stdio.h>
#include<algorithm>
#include<string.h>

using namespace std;

const int WHITE = 1;
const int MAXN = 21;

int candidates[10][46][1024];

int n, color[MAXN][MAXN], value[MAXN][MAXN], hint[MAXN][MAXN][2];
int q, sum[MAXN*MAXN], length[MAXN*MAXN], known[MAXN*MAXN];

int getSize(int mask) {
	int ret = 0;

	for (int i = 0; i <= 9; i++)
		if (mask & (1 << i))
			ret++;

	return ret;
}
int getSum(int mask) {
	int ret = 0;

	for (int i = 0; i <= 9; i++)
		if (mask & (1 << i))
			ret += i;

	return ret;
}

void generatesCandidates() {
	memset(candidates, 0, sizeof(candidates));

	for (int set = 0; set < 1024; set += 2) {
		int l = getSize(set), s = getSum(set);
		int subset = set;

		while (true) {
			candidates[l][s][subset] |= (set & ~subset);
			if (subset == 0) break;
			subset = (subset - 1)&set;
		}
	}
}

void put(int r, int c, int val) {
	for (int h = 0; h < 2; h++)
		known[hint[r][c][h]] += (1 << val);
	value[r][c] = val;
}

void remove(int r, int c, int val) {
	for (int h = 0; h < 2; h++)
		known[hint[r][c][h]] -= (1 << val);
	value[r][c] = 0;
}

int getCandHint(int hint) {
	return candidates[length[hint]][sum[hint]][known[hint]];
}

int getCandCoord(int r, int c) {
	return getCandHint(hint[r][c][0])&getCandHint(hint[r][c][1]);
}

void printSolution() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) 
			printf("%d ", value[i][j]);
		printf("\n");
	}
}

void setSum(int hint, int hintSum) {
	sum[hint] = hintSum;
}

void setLen(int hintNum, int direct, int r, int c) {
	int len = 0;

	int inc_r = 0, inc_c = 0;
	if (direct == 0)
		inc_c++;
	else
		inc_r++;

	r += inc_r, c += inc_c;
	while (true) {
		if (r > n || c > n || color[r][c] != 1)
			break;
		hint[r][c][direct] = hintNum;
		r += inc_r;
		c += inc_c;

		len++;
	}

	length[hintNum] = len;
}

bool search() {
	int y = -1, x = -1, minCands = 1023;

	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++)
			if (color[i][j] == WHITE && value[i][j] == 0) {
				int cands = getCandCoord(i, j);
				if (getSize(minCands) > getSize(cands)) {
					minCands = cands;
					y = i, x = j;
				}
			}

	if (minCands == 0) return false;

	if (y == -1) {
		printSolution();
		return true;
	}

	for (int val = 1; val <= 9; val++) {
		if (minCands & (1 << val)) {
			put(y, x, val);
			if (search()) return true;
			remove(y, x, val);
		}
	}

	return false;
}

int main() {

	int tc, r, c, dir, s;

	generatesCandidates();

	freopen("input.txt", "r", stdin);
	scanf("%d", &tc);

	while (tc--) {
		scanf("%d", &n);


		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++) {
				scanf("%d", &color[i][j]);
				value[i][j] = 0;
				hint[i][j][0] = hint[i][j][1] = 0;
			}

		for (int i = 1; i <= MAXN*MAXN; i++)
			length[i] = sum[i] = known[i] = 0;

		scanf("%d", &q);

		for (int i = 1; i <= q; i++) {
			scanf("%d%d%d%d", &r, &c, &dir, &s);
			setSum(i, s);
			setLen(i, dir, r, c);
		}

		search();
	}

	return 0;
}


이런 문제를 보면 감탄스러우면서도 이런 코드를 과연 작성 할 수 있을지 마음이 착잡하다..


'알고리즘 > algospot' 카테고리의 다른 글

카쿠로  (0) 2016.12.11
회전초밥  (0) 2016.08.01
블록게임  (0) 2016.08.01
조합게임  (0) 2016.07.25
ASYMTLING  (0) 2015.02.21
NUMB3RS  (0) 2015.02.21

회전초밥

알고리즘/algospot 2016.08.01 23:06 Posted by 아는 개발자 아는 개발자

항상 이런 DP문제들을 보면 어떤 값을 배열의 index로 표현할까가 나의 관심사였다. 가장 배열에 넣을 만한 값들은 예산에 해당하는 값들이었고 이 값들이 배열의 최대 범위를 초과하지 않기를 기도할 뿐이었다.


하지만 최대 범위를 초과한다면.. 그 문제는 내겐 그때부터는 DP문제가 아니였다. 어떻게 최적화 할 것인가 머리를 짜매다가 풀지 못한 문제로 남아버렸다.


책에서본 회전초밥문제도 그랬다. 단순 DP문제로 풀 수 있을 줄 알았는데 예산의 범위가 10^9이하여서 배열로 넣기는 무리였다. 문제의 힌트로 가격이 항상 100의 배수라 10^7정도는 배열에 넣으면 되겠다 생각했는데 메모리의 크기 제한이 64MB였다.


int형으로 배열의 크기가 10^7로 잡자니 메모리가 초과할 것 같고 그렇다고 최대한 메모리를 쪼개고 쪼개 char형으로 배열을 선언하지나 답의 범위를 온전히 표현하지 못할 것 같았다.


이런 경우에 사용하는 방법이 슬라이딩 윈도우이다. 슬라이딩 윈도우란 사용하는 데이터 전체를 메모리에 유지하는 것이 아니라 필요한 것들만 저장해두는 방식이다. 가장 대표적인예로는 피보나치배열의 n번째 항을 구하는 방법이다.


 
int fibo(int n) {
	if (n <= 1) return n;
	int seq[3];
	seq[0] = 0;
	seq[1] = 1;
	for (int i = 2; i <= n; i++)
		seq[i % 3] = seq[(i - 1) % 3] + seq[(i - 2) % 3];
}

하나의 피보나치 항을 업데이트하는데 필요한 값은 총 3개이고 이때 사용하는 메모리들은 모두 재활용 될 수 있기에 크기 3인 배열로 해결 할 수 있다.

위 기법을 초밥문제 풀 때도 사용해볼 수 있었다.

c[현재 체크중인 예산 - 초밥의 최대 가격]이전의 값들은 필요가 없다. 배열의 값이 업데이트하면서 예전에 사용했던 값들은 쓸모가 없어진다. 이런 경우에 모든 최적화 경우의 값들을 초밥의 최대 가격 안에서 표현이 가능해진다. 즉 초밥의 최대 가격 만큼 배열의 크기를 선언해줄 수 있다.

 
int solve(int c, int n) {
	int budget, i;
	int ret = 0;

	for (budget = 0; budget <= c; budget++) {
		int cand = 0;
		for (i = 0; i < n; i++) {
			if (budget >= price[i])
				cand = max(cand, cost[(budget - price[i]) % 201] + pref[i]);
			cost[budget % 201] = cand;
			ret = max(ret, cand);
		}
	}

	return ret;
}

cost[(budget-price[i])%201] 은 budget - price 예산에서 최대 높은 선호도를 갖는 값이다. 모듈러 연산을 통해 이전의 필요없는 값들을 제거한 것에 주목할 필요가 있다.

역시 고수들은 다르다. 책에서 많은걸 배우는것 같다

'알고리즘 > algospot' 카테고리의 다른 글

카쿠로  (0) 2016.12.11
회전초밥  (0) 2016.08.01
블록게임  (0) 2016.08.01
조합게임  (0) 2016.07.25
ASYMTLING  (0) 2015.02.21
NUMB3RS  (0) 2015.02.21

블록게임

알고리즘/algospot 2016.08.01 22:11 Posted by 아는 개발자 아는 개발자

조합게임의 예제로 나온 문제. 모두가 최선을 다했을 때 이길 수 있는 경우에 대한 것은 앞에서 설명했으니 넘어가고 블록과 보드게임의 상태를 비트 연산을 이용해 어떻게 깔끔히 표현했는지에 주목하자.


 
void precalc() {
	for(int y = 0; y < 4; y++)
		for (int x = 0; x < 4; x++) {
			vector<int> cells;
			for (int dy = 0; dy < 2; dy++)
				for (int dx = 0; dx < 2; dx++)
					cells.push_back(cell(y + dy, x + dx));
			int square = cells[0] + cells[1] + cells[2] + cells[3];

			for (int i = 0; i < 4; i++)
				moves.push_back(square - cells[i]);
		}

	for(int i=0; i<5; i++)
		for (int j = 0; j < 4; j++) {
			moves.push_back(cell(i, j) + cell(i, j+1));
			moves.push_back(cell(j, i) + cell(j+1, i));
		}
}

char play(int board) {
	char& ret = cache[board];

	if (ret != -1)
		return ret;

	ret = 0;

	for(int i=0; i<moves.size(); i++)
		if((moves[i] & board) == 0)
			if (!play(board | moves[i])) {
				ret = 1;
				break;
			}

	return ret;
}

먼저 5*5 board판인 점을 이용해서 비트를 이용해 각각의 상태를 표현한다는 접근법부터 놀랍다. 나라면 또 board의 상태에 따라서 행렬을 그리고 이중포인터 사용하고 지저분해졌을것 같은데 저자는 board의 상태를 비트로 표현해 int변수 만으로 표현해줄 수 있었다.

또한 precalc()는 모든 위치에서 블록을 둘 수 있는 경우의 수들을 저장해둔것인데 모든 위치에 대해 둘 수 있는 블록의 경우의 수를 미리 계산한 것도 멋지고 또다시 주목할만한 부분은 L모양의 블록을 비트로 표현할 때 square값에다가 각각의 cell값을 빼준 것이다. 생각하는 방식이 나와 다른 것 같다.

play함수 내에서 블럭을 놓을 수 있는지를 간단히 AND 연산으로 처리했고 블럭을 놓는 경우는 OR연산으로 처리했다. 고수들만이 이런 경지에 오르는 것이 아닐까 싶다.


'알고리즘 > algospot' 카테고리의 다른 글

카쿠로  (0) 2016.12.11
회전초밥  (0) 2016.08.01
블록게임  (0) 2016.08.01
조합게임  (0) 2016.07.25
ASYMTLING  (0) 2015.02.21
NUMB3RS  (0) 2015.02.21

조합게임

알고리즘/algospot 2016.07.25 21:27 Posted by 아는 개발자 아는 개발자

난 항상 이런 문제가 싫었다.


- 현재 상태에서 두 선수가 최선을 다했을때 승자는 누가 될 것인가.


여기서 두 선수가 최선을 다한다는 문제의 조건이 항상 마음에 들지 않았다. 도대체 두 선수가 최선을 다한다는 것을 어떻게 정의한다는 것인가? 어떤 경우가 최선을 다하는 것이고 어떤 경우는 최선을 다하지 않는 것인가?


하지만 알고리즘 문제해결전략 책을 탐독한 결과 이런 경우는 현재 상태로부터 가능한 모든 상태를 수를 고려했을때(컴퓨터의 빠른 연산 능력을 이용해) 내가 이길 수 있는지 없는지를 판독해내는 과정이다.


책에서 나온 예제로는 Tic Tac Toc가 있었다.


여기서 책에서 큰 깨달음을 얻은 부분이


"현재의 참가자는 모든 수를 둬 보면서 다음 상태 board에 대해서 이길 수 있는 수가 있으면 무조건 그 수를 선택하고 없으면 비기는쪽 아니면 지는 쪽을 선택해야" 한다는 것이다.


 
int canWin(char turn) {
	int i, j, ret;
	int state = retState();

	if (isFinished('o' + 'x' - turn)) return -1;
	if (memo[state] != -2) return memo[state];

	ret = 2;
	for (i = 0; i < 3; i++) {
		for (j = 0; j < 3; j++) {
			if (board[i][j] == '.') {
				board[i][j] = turn;
				ret = MIN(ret, canWin('o' + 'x' - turn));
				board[i][j] = '.';
			}
		}
	}

	if (ret == 2 || ret == 0) 
		return memo[state] = 0;

	return memo[state] = -ret;
}


즉 다음에 두는 수가 발생시키는 경우들에 대한 return값들 중에서 최대한 이기거나 지는 쪽으로 선택해야한다는 것이다.

이렇게 가정을 세우고 나면 각 참가자가 최선을 다해 경기를 한다는 조건이 만족할 수 있다.


중복되는 상태들은 메모마이제이션을 통해서 간단히 해결 할 수 있다.


이러한 개념은 중요한것 같다. 잘 참고해야겠다.

'알고리즘 > algospot' 카테고리의 다른 글

카쿠로  (0) 2016.12.11
회전초밥  (0) 2016.08.01
블록게임  (0) 2016.08.01
조합게임  (0) 2016.07.25
ASYMTLING  (0) 2015.02.21
NUMB3RS  (0) 2015.02.21

ASYMTLING

알고리즘/algospot 2015.02.21 12:31 Posted by 아는 개발자 아는 개발자

내가 스스로 풀때는 n개를 채울 때 대칭인 경우와 비대칭인 경우로 나누어서

접근하려고 했는데 그렇게 풀 필요가 전혀 없었다.

책에서 양 끝에서부터 채워가는 방식을 읽고 정말 놀랬다 ㄷㄷㄷㄷ

이렇게 생각하면 정말 쉽게 풀리는 구나... 

재귀함수의 매력에 놀랬고 저자의 천재성에 감탄하고 나의 부족함을 다시한번 깨달았다 ㅠㅠ

양끝이 대칭이면 내부는 비대칭이어야 하고

양끝이 비대칭이면 내부는 대칭이어야 한다. 이 경우로 모든 경우의 수를 만들 수 있었다...

dp로 문제를 해결하는 두 가지 조건

- 모든 경우의 수를 포함해야 하며

- 중복되는 경우가 있어선 안된다

를 다시 한번 실감하는 순간이었다


'알고리즘 > algospot' 카테고리의 다른 글

카쿠로  (0) 2016.12.11
회전초밥  (0) 2016.08.01
블록게임  (0) 2016.08.01
조합게임  (0) 2016.07.25
ASYMTLING  (0) 2015.02.21
NUMB3RS  (0) 2015.02.21

NUMB3RS

알고리즘/algospot 2015.02.21 12:15 Posted by 아는 개발자 아는 개발자

동적 계획법을 이용하면 풀기 편하다.

d[마을수][지난날수]로 자료형을 잡고

if(connected[현위치][마을])

d[현위치][날짜] += d[마을][날짜-1]/deg[마을]로

구할 수 있다.

그런데 제출하면 왜 틀리다고 나오는지 모르겠다;

책에있는데로 그대로 따라하는데... 

알고스팟 뭔가 좀 이상하다.... 물론 나한테 문제가 있는거지만 ㅠ

'알고리즘 > algospot' 카테고리의 다른 글

카쿠로  (0) 2016.12.11
회전초밥  (0) 2016.08.01
블록게임  (0) 2016.08.01
조합게임  (0) 2016.07.25
ASYMTLING  (0) 2015.02.21
NUMB3RS  (0) 2015.02.21