Search

'알고리즘/acmicpc'에 해당되는 글 61건

  1. 2017.04.21 SW 역량테스트 기출 문제집 분석 (4)
  2. 2017.04.05 10422
  3. 2016.09.06 1937
  4. 2016.08.15 4095
  5. 2016.07.30 11437
  6. 2016.07.24 2253
  7. 2016.07.24 11049
  8. 2016.07.24 2229
  9. 2015.10.17 4307
  10. 2015.10.16 1577
  11. 2015.10.16 1946
  12. 2015.10.15 2590
  13. 2015.10.14 1931
  14. 2015.10.11 11000
  15. 2015.10.09 2405
  16. 2015.10.09 2437
  17. 2015.10.03 2616
  18. 2015.09.29 2463
  19. 2015.09.13 9079
  20. 2015.09.08 2465
  21. 2015.09.04 2457
  22. 2015.09.01 2481
  23. 2015.08.26 1987
  24. 2015.08.26 10217
  25. 2015.08.24 2638
  26. 2015.08.24 1238
  27. 2015.08.22 9470
  28. 2015.07.17 2515
  29. 2015.07.15 2458
  30. 2015.07.07 1365
  31. 2015.07.06 7578
  32. 2015.07.01 1753
  33. 2015.07.01 1795
  34. 2015.06.27 1197
  35. 2015.06.26 2268
  36. 2015.06.25 2357
  37. 2015.06.25 1138
  38. 2015.06.18 4158
  39. 2015.06.18 4883 (1)
  40. 2015.06.18 1890

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

알고리즘/acmicpc 2017.04.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.04.05 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

1937

알고리즘/acmicpc 2016.09.06 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.08.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

11437

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

2253

알고리즘/acmicpc 2016.07.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.07.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.07.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

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.09 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.09 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.03 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.09.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.09.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.09.08 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

2457

알고리즘/acmicpc 2015.09.04 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.09.01 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

1987

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

10217

알고리즘/acmicpc 2015.08.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.08.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.08.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.08.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.07.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

2458

알고리즘/acmicpc 2015.07.15 20:13 Posted by 아는 개발자

초등학생들한테 이런 문제를 풀라고 하는 것도 웃기고 이것 가지고 몇시간 낑낑데는 나도 참 웃기다... 간단히 생각하면 되는데 왜 나는 이 문제를 가지고 stack이니 queue니 하면서 접근 한건지..


비교 가능을 묻는 문제는 그래프 문제로 바꿀 수 있고 각 그래프가 연결 되었는지로 판별 가능하다.


연결 가능성은 floyd warshall 알고리즘으로 한방에 해결 가능하다. 어차피 input도 500개라 사용해도 무방하다. 그런데 나는 방향성을 가진 그래프라 적용할 수 없다고 생각해 계속 문제를 돌려서 풀었다. 양측에서의 도달가능성을 생각해주면 되는 간단한 사실을 알지 못해서 계속 이상한짓 하다가 겨우 풀었다.


아... 아직도 실력이 부족한건지 아니면 마음이 조급해서 그런건지 모르겠다

요즘 문제가 진짜 안풀린다 ㅠㅠ


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

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
1753  (0) 2015.07.01

1365

알고리즘/acmicpc 2015.07.07 18:01 Posted by 아는 개발자

전선이 꼬이지 않으려면 몇개의 전깃줄을 제거하면 되느냐는 문제는 LIS의 변형 문제와 같다.


연결되어있는 전선들 각각에 수치들을 준다면 하나도 꼬이지 않은 형태는 연결된 전선들이 증가하는 순열의 모양새와 같을 것이다.


이 순열들 중에서 가장 긴 순열을 찾으면 잘라내야하는 전선의 수도 자동적으로 알수있다.

(잘라내야하는 전선의 수 = 총 전선의 수 - 가장 긴 순열에 포함된 전선의 수)


LIS 는 기본적으로 dp를 이용해서 해결하는데 어떻게 푸느냐에 따라서 시간 복잡도가 다르다


예전에 for문을 두번 돌린 O(n^2)로 풀다가 조금 더 개선된 방법인 우선순위 큐를 사용했었지만 여기서는 우선순위큐로도 시간초과가 떴다


꽤 고민했지만 찾을수 없어 LIS 알고리즘을 인터넷으로 참고해보니 인덱스 트리를 사용하는 방법이 있었다. 


각각의 전선들은 자신과 연결된 전선들 보다 작은 값을 가지는 것 중에서 현재 가장 길게 연결된 순열을 찾아야 한다. 내가 연결되는 전선이 i라고 하면 0~i-1 구간 중에서 최장 증가 순열을 찾아야 한다는 것이다. 이때 이것을 단순히 탐색 알고리즘을 하면 O(N)의 시간이 걸리지만, 인덱스트리를 통해 각 구간별로 최대값을 찾도록 하면 O(logN) 시간 내에 찾을 수 있다.


인덱스 트리 만드는것은 만만치 않고 중간에 실수하면 디버깅하는데 시간이 오래 걸린다. 나는 각각의 노드에서 구간을 정리하는데 시간이 오래걸렸다...



 
#include<iostream>
#include<cstdio>

using namespace std;

int tree[20][100000];



void update(int height, int piv, int data){
	if(height==18)
		return;

	if(tree[height][piv] < data){
		tree[height][piv] = data;
		update(height+1, piv/2, data);
		return;
	}
}

int myPow(int height){
	int ret=1;
	for(int i=0; i<height; i++){
		ret*=2;
	}
	return ret;
}

int findMax(int height, int piv, int from, int to){
	
	int range=myPow(height)-1;

	if(from > to)
		return 0;

	int hereFrom = myPow(height)*piv;
	int hereTo = myPow(height)*piv+range;
	if(hereFrom==from && hereTo==to)
		return tree[height][piv];

	if(hereFrom>to || hereFrom+range < from)
		return 0;

	return max(findMax(height-1, piv*2, from, min(to, hereFrom+myPow(height-1)-1)),
		findMax(height-1, piv*2+1, max(from, hereFrom+myPow(height-1)), to));
}

int main()
{
	int n, idx, cur, ret;
	scanf("%d", &n);

	ret = 0;

	for(int i=0; i<n; i++){
		scanf("%d", &idx);
		cur = findMax(17, 0, 0, idx-1) + 1;
		ret = max(ret, cur);
		update(0, idx-1, cur);
	}

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

	return 0;
}

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

2515  (0) 2015.07.17
2458  (0) 2015.07.15
1365  (0) 2015.07.07
7578  (0) 2015.07.06
1753  (0) 2015.07.01
1795  (0) 2015.07.01

7578

알고리즘/acmicpc 2015.07.06 18:15 Posted by 아는 개발자

문제를 푸는것 자체는 별로 어렵지 않았다. 


부분합 문제를 변형한 형태이기 때문에 그 점을 잘 파악해서 풀면 된다. 가장 왼쪽에 있는 기기 부터 전선을 하나씩 이어가며 교차점의 수를 늘려간다.


교차점의 수를 찾는 방법은 가장 오른쪽으로 떨어진 지점까지 현결된 전선의 개수와 현재의 위치에서 기계와 연결된 지점 까지의 전선 개수를 빼면 된다. 


가장 오른쪽으로 떨어진 점 까지의 연결된 전선의 개수는 교차 가능성이 있는 전선들이고 연결된 지점의 왼쪽에 있는 전선의 개수는 교차 가능성이 없는 전선들이기 때문에 둘의 차는 해당 지점에서 전선을 연결 했을 때 교점과 같다.




알고리즘은 쉽게 생각했는데 내가 틀렸던 이유는 교차점의 수가 int의 범위를 넘을 수 있다는 것을 생각하지 못했기 때문이다... 이미 틀려버린 3 문제가 정말 억울하다...


교차점은 0+1+2+...+499999까지 생기는데 이러면 int범위를 거뜬히 넘어버린다

앞으로 결과의 자료형은 왠만하면 long long을 사용해야겠다.



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

2458  (0) 2015.07.15
1365  (0) 2015.07.07
7578  (0) 2015.07.06
1753  (0) 2015.07.01
1795  (0) 2015.07.01
1197  (0) 2015.06.27

1753

알고리즘/acmicpc 2015.07.01 19:41 Posted by 아는 개발자

너무나 당연하게 알고있을 거라 생각했던 다익스트라....

나는 다익스트라 알고리즘이 우선순위을 사용해야 한다는 것을 깜빡하고 있었다.


이 문제는 맨 처음에는 메모리 초과를 어떻게 해결할 것이냐로 속을 썩였었는데

메모리 초과를 해결 한 후에는 나의 다익스트라 알고리즘의 문제때문에 한동안 애를 먹었다..


먼저 메모리 초과를 해결하는 방법부터 설명하면


정점의 개수가 20000개이기 때문에 20000*20000의 배열은 만들 수 없다.

그러므로 간선들만의 집합을 만들어두어야 한다.


이때 특정 정점에서 나오는 간선을 어떻게 indexing하느냐 문제가 있었는데

각 간선들을 출발 위치에 대해서 오름 차순으로 정리한 후 범위를 지정해주어서 해결했다.

(지금 생각하면 간단하지만 여기까지 생각해내는 것도 참 힘들었다...)


이제 그에 맞추어서 다익스트라를 적용하면 되는데


나는 너무도 당연하게 다익스트라를 큐를 이용해서 구현하면 될 줄 알았다...

하지만 다익스트라는 우선순위 큐를 이용해서 구현해야 한다.


그 이유는 연결된 노드들 중에서 가장 가까운 점과 연결되어야 하는데 이때 나중에 추가된 점이 먼저 추가된 점보다 더 가까이 있는 경우가 생기기 때문이다.

(설명이 그지같으니 혹시나 이글을 보시는 분은 반드시 책을 참조하시길)


맨날 다익스트라 다익스트라 떠들고다녀서 나 스스로 잘 알고 있을 줄 알았는데

오늘 알고리즘 책을 보고 다시 깨달았다.


역시나 잘 알고 있다고 방심하는 순간 틀리는 것 같다.


겸손해야지


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

1365  (0) 2015.07.07
7578  (0) 2015.07.06
1753  (0) 2015.07.01
1795  (0) 2015.07.01
1197  (0) 2015.06.27
2268  (0) 2015.06.26

1795

알고리즘/acmicpc 2015.07.01 16:13 Posted by 아는 개발자

이 문제는 딱 보면 어떻게 해결해야 할지 감이 안잡히는데

그래프를 사용하라 하면 어느정도 문제푸는 방법을 깨닫는다


이 문제에서 힌트는 암호들이 정렬되어 있다는 것이다.

사용하는 문자들의 알파벳 정렬을 그래프의 간선으로 설정해서 표현하고

DFS를 통해서 풀면 된다.


기존 DFS랑 다른 점은 한 번 방문한 점을 또 방문 할 수 있다는 점인데

그 노드에서 빠져 나올 때 방문하지 않은 걸로 바꾸면 풀 수 있다.




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

7578  (0) 2015.07.06
1753  (0) 2015.07.01
1795  (0) 2015.07.01
1197  (0) 2015.06.27
2268  (0) 2015.06.26
2357  (0) 2015.06.25

1197

알고리즘/acmicpc 2015.06.27 10:53 Posted by 아는 개발자

반성해야하는 문제다

너무 문제에 성급하게 접근했다.


최소스패닝트리는 kruskal이든 prim이든 둘 중 하나를 이용해서 풀면된다.

나는 kruskal을 사용했는데 여기서 각각의 클라우드를 병합하는 과정에서 실수가 있었다.


이것은 union find라는 자료구조를 이용해서 해결해야하는데


나는 두 노드중 발견된 것들을 제외한 것만 본다고 했으니 당연히 틀릴 수밖에 없다.

(아마 이 글을 읽는 사람은 뭔말인지 모를 것이다 나만 이해할 수 있는 문장..)


프림알고리즘을 사용했으면 틀리지 않았을 것 같다...



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

1753  (0) 2015.07.01
1795  (0) 2015.07.01
1197  (0) 2015.06.27
2268  (0) 2015.06.26
2357  (0) 2015.06.25
1138  (0) 2015.06.25

2268

알고리즘/acmicpc 2015.06.26 11:54 Posted by 아는 개발자

집가기 전에 하나 풀고 가겠다고 성급하게 덤볐다가 쓸데없이 두 번 틀린 문제다.


펜윅트리를 다시 정의해서 풀면 된다.


update를 이전 값에서 차이값을 갱신해주면 된다.



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

1795  (0) 2015.07.01
1197  (0) 2015.06.27
2268  (0) 2015.06.26
2357  (0) 2015.06.25
1138  (0) 2015.06.25
4158  (0) 2015.06.18

2357

알고리즘/acmicpc 2015.06.25 16:10 Posted by 아는 개발자

각 구간별로 최소값과 최대값을 구하는 문제


가장 쉽게 생각하면 매번 구간이 주어질 때마다 최대값과 최소값을 구하는 방법이 있겠으나

그렇게 쉽게 문제를 냈을 리가 없다.


방법은 Min Max Tree를 만드는 것이다


옛날 자료구조 시간에 Tree의 존재를 배우기는 했으나 직접 구현하지는 않아봐서

이번에 구현하는데 시간이 좀 걸렸고,,,


구간 부분을 지정해주는 것도 꽤 힘들었다.

(이거 진짜 귀찮은 작업이다...)


하지만 한번에 맞춰서 기분이 좋다


나의 미천한 코딩실력도 조금씩 상승하는 것 같은 느낌이다.



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

1197  (0) 2015.06.27
2268  (0) 2015.06.26
2357  (0) 2015.06.25
1138  (0) 2015.06.25
4158  (0) 2015.06.18
4883  (1) 2015.06.18

1138

알고리즘/acmicpc 2015.06.25 14:03 Posted by 아는 개발자

이 문제는 줄을 모두 비운 다음 입력에 따라서 하나씩 채워가면 된다.


예제로 나온 것을 보자


2 1 1 0


-1을 비어있는 것으로 보고 줄을 만들어보면


-1, -1, -1, -1


먼저 1의 크기를 가진 참가자는 자신의 앞에 두명이 있어야 한다.

그런데 다음으로 검사할 참가자들은 모두 1보다 키가 클 것이므로

앞에 두명을 비운 다음에 자신의 위치를 잡아 줄 수 있다.


-1, -1, 1, -1


다음 2의 크기를 가진 참가자는 자신 앞에 한명이 있어야 한다.

앞의 경우와 마찬가지로 다음으로 검사할 참가자들은 모두 2보다 키가 크기 때문에

3이 올지 4가 올지 생각하지 않고 그냥 앞에 한 칸을 비우면 된다


-1, 2, 1, -1


핵심은 키의 순서대로 적용하고 있다는 것이고 

그 숫자만큼 빈칸을 만들어 두면 된다는 것이다.


처음에는 이 문제를 풀 때 무식하게 접근했는데

잘 생각해보니 쉽게 풀렸던 것 같다.



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

2268  (0) 2015.06.26
2357  (0) 2015.06.25
1138  (0) 2015.06.25
4158  (0) 2015.06.18
4883  (1) 2015.06.18
1890  (0) 2015.06.18

4158

알고리즘/acmicpc 2015.06.18 16:41 Posted by 아는 개발자

속도를 어떻게 높일 것인가에 대한 문제인데


문제에서 힌트로 주어지는 CD 넘버가 오름차순을 띤다고 했다.


가장 일반적으로 생각할 수 있는 방법은 트리 구조임을 이용해 O(nlogn)시간 내에 푸는 방법이 있을 수 있지만


상근이와 선영이의 CD로 주어지는 넘버 모두 오름차순을 띈다는 점을 이용해

O(N)시간에 해결 할 수 있다.



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

2357  (0) 2015.06.25
1138  (0) 2015.06.25
4158  (0) 2015.06.18
4883  (1) 2015.06.18
1890  (0) 2015.06.18
1976  (0) 2015.03.29

4883

알고리즘/acmicpc 2015.06.18 16:10 Posted by 아는 개발자

삼각그래프


알고리즘 문제를 풀 때 가장 기본적인 태도는


1. 먼저 문제를 잘 읽는다


2. 문제를 의심한다


여기선 문제를 잘 읽기는 했는데 문제를 의심하는 단계가 부족했다.


입력으로 비용의 제곱은 1000000보다 작다고 했는데 그렇다면 비용은 음수가 들어올 수도 있다는 이야기...


하지만 나는 그걸 몰랐고 쓸데 없이 틀렸다.


그런데 이런건 좀 친절히 설명해줘야 하는거 아닌가 ㅡㅡ



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

1138  (0) 2015.06.25
4158  (0) 2015.06.18
4883  (1) 2015.06.18
1890  (0) 2015.06.18
1976  (0) 2015.03.29
1199  (0) 2015.03.01
  1. 류현준 2016.12.15 15:29  댓글주소  수정/삭제  댓글쓰기

    좀 하시네요 ㅋㅋ

1890

알고리즘/acmicpc 2015.06.18 11:21 Posted by 아는 개발자

도착 할 경로가 몇개나 있는지 묻는 문제이다.


도착 할 좌표의 경로를 찾는데 집중 하기 보다는


각 좌표까지 이동 할 수 있는 경우의 수들을 모두 계산 한 후


마지막에 도착 지점의 경우의 수를 구해주면 풀기 쉽다.




여기서 도착할 경로의 범위가 2^63 까지 된다고 했는데

unsinged long long을 위 범위를 표현할 수 있다

printf로 표현하는 방법은 "%llu%이다.

방학도 끝났으니 분발해야겠다.


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

4158  (0) 2015.06.18
4883  (1) 2015.06.18
1890  (0) 2015.06.18
1976  (0) 2015.03.29
1199  (0) 2015.03.01
4256  (0) 2015.02.28