Search

'알고리즘'에 해당되는 글 83건

  1. 2017.04.21 SW 역량테스트 기출 문제집 분석 (4)
  2. 2017.04.05 10422
  3. 2016.12.11 카쿠로
  4. 2016.12.10 모듈러 나눗셈 연산 처리하기 (2)
  5. 2016.12.04 완전순열(교란순열)
  6. 2016.09.06 1937
  7. 2016.08.15 4095
  8. 2016.08.01 회전초밥
  9. 2016.08.01 블록게임
  10. 2016.07.30 11437
  11. 2016.07.30 LCA(Lowest Common Ancestor)
  12. 2016.07.25 조합게임
  13. 2016.07.24 2253
  14. 2016.07.24 11049
  15. 2016.07.24 2229
  16. 2016.07.23 Count sort
  17. 2015.10.17 4307
  18. 2015.10.16 1577
  19. 2015.10.16 1946
  20. 2015.10.15 2590
  21. 2015.10.14 1931
  22. 2015.10.11 11000
  23. 2015.10.09 2405
  24. 2015.10.09 2437
  25. 2015.10.03 2616
  26. 2015.09.29 2463
  27. 2015.09.13 9079
  28. 2015.09.08 2465
  29. 2015.09.07 Segment Tree
  30. 2015.09.05 SQRT Decomposition
  31. 2015.09.04 2457
  32. 2015.09.01 2481
  33. 2015.08.27 LIS를 O(nlogn)시간 내에 해결하는 방법
  34. 2015.08.26 1987
  35. 2015.08.26 c++ priority_queue에서 comparator 선언해주는 방법
  36. 2015.08.26 10217
  37. 2015.08.24 2638
  38. 2015.08.24 1238
  39. 2015.08.22 9470
  40. 2015.07.17 2515

SW 역량테스트 기출 문제집 분석

알고리즘/acmicpc 2017. 4. 21. 20:12 Posted by 아는 개발자

백준 온라인 저지에서 삼성 SW 역량테스트 기출 문제집을 발견 했다. 분명히 시험시간에 감독관이 외부에 유출하지 말라고(말아달라고) 했을 텐데 싸트 문제처럼 이것도 외부 유출은 막을 수 없나 보다. 재미 삼아 여기 있는 문제들을 한 번 풀어 봤는데 문제들이 공통적으로 뚜렷한 경향이 있었다. 이번 포스트에서는 (문제집에 올라온 기출 문제들이 모두 사실이라는 전제 하에) 기출 문제를 분석하고 취준생 입장에서 어떻게 준비하는 것이 좋을 지를 정리 해봤다.


기출 문제 분석


1. 시뮬레이션 문제가 대부분


대부분의 문제들이 고급 알고리즘 없이도 풀 수 있다. 여기서 고급 알고리즘은 다익스트라나 최소 스패닝 트리 같이 대학교 알고리즘 강의에서 배우는 내용들을 말한다. 물론 기출로 나온 문제들을 고급 알고리즘을 적용한다면 좀 더 빠르게 풀 수도 있을 것이다. 하지만 문제의 조건으로 주어지는 N값이 작기 때문에(대부분의 문제가 100 이하로 주어진다) 적용한 알고리즘이 O(N^2)이든 O(N^3)이든 중요치 않다. 모든 경우에 대해서 탐색 할 수 있도록 코드를 작성 할 수 있으면 시간 초과 없이 맞출 수 있는 문제다.


2. 구현이 까다롭다.


그러나 실수하기 딱 좋은 조건들만 문제에 나왔다. 알고리즘 문제를 많이 풀어본 사람들도 지도 유형의 문제를 까다로워 하는데 여기 서는 거기에 한 술 더 떠서 지도를 회전시키고 기울이기까지한다. 싸트를 생략하는 대신 여기서 공간 능력을 테스트 해보려는 의도인지 모르겠으나 단순 구현이라고 하기엔 머리가 좀 아프다. 문제 자체는 이해하기 쉽고 풀이법도 빠르게 떠오르는데 막상 손을 대려면 소소한 조건들을 구현하는 것이 난감하고 어찌어찌 구현을 해내면 예상치 못한 예외 케이스들이 나와 디버깅 하는데 시간을 다 쓰게 된다. 실제로 13460 문제를 집에서 한 번 풀어봤는데 세로/가로 크기가 10이하인 것을 캐치해 모든 경우에 대해서 시뮬레이션 하는 것으로 방향을 잘 잡았으나 '빨간공/파란공이 인접했을 때 움직임을 어떻게 구현 할 것인가'를 놓고 꽤 고민했고 또 예상치 못한 케이스를 해결하는데 시간을 오래 썼다. 만약 시험장에서 긴장과 압박감 속에서 풀어야 했다면 결코 쉽지 않았을 것 같다.



어떻게 준비하는 것이 좋을까?


기출 문제들로만 미루어 봤을 때 여기선 '똑똑하지 않아도 구현은 제대로 할 줄 아는 프로그래머'를 원하는 것 같다. 구현하기 까다로운 문제들을 실수 없이 빠르게 구현해내기 위해선 자신만의 코딩 스타일을 가지는 것이 중요하다. 시험장에서 배열의 인덱스를 0에서부터 시작 할 지, 1에서부터 시작할지나 지도상의 동서남북 탐색 방법을 구현하는 것을 어떤 식으로 구현할 지 고민하면 너무 늦다. 문제의 다양한 조건들을 어떻게 대처 할 것인지 미리 훈련이 되어 있어야 되도록 실수 없이 한 번에 구현 할 수 있어야 한다.


1. 나만의 코딩 스타일을 가지기


글쓴이는 로봇 청소기 문제에서 회전 방법과 각 방향 별로 전진, 후퇴를 아래 코드로 구현 했다.


 
int dir_r[4] = { -1, 0, 1, 0 };
int dir_c[4] = { 0, 1, 0, -1 };
int process(int r, int c, int dir) {

	int cnt = 0;
	int befo_r = -1, befo_c = -1;
	int ret = 0;

	while (1) {

		....

		int turn_dir = (dir - 1 + 4) % 4;

		// turn left,,,
		if (r + dir_r[turn_dir] >= 0 && r + dir_r[turn_dir] < R &&
			c + dir_c[turn_dir] >= 0 && c + dir_c[turn_dir] < C) {

			int exist = 0;

			if (map[r + dir_r[turn_dir]][c + dir_c[turn_dir]] == 0)
				exist = 1;

			if (exist) {
				dir = turn_dir;
				r += dir_r[turn_dir];
				c += dir_c[turn_dir];
				continue;
			}
			else
				dir = turn_dir;
		}
		else
			dir = turn_dir;

	}

	return -1;
}


dir_r, dir_c 변수는 북,동,남,서 방향 별로 전진 할 시 변경해야 하는 행과 열의 변화 값을 갖고 있다. 현재 방향만 알면 앞으로 이동하게 되는 위치 값을 쉽게 표현 할 수 있게 된다(물론 뒤로 후퇴하는 것까지 가능!). 그리고 북,동,남,서의 순서는 각각 오른쪽으로 회전하는 순서다. 이는 곧 순서를 반대로만 하면 왼쪽으로 회전 하는 것까지 쉽게 표현 할 수 있다. turn_dir 변수에 왼쪽으로 회전하는 경우의 방향 값을 저장 해뒀다.


물론 위 방법이 최선이라고 할 수는 없다. 다만 나는 위 방식으로 구현할 때 가장 빠르고 실수도 없다. 각자 자신에게 익숙한 방식으로 구현 할 때 실수를 줄일 수 있다.


물론 실무에서는 자신만의 코드 스타일로 코드를 짤 경우 리뷰 받을 때는 상당히 피곤한 코멘트를 받게 되겠지만... 일단 합격을 해야 리뷰를 받을 수 있으니 자신이 최대한 실수 하지 않도록 훈련을 해두자.


2. 척박한 디버깅 환경에서 연습하기


코드 스타일을 만드는 것 뿐만 아니라 평소에 좋은 디버깅 툴을 되도록 사용하지 않는 훈련을 하는 것도 중요하다. 시험 볼 때는 비주얼 스튜디오를 사용하고 거기에 있는 모든 디버깅 기능들을 사용 할 수 있다고 하니 사용 방법만 알아두고 평소에는 되도록 사용하지 말자. 육상선수가 모래주머니를 달고 훈련 하는 것과 비슷하다고 할까, 되도록 원하는 코드를 한번에 구현 하는 연습을 해보는 것이 좋고 예상한 결과 값이 나오지 않더라도 자신의 코드에서 논리적으로 유추해서 파악하는 것이 중요하다. 처음에는 힘들지만 계속 해보면 자신이 어느 부분에서 반복적으로 실수하는 지 알 수 있고 고칠 수 있다. 글쓴이는 알고리즘 문제 풀 때는 되도록 우분투 Vim 에디터에서 문제를 푼다. 이런 훈련은 알고리즘 문제 뿐만 아니라 디버깅 환경이 척박한 실무에서도 도움이 된다.



(필자가 Vim에디터로 문제를 푸는 모습. 뱀 문제는 왜 틀렸는지 아직도 모르겠다)


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

SW 역량테스트 기출 문제집 분석  (4) 2017.04.21
10422  (0) 2017.04.05
1937  (0) 2016.09.06
4095  (0) 2016.08.15
11437  (0) 2016.07.30
2253  (0) 2016.07.24
  1. 아는개발자를알고싶은개발자 2017.10.16 23:09  댓글주소  수정/삭제  댓글쓰기

    이런 분석 글 너무 좋습니다! 감사합니다~

  2. 아는개발자팬 2017.10.30 23:46  댓글주소  수정/삭제  댓글쓰기

    멋있으세요!!!><

10422

알고리즘/acmicpc 2017. 4. 5. 23:03 Posted by 아는 개발자

문제를 보자마자 DP를 써야 한다는건 직감했는데 식을 어떻게 세워야 할지 쉽게 감이 오지 않았다. 가장 직감적으로 들었던 식은 이렇다.


문자열의 길이가 K인 경우의 식은 아래와 같이 구할 수 있다고 생각했다.


1. dp[K] = dp[K-2]

2. dp[K] += dp[2]*dp[K-2] + dp[4]*dp[K-4] + ... dp[K-2]*dp[2]


이미 괄호의 개수가 정해진 K-2개의 문자열에 괄호를 끼운다고 생각하면 반드시 올바른 괄호가 되므로 1번 식은 성립한다. 2번 식은 나머지 경우들을 처리하는 식인데, K개의 괄호식을 만든다고 생각할 때 앞부분에 해당하는 괄호의 경우의 수 와 뒷부분에 해당하는 괄호의 경우의 수를 곱해주면 길이가 K인 문자열을 구할 수 있다고 생각했다. 하지만 위의 식은 중복되는 경우의 수들을 처리하지 못한다.


만약 위의 식으로 K=6인 경우를 구하면


dp[2] = 1, ()

dp[4] = 2, (()) ()()


1번식에 의해 dp[6] = 2    ->     ((())), (()())

2번식에 의해 dp[6] += dp[2]*dp[4]     ->     ()(()), ()()()

       + dp[4]*dp[2]    ->    (())(), ()()()


'()()()' 라는 중복된 경우가 생겨버린다. DP를 사용하면서 중복된 경우가 생기지 않도록 식을 만들어야한다.


K개의 문자열의 앞부분과 뒷부분을 크게 A와 B로 나뉘어보자. 2번식에 따르면 A의 크기는 점점 커지고, B의 크기는 점점 작아질 것이다.



만약 크기가 달라지면서 생기는 모든 A영역들에 대하여 중복된 경우가 없다고 할 수 있다면, B영역에 대해서 생각 할 필요 없이 위 문자열은 중복되지 않았다고 정의 할 수 있다.



B영역내에서 중복이 있든 없든 문자열 전체로 보면 A 영역내에서 이미 특수성을 가지고 있기 때문에 고려할 대상이 아니다.

중복하지 않는 각 A 영역의 경우의 수는 어떻게 구할 것이냐? 이건 1번식을 통해서 이미 구했다. 1번식은 바로 전 문자열에서 괄호 두 개를 덮은 것이기 때문에 길이가 달라도 중복된 것이 생기지 않는다고 할 수 있다.


위 방법으로 DP식을 다시 정리해보자.


1. dp[K][0] = dp[K-2][0] + dp[K-2][1]    -> 이전 문자열에 괄호를 씌운 경우

2. dp[K][1] = dp[2][0]*(dp[K-2][0] + dp[K-2][1]) + dp[4][0]*(dp[K-4][0] + dp[K-4][1]) ... + dp[K-2][0]*(dp[2][0] + dp[2][1])


 
#include <stdio.h>

using namespace std;

#define MAXN 5005
#define MOD 1000000007

long long dp[MAXN+1][2];

void init() {
	dp[2][0] = 1;

	for(int i=3; i <= MAXN; i++) {
		if(i%2)
			continue;
		for(int j=2; j<i; j+=2) {
			dp[i][1] = (dp[i][1] + dp[j][0]*dp[i-j][0])%MOD;
			dp[i][1] = (dp[i][1] + dp[j][0]*dp[i-j][1])%MOD;
		}
		dp[i][0] = (dp[i-2][0] + dp[i-2][1])%MOD;
	}
}

int main()
{
	freopen("input.txt", "r", stdin);

	int tc, inp;

	init();
	scanf("%d", &tc);

	while(tc--) {
		scanf("%d", &inp);
		printf("%lld\n", (dp[inp][0] + dp[inp][1])%MOD);
	}


	return 0;
}


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

SW 역량테스트 기출 문제집 분석  (4) 2017.04.21
10422  (0) 2017.04.05
1937  (0) 2016.09.06
4095  (0) 2016.08.15
11437  (0) 2016.07.30
2253  (0) 2016.07.24

카쿠로

알고리즘/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

모듈러 나눗셈 연산 처리하기

알고리즘/자료구조 2016. 12. 10. 12:14 Posted by 아는 개발자

프로그래밍 문제에서 가끔 이런 연산을 요구하는 문제들이 있다.


(N/K) % MOD


N과 K의 값이 작으면 N과 K의 값을 먼저 계산 하고 나서 모듈러 연산을 취해주면 문제가 없다.


하지만 N과 K값이 64bit 이상으로 변수에 넣을 크기를 초과하는 경우 앞의 나눗셈 계산은 정상적인 값을 내놓지 않을 것이고 모듈러 연산은 정상이 아닌 값을 받아 처리해 결론적으로 잘못된 값을 낸다.


주로 N과 K를 팩토리얼로 받는 조합의 경우의 수를 구할 때 난감하다 -> nCr % MOD 인 경우


이런 경우를 해결 하기 위해 모듈러 연산의 나눗셈을 계산하는 특별한 방법이 존재한다.


모듈러 연산에서 나눗셈 N/K는 K로 나누는 대신에 K의 곱셈 역원(multiple inverse)를 곱하는 방식으로 이뤄진다. 곱셈 역원은 MOD(모듈러 연산으로 나누는 값)과 나누는 값 K가 서로소일때만 존재한다. 곱셈 역원을 구하는 방법은 다음과 같다.


modInv(K, MOD) = K^(MOD-2)%MOD


곱셈역원을 이용해 나눗셈을 다음과 같이 정리 할 수 있다.


(N/K) % MOD = (N * modInv(K, MOD-2))%MOD    (페르마의 소정리라고도 한다. 이해하긴 어려우니 일단 외우자)


하지만 여기서 MOD 값이 매우 크다면 (대부분 문제에서 1,000,000,007을 잡는다) K^(MOD-2) 까지 곱하는데 시간이 오래 소요될것이다. 그래서 이런 경우 최적화 할 방법도 같이 기억해두면 좋다.


1. 가장 간단한 방법은 지수의 제곱승을 이용하는 방법이다(이 테크닉의 정확한 이름을 모르겠다)


예를들어 A^5 을 구한다고 한다면, A를 다섯번 곱해 A*A*A*A*A 구하는 방법이 있지만 다른 방법은 A*(A^2)*(A^2) 로 구하는 방법도 있다. A^2를 한 번만 구하면 되므로 기존 방법보다 곱셈의 횟수를 줄일 수 있다. 시간 복잡도는 O(logMOD)이다.


코드는 이렇다

 
long long modInv(long long a, int M) {
	if (M == 1)
		return a;
	if (M == 0)
		return 1;

	long long  tmp = modInv(a, M / 2);
	if (M % 2)
		return (long long)((long long)((tmp*tmp) % MOD)*a) % MOD;
	else
		return (long long)(tmp*tmp) % MOD;
}


2. O(logMOD)말고 O(1)에 해결하는 방법도 있다고 한다. 이건 이 포스트를 참고하자. 나도 증명은 잘 모르겠다.


http://koosaga.myungwoo.kr/entry/%EC%9D%B4%ED%95%AD%EA%B3%84%EC%88%98-nCr-mod-p-%EA%B3%84%EC%82%B0%ED%95%98%EA%B8%B0


위 포스트 글을 코드로 옮기면 이렇다.

 
	for (int i = 2; i <= MAX; i++) {
		inv[i] = (-(MOD / i)*inv[MOD%i] + MOD)%MOD;
		if (inv[i] < 0)
			inv[i] += MOD;
		inc[i] = (inc[i - 1] * inv[i]) % MOD; // 팩토리얼 곱셈역원 계산
	}


모듈러 연산은 진짜 왠만하면 피하고 싶은 문제인데, 그래도 이번 기회에 테크닉이라도 배워 뒀으니 앞으로 자주 써먹어야겠다.

'알고리즘 > 자료구조' 카테고리의 다른 글

모듈러 나눗셈 연산 처리하기  (2) 2016.12.10
완전순열(교란순열)  (0) 2016.12.04
LCA(Lowest Common Ancestor)  (0) 2016.07.30
Count sort  (0) 2016.07.23
Segment Tree  (0) 2015.09.07
SQRT Decomposition  (0) 2015.09.05
  1. 깜장호랭 2017.10.07 22:33  댓글주소  수정/삭제  댓글쓰기

    좋은 설명 감사합니다. O(1)방법에서 inv[1] = 1; 이 꼭 있어야 하네요. 쉽게 찾을 수 있는 것이지만, 코드에서 빠져 있어서요.

완전순열(교란순열)

알고리즘/자료구조 2016. 12. 4. 20:52 Posted by 아는 개발자

어떤 배열의 원소 Xi의 위치가 i라고 할 때 모든 원소들이 자기의 위치에 존재하지 않을 때 이를 완전 순열이라고 한다.


 X2

X1 

X4 

X3 


점화식을 통해 원소의 개수에 따라 완전순열의 개수를 구할 수 있다.


공식은 다음과 같다


a(n) = (n-1) * (a(n-1) + a(n-2))


증명을 하면,


1 부터 N까지 오름 차순으로 이뤄진 배열이 있다고 하자 여기서 배열내의 원소중 1의 위치를 X로 옮기려고 한다. 이럴 경우 두가지 경우가 발생한다.


- X를 1의 위치로 옮기는 경우 -> N-2의 개수로 완전순열을 구하는 경우와 같다.

- X를 1의 위치로 옮기지 않는 경우 -> N-1의 개수로 완전순열을 구하는 경우와 같다.


1이 선택 할 수 있는 X 의 개수는 N-1개 이므로 이를 점화식으로 나타내면 위와 동일하게


a(N) = (N-1) * (a(N-1) + a(N-2)) 가 나온다.


위의 경우처럼 단순히 원소들이 자기의 위치에 존재하지 않는 경우만 생각하면 별 쓰임이 없을 것 같은데,

여러 원소들을 분산해서 써야하는 경우를 생각하면 쓸데가 있다.

(결론은 기억은 해두자)

'알고리즘 > 자료구조' 카테고리의 다른 글

모듈러 나눗셈 연산 처리하기  (2) 2016.12.10
완전순열(교란순열)  (0) 2016.12.04
LCA(Lowest Common Ancestor)  (0) 2016.07.30
Count sort  (0) 2016.07.23
Segment Tree  (0) 2015.09.07
SQRT Decomposition  (0) 2015.09.05

1937

알고리즘/acmicpc 2016. 9. 6. 18:50 Posted by 아는 개발자

모든 경로를 탐색하려고 하면 경우의 수가 무척 많아져서 어렵다. 여기서는 문제의 조건을 잘 살펴야 한다.


- 판다는 상,하,좌,우 중 하나의 경로로 이동한다

- 대나무의 양은 증가하는 순서여야 한다.


위 두가지 조건만을 이용해서 dp를 만들어 줄 수 있다.


dp[x][y]는 어떤 위치(x,y)로 도달 할 때 판다가 최대 살 수 있는 일 수를 가지고 있다고 하자.


그럼 다음과 같은 점화식을 적용 할 수 있다.


dp[x][y] = (상하좌우에 있는 대나무중 현재 위치의 대나무보다 양이 작은 값들의 dp중 가장 큰 것) + 1


이해를 돕기 위해 그림으로 부연 설명을 하면..

파란색으로 칠해둔 위치의 dp값을 업데이트 하려고 한다. 이때 파란색 위치로 접근 할 수 있는 경로는 (x,y)위치의 상하좌우중 (x,y)의 위치보다 대나무 수가 적은 곳(상, 우)이다. 상, 우의 dp값중 가장 큰 값(2)에서 하루를 더 살 수 있는 것으로 (x,y)의 위치에 도달 할 때는 판다는 최대 3일을 살 수 있다.


위 알고리즘을 적용하려면 대나무의 수가 적은 순서대로 탐색을 해야한다. 그렇지 않으면 중간에 누락되는 경로가 생길 수 있다.


반드시 대나무가 증가하는 순서대로 진행되므로 circle이 생기지 않기 때문에 위 알고리즘 만으로 모든 경우를 포함 할 수 있다.


 
#include<cstdio>
#include<algorithm>

#define MAX(a, b) ((a) > (b) ? (a) : (b))

using namespace std;

struct Node {
	int val, r, c;
};

int map[505][505];
int dp[505][505];

Node node[500 * 500];

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

bool compare(Node a, Node b) {
	if (a.val < b.val)
		return true;
	return false;
}

int main() {
	int N, i, j, nr;
	int r, c, val, ans;

	scanf("%d", &N);

	nr = 0;
	for (i = 1; i <= N; i++){
		for (j = 1; j <= N; j++) {
			scanf("%d", &map[i][j]);
			node[nr].r = i;
			node[nr].c = j;
			node[nr++].val = map[i][j];
		}
	}

	sort(&node[0], &node[nr], compare);
	ans = 0;

	for (int i = 0; i < nr; i++) {
		r = node[i].r, c = node[i].c, val = node[i].val;

		dp[r][c] = 1;
		for (int j = 0; j < 4; j++) {
			if (map[r][c] > map[r + dr[j]][c + dc[j]]) {
				dp[r][c] = MAX(dp[r][c], dp[r + dr[j]][c + dc[j]] + 1);
				ans = MAX(ans, dp[r][c]);
			}
		}
	}

	printf("%d\n", ans);

	return 0;
}

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

SW 역량테스트 기출 문제집 분석  (4) 2017.04.21
10422  (0) 2017.04.05
1937  (0) 2016.09.06
4095  (0) 2016.08.15
11437  (0) 2016.07.30
2253  (0) 2016.07.24

4095

알고리즘/acmicpc 2016. 8. 15. 21:54 Posted by 아는 개발자

행렬안에서 1로 이루어진 최대 정사각형을 찾는문제.


가장 쉽게 생각한다면 모든 점에서 만들 수 있는 최대 정사각형을 탐색해보는 방법이 있지만 이럴경우 O(N^4)로 시간초과가 날 수 밖에 없다. 하지만 구하고자하는 사각형의 형태가 정사각형인점을 잘 이용하면 다이나믹 프로그래밍을 이용해 O(N^2)안에 해결 할 수 있다.


어떠한 위치에서 정사각형을 만들 때, 이전에 만들어진 정사각형의 정보를 활용할 수 있는 방법을 생각해보자.


4번(X, Y) 위치를 꼭지점으로 하는 정사각형을 만들려고하자. 그러면 4번위치 주위에 1, 2, 3번의 사각형들을 생각해볼 수 있다.


- 1번은 (X-1, Y-1)을 오른쪽 아래 꼭지점으로 할 때 가장 큰 정사각형이다.

- 2번은 4번에서 위로 그을 수 있는 최대 선분의 길이다.

- 3번은 4번에서 왼쪽으로 그을 수 있는 최대 선분의 길이다.


4번 위치를 꼭지점으로 하는 정사각형은 1, 2, 3번 사각형의 조합으로 만들어진다. 여기서 1, 2, 3번의 각각의 선분의 크기를 비교해가면서 다음과 같이 점화식을 정해줄 수 있다.


dp[x][y] = min(row[x][y], col[x][y], dp[x-1][y-1]+1)  



 
#include<stdio.h>
#define MAX 1001

#define MIN(a, b) ((a) < (b) ? (a) : (b))

int dp[MAX][MAX];
int conti[MAX][MAX][2];	// row : 0, col : 1

int map[MAX][MAX];

int main() {
	int R, C;
	int i, j, ans;

	while (1) {
		scanf("%d %d", &R, &C);

		ans = 0;

		if (R == 0 && C == 0)
			break;

		for (i = 1; i <= R; i++)
			for (j = 1; j <= C; j++) {
				scanf("%d", &map[i][j]);
				dp[i][j] = conti[i][j][0] = conti[i][j][1] = 0;
			}


		for (i = 1; i <= R; i++)
			for (j = 1; j <= C; j++) {
				if (!map[i][j])
					continue;
				conti[i][j][0] = conti[i - 1][j][0] + 1;
				conti[i][j][1] = conti[i][j - 1][1] + 1;

				dp[i][j] = MIN(dp[i - 1][j - 1] + 1, MIN(conti[i][j][0], conti[i][j][1]));

				if (dp[i][j] > ans)
					ans = dp[i][j];
			}

		printf("%d\n", ans);
	}

	return 0;
}

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

10422  (0) 2017.04.05
1937  (0) 2016.09.06
4095  (0) 2016.08.15
11437  (0) 2016.07.30
2253  (0) 2016.07.24
11049  (0) 2016.07.24

회전초밥

알고리즘/algospot 2016. 8. 1. 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. 8. 1. 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

11437

알고리즘/acmicpc 2016. 7. 30. 14:21 Posted by 아는 개발자

LCA를 푸는 문제다. LCA 최적화 알고리즘은 이미 정리해두었으니 넘기자.


문제에 주어진 간선을 가지고 어떻게 트리의 형태로 만드느냐가 LCA를 풀기 위한 조건이다.


일반적으로 간선에 대한 자료구조들은 2차원 배열을 이용해서 표현하지만 N이 10000을 넘어가면 2차원 배열의 최대 크기를 초과하게된다.

C++에서는 vector를 사용해서 위와같은 문제를 간단히 해결 할 수 있지만 경우에 따라서 vector를 사용하지 못하는 상황도 존재한다.

간선 정보들을 필요할 때 마다 신속히 접근하는 자료구조가 중요한데 매번 모든 간선 정보O(N)를 찾아볼 수도 없을 노릇이다.


이런 경우에는 특정 경우 대해서 정렬을 해주는 방법이 유용하다.


간선에 대한 정보를 from들에 대해서 정렬을 해주고 각각의 시작점을 확인해서 찾아 볼 수 있다.


 

bool compare(Edge a, Edge b) {
	if (a.from < b.from)
		return true;
	return false;
}

int main() {

	for (i = 0; i < N - 1; i++) {
		scanf("%d %d", &from, &to);
		edge[nredges].par = from, edge[nredges].child = to;
		nredges++;
		edge[nredges].par = to, edge[nredges].child = from;
		nredges++;
	}

	sort(&edge[1], &edge[nredges], compare);

	for (i = 0; i < nredges; i++) {
		if (!stIdx[edge[i].par])
			stIdx[edge[i].par] = i;
	}

	queue[nrque++] = 1;

	for (i = 0; i < nrque; i++) {
		front = queue[i];
		if (visited[front])
			continue;
		visited[front] = 1;
		for (j = stIdx[front]; edge[j].par == front; j++) {
			if (visited[edge[j].child])
				continue;
			child = edge[j].child;
			queue[nrque++] = child;
			depth[child] = depth[front] + 1;

			parent[child][0] = front;
			for (k = 1; k < 20; k++) 
				parent[child][k] = parent[parent[child][k - 1]][k - 1];
		}
	}

	scanf("%d", &M);

	return 0;

}


(*여기서는 방문 순서는 중요하지 않기 때문에 to에 대해서는 정렬을 해주지 않았지만 특정한 to에 대해서 접근이 필요하다면 to에 대해서도 추가적인 정렬을 수행해 from에 대한 접근(O(1)) + to에 대한 이진탐색(O(log(M)) M은 동일한 from 간선 개수 로 빠르게 접근 할 수 있다.)


이렇게 간선 정보들을 정렬해서 정리해두었으면 이제 트리의 형태를 만들어야하는데


이거는 BFS로 구현하던지 아니면 DFS로 구현하던지 하면 된다.


나는 BFS가 사용하기 편해 BFS로 구현했다.

각각의 노드들을 한 번만 방문하면 된다는 점을 유의하자


 
	for (i = 0; i < nrque; i++) {
		front = queue[i];
		if (visited[front])
			continue;
		visited[front] = 1;
		for (j = stIdx[front]; edge[j].par == front; j++) {
			if (visited[edge[j].child])
				continue;
			child = edge[j].child;
			queue[nrque++] = child;
			depth[child] = depth[front] + 1;

			parent[child][0] = front;
			for (k = 1; k < 20; k++) 
				parent[child][k] = parent[parent[child][k - 1]][k - 1];
		}
	}

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

1937  (0) 2016.09.06
4095  (0) 2016.08.15
11437  (0) 2016.07.30
2253  (0) 2016.07.24
11049  (0) 2016.07.24
2229  (0) 2016.07.24

LCA(Lowest Common Ancestor)

알고리즘/자료구조 2016. 7. 30. 13:24 Posted by 아는 개발자

트리 내부에 있는 두개의 노드 사이의 최저 공통 조상을 효율적으로 찾아주는 자료구조이다.


가장 간단히 생각 할 수 있는 구현방법(모든 모드를 일일히 탐색하는)으로는 최저 공통 조상을 찾는데 O(N)의 시간이 걸리지만


최적화된 LCA 알고리즘으로는 O(logN)시간만에 구할 수 있다.


LCA 알고리즘에서 트리의 노드들은 자신의 부모노드에 대한 정보외에 현재 높이에서 2^i 위에 위치한 조상노드에 대한 정보도 가지고 있다.

그림으로 표현하면 다음과 같다.


(자신의 부모노드 뿐만 아니라 2^i위치에 해당하는 조상노드의 정보를 가지는 것은 빠른 탐색을 할 때 유용하게 쓰인다.)


알고리즘의 절차는 다음과 같다.


1. 두 노드의 depth가 다르다면 depth를 맞춰준다.

* 이때 일일히 모든 부모노드를 방문하는 것이 아니라, 2^i에 대한 높이의 정보를 이용하면 신속하게 동일한 depth를 가지는 곳으로 이동 할 수 있다.

코드는 다음과 같다.



2. 가장 높은 조상부터 찾도록 하고 두 노드간의 공통조상이 다른 경우에는 그 위치부터 다시 조상을 찾도록 한다.



두 노드가 동일하거나, 두 노드의 공통조상이 모두 동일하다면 가장 낮은 조상을 return한다.


여기서 왜 공통조상이 아닐 때 재귀함수를 부르는지 이해가 가지 않았었다. 그래서 아예 가장 낮은 높이부터 조상들을 비교해 동일한 조상이 나오면 return하도록 했는데 이런경우 문제점은 공통 조상은 찾아주는데 최저 공통조상은 찾아줄 수 없다(높이 자체가 2의 지수 형태로 되어 있기 때문). 이때 찾는 공통 조상은 현재 위치에서 2의 지수 높이에 있는 공통 조상중 가장 낮은 위치에 있는 공통조상을 찾아주게된다.


동일한 level을 맞춰주기 위해 2^i의 형태로 이동했던 것 처럼 위 경우에도 가장 낮은 부분 부터 하나씩 올라가야 한다.


LCA 알고리즘의 가장 키 포인트는


2의 지수승에 해당하는 자료구조를 만들 때 최적화 효과를 볼 수 있다는것.


이런 아이디어는 LCA뿐만 아니라 다른 형태의 문제를 풀 때도 유용하게 사용 할 수 있을 것 같다.

'알고리즘 > 자료구조' 카테고리의 다른 글

모듈러 나눗셈 연산 처리하기  (2) 2016.12.10
완전순열(교란순열)  (0) 2016.12.04
LCA(Lowest Common Ancestor)  (0) 2016.07.30
Count sort  (0) 2016.07.23
Segment Tree  (0) 2015.09.07
SQRT Decomposition  (0) 2015.09.05

조합게임

알고리즘/algospot 2016. 7. 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

2253

알고리즘/acmicpc 2016. 7. 24. 13:10 Posted by 아는 개발자

위 문제는 가속/감속을 최대 1 만큼 한다는 것에 힌트가 있다.


돌의 개수가 최대 10000개 일 때 최대로 낼 수 있는 속도는 142이다. K*(K+1)/2 < 10000

현재 위치의 돌과 돌에 도착할 때의 속도로 새롭게 정점을 표현한다면 최대 정점의 개수는 10000 * 142 로 배열 내에서 선언이 가능한 범위가 된다.


dp[N][V] : N번째 돌에 V번째 속도로 도착할 때의 최소 점프횟수


이제 각각의 정점을 방문해서 다음 위치에 움직일 때 최소 횟수로 움직이는 값을 업데이트 해주면 된다.


 
#include<cstdio>

#define MAXN 10000

int dp[MAXN + 5][200];
int forbid[MAXN];

int main() {
	int N, M;
	int i, j, tmp;

	int ans;

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

	while (M--) {
		scanf("%d", &tmp);
		forbid[tmp] = 1;
	}

	dp[1][0] = 1;

	for (i = 1; i <= N; i++) {
		if (forbid[i])
			continue;
		for (j = 0; j < 200; j++) {
			if (dp[i][j]) {
				if (i + j <= N) {
					if (dp[i + j][j] == 0 || dp[i + j][j] > dp[i][j] + 1)
						dp[i + j][j] = dp[i][j] + 1;
				}
				if (i + j + 1 <= N) {
					if (dp[i + j + 1][j + 1] == 0 || dp[i + j + 1][j + 1] > dp[i][j] + 1)
						dp[i + j + 1][j + 1] = dp[i][j] + 1;
				}
				if (j - 1 > 0 && i + j - 1 <= N) {
					if (dp[i + j - 1][j - 1] == 0 || dp[i + j - 1][j - 1] > dp[i][j] + 1)
						dp[i + j - 1][j - 1] = dp[i][j] + 1;
				}
			}
		}
	}

	ans = 0;

	for (i = 0; i < 200; i++) {
		if (dp[N][i] != 0)
			if(ans == 0 || ans!=0 && dp[N][i] < ans)
				ans = dp[N][i];
	}
		
	printf("%d\n", ans - 1);

	return 0;

}

문제에서 제시한 정점에서 벗어나 새로운 정점을 만들어주는 방식이 중요하다. DP문제를 풀 때는 위 방식이 핵심이다.


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

4095  (0) 2016.08.15
11437  (0) 2016.07.30
2253  (0) 2016.07.24
11049  (0) 2016.07.24
2229  (0) 2016.07.24
4307  (0) 2015.10.17

11049

알고리즘/acmicpc 2016. 7. 24. 12:14 Posted by 아는 개발자

DP의 예시로 알고리즘 책에서 자주 나오는 유형


DP는 배열의 인덱스 값을 얼마나 유용하게 잘 사용하느냐에 달려있는 것 같다.


dp[FROM][TO] : FROM부터 TO까지의 행렬들을 곱할 때의 값


위 값을 통해서 지속적으로 업데이트 해나가면 문제를 풀 수 있다.


 
#include<cstdio>

#define MAXN 500

int dp[MAXN][MAXN];

int data[MAXN][2];

int main() {
	int N;
	int i, j, len;

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

	for (i = 0; i < N; i++)
		scanf("%d%d", &data[i][0], &data[i][1]);

	for (len = 1; len < N; len++) {
		for (i = 0; i + len < N; i++) {
			for (j = i; j < i+len; j++) {
				if (dp[i][i + len] == 0 ||
					dp[i][i + len] > dp[i][j] + dp[j + 1][i + len] + data[i][0] * data[j + 1][0] * data[i + len][1])
					dp[i][i + len] = dp[i][j] + dp[j + 1][i + len] + data[i][0] * data[j + 1][0] * data[i + len][1];
			}
		}
	}

	printf("%d\n", dp[0][N - 1]);

	return 0;

}

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

11437  (0) 2016.07.30
2253  (0) 2016.07.24
11049  (0) 2016.07.24
2229  (0) 2016.07.24
4307  (0) 2015.10.17
1577  (0) 2015.10.16

2229

알고리즘/acmicpc 2016. 7. 24. 11:38 Posted by 아는 개발자

나이순으로 정렬이 이미 되었으니 해야 할 일은 여기서 연속된 배열을 어떻게 여러개로 나눠서 최대의 점수를 내는 조를 만드느냐이다.

(문제가 나이 정렬을 해주지 않고 냈으면 더 어려울 뻔 했는데 친절하게 나이 정렬을 해준 뒤에 문제를 풀라고 했다)


위 문제는 DP로 풀 수 있다. 먼저 다음과 같은 배열을 선언한다


dp[FROM][TO] : FROM학생부터 TO학생까지 조를 짤 때의 최대의 점수가 나오는 경우

목표는 FROM, TO까지 무조건 최대의 점수를 가지는 것이며 어떻게 분할 되는지는 상관하지 않는다


FROM에서 TO까지의 범위를 차근차근 늘려서 1번 학생부터 N번 학생가지 포함되는 경우까지 만들어준다.


 
#include<cstdio>

#define MAXN 1000

#define MAX(A, B) ((A) > (B) ? (A) : (B))
#define MIN(A, B) ((A) < (B) ? (A) : (B))
#define INF 10005


int dp[MAXN + 5][MAXN + 5];

int arr[MAXN + 5];

int main() {
	int N, i, j, len;

	int _min, _max;

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

	for (i = 0; i < N; i++)
		scanf("%d", &arr[i]);

	for (len = 0; len < N; len++) {
		for (i = 0; i + len < N; i++) {
			_min = INF, _max = 0;

			for (j = i; j <= i + len; j++) {
				_min = MIN(_min, arr[j]);
				_max = MAX(_max, arr[j]);

				dp[i][i + len] = MAX(dp[i][j] + dp[j + 1][i + len], dp[i][i+len]);
			}

			dp[i][i + len] = MAX(_max - _min, dp[i][i + len]);
		}
	}

	printf("%d\n", dp[0][N - 1]);

	return 0;
}

하지만 위 방법은 O(N^3)이다. 2초 제한시간에 아슬아슬하게 통과했지만(772ms) 원칙상으로는 통과해선 안된다.
다른 사람들의 코드를 봤는데 상위랭크는 대부분 O(N^2)로 풀었다.

나와 푼 방식의 개념은 기본적으로 비슷하나 이분들은 FROM은 어차피 1이 될 것이기 때문에 이 경우를 무시하고 dp[TO]만 가지고 풀었다.

새로운 dp[TO]를 만들기 위해 TO' < TO에서 dp[TO'] + (TO'+1 부터 TO 까지 조를 짤 경우)에 대한 최대값을 계속 업데이트 해줬다.

내 방법보다 한 번 더 추상화해서 문제에 접근한 방식이다.

정말 고수는 다르구나 하는 생각이 들었다.


 
    dp[1] = fabs(arr[1]-arr[0]);
    for(int i=2; i<n; i++)
    {
        maxnum=minnum=arr[i];
        for(int j=i; j>0; j--)
        {
            maxnum = max(maxnum, arr[j]);
            minnum = min(minnum, arr[j]);
            dp[i] = max(dp[i], maxnum-minnum+dp[j-1]);
        }
    }
    printf("%d", dp[n-1]);

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

2253  (0) 2016.07.24
11049  (0) 2016.07.24
2229  (0) 2016.07.24
4307  (0) 2015.10.17
1577  (0) 2015.10.16
1946  (0) 2015.10.16

Count sort

알고리즘/자료구조 2016. 7. 23. 19:47 Posted by 아는 개발자

quicksort나 mergesort처럼 일반적인 sorting알고리즘은 O(NlogN)을 가지나 sorting에 사용되는 값들을 사전에 알고 있는 경우에는 시간복잡도를 O(N)까지 단축 시킬 수 있다. 그중에서도 가장 강력하게 사용되는 알고리즘이 Count sorting이다.


Count sorting은 정렬에 쓰이는 값이 충분히 작은 경우(배열의 최대 크기가 될 수 있는 값보다 작아야 한다)에 주로 사용할 수 있다. 배열의 인덱스는 이미 자동적으로 정렬되있으니 수열에 포함된 값 각각의 개수를 배열의 인덱스에 해당하는 값에 저장해둔 후 그 그 개수를 참고해서 정렬하는 방식이다.


글로 설명하기에는 어려우니 예를 들어보자. 


5 3 6 7 4 5 인 수열을 정렬한다고 하자. 위 수열의 각 값의 개수를 관리하는 배열을 count[10]라 하자. 그러면 count의 값은 다음과 같을 것이다.


count[0] = 0

count[1] = 0

count[2] = 0

count[3] = 1

count[4] = 1

count[5] = 2

count[6] = 1

count[7] = 1

count[8] = 0

count[9] = 0


정렬하고자한 수열의 값들은 이미 배열의 index를 통해서 자동적으로 정렬이 되었다. 이제 각각의 개수만큼 표현만 해주면 된다.


count[0] = 0 -> 수열에 포함 안됨

count[1] = 0 -> 수열에 포함 안됨

count[2] = 0 -> 수열에 포함 안됨

count[3] = 1 -> 3

count[4] = 1 -> 3, 4

count[5] = 2 -> 3, 4, 5, 5

count[6] = 1 -> 3, 4, 5, 5, 6

count[7] = 1 -> 3, 4, 5, 5, 6, 7

count[8] = 0 -> 수열에 포함 안됨

count[9] = 0 -> 수열에 포함 안됨


생각해보면 정말 자명하고 직관적이어서 쉽다. 구현도 쉬워서 자주자주 써먹을 수 있을 것 같으나 써야할 때를 자주 깜빡한다.


가장 최근에 푼 문제중에는 좌표상에 표현되는 값을 x, y로 정렬해야 했는데 조건이 x, y < 1000000이었다. 이때도 count sort를 사용해서 정렬 할 수 있었는데 구현도 어려운 quicksort를 구현하느라 시간을 한참 소비했다 ㅡㅡ


다른분이 정렬한 코드를 참고해서 새롭게 작성한 후 올린다..




'알고리즘 > 자료구조' 카테고리의 다른 글

완전순열(교란순열)  (0) 2016.12.04
LCA(Lowest Common Ancestor)  (0) 2016.07.30
Count sort  (0) 2016.07.23
Segment Tree  (0) 2015.09.07
SQRT Decomposition  (0) 2015.09.05
LIS를 O(nlogn)시간 내에 해결하는 방법  (0) 2015.08.27

4307

알고리즘/acmicpc 2015. 10. 17. 22:58 Posted by 아는 개발자

처음에는 '와 이 문제 장난아니다. 어떻게 풀어야되냐, 감이안온다 ㄷㄷ' 라 생각했는데 자세히 생각해보니 매우 간단한 문제임을 발견했다.


두 개미가 부딪히면 다른 방향으로 이동한다. 이건 둘이 교차한다는 의미랑 같다. 어차피 충돌하면 한 개미는 왼쪽으로 이동하고 다른 개미는 오른쪽으로 이동한다. 그러면 이건 교차한다고 봐도 무방하다. 


결국 막대기를 벗어나는 개미들 중에 가장 오랜 시간이 걸리는 애를 고르면 되는 문제..


 
#include<cstdio>

int main(){
	int tc;
	scanf("%d", &tc);

	while(tc--){
		int len, n, loc, 
			min=0, max=0;
		scanf("%d %d", &len, &n);
		while(n--){
			scanf("%d", &loc);
			int cur_min, cur_max;
			if(loc > len-loc)
			{
				cur_min = len-loc;
				cur_max = loc;
			}
			else{
				cur_min = loc;
				cur_max = len-loc;
			}

			if(cur_min > min)
				min = cur_min;
			if(cur_max > max)
				max = cur_max;
		}
		printf("%d %d\n", min, max);
	}

	return 0;
}

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

11049  (0) 2016.07.24
2229  (0) 2016.07.24
4307  (0) 2015.10.17
1577  (0) 2015.10.16
1946  (0) 2015.10.16
2590  (0) 2015.10.15

1577

알고리즘/acmicpc 2015. 10. 16. 22:17 Posted by 아는 개발자

아 도로문제 ㅠㅠ

예전부터 이상하게 틀리던 문젠데 오늘 풀었는데 또 틀렸다. 대체 뭐가 문제인가 해서 친구한테 물어봤더니 장애물 저장방식에 문제가 있다고 했다...


사실 이문제는 별로 어려운 문제는 아닌데말이다... 

내 실수는 0 0 0 1 1 0 1 1 이면 0 0 에서 1 0 은 장애물이 없는데 장애물이 있는것으로 인식한다는 것이다...


괜히 인접행렬 형태로 간소화해서 풀어보겠다고 했다가 틀렸다. 기하학 문제에선 여러가지 경우를 동시에 생각했어야 하는데 크으... 생각하지 못했다. 반성할 부분이다.


 
#include<cstdio>

using namespace std;

struct obstacle{
	int ax, ay;
	int bx, by;
};

long long map[105][105];

obstacle obs[105];

int main(){
	int n, m, k;
	int a, b, c, d;

	scanf("%d %d", &n, &m);


	scanf("%d", &k);

	for(int i=0; i<k; i++){
		scanf("%d %d %d %d", &obs[i].ax, &obs[i].ay, &obs[i].bx, &obs[i].by);
	}

	map[0][0]=1;

	for(int i=0; i<=n; i++)
		for(int j=0; j<=m; j++){
			bool up=true, left=true;
			for(int piv=0; piv<k; piv++){

				if(i>0){
					if(i-1 == obs[piv].ax && j==obs[piv].ay && i==obs[piv].bx && j==obs[piv].by)
						up=false;
					if(i-1 == obs[piv].bx && j==obs[piv].by && i==obs[piv].ax && j==obs[piv].ay)
						up=false;

				}else
					up=false;
				if(j>0){
					if(i == obs[piv].ax && j-1==obs[piv].ay && i==obs[piv].bx && j==obs[piv].by)
						left=false;
					if(i == obs[piv].bx && j-1==obs[piv].by && i==obs[piv].ax && j==obs[piv].ay)
						left=false;
				}
				else
					left=false;
			}
			if(up)
				map[i][j] += map[i-1][j];
			if(left)
				map[i][j] += map[i][j-1];
		}

	printf("%lld\n",map[n][m]);

	return 0;
}

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

2229  (0) 2016.07.24
4307  (0) 2015.10.17
1577  (0) 2015.10.16
1946  (0) 2015.10.16
2590  (0) 2015.10.15
1931  (0) 2015.10.14

1946

알고리즘/acmicpc 2015. 10. 16. 02:03 Posted by 아는 개발자

진짜 문제를 무지하게 꼼꼼히 읽어야 한다. 문제 잘못 이해하면 바로 틀린다. 이 문제를 풀때 나는 생각보다 빨리 서류심사 결과 또는 면접 성적으로 정렬해야 하는것을 깨달았다. 


하지만 여기서 부터 꼬이기 시작했는데 서류심사 1등의 면접 성적 만큼 뒤에있는 서류 심사 순위는 모두 커버된다는 괴상한 논리를 펴기 시작했다. 서류 심사가 떨어지고 면접심사도 동시에 떨어질 수 잇는 것인데도 나는 혼자만의 논리에 빠져서 이상하게 문제를 질질 끌었다..


예제문제부터 제대로 풀지 않았다. 누구 누구가 합격한다는 힌트만 줘도 이렇게 뻘짓은 하지 않았을 것 같다. 하지만 뭐 이건 내 실수니...


문제자체는 많이 어렵지는 않았던 것 같다. 일단 서류 순위로 정렬한다. 서류 1등은 면접과 상관없이 독보적이므로 무조건 포함될 수 밖에 없다. 그 뒤로는 서류 순위대로 추가해주는데 이떄 자신의 앞에 있는 애보다 면접 순위가 높아야 한다. 추가 할 때마다 면접 순위를 계속 업데이트 해주어서 O(N)에 해결 할 수 있다.


하 그건 그렇고 이렇게 뻘짓해서 시간 보내니 정말 아쉽다... 실전에는 이러면 안되는데...


 
#include<cstdio>
#include<algorithm>

#include<fstream>

using namespace std;

pair<int, int> d[100005];

int main(){
	int tc;

	ifstream ifp("input.txt");

	ifp>>tc;
	//scanf("%d", &tc);

	while(tc--){
		int n;

		ifp>>n;
		//scanf("%d", &n);
		for(int i=0; i<n; i++)
			ifp>>d[i].first>>d[i].second;
			//scanf("%d %d", &d[i].first, &d[i].second);
		sort(d, d+n);

		int ends = d[0].second;
		int res = 1;

		for(int piv=1; piv<n; piv++){
			if(d[piv].second < ends){
				res++;
				ends = d[piv].second;
			}
		}
		printf("%d\n", res);
	}

	return 0;
}

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

4307  (0) 2015.10.17
1577  (0) 2015.10.16
1946  (0) 2015.10.16
2590  (0) 2015.10.15
1931  (0) 2015.10.14
11000  (0) 2015.10.11

2590

알고리즘/acmicpc 2015. 10. 15. 11:34 Posted by 아는 개발자

처음에는 엄청 어려운 문제인줄 알았다... 색종이가 판의 경계에도 놓일 수 있다면 이건 정말 어려운 문제고 초딩용으로는 전혀 적합하지 않은 문제라 생각했다..


그런데 문제를 꼼꼼히 읽어보니 하나의 색종이는 하나의 판에만 놓일 수 있다는 조건을 확인했다. 그러면 문제가 정말 쉬워진다. 색종이 큰 것 부터 탐색하고 남는 것들을 채워나가는 식으로 하면 된다.


이런 문제는 코드를 깔끔이 짜는것이 관건이다. 잘못하다간 자신도 코드를 알아보지 못하는 경우가 있기 때문이다. 반드시 수기 작업에서 변수명까지 선언해준 후 컴퓨터로 옮기도록 하자


 
#include<cstdio>

int main(){

	int d[7];
	for(int i=1; i<7; i++)
		scanf("%d", &d[i]);

	int res=0;
	for(int cur=6; cur>0; cur--){
		while(d[cur]!=0){
			res++;
			int rem = 36 - cur*cur;
			d[cur]--;
			int end = 6-cur;

			for(int piv=end; piv>0 && rem>0; piv--){
				while(d[piv]>0 && rem>0){
					if(rem >= piv*piv)
					{
						rem -= piv*piv;
						d[piv]--;
					}
					else
						break;
				}
			}
		}
	}

	printf("%d\n", res);
	return 0;
}

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

1577  (0) 2015.10.16
1946  (0) 2015.10.16
2590  (0) 2015.10.15
1931  (0) 2015.10.14
11000  (0) 2015.10.11
2405  (0) 2015.10.09

1931

알고리즘/acmicpc 2015. 10. 14. 20:40 Posted by 아는 개발자

mergesort를 직접 구현해서 풀어보려고했는데 stack overflow문제가 계속 났었다.


나는 무한루프 때문인가 생각했는데 알고보니 함수 내에 지역변수를 너무 크게 잡은 메모리 초과가 원인이었다.


recursion 할 때 stack 메모리에 어떻게 쌓이는지 다시 한 번 복습하는 기분이었다.


해결방법은

지역변수를 크게 안잡고 전역 변수로 두면 된다. 어차피 한 번의 recursive한 함수가 한 번만 접근하니까. 여기서 여러개의 thread돌리는 것이 아니기 때문에 공유 문제는 걱정 안해도 된다.


 
#include<cstdio>

using namespace std;
struct course{
	int start, end;
};

course c[100005];
course tmp[100005];

int mySort(int start, int end){
	if(start==end)
		return 0;

	int mid = (start+end)/2;

	mySort(start, mid);
	mySort(mid+1, end);

	int piv_a=start, piv_b=mid+1;

	int cur=0;
	while(1){
		if(piv_a==mid+1 && piv_b == end+1)
			break;
		else if(piv_a==mid+1)
			tmp[cur++]=c[piv_b++];
		else if(piv_b==end+1)
			tmp[cur++]=c[piv_a++];
		else{
			if(c[piv_a].end < c[piv_b].end)
				tmp[cur++] = c[piv_a++];
			else if(c[piv_a].end > c[piv_b].end) 
				tmp[cur++] = c[piv_b++];
			else{
				if(c[piv_a].start < c[piv_b].start)
					tmp[cur++] = c[piv_a++];
				else
					tmp[cur++] = c[piv_b++];
			}
		}
	}

	for(int i=0; i<cur; i++)
		c[start+i]=tmp[i];
	
	return 0;
}


int main(){

	int n;
	scanf("%d", &n);

	for(int i=0; i<n; i++)
		scanf("%d %d", &c[i].start, &c[i].end);

	mySort(0, n-1);

	int cur_end = c[0].end;
	int res=1;

	for(int piv=1; piv<n; piv++){
		if(c[piv].start >= cur_end){
			res++;
			cur_end = c[piv].end;
		}
	}

	printf("%d\n", res);

	return 0;
}

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

1946  (0) 2015.10.16
2590  (0) 2015.10.15
1931  (0) 2015.10.14
11000  (0) 2015.10.11
2405  (0) 2015.10.09
2437  (0) 2015.10.09

11000

알고리즘/acmicpc 2015. 10. 11. 15:00 Posted by 아는 개발자
최소 강의실의 개수를 구하는 문제.

먼저 수업들을 시작 시간을 기준으로 다시 정렬을 해두자. class[]

그리고 현재 강의실중 가장 수업이 빨리 끝나는 강의실을 관리하는 자료구조를 가지고 있다고 하자. (우선순위 큐를 이용해서 관리하는게 좋다)


정렬된 배열 class[] 에 있는 i번째 수업을 내가 추가하고자 한다면

현재 강의실 중에서 가장 수업이 빨리 끝나는 강의실에 추가하는 것이 최적의 경우일 것이다.


만약 i번째 수업의 시작시간이 가장 수업이 빨리 끝나는 강의실의 끝나는 시간보다 더 일찍 시작한다면, i번째 수업은 반드시 강의실을 추가해서 들을 수밖에 없다. 다른 강의실들은 가장 수업이 빨리 끝나는 강의실보다 더 늦게 끝날 것이 분명하기 때문이다.


우선순위큐와 정렬을 적당히 활용해서 풀면 쉽게 풀수 있다.




 
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>

using namespace std;

vector<int> rooms;
vector<pair<int, int> > c;

int main(){
	
	int n, from, to;
	scanf("%d", &n);

	for(int i=0; i<n; i++){
		scanf("%d %d", &from, &to);
		c.push_back(make_pair(from, to));
	}
	sort(c.begin(), c.end());

	priority_queue<int > pq;
	pq.push(0);
	for(int piv=0; piv < c.size(); piv++){
		int cur_finish = -pq.top();
		if(c[piv].first < cur_finish){
			pq.push(-c[piv].second);
		}
		else{
			cur_finish = -c[piv].second;
			pq.pop();
			pq.push(cur_finish);
		}
	}

	printf("%d\n", pq.size());
	return 0;
}

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

2590  (0) 2015.10.15
1931  (0) 2015.10.14
11000  (0) 2015.10.11
2405  (0) 2015.10.09
2437  (0) 2015.10.09
2616  (0) 2015.10.03

2405

알고리즘/acmicpc 2015. 10. 9. 20:39 Posted by 아는 개발자

상당한 아이디어를 요구하는 것 같은 문제이나 실제로 푸는 방법은 간단하다.


N이 최대 1000이기 때문에 가능한 모양 순열 123, 132, 213, 231, 312, 321 의 가정답을 나열한 다음 원래 주어진 모양 순열에서 가정답으로 바꿀 때 각각의 최소 횟수를 구해 전체 최소 횟수를 구할 수 있다.


각 모양은 최소 한 번 이상 나타난다는 조건으로 문제 풀이에 살짝 힌트를 주었다.


최소 횟수를 구하는 것은 간단하다. 여기서는 3가지 모양 밖에 없다는 사실을 잘 이용하자.


 
#include<cstdio>
#include<algorithm>

using namespace std;

int data[100005];
int res_arr[100005];
int d[4];

int main(){
	int N, ret;
	scanf("%d", &N);

	ret = N;

	int order[3] = {1, 2, 3};

	for(int i=0; i<N; i++){
		scanf("%d", &data[i]);
		d[data[i]]++;
	}

	do{
		int res = 0;
		int rem = 0;
		
		int piv=0;
		for(int i=0; i<3; i++){
			for(int j=0; j<d[order[i]]; j++)
				res_arr[piv++]=order[i];
		}

		int a[4][4]={0};

		for(int i=0; i<N; i++)
			if(data[i]!=res_arr[i])
				a[data[i]][res_arr[i]]++;

		for(int i=1; i<3; i++)
			for(int j=i+1; j<=3; j++)
			{
				if(a[i][j] > a[j][i])
				{
					res += a[j][i];
					rem += a[i][j] - a[j][i];
				}
				else
				{
					res += a[i][j];
					rem += a[j][i] - a[i][j];
				}
			}

		res += (rem/3)*2;
		ret = min(res, ret);
	}while(next_permutation(order, order+3));

	printf("%d\n", ret);

	return 0;
	
}

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

1931  (0) 2015.10.14
11000  (0) 2015.10.11
2405  (0) 2015.10.09
2437  (0) 2015.10.09
2616  (0) 2015.10.03
2463  (0) 2015.09.29

2437

알고리즘/acmicpc 2015. 10. 9. 19:47 Posted by 아는 개발자

이것도 스스로 못풀고 인터넷에 있는 풀이를 보고 풀었는데 정말 어떻게 이걸 생각해냈는지 대단하다는 느낌이 들면서도 간단한 풀이를 생각하지 못한 스스로에게 반성하게 되었다.


이건 dp문제로도 볼 수 있다.


먼저 추들을 정렬한다. 그리고 k는 1~N 사이에 있는 수로 가정하자


나는 1~k번까지의 추들을 통해서 최대 M까지의 무게를 만들 수 있다 치자(만약 못 만든다면 그전에 끝내버리면 된다)


이제 나는 k+1번째 추를 추가하고 싶다.


그런데 k+1번째 추의 무게가 M+1이 아니고 1을 더해서(1을 더하는 이유는 앞에서 내가 1부터 만들어 낼 수 있기 때문이다) M+1보다 크다면 나는 죽었다 깨어나도 주어진 추들의 조합으로 M+1을 만들 수 없다. 왜냐면 k+1보다 뒤에 있는 추들은 k+1보다 무거운 추들이기 때문에 얘네들로는 절대 못만든다.


만약 위와 같은 경우에수가 생긴다면 나는 M+1의 추를 만들 수 없는 것이다.


이런문제를 초딩이 풀다니...


 
#include<cstdio>
#include<algorithm>

using namespace std;

int d[1005];
int main(){
	int N;
	scanf("%d", &N);

	for(int i=0; i<N; i++)
		scanf("%d", &d[i]);

	sort(d, d+N);

	int makable=1;
	if(d[0]!=1){
		printf("1\n");
		return 0;
	}
	else{
		for(int i=1; i<N; i++){
			if(d[i]!=makable+1 && d[i]+1 > makable+1){
				printf("%d\n", makable+1);
				return 0;
			}
			makable += d[i];
		}
	}
	printf("%d\n", ++makable);

	return 0;
}

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

11000  (0) 2015.10.11
2405  (0) 2015.10.09
2437  (0) 2015.10.09
2616  (0) 2015.10.03
2463  (0) 2015.09.29
9079  (0) 2015.09.13

2616

알고리즘/acmicpc 2015. 10. 3. 00:34 Posted by 아는 개발자

이런 문제가 2003년 초등부 올림피아드에 나왔으니 내가 당시 초등학교 6학년이었으니까,, 감히 이런걸 푼다고 상상도 했을까... 이런 문제를 푸는 괴물들도 있었겠지. 나는 이걸 대학생이 되어서야 풀게 되었다.


이 문제는 DP문제이다. 어떻게 DP를 구현하느냐에 따라서 해결 방법이 천차 만별이다.


총 세개의 기관차를 쓰는게 이 문제를 푸는데 핵심이다.


처음에는 각 구간별로 n개의 소형기관차를 썼을 때 최대 값을 구하는 함수를 사용했다. 하지만 이건 배열을 여러번 탐색해야해서(O(N^n)) 시간초과가 뜬다.


어떻게 해야할지 고민하다가 세개의 기관차를 사용하는 것에서 방법을 찾았다.


먼저 현재 위치에서 소형차기관차를 연결했을 때 태울 수 있는 승객을 저장하는 배열을 만든후 d[0][50000]에 넣어둔다.


그 후 d[1][50000]은 이전 d[0]에 넣은 것들에서 현재 소형 기관차 앞에 있는 객차중 소형기관차를 연결 했을 떄 최대가 되는 것들을 찾는다. 그러면 d[1][50000]은 소형 기관차 두 개를 연결 했을 때 손님의 객수를 최대로 하는 방법이다.


마지막으로 d[2][50000]은 d[1]에 넣은 것들에서 현재 소형기관차 뒤에 있는 객차중 소형기관차를 연결 했을 때 최대가 되는 것들을 찾는다. 이전에 앞에 있는 객차들 중에서 찾았기 때문에 지금은 뒤에있는 것들에서 찾아야 중복이 되지 않는다.


만약 4개의 소형기관차를 사용한다면 위 알고리즘을 사용할 수 없다. 시간초과가 뜬 원래 알고리즘을 사용할 수밖에.


 
#include<cstdio>
#include<iostream>

#include<fstream>

using namespace std;

int d[3][50000];
int partialSum[50005];
int length;
int N;


int main(){
	int tmp;
	int res=0;

	ifstream ifp("input.txt");

	ifp>>N;
	//scanf("%d", &N);
	for(int i=1; i<=N; i++){
		ifp>>tmp;
		//scanf("%d", &tmp);
		partialSum[i] = partialSum[i-1]+tmp;
	}

	ifp>>length;
	//scanf("%d", &length);

	for(int piv=1; piv<=N-length+1; piv++){
		d[0][piv]=partialSum[piv+length-1]-partialSum[piv-1];
	}

	
	int partialMax=0;
	for(int piv=1; piv<=N-length+1; piv++){
		int addable = piv-length;
		if(addable > 0){
			partialMax = max(d[0][addable], partialMax);
		}
		d[1][piv] = d[0][piv] + partialMax;
	}

	partialMax = 0;
	for(int piv=N-length+1; piv>=1; piv--){
		int addable = piv+length;
		if(addable <= N-length+1){
			partialMax = max(d[0][addable], partialMax);
		}
		d[2][piv]=d[1][piv] + partialMax;

		res = max(res, d[2][piv]);
	}
	
	printf("%d\n", res);
	return 0;
}

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

2405  (0) 2015.10.09
2437  (0) 2015.10.09
2616  (0) 2015.10.03
2463  (0) 2015.09.29
9079  (0) 2015.09.13
2465  (0) 2015.09.08

2463

알고리즘/acmicpc 2015. 9. 29. 14:05 Posted by 아는 개발자

내가 직접 푼 문제는 아니고 게시판의 글을 참조해서 풀었는데 정말 감탄할만한 방법으로 풀었다... 기본적으로 이 문제는 MST의 형태를 가진 문제이다. 여기서 MST는 최소 스패닝 트리가 아니라 최대 스패닝 트리이다.


문제가 요구하는 조건이 다르다보니 기존 방식으로 트리를 형성해야 문제를 풀 수 있다.


문제를 푸는 핵심은 각각의 클라우드 사이를 연결 시키기 전에 형성된 에지들을 제외하고는 모든 에지들의 가중치를 더해야 한다는 점.


기존에 형성된 에지들의 가중치를 pastCost에 넣어서 정리하는 깔끔함이 놀라웠다...


게다가 이미 두 클라우드의 크기가 2 이상인 경우는 두 클라우드의 크기를 곱해서 가중치를 정리하는 방식까지. 이해하는 것은 별로 어려운 것은 아니나 이렇게 생각해낸다는 것 자체가 어려운것 같다.


이것을 어떻게 생각해냈는지 참으로 감격스럽다..


나는 언제쯤 이런 경지에 오를 수 있을지....



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

2437  (0) 2015.10.09
2616  (0) 2015.10.03
2463  (0) 2015.09.29
9079  (0) 2015.09.13
2465  (0) 2015.09.08
2457  (0) 2015.09.04

9079

알고리즘/acmicpc 2015. 9. 13. 16:20 Posted by 아는 개발자

다익스트라를 이용해서 해결하면 간단하다. 여기서 오래 걸린거는 input값을 받는 것이다. scanf로 문자열을 받을때는 공백도 인식한다는 것에 주의해야하는데 그걸 알아채리지 못하고 쓸데 없이 시간을 많이 끌었다. 반성해야하는 부분이다...


 
#include<iostream>
#include<queue>
#include<cstdio>

using namespace std;

int d[(1<<9)];

const int MAX = 1<<9;

int allH = (1<<9)-1;
int allT = 0;

int edge[8][3] = {
	{ 0, 1, 2 },
	{ 3, 4, 5 },
	{ 6, 7, 8 },
	{ 0, 3, 6 },
	{ 1, 4, 7 },
	{ 2, 5, 8 },
	{ 0, 4, 8 },
	{ 2, 4, 6 }
};

int main(){
	int tc, res;
	char tmp;

	cin>>tc;

	while(tc--){
		int cur=0, up=1;
		res=-1;

		for(int i=0; i<9; i++){
			cin>>tmp;
			if(tmp=='H')
				cur+=up;
			up*=2;
		}

		for(int i=0; i<MAX; i++)
			d[i]=-1;

		priority_queue<pair<int, int> > pq;
		pq.push(make_pair(0, cur));

		while(!pq.empty()){
			pair<int, int> front=pq.top();
			pq.pop();
			int cur_d=-front.first;
			int cur_p=front.second;
			
			if(d[cur_p]!=-1 && d[cur_p] <= cur_d)
				continue;
			d[cur_p]=cur_d;

			if(cur_p == allH || cur_p == allT){
				res = cur_d;
				break;
			}

			for(int i=0; i<8; i++){
				int next_p = cur_p;
				for(int j=0; j<3; j++){
					if(cur_p & (1<<edge[i][j]))
						next_p -= 1<<edge[i][j];
					else
						next_p += 1<<edge[i][j];
				}
				pq.push(make_pair(-(cur_d+1), next_p));
			}
		}
		printf("%d\n", res);
	}
}

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

2616  (0) 2015.10.03
2463  (0) 2015.09.29
9079  (0) 2015.09.13
2465  (0) 2015.09.08
2457  (0) 2015.09.04
2481  (0) 2015.09.01

2465

알고리즘/acmicpc 2015. 9. 8. 17:24 Posted by 아는 개발자

Segment Tree를 공부한 후 풀지 못했던 문제들을 쏙쏙 해결하고 있다. 정보가 계속 업데이트 되며 거기서 특정한 값을 구해야 할 때 사용하기 유용한 자료구조이다. 줄세우기 문제 또한 그렇다. 


문제를 풀기 위한 전체적인 알고리즘은 주어진 키를 정렬 한 후 문제에서 주어진 수열의 맨 뒤 하나씩 확인한다. 현재의 정렬에서 주어진 값에 해당하는 index를 고르고(배열은 0부터 시작한다 그러면 앞에 주어진 값 만큼이 자신보다 작은게 있는게 확실해지므로) 선택한 키 값은 정렬에서 뺀다 그렇게하면 식이 하나밖에 성립되지 않을 것이다.


여기서 문제는 뒤에서 중간에 있는 것들을 선택하기 때문에 배열 자체가 계속 작아진다는 것이다. 이것을 해결하기 위해 어떻게할까 생각을 많이 했었는데 segment tree를 사용해서 해결 할 수 있었다. 참 무궁무진한 자료구조인듯하다..



 
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<fstream>

using namespace std;

int s[400005];
int t[400005];
int h[100005];
int d[100005];
int r_idx[400005];

int N;

void build(int id=1, int l=0, int r=N){
	if(r-l<2){
		t[id]=1;
		r_idx[id]=r;
		s[id]=1;
		return;
	}

	int mid = (l+r)/2;
	build(id*2, l, mid);
	build(id*2+1, mid, r);

	s[id]=s[id*2] + s[id*2+1];
	r_idx[id]=r;
}

void modify(int p, int x, int id=1, int l=0, int r=N){
	s[id] += x-d[p];
	if(r-l<2){
		d[p]=0;
		s[id]=0;
		return;
	}

	int mid = (r+l)/2;
	if(p<mid)
		modify(p, x, id*2, l, mid);
	else
		modify(p, x, id*2+1, mid, r);
}

int main(){

	int line[100005];
	int res[100005];

	ifstream ifp("input.txt");


	ifp>>N;
	//scanf("%d", &N);
	
	for(int i=0; i<N; i++)
		ifp>>h[i];
		//scanf("%d", &h[i]);
	
	sort(&h[0], &h[N]);

	build(1, 0, N);

	for(int i=0; i<N; i++){
		ifp>>line[i];
		//scanf("%d", &line[i]);
		d[i]=1;
	}

	
	for(int idx=N-1; idx>=0; idx--){
		int size = line[idx];

		size++;
		int piv=1;
		
		int here;
		while(1){
			if(t[piv]){
				here = r_idx[piv]-1;
				break;
			}
			int l_child = piv*2;
			int r_child = piv*2+1;
			if(size <= s[l_child]){
				piv=l_child;
			}
			else{
				size -= s[l_child];
				piv=r_child;
			}
		}
		res[idx]=h[here];
		modify(here, 0, 1, 0, N);
		d[here]=0;
	}

	for(int i=0; i<N; i++)
		printf("%d\n", res[i]);

	return 0;

}

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

2463  (0) 2015.09.29
9079  (0) 2015.09.13
2465  (0) 2015.09.08
2457  (0) 2015.09.04
2481  (0) 2015.09.01
1987  (0) 2015.08.26

Segment Tree

알고리즘/자료구조 2015. 9. 7. 16:34 Posted by 아는 개발자

옛날에 min max Tree를 공부 할 때 배열 특정 구간 내에서의 최대값과 최소값을 미리 저장해두어 범위가 주어 질 때 O(logN)시간내에 해결 했었는데 이렇게 구간 내의 특정 값을 저장해두는 방식을 Segment Tree라고 하나 보다.



범위가 주어지면 위 배열을 이용해서 해결하면 된다. 만약 3~6사이의 범위에 대해 구하라고 하면


이렇게 풀면 된다.


사실 이건 생각하는 것은 책 한번 보면 어렵지 않은데 이걸 어떻게 구현 할 것인가가 문제이다. 예전에는 이차원 배열 사용하며 메모리 낭비도 심하고 코드도 지저분하게 풀었는데 코드포스에 깔끔한 구현이 있어 참조해본다




펜윅트리와는 다르게 Segment 트리는 구간의 최대값과 최소값 또한 저장 할 수 있고 갱신도 용이하다. 앞으로 자주 사용해야겠다.


'알고리즘 > 자료구조' 카테고리의 다른 글

LCA(Lowest Common Ancestor)  (0) 2016.07.30
Count sort  (0) 2016.07.23
Segment Tree  (0) 2015.09.07
SQRT Decomposition  (0) 2015.09.05
LIS를 O(nlogn)시간 내에 해결하는 방법  (0) 2015.08.27
c++ priority_queue에서 comparator 선언해주는 방법  (0) 2015.08.26

SQRT Decomposition

알고리즘/자료구조 2015. 9. 5. 20:39 Posted by 아는 개발자

만약 알고리즘 문제에서 해당 배열의 특정 구간(L, R)에서 최소값을 구하라는 문제가 나왔다면 가장 일반적으로 생각 할 수 있는 방법은 L, R 구간을 모두 탐색해보는 방법일 것이다.


하지만 테스트 케이스의 개수가 많고 배열의 크기가 크다면 시간이 오래 걸릴 것이다. 여기서 사용 할 수 있는 방법이 sqrt decomposition이다.




크기 N인 배열을 sqrt(N)으로 쪼개서 최소값을 저장하는 배열(sqrt 배열)을 미리 만들어 둔 후


주어진 구간의 최소값 찾을 때는 구간 내에 포함된 sqrt배열에 해당하는 최소값과 그 이외의 부분들의 값을 비교해서 해결 할 수 있다


현재는 최소값을 구하는데 사용했는데 이것 말고도 다양한 정보를 저장하는데 사용 할 수 있을 것 같다

'알고리즘 > 자료구조' 카테고리의 다른 글

Count sort  (0) 2016.07.23
Segment Tree  (0) 2015.09.07
SQRT Decomposition  (0) 2015.09.05
LIS를 O(nlogn)시간 내에 해결하는 방법  (0) 2015.08.27
c++ priority_queue에서 comparator 선언해주는 방법  (0) 2015.08.26
인덱스 트리  (0) 2015.07.07

2457

알고리즘/acmicpc 2015. 9. 4. 11:37 Posted by 아는 개발자

월과 일로 표현되어있는 날짜 단위를 하나로 통합한 후에 문제를 풀어야 한다.

나는 월/일을 모두 일로 바꿔서 계산했다. 이게 가장 쉬운 방법인것 같다.


나머지는 회의실 배정 문제와 비슷하다.


현재 꽃이 지기 전에 먼저 피어있는 꽃 들중에서 가장 늦게 지는 꽃을 고르면 된다.

여기서는 범위가 주어진다는 점 (3/1~11/30)과

문제의 조건에서 꽃이 지는 날은 꽃이 폈다고 볼 수 없다는 조건에 유의해서 문제를 풀면된다


O(N)에 해결하기 위해 sorting한 후 알고리즘을 적용했다.




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

9079  (0) 2015.09.13
2465  (0) 2015.09.08
2457  (0) 2015.09.04
2481  (0) 2015.09.01
1987  (0) 2015.08.26
10217  (0) 2015.08.26

2481

알고리즘/acmicpc 2015. 9. 1. 19:39 Posted by 아는 개발자

경로가 주어지지 않아 스스로 경로를 만들고 최단 경로를 찾아내는 문제이다.


각각의 이진수들 마다 정점으로 생각하고 그 정점과 해밍 거리가 1인 정점들을 연결해야 한다. 기존의 방법들은 간선을 배열에 저장해두기도 하는데 여기서는 정점의 최대 개수가 100000이라 n*n으로는 저장이 안될 것 같아서 정점을 방문 할 때마다 매번 간선을 확인하는 것으로 했다(정점마다 가능한 최대 간선수가 30뿐이라 시간 복잡도에 영향을 주지 않을 것 같기 때문이도 했다)


여기서 이진수를 그대로 가져 갈 것인가? 아니변 변환 할 것인가로 고민을 했는데 다행히 이진수의 최대 길이가 30이므로 int 10진수 값으로 변환했다. 정점을 표현하는데 더 쉬웠다.


특정 정점에서 해밍 거리가 1인 정점이 존재하는지 안하는지를 파악해야한다. 모든 정점을 뒤진다면 O(N)시간이 걸려 모든 정점에서 수행하면 O(N*N)으로 시간초과가 걸릴 것이다. 해결하기 위해서 정점들의 값들을 sort해 binary search를 가능하도록 했다.


binary search를 하기 위해 정점들을 sort한 후에는 기존에 어느 위치에 있었는지를 저장해두어야 했는데 여기서 디버그하는데 상당히 오래걸렸다. 연습장에 예상 결과값을 만들어서 풀었으면 빨랐을 것 같은데 스스로 운에 맡기다가 계속 F10만 눌렀다.


최단 경로의 길이는 다익스트라로 구하면 되고 지나치는 정점 대한 정보는 현재 정점이 이전 정점에 어디를 가리키는지를 각각 저장해두어서 풀었다.


다익스트라, 순회정점, 이진수, 이진탐색이 종합된 문제였다.


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

2465  (0) 2015.09.08
2457  (0) 2015.09.04
2481  (0) 2015.09.01
1987  (0) 2015.08.26
10217  (0) 2015.08.26
2638  (0) 2015.08.24

LIS를 O(nlogn)시간 내에 해결하는 방법

알고리즘/자료구조 2015. 8. 27. 11:13 Posted by 아는 개발자

LIS는 수열 중에서 가장 긴 수열의 길이를 찾는 방법이다.


동적 계획법 해결 방법은 이전에 찾았던 수열의 마지막 값들 중 현재의 위치의 값보다 작으면 그 마지막 값이 가지고 있는 수열의 길이에 1을 더하는 방식이다. 조건에 해당하는 수열 중에서 가장 긴 수열을 선택해야 한다.


기존의 방법은 긴 수열을 찾는데 O(N)의 시간이 걸려 모든 배열의 값을 탐색한 후에는 전체 알고리즘 복잡도는 O(N^2)가 되었다 


하지만 길이 L 인 수열의 마지막 값들 중 최소 값을 저장하는 배열을 둔다고 생각해보자 C[L]


C[]배열은 순 증가하는 그래프가 될 것이다. 

(간단히 설명하자면 C[N]은 C[N-1]의 영향을 받을 것이고 C[N-1]은 현재 길이에서 최소의 값을 가지기 때문에...귀납적으로 설명하면 그렇다. 직감적으로도 그러하고)


만약 나의 현재 위치의 값이 S라면 C[]에서 이분 탐색을 하고 index값을 통해 위치를 반환 할 수 있을 것이다.


출처 - 알고리즘 문제해결 전략

'알고리즘 > 자료구조' 카테고리의 다른 글

Segment Tree  (0) 2015.09.07
SQRT Decomposition  (0) 2015.09.05
LIS를 O(nlogn)시간 내에 해결하는 방법  (0) 2015.08.27
c++ priority_queue에서 comparator 선언해주는 방법  (0) 2015.08.26
인덱스 트리  (0) 2015.07.07
union find  (0) 2015.06.27

1987

알고리즘/acmicpc 2015. 8. 26. 13:19 Posted by 아는 개발자

BFS로 풀다가 메모리 초과가 떠서 DFS로 해결했다.


간단히 재귀함수를 만들어서 해결했는데 속도를 높이고 싶으면 재귀 함수를 사용하지 않고 stack을 이용해서 해결해도 좋을 것 같다.



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

2457  (0) 2015.09.04
2481  (0) 2015.09.01
1987  (0) 2015.08.26
10217  (0) 2015.08.26
2638  (0) 2015.08.24
1238  (0) 2015.08.24


위의 Prove class는 내가 문제를 풀기 위해 임의로 만든 것이기 떄문에 무시해도 된다.
만약 int인 priorityqueue를 만들고 싶다면

priority_queue<int, vector<int>, mycomparison>
으로 선언하면 된다.

여기서 세가지 인자가 들어가는데 하나는 자료형, 자료형을 저장하는 자료구조, 그리고 비교연산이다

자료구조는 별일 없으면 vector로 선언하면 된다.
mycomparison이 비교 연산을 하는 것인데 이건 class로 선언해줘야 한다.

algorithm 라이프러리에 sort를 해결할 때는 일반 함수처럼 선언해서 해결하면 되었었는데 priority_queue는 그렇지 않았다

그리고 여기서 heap을 어떤 순서로 나열하느냐는 일반적인 compare와 다르다

sort에서는 오름 차순으로 하려면

compare(int a, int b) return a < b;

이렇게 했는데 priority_queue에서는

compare(int a, int b) return a > b;
로 해주어야 한다.

heap만의 특성이라 그런가 보다


'알고리즘 > 자료구조' 카테고리의 다른 글

SQRT Decomposition  (0) 2015.09.05
LIS를 O(nlogn)시간 내에 해결하는 방법  (0) 2015.08.27
c++ priority_queue에서 comparator 선언해주는 방법  (0) 2015.08.26
인덱스 트리  (0) 2015.07.07
union find  (0) 2015.06.27
오일러회로  (0) 2015.02.27

10217

알고리즘/acmicpc 2015. 8. 26. 11:43 Posted by 아는 개발자

최단거리 + 제한비용 문제이다. 


다익스트라로 해결하면 쉽겠지 하고 생각하다가 곰곰히 생각해보니 순수한 다익스트라 방법으로는 위 문제를 풀 때 예외가 발생한다는 것을 깨달았다.


다익스트라는 

"어느 정점의 최단 경로를 확인 했다면 그 경로와 그와 인접한 정점들의 최단 경로를 연결 할 수 있다" 는 원리로 구할 수 있다


하지만 위 문제에서는


어느 정점의 최단 경로를 확인해도 그 정점과 연결된 다른 정점들과의 최단 경로를 연결 할 수 있다고 말을 할 수가 없다. 왜냐하면 제한비용이 있기 때문이다.


예를 들어


현재 A점에 오는데 두 가지 방법이 있다고 하자 

경로를 (최단거리, 현재 남은 비용)이라 하겠다


(10, 5), (30, 100)


여기서 B점까지 가야한다. 그런데 B점까지 가는 방법으로는 두가지 방법이 있다

(5, 60), (100, 5)


A점까지 최단 거리로 이동하는 경우는 (10, 5)이다. 최단 거리 경로에서는 반드시 (100, 5)인 경로를 선택 할 수 밖에 없다. 그러면 B까지 이동하는데 경로는 110이 된다.


하지만 A점까지 최단 거리가 아니였던 경로 (30, 100)을 이용하면 B점을 이동 할 때 (5, 60)인 경로를 선택 할 수 있다. 따라서 B점까지 이동하는데 경로는 35가 된다.


그러므로 정점으로 이동하는 최단 경로만 보는 것이 아니라 여러가지 경로를 모두 봐야 한다.


하지만 모든 경로들을 다 보면 메모리가 매우 많이 들기 때문에 어떻게 처리할 것인가를 고심하다 정점이 최대 100개이고 비용이 최대 10000인 점을 이용해 배열 내부에 선언이 가능한하다고 판단했고 각 정점들마다 이동하는데 드는 비용에 대한 최단 거리를 저장하는 배열을 선언해서 해결했다.


쉽지 않았지만 풀고나니 개운한 문제였다



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

2481  (0) 2015.09.01
1987  (0) 2015.08.26
10217  (0) 2015.08.26
2638  (0) 2015.08.24
1238  (0) 2015.08.24
9470  (0) 2015.08.22

2638

알고리즘/acmicpc 2015. 8. 24. 17:33 Posted by 아는 개발자

어떻게 외부 공기를 깔끔하게 처리할 것이냐가 위 문제를 푸는데 가장 중요한 요소이다


초등부 문제와는 다르게 위 문제는 격자 가장자리에도 치즈를 올려 둘 수 있다는 조건이 문제를 푸는데 어려운 요소였던 것 같다.


그래서 나는 애초에 치즈 격자를 1,1 부터 시작하게 한 후

바깥 공기를 찾기 위해서 0,0 부터 찾도록 만들었다.


즉 문제에서 주어진 격자 보다 2열을 더 추가해 격자를 만들고 추가한 격자를 이용해

바깥 공기를 자동으로 찾을 수 있도록 만들었다.



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

1987  (0) 2015.08.26
10217  (0) 2015.08.26
2638  (0) 2015.08.24
1238  (0) 2015.08.24
9470  (0) 2015.08.22
2515  (0) 2015.07.17

1238

알고리즘/acmicpc 2015. 8. 24. 15:20 Posted by 아는 개발자

파티하는 학생의 집에 까지 가는 경우와 돌아오는 경우

각각에 대해서 시간을 따로 구해야 하는것이 문제의 핵심이다.


처음에는 문제를 풀 때 각 노드 사이에 걸리는 모든 시간을 다 구해야 하나 하고 생각을 하다

파티하는 학생의 집을 출발점으로 두는것과 도착점으로 두는 것 모두 동일한 경우로 판단 할 수 있어서 다익스트라 알고리즘을 두 번 돌리는 것으로 해결했다.


각각의 노드들 마다 간선을 inflow, outflow로 arrow를 표현하니 코드가 간결해졌다.



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

10217  (0) 2015.08.26
2638  (0) 2015.08.24
1238  (0) 2015.08.24
9470  (0) 2015.08.22
2515  (0) 2015.07.17
2458  (0) 2015.07.15

9470

알고리즘/acmicpc 2015. 8. 22. 16:22 Posted by 아는 개발자

topological sort를 이용하면 별로 어렵지 않은 문제...

하지만 이 문제는 꽤 많은 시간을 허비했다


알고리즘 문제를 풀 때 자신이 유지하는 자료구조의 스펙을 정확히 해야한다.

내가 위 자료구조는 어떠한 값을 입력해둘 것인가를 확실히 해두어야 후에 스스로에게 헷갈리지 않는다.


머릿 속으로만 모두 해결하려 하지 말고 자신의 자료구조를 손으로 그려보는 것이 가장 좋은 방법일 것 같다.




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

2638  (0) 2015.08.24
1238  (0) 2015.08.24
9470  (0) 2015.08.22
2515  (0) 2015.07.17
2458  (0) 2015.07.15
1365  (0) 2015.07.07

2515

알고리즘/acmicpc 2015. 7. 17. 13:59 Posted by 아는 개발자

옛날에는 못풀다가 컨디션 좋은날 불현듯이 아이디어가 생각나서 풀었다. 예전에 내가 풀었던 방식은 DP였긴 한데 너무 문제를 어렵게 생각해서 못풀었던 것 같다. 그때나 지금이나 원리는 비슷한데 한 끗의 차이 때문에 맞고 틀림이 결정되었다.


어차피 최대의 이윤을 내려면 전시품들이 키 순서대로 있어야 한다. 먼저 키 순대로 정렬하고 크기 차이가 S이상 나는 전시품들의 부분 집합 중에서 가장 큰 부분 집합을 구하는 것이 문제 푸는 데 핵심이다.


위 문제는 DP로 해결 할 수 있다. 키 순서대로 하나 하나씩 차근차근 풀어가면 된다. 알고리즘 순서도는 다음과 같다.


1. 내가 i 번째 그림을 체크 한다고 하자. 

2. i번째 그림과 크기 차가 S이하로 나는 그림들 중(j까지라 하자)에서 지금까지 나온 가장 최고의 이윤을 확인 한다.

3. i번째 그림의 가격과 j의 범위 까지 최고의 이윤의 값을 더하면 그 그림까지 샀을 때 최고의 이윤을 확인 할 수 있다.


이전에 어떤 그림들이 포함되었는지 알 필요가 없으며 단지 최대의 값만 확인하면 된다.

어차피 탐색하는 그림의 크기는 계속 증가하므로 이 전의 그림들을 탐색할 필요는 없다는 원리를 두어서 O(1)에 해결 할 수 있다.


알고리즘의 시간 복잡도는 O(N)



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

1238  (0) 2015.08.24
9470  (0) 2015.08.22
2515  (0) 2015.07.17
2458  (0) 2015.07.15
1365  (0) 2015.07.07
7578  (0) 2015.07.06