벡터와 기존 타 STL 컨테이너 차이를 알고자 검색하다가
굉장히 정리가 잘된 블로그를 찾아서 링크 해놓는다.
vector 이외에도 List 등의 STL Container 내용이 상세히 설명되어있다.
Link : http://blog.daum.net/coolprogramming/77
2011년 2월 5일 토요일
Best Path On a Diamond
문제 : http://algospot.com/problems/read/DIAMONDPATH
접근 방법
Solution을 도출하기까지의 과정은 굉장히 빨랐다.
다만, 쌍for 한번으로 다이아몬드를 받아내려고, 테크닉을 부리다가 시간이 꽤 지났다..
(그냥 쌍for로 상단 삼각형모양받고 , 다시한번 쌍for로 받아도 되는걸 객기 부려봤다.;)
Input은 다소 낭비가 있더라고 다이아몬드를 받을 수 있는 크기의 2차원 배열(Notj jagged)로 받아서 처리했다. Memoization을 위한 배열 역시 같은 크기의 Array를 사용하였다.
다이아몬드 임의의 위치 n자신의 Cost를 Cost(n)이라고 하고, n까지의 도달하는데 최대Cost를 An이라고 하자.
An = Cost(n) + MAX( n에 도달할 수 있는 2개까지의 Path (A(n-1))
Array로 표현하자면,
Path[n][k] = Cost[n][k] + Max(Path[n-1][k],Path[n-1][k-1]) // 다이아몬드 확장 루틴
Path[n][k] = Cost[n][k] + Max(Path[n-1][k],Path[n-1][k+1]) // 다이아몬드 축소 루틴
// n-1, k-1, k+1을 하기 때문에 Index Overflow, Underflow관리는 알아서 해줘야 하는 사안.
몇문제 풀고 보니 DP가 분석 후 문제 구축만 잘해내면 프로그래밍은 굉장히 깔끔하고
코드도 짧다.
접근 방법
Solution을 도출하기까지의 과정은 굉장히 빨랐다.
다만, 쌍for 한번으로 다이아몬드를 받아내려고, 테크닉을 부리다가 시간이 꽤 지났다..
(그냥 쌍for로 상단 삼각형모양받고 , 다시한번 쌍for로 받아도 되는걸 객기 부려봤다.;)
Input은 다소 낭비가 있더라고 다이아몬드를 받을 수 있는 크기의 2차원 배열(Notj jagged)로 받아서 처리했다. Memoization을 위한 배열 역시 같은 크기의 Array를 사용하였다.
다이아몬드 임의의 위치 n자신의 Cost를 Cost(n)이라고 하고, n까지의 도달하는데 최대Cost를 An이라고 하자.
An = Cost(n) + MAX( n에 도달할 수 있는 2개까지의 Path (A(n-1))
Array로 표현하자면,
Path[n][k] = Cost[n][k] + Max(Path[n-1][k],Path[n-1][k-1]) // 다이아몬드 확장 루틴
Path[n][k] = Cost[n][k] + Max(Path[n-1][k],Path[n-1][k+1]) // 다이아몬드 축소 루틴
// n-1, k-1, k+1을 하기 때문에 Index Overflow, Underflow관리는 알아서 해줘야 하는 사안.
// Maximum Cost로 Table Construction
bool flag=false;
tmpsize = size;
path[0][0] = dia[0][0];
for(int i=1; i<2*size-1; i++)
{
if( i>=size ) {tmpsize--; flag=true;}
for(int j=0; j<tmpsize; j++)
{
if(flag) path[i][j] = dia[i][j] + max(path[i-1][j+1], path[i-1][j]);
if( j==0 && !flag ) path[i][j] = dia[i][j]+path[i-1][j];
else if(!flag)path[i][j] = dia[i][j] + max(path[i-1][j-1], path[i-1][j]);
if( i==j ) break;
}
}몇문제 풀고 보니 DP가 분석 후 문제 구축만 잘해내면 프로그래밍은 굉장히 깔끔하고
코드도 짧다.
2011년 2월 4일 금요일
Coin Change
문제 : http://algospot.com/problems/read/COINS
접근 방법
알고리즘 수업시간에 배웠던 내용이고, 공부했던 기억이 분명히 있었는데 한참을 떠올리려 고민하다가, 결국 강의자료 앞부분을 보고 점화식을 만들어 풀었다 ...;; 그때는 이해를하지 않고 암기를 해서 풀었나보다 (반성)ㅠ
잔돈의 종류가 n개로 k원의 거스름돈을 주는 가지수를 Coin(n, k)라고 하면,
임의의 잔돈 Cn이 포함된 경우 + 동전 Cn이 포함되지 않는 경우로 나눌 수 있다.
전자의 경우 Coin(n, k-Cn)
후자의 경우 Coin(n-1, k)
따라서 Coin(n, k) = Coin(n, k-Cn) + Coin(n-1, k)
발전적 제언.
k개 만큼의 배열을 선언하는데, 몇만원을 거슬러주는 경우 상당히 큰 배열을 필요로 하기때문에 메모리 초과현상이 나타날 수 있다. 이를 해결하기 위한 테크닉이 필요할 것 같다.
(물론 위 문제에서는 Cover 가능한 범위에서 Constraint되어 있다.)
접근 방법
알고리즘 수업시간에 배웠던 내용이고, 공부했던 기억이 분명히 있었는데 한참을 떠올리려 고민하다가, 결국 강의자료 앞부분을 보고 점화식을 만들어 풀었다 ...;; 그때는 이해를하지 않고 암기를 해서 풀었나보다 (반성)ㅠ
잔돈의 종류가 n개로 k원의 거스름돈을 주는 가지수를 Coin(n, k)라고 하면,
임의의 잔돈 Cn이 포함된 경우 + 동전 Cn이 포함되지 않는 경우로 나눌 수 있다.
전자의 경우 Coin(n, k-Cn)
후자의 경우 Coin(n-1, k)
따라서 Coin(n, k) = Coin(n, k-Cn) + Coin(n-1, k)
발전적 제언.
k개 만큼의 배열을 선언하는데, 몇만원을 거슬러주는 경우 상당히 큰 배열을 필요로 하기때문에 메모리 초과현상이 나타날 수 있다. 이를 해결하기 위한 테크닉이 필요할 것 같다.
(물론 위 문제에서는 Cover 가능한 범위에서 Constraint되어 있다.)
#define REP(i,n) for((i)=0; (i)<(int)(n); (i)++)
// 초항 대입
REP(i, numOfCoin+1) dp[i][0]=1;
REP(i, change+1) dp[0][i]=0;
//DP table 계산
for(i=1; i<numOfCoin+1; i++)
{
for(int j=1; j<change+1; j++)
{
if(j-coins[i-1] < 0)
dp[i][j] = dp[i-1][j];
else
dp[i][j] = (dp[i][j-coins[i-1]]+dp[i-1][j])%1000000007;
}
}
Tiling a Grid With Dominoes
출처 : http://algospot.com/problems/read/GRID
해법
Google Code jam 문제풀다가 Dynamic Programming 벽에 부딫혀서 알고스팟의 DP문제를 물면서 연습도 하고, 감각을 익히려 한다.
- Time Limit: 1000 ms
- Memory Limit: 65536 kb
We wish to tile a grid 4 units high and N units long with rectangles (dominoes) 2 units by one unit (in either orientation). For example, the figure shows the five different ways that a grid 4 units high and 2 units wide may be tiled.
Write a program that takes as input the width, W, of the grid and outputs the number of different ways to tile a 4-by-W grid.
Input Specification
The first line of input contains a single integer N, (1 ≤ N ≤ 1000) which is the number of datasets that follow.
Each dataset contains a single decimal integer, the width, W, of the grid for this problem instance.
Output Specification
For each problem instance, there is one line of output: The problem instance number as a decimal integer (start counting at one), a single space and the number of tilings of a 4-by-W grid. The values of W will be chosen so the count will fit in a 32-bit integer.
Sample Input
3
2
3
7Sample Output
1 5
2 11
3 781해법
점화식 세우는 것이 관건.
An, Bn, Cn으로 나누어서 점화식을 다음과 같이 세웠다.
An = A(n-1)+A(n-2)+2*B(n-1)+Cn : n번째 너비만큼 채우는 방법의 수
Bn = A(n-1)+B(n-1) : n번째 너비만큼 모서리2칸을 비운 나머지를 모두 채우는 방법의 수
Cn = A(n-2)+C(n-2) : n번째 너비만큼 'ㄷ'형태로 채우는 방법의 수
각 점화식의 초항(n=0~2까지)은 간단하기 때문에 손으로 구했다.
An = A(n-1)+A(n-2)+2*B(n-1)+Cn : n번째 너비만큼 채우는 방법의 수
Bn = A(n-1)+B(n-1) : n번째 너비만큼 모서리2칸을 비운 나머지를 모두 채우는 방법의 수
Cn = A(n-2)+C(n-2) : n번째 너비만큼 'ㄷ'형태로 채우는 방법의 수
각 점화식의 초항(n=0~2까지)은 간단하기 때문에 손으로 구했다.
int a[1001], b[1001], c[1001];
int size;
a[0]=0; a[1]=1; a[2]=5;
b[0]=0; b[1]=1; b[2]=2;
c[0]=0; c[1]=0; c[2]=1;
in >> size;
for(int i=3; i<=size; i++)
{
c[i] = a[i-2]+c[i-2];
b[i] = a[i-1]+b[i-1];
a[i] = a[i-2]+a[i-1]+2*b[i-1]+c[i];
}
ps. 문제 붙이니까 내 블로그 Grid랑 잘 안맞네;; 다음부턴 링크만 걸어둬야 겠다;
2011년 2월 3일 목요일
Google code jam 2010 Round A : Problem A
Problem : http://code.google.com/codejam/contest/dashboard?c=544101#s=p0&a=0
문제 접근
Rotation 후 중력작용이라고 했는데 결국 둘을 종합해서 Gravity방향을 파악해서 땡겨주면 된다는 점을 아는게 핵심이면 핵심이겠다. ( 이걸 몰라도 답은 구하겠지만, 소스 TLE나올 우려가 있다.) 나름 TLE 염려하면서 코딩했는데도 Large Set 컴파일하니까 0.5초정도 걸리더라..
천천히 모듈별로 짜서 하루 걸렸다. 문제에서 clockwise의 단어를 몰라서 그냥 그러려니 하고 넘어갔다가 나중에 90도 방향으로 1번 돌릴 수 있다고 해서... 나는 왼쪽 오른쪽 전부 코딩했다..;; 그리고 처음 상태에서 판별 + 회전한 상태에서 모두 판별 해서 이상하게 종합된 결과를 내서 Incorrect를 계속 받았다.. -_-;; (역시 영어가 엄청 중요하다 ㅠㅠ - 해석이 어렵다가 이제는 아예 잘못읽어서 산으로 가다니...;;)
Rotation도 다 짜고 가만생각하니까 필요가 없었고... Gravity방향만 조절해주면 되었다..
여러모로 삽질을 많이 했던 문제.
디버깅할때 winCondition Size를 1줄이지 않은것때문에 2시간정도 찾다가 완전 의욕 잃고 게임좀하다가 다시 예제 하나하나 살펴보다가 이상한 곳을 발견해서 추적해 찾았다 -_ㅠ...
역시 WA가 뜰때는 완전 포기한 상태에서 처음부터 차근따라가는게 좋은 수다..;;
모듈별로 나눠서 코딩해서 그런지 코드가 나름 짧게 짰다. 하지만 그래도 130라인 ;;
8방향 삽질을 줄이고자 노력했으나, 쩝...;; 비슷한 라인이 뭉탱이로 있는곳이 군데군데 보인다 ㅠ
int를 리턴하는데, 0 : Neither, 1 : Blue, 2 : Red, 3 : Both 를 의미한다.
자질구레한 if문장이 엄청많은 이유는 8방향에 대한 제한 조건이 각각 달라서이다 ㅠ...
(처음에 엉뚱한 생각으로 통합했다가 디버깅으로 고친 문장..;;)
if문장은 Time Complexity에 큰 영향을 안주기에 더덕더덕 붙여서 썼다.
문제 접근
Rotation 후 중력작용이라고 했는데 결국 둘을 종합해서 Gravity방향을 파악해서 땡겨주면 된다는 점을 아는게 핵심이면 핵심이겠다. ( 이걸 몰라도 답은 구하겠지만, 소스 TLE나올 우려가 있다.) 나름 TLE 염려하면서 코딩했는데도 Large Set 컴파일하니까 0.5초정도 걸리더라..
천천히 모듈별로 짜서 하루 걸렸다. 문제에서 clockwise의 단어를 몰라서 그냥 그러려니 하고 넘어갔다가 나중에 90도 방향으로 1번 돌릴 수 있다고 해서... 나는 왼쪽 오른쪽 전부 코딩했다..;; 그리고 처음 상태에서 판별 + 회전한 상태에서 모두 판별 해서 이상하게 종합된 결과를 내서 Incorrect를 계속 받았다.. -_-;; (역시 영어가 엄청 중요하다 ㅠㅠ - 해석이 어렵다가 이제는 아예 잘못읽어서 산으로 가다니...;;)
Rotation도 다 짜고 가만생각하니까 필요가 없었고... Gravity방향만 조절해주면 되었다..
여러모로 삽질을 많이 했던 문제.
디버깅할때 winCondition Size를 1줄이지 않은것때문에 2시간정도 찾다가 완전 의욕 잃고 게임좀하다가 다시 예제 하나하나 살펴보다가 이상한 곳을 발견해서 추적해 찾았다 -_ㅠ...
역시 WA가 뜰때는 완전 포기한 상태에서 처음부터 차근따라가는게 좋은 수다..;;
//right gravity
for(int i=0; i<mapsize; i++)
{
int cnt=0;
for(string::iterator iter=right[i].begin(); iter!=right[i].end(); )
{
if(*iter == '.')
{
iter = right[i].erase(iter);
cnt++;
}
else iter++;
}
if(cnt==mapsize) continue;
else
{
for(int j=0; j<cnt; j++)
right[i].insert(0,".");
}
}
//checking Winner
result = checking(right, winCondition, mapsize, &Bwin, &Rwin);
모듈별로 나눠서 코딩해서 그런지 코드가 나름 짧게 짰다. 하지만 그래도 130라인 ;;
8방향 삽질을 줄이고자 노력했으나, 쩝...;; 비슷한 라인이 뭉탱이로 있는곳이 군데군데 보인다 ㅠ
int를 리턴하는데, 0 : Neither, 1 : Blue, 2 : Red, 3 : Both 를 의미한다.
int checking(string* map, int win, int size, bool* Bwin, bool* Rwin)
{
const char** tmp = new const char*[size];
for(int i=0; i<size; i++)
{
tmp[i] = map[i].c_str();
}
for(int i=0; i<size; i++)
{
for(int j=0; j<size; j++)
{
if(tmp[i][j]=='B'&&!(*Bwin) || tmp[i][j]=='R'&&!(*Rwin))
{
bool flag=false;
// 8방향에 대한 test 호출
if(direction8(tmp, i, j, -1, -1, win-1, size)){flag=true;} //좌상
else if(direction8(tmp, i, j, -1, 0, win-1, size)){flag=true;} //상
else if(direction8(tmp, i, j, -1, 1, win-1, size)){flag=true;} //우상
else if(direction8(tmp, i, j, 0, 1, win-1, size)){flag=true;} //우
else if(direction8(tmp, i, j, 1, 1, win-1, size)){flag=true;} //우하
else if(direction8(tmp, i, j, 1, 0, win-1, size)){flag=true;} //하
else if(direction8(tmp, i, j, 1, -1, win-1, size)){flag=true;} //좌하
else if(direction8(tmp, i, j, 0, -1, win-1, size)){flag=true;} //좌
if(flag && tmp[i][j]=='B') *Bwin=true;
else if(flag && tmp[i][j]=='R') *Rwin=true;
}
}
}
if(*Bwin && *Rwin) return 3;
else if(*Rwin) return 2;
else if(*Bwin) return 1;
else return 0;
}
자질구레한 if문장이 엄청많은 이유는 8방향에 대한 제한 조건이 각각 달라서이다 ㅠ...
(처음에 엉뚱한 생각으로 통합했다가 디버깅으로 고친 문장..;;)
if문장은 Time Complexity에 큰 영향을 안주기에 더덕더덕 붙여서 썼다.
bool direction8(const char** map, int x, int y, int dir1, int dir2, int win, int size)
{
bool winflag = true;
//해당 direction 방향으로 진행할때 map을 벗어나는 경우 false 처리
if( dir1==-1 && dir2==-1 ) //좌상
{ if(x+dir1*win<0 || y+dir2*win<0) return false;}
else if(dir1==-1 && dir2==0) //상
{ if(x+dir1*win<0) return false;}
else if(dir1==-1 && dir2==1) //우상
{ if(x+dir1*win<0 || y+dir2*win>=size) return false;}
else if(dir1==0 && dir2==1) //우
{ if(y+dir2*win>=size) return false;}
else if(dir1==1 && dir2==1) //우하
{ if(x+dir1*win>=size || y+dir2*win>=size) return false;}
else if(dir1==1 && dir2==0) //하
{ if(x+dir1*win>=size) return false;}
else if(dir1==1 && dir2==-1) //좌하
{ if(y+dir2*win<0 || x+dir1*win>=size) return false;}
else if(dir1==0 && dir2==-1) //좌
{ if(y+dir2*win<0) return false;}
for(int i=1; i<=win; i++)
{
if(map[x][y] != map[x+dir1*i][y+dir2*i])
winflag =false;
}
return winflag;
}
피드 구독하기:
글 (Atom)