'Algorithm'에 해당되는 글 4건

  1. 2010.08.05 Palindrome Numbers (2)
  2. 2010.08.03 The Tourist Guide
  3. 2010.07.31 Word Index
  4. 2010.07.29 Knights Move

Palindrome Numbers

알고리즘 2010.08.05 15:30 |

문제 요약 : 
좌우가 대칭이 palindrome 수가 있습니다. 1, 2, 3, 4, ... 9, 11, 22, 33, ... 으로 순서가 있으며, 각 palindrome 숫자마다 차례대로 인덱스가 부여됩니다. 이러한 상황에서 인덱스를 주면 해당 인덱스의 palindrome 숫자를 구하는 문제입니다.


해결 방법 : 
일단 palindrome은 좌우가 대칭이므로 숫자의 반만 생각하면 됩니다.
저는 자리수별로 생각을 했는데,
1자리 수 = 1, 2, ... , 9까지 모두 9개가 있습니다.
2자리 수 = 11, 22, .. , 99까지 모두 9개가 있습니다.
3자리 수 = 101, 111, 121, ..., 191, 202, 212, ...292, .... , 999 까지 9 * 10개(90)가 있습니다.
이런 식으로 하는데,

자세히 살펴 보면,
1자리 수와 2자리 수는 모두 1자리만 보고 해당 자리수에서 나올 수 있는 가지수를 생각할 수 있습니다.
마찬가지로 3자리 수는 앞의 두자리 수만 가지고 가지수를 결정할 수 있고, 4자리수는 3자리수와 동일한 가지수를 가집니다.
이런 식으로 각 자리수 마다 나올 수 있는 가지수를 구하고 이를 누적하면 n자리수에서의 마지막 인덱스 값을 알 수 있습니다.(이 값을 배열에 저장해둡니다..)
예를들어, 1자리수는 9, 2자리수는 18, 3자리수는 108, ...

그리고 각 자리수마다 시작수를 저장해 둡니다. 
예를들어, 1자리수는 1, 2자리수는 1, 3자리수는 10, 4자리수는 10, ...
왜냐하면 1자리수는 1로 시작하고, 2자리수는 11로 시작하는데 11중에 1만 보면 되기 때문입니다.

이런식으로 테이블을 구성하고, 최대로 들어오는 index값이 2 * 10^9이므로 이 값 이상의 값이 누적값으로 나올때까지 배열을 구성하면 됩니다.

 자리수 1 2
누적 인덱스  18  108 198
 시작수 10 10 

배열을 다 구성하면 인풋을 받고, 받은 수의 자리수를 판단할 수 있겠죠.
예를 들어, 입력 인덱스가 13이라면 누적 인덱스를 차례대로 돌면서 누적인덱스가 입력 인덱스보다 큰 부분을 찾습니다. 그러면 그 인덱스가 입력 인덱스의 자리수가 되는거죠.
위의 표를 보면 18이 13보다 크므로 현재 인덱스의 자리수는 2가 되는 겁니다. 

자리수를 구했으면 이제 palindrome값을 찾아야 합니다.
만약 입력 인덱스가 N이고, 현재 자리수가 i라하면, 

찾아야할 palindrome의 절반에 해당하는 수 = N - lastIndex[i - 1] - 1

이 됩니다.
여기서 lastIndex배열은 누적 인덱스 배열입니다.
이런 식으로 숫자의 반을 구했으면 index가 홀수이냐, 짝수이냐에 따라 출력만 약간 다르게 해주면 끝납니다.

그리고 만약 누적 인덱스와 입력 인덱스가 동일하다면 결과는 그 자리수만큼 9로 채운 숫자이죠.
예를 들어, 입력 인덱스가 18이 들어왔다면, 이는 누적인덱스 표에 있는 18과 같으므로 2자리 수이고, 이 2자리수가 9로 채워지므로 답은 99가 됩니다.

결과 : Accepted

소스 코드


#include<iostream>
#include<cmath>
#include<string>

using namespace std;

const long long MAX_NUMBER = 2000000000;

long long N;
long long lastIndex[100];
long long startNumber[100];
int lastDigit;
int digit;
bool isLast;
string result;



void makeLastIndex() {
	startNumber[0] = 0;
	lastIndex[0] = 0;
	for(int i = 1; i <= 99; i++) {
		startNumber[i] = (int)pow(10.0, ceil(i / 2.0) - 1);
		lastIndex[i] = lastIndex[i - 1] + 9 * startNumber[i];
		if(lastIndex[i] >= MAX_NUMBER) {
			lastDigit = i;
			break;
		}
	}
}



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

	while(true) {
		cin >> N;
		if(N == 0) break;
		//end of input
		
		isLast = false;
		digit = lastDigit;
		//end of init

		for(int i = 1; i <= lastDigit; i++) {
			if(N == lastIndex[i]) {
				isLast = true;
				digit = i;
				break;
			} else if(N < lastIndex[i]) {
				digit = i;
				break;
			}
		}	//end of deciding digit

		result = "";
		if(isLast) {	
			//해당 자리 수의 마지막 인덱스일 경우 9가 자릿수만큼 채워진다.
			for(int i = 0; i < digit; i++) {
				result += "9";
			}
		} else {	
			long addingNumber = N - lastIndex[digit - 1] - 1;
			//palindrome의 반만 구한다.
			long halfResult = startNumber[digit] + addingNumber;
			//구한 값을 출력하기 쉽게 하려고 char[]에 넣는다.
			char halfResultString[20];
			sprintf(halfResultString, "%d", halfResult);

			//출력한다.
			int halfDigit = (int)ceil(digit / 2.0) - 1;
			for(int i = 0; i <= halfDigit; i++) {
				result += halfResultString[i];
			}

			if(digit % 2 == 0) {
				result += halfResultString[halfDigit];
			}

			for(int i = halfDigit - 1; i >= 0; i--) {
				result += halfResultString[i];
			}
		}

		cout << result << endl;
	}
	return 0;
}
저작자 표시
신고

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

Prime Gap  (0) 2010.08.28
Palindrome Numbers  (2) 2010.08.05
The Tourist Guide  (0) 2010.08.03
Word Index  (0) 2010.07.31
Knights Move  (0) 2010.07.29
Posted by Code-Moon

댓글을 달아 주세요

  1. BlogIcon acude 2010.08.07 14:05 신고 Address Modify/Delete Reply

    재미있네요!

The Tourist Guide

알고리즘 2010.08.03 00:22 |

문제 요약 : 출발 지점과 도착지점이 정해진 상태.
버스기사가 승객을 데리고 출발점에서 도착점까지 이동해야 합니다. 
하지만 승객 수가 많고, 각 도시간의 길에는 제한 인원이 있기 때문에 1번 이상의 trip이 필요합니다.
최소한의 trip수로 모든 승객을 다 도착지로 보내는 문제입니다.

문제 링크

해결 방법 : 다익스트라 알고리즘을 활용했습니다.

결과 : Accepted

소스 코드

#include<iostream>


using namespace std;

int N, R;
int c1, c2, p;
int start, dest, numOfTourists;
int line[101][101];
int value[101];
bool check[101];
int cur;

void init() {
	for(int i = 1; i <= 100; i++) {
		check[i] = false;
		value[i] = 0;
		for(int j = 1; j <= 100; j++) {
			line[i][j] = -1;
		}
	}
}

int calc() {
	check[start] = true;
	value[start] = 0;
	cur = start;
	
	while(true) {
		for(int i = 1; i <= 100; i++) {
			if(line[cur][i] != -1) {
				if(check[i]) continue;

				int temp;
				if(value[cur] > line[cur][i]) {
					temp = line[cur][i];
				} else {
					temp = value[cur];
				}

				if(value[i] == 0) {
					//i번째 vertex의 값이 비어 있다.
					value[i] = line[cur][i];
				} else if(value[i] < temp) {
					//i번째 vertext 값보다 현재 vertex 값에서 i번 vetex로 향하는 엣지의 합이 더 큰 경우
					value[i] = temp;
				} else if(value[i] > temp) {
					line[i][cur] = line[cur][i] = -1;
				}
			}
		}

		int max = -1;
		int index = 0;
		for(int i = 1; i <= 100; i++) {
			if(check[i] || value[i] == 0) continue;
			if(max < value[i]) {
				max = value[i];
				index = i;
			}
		}
		
		check[index] = true;
		cur = index;
		if(cur == dest) return value[dest];
	}
}

int calc2(int maxNum) {
	int num = 1;
	int addingNum = maxNum - 1;
	int sum = 0;
	while(true) {
		sum += addingNum;
		if(sum >= numOfTourists) return num;
		num++;
	}
}

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

	int index = 1;
	while(true) {
		cin >> N >> R;
		if(N == 0 && R == 0) break;

		init();

		for(int i = 0; i < R; i++) {
			cin >> c1 >> c2 >> p;
			line[c1][c2] = p;
			line[c2][c1] = p;
		}
		cin >> start >> dest >> numOfTourists;
		//end of input

		int result = calc();
		cout << "Scenario #" << index << endl;
		cout << "Minimum Number of Trips = " << calc2(result) << endl << endl;
		index++;
	}

	return 0;
}
저작자 표시
신고

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

Prime Gap  (0) 2010.08.28
Palindrome Numbers  (2) 2010.08.05
The Tourist Guide  (0) 2010.08.03
Word Index  (0) 2010.07.31
Knights Move  (0) 2010.07.29
Posted by Code-Moon

댓글을 달아 주세요

Word Index

알고리즘 2010.07.31 00:58 |

문제 요약 : 어떤 string이 숫자 값을 갖게 됩니다. string의 길이는 1~5이고, 뒤에 나오는 문자가 앞의 문자보다 커야만 합니다.
그렇지 않을 경우에는 invalid하다고 하여 0을 출력합니다.

예를 들면, 
a = 1
b = 2
c = 3
...
z = 26
ab = 27
aa는 invalid이므로 0
...
vwxyz = 83681

입력으로 스트링이 들어오면, 그 스트링에 해당하는 숫자를 반환하면 됩니다.

문제 링크





해결 방법 : 경우의 수를 따져가며 대표 string의 테이블을 구성했습니다. 
대표 string은 1자리 문자열일 경우 a, b, c, ,.... , z까지 모두 되고,
2자리 문자열일 경우 ab, bc, cd, de, .... , yz 가 됩니다. 
3자리 문자열일 경우 abc, bcd, cde, def, ... xyz가 됩니다.
이렇게 대표 문자열의 숫자 값을 테이블에 넣어두고, 계산을 진행합니다.

이 대표 문자열은 테이블에 다음과 같이 대응시켰습니다.

a = table[a][1]
b = table[b][1]
...
z = table[z][1]
ab = table[a][2]
bc = table[b][2]
...
yz = table[y][2]
abc = table[a][3]

즉, 이중 배열 table[][]이 있는데, 첫번째 대괄호 안에는 대표 문자의 시작 문자가 들어가고, 두번째 대괄호에는 문자열의 자리수가 들어갑니다.

그리고 그 값을 구할 때에는 테이블에서 약간의 규칙을 찾아야하는데, 경우의 수를 조금 생각해야할 것 같군요.
그리고 테이블의 값을 구하는 순서는 1자리 문자열부터 a~z까지 차례대로 구하고, 그 다음에 2자리 문자열 a~y까지 구하는 방식으로 합니다.(2자리 문자열은 yz가 마지막이므로 z는 구할 필요가 없습니다.) 

그러면 예를 들어 ab까지 즉, table[a][2]까지 구해진 상태에서 bc (table[b][2])를 구하려고 해봅시다.
bc의 값은 일단 ab의 값에서 출발해야 합니다. 왜냐하면 ab -> ac -> ad -> ... -> bc가 되기 때문이죠.
bc를 구하기 전에 az를 먼저 구해봅시다. az는 ab의 값에서 z의 값을 더하고 b의 값을 뺀 것과 같습니다.(왜 그런지는 직접 손으로 테이블 그려서 해보세요^^)
그렇게 az를 구하면 bc는 az의 바로 다음 문자열이라는 것을 깨닫게 됩니다.

즉, table[b][2] = table[a][2] + table[z][1] - table[b][1] + 1 이 됩니다.

이 식을 조금더 일반화 해보면, 

table[j][i] = table[j - 1][i] + table['z' - i + 1][i - 1] - table[j][i - 1] + 1;

이 됩니다.
위 식에서 table['z' - i + 1][i - 1]이 되는 것은, 1자리에서는 z까지 계산하지만, 2자리에서는 y까지 계산하고, 3자리에서는 x까지 계산하는 것과 관계가 있습니다.

이런 부분은 글로 적는 것보다 직접 테이블을 그려서 이해하는게 더 나을거라 생각이 드네요.


이런 방법으로 테이블을 구성하면 문제의 80% 정도는 푼거라 생각이 듭니다.

이제는 이미 구성된 테이블을 이용해서 문자열의 숫자만 계산해내면 되는거죠. ㅎ
예를 들어서 바로 설명하겠습니다.

만약, ace의 값을 구하고자 한다하면,
ace는 일단 테이블의 abc 값에서 시작합니다.
그리고 여기에서 bc의 값을 빼고 cd의 값을 더합니다.
또 여기에서 d의 값을 빼고 e의 값을 더합니다.

다시 식으로 정리를 해보면
ace = +abc - bc + cd - d + e
가 됩니다.

대충 감이 오시나요?
일단 위 식에서 사용한 값들은 모두 테이블에 저장되어 있는 대표값들 입니다.
그리고 abc에서 bc를 빼준 뒤 cd로 가는 것은, abc에서 acd 의 값으로 가기 위해서 입니다.
그리고 여기에서 d를 빼준 뒤 e를 더하는 것이 acd에서 ace가 되는 길이죠.

결과 : Accepted

이쯤에서 소스 코드를 보여드리겠습니다.

#include<iostream>
#include<string>

using namespace std;

int table['z' + 2][6];

void makeTable() {
	//테이블은 단 1회 만든다.
	//init
	memset(table, 0, sizeof(table));

	//process
	for(int i = 1; i <= 5; i++) {
		int c = 'z' - i + 2;
		int iterSize = c - 1;
		int addingNumber = table[c][i - 1];

		for(int j = 'a'; j <= iterSize; j++) {
			table[j][i] = table[j - 1][i] + addingNumber + 1 - table[j][i - 1];
		}
		table['a' - 1][i + 1] = table['a'][i];
	}
}

bool isNotValid(string str) {
	int size = str.length();
	for(int i = 0; i < size - 1; i++) {
		if(str[i] >= str[i + 1]) return true;
	}
	
	return false;
}

int getNumber(string str) {
	int sum = 0;
	int size = str.length();
	int digit = size;

	for(int i = 0; i < size; i++) {
		char c = str[i];
		sum += table[c][digit] - table[c + 1][digit - 1];
		digit--;
	}

	return sum;
}

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

	makeTable();

	string str;
	while(cin >> str) {
		if(isNotValid(str)) 
			cout << 0 << endl;
		else 
			cout << getNumber(str) << endl;
	}
	return 0;
}




글로 적으려니 정말 힘들군요..
어쨌든 이러한 방법으로 문제를 풀 수 있었습니다.
더 좋은 방법이 있다면 피드백 부탁드립니다.^^
저작자 표시
신고

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

Prime Gap  (0) 2010.08.28
Palindrome Numbers  (2) 2010.08.05
The Tourist Guide  (0) 2010.08.03
Word Index  (0) 2010.07.31
Knights Move  (0) 2010.07.29
Posted by Code-Moon

댓글을 달아 주세요

Knights Move

알고리즘 2010.07.29 23:47 |

문제 요약 : 체스 판의 크기와 출발점, 도착점이 주어지는데, 프로그래머는 출발점에서 시작하여 도착점으로 몇번 만에 도착하는가를 출력해야 합니다.

문제 링크

알고리즘 : BFS
자료구조 : 원형 큐(배열로 구현)

느낀 점 : STL의 deque... 엄청나게 느리다는 것.

Accept된 소스 코드
#include<iostream>

using namespace std;

typedef struct {
	int x, y;
}Point;

const int qSize = 90000;
Point q[qSize];
int pop = 0, push = 0;
int N, boardSize;
Point first, end, cur;
int board[300][300];
int curValue, childValue;
int left1, left2, right1, right2, up1, up2, down1, down2;

void init() {
	for(int i = 0; i < 300; i++) {
		for(int j = 0; j < 300; j++) {
			board[i][j] = -1;
		}
	}
	pop = 0;
	push = 0;
}

int BFS() {
	while(pop != push) {
		cur.x = q[pop].x;
		cur.y = q[pop].y;
		pop = (pop + 1) % qSize;
		curValue = board[cur.x][cur.y];
		childValue = curValue + 1;

		if(cur.x == end.x && cur.y == end.y) return curValue;

		left1 = cur.x - 1;
		left2 = cur.x - 2;
		right1 = cur.x + 1;
		right2 = cur.x + 2;
		up1 = cur.y - 1;
		up2 = cur.y - 2;
		down1 = cur.y + 1;
		down2 = cur.y + 2;

		if(left1 >= 0 && left1 < boardSize) {
			if(up2 >= 0 && up2 < boardSize) {
				if(board[left1][up2] == -1) {
					q[push].x = left1;
					q[push].y = up2;
					push = (push + 1) % qSize;
					board[left1][up2] = childValue;
				}
			}
			if(down2 >= 0 && down2 < boardSize) {
				if(board[left1][down2] == -1) {
					q[push].x = left1;
					q[push].y = down2;
					push = (push + 1) % qSize;
					board[left1][down2] = childValue;
				}
			}
		}

		if(left2 >= 0 && left2 < boardSize) {
			if(up1 >= 0 && up1 < boardSize) {
				if(board[left2][up1] == -1) {
					q[push].x = left2;
					q[push].y = up1;
					push = (push + 1) % qSize;
					board[left2][up1] = childValue;
				}
			}
			if(down1 >= 0 && down1 < boardSize) {
				if(board[left2][down1] == -1) {
					q[push].x = left2;
					q[push].y = down1;
					push = (push + 1) % qSize;
					board[left2][down1] = childValue;
				}
			}
		}

		if(right1 >= 0 && right1 < boardSize) {
			if(up2 >= 0 && up2 < boardSize) {
				if(board[right1][up2] == -1) {
					q[push].x = right1;
					q[push].y = up2;
					push = (push + 1) % qSize;
					board[right1][up2] = childValue;
				}
			}
			if(down2 >= 0 && down2 < boardSize) {
				if(board[right1][down2] == -1) {
					q[push].x = right1;
					q[push].y = down2;
					push = (push + 1) % qSize;
					board[right1][down2] = childValue;
				}
			}
		}

		if(right2 >= 0 && right2 < boardSize) {
			if(up1 >= 0 && up1 < boardSize) {
				if(board[right2][up1] == -1) {
					q[push].x = right2;
					q[push].y = up1;
					push = (push + 1) % qSize;
					board[right2][up1] = childValue;
				}
			}
			if(down1 >= 0 && down1 < boardSize) {
				if(board[right2][down1] == -1) {
					q[push].x = right2;
					q[push].y = down1;
					push = (push + 1) % qSize;
					board[right2][down1] = childValue;
				}
			}
		}

	}
}

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

	cin >> N;
	while(N--) {
		cin >> boardSize;
		cin >> first.x >> first.y;
		cin >> end.x >> end.y;

		init();

		board[first.x][first.y] = 0;
		q[push].x = first.x;
		q[push].y = first.y;
		push = (push + 1) % qSize;

		cout << BFS() << endl;
	}


	return 0;
}

저작자 표시
신고

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

Prime Gap  (0) 2010.08.28
Palindrome Numbers  (2) 2010.08.05
The Tourist Guide  (0) 2010.08.03
Word Index  (0) 2010.07.31
Knights Move  (0) 2010.07.29
Posted by Code-Moon

댓글을 달아 주세요

티스토리 툴바