[문제 링크]

algospot.com :: JUMPGAME

외발 뛰기 문제 정보 문제 땅따먹기를 하다 질린 재하와 영훈이는 땅따먹기의 변종인 새로운 게임을 하기로 했습니다. 이 게임은 그림과 같이 n*n 크기의 격자에 각 1부터 9 사이의 정수를 쓴 상��

www.algospot.com

책보고 정석으로 공부하면서 스스로 풀게된 첫번째 동적계획법 유형의 문제이다.

 

Solution(y, x)는 입력이 같을 경우 항상 같은 값을 반환하는 참조적 투명 함수이기 때문에, 메모이제이션 기법을 적용할 수 있다.

최대 크기가 100X100인 2차원 배열 memo[100][100] 를 선언하고 -1로 초기화하여, memo[y][x]가 -1이라면 처음 방문하는 지점이므로 성공 여부를 탐색하고, 성공 여부를 저장한다. -1이 아니라면 이미 탐색했던 지점이므로 memo[y][x]값을 바로 리턴해준다.

 

기저사례로 배열의 범위를 벗어날 경우 false, 현재 좌표가 (N-1, N-1) 이라면 끝에 도달한 것이므로 true를 반환해주도록 구현하였다.

#include <iostream>
#include <cstring>
using namespace std;

int N, board[100][100], memo[100][100];

bool Solution(int startY,int startX)
{
	if (startY >= N || startX >= N) return false; // 기저사례. 범위 벗어나면 false

	if (startY == N - 1 && startX == N - 1) return true; // 기저사례. 끝에 도달했다면 true

	int& ret = memo[startY][startX];

	if (ret != -1) return ret; // 메모이제이션. 이미 해당 좌표에 대해 경로탐색을 해봤다면 저장한 성공여부 반환

	return ret = Solution(startY + board[startY][startX], startX) || Solution(startY, startX + board[startY][startX]);
}

int main(void)
{
	int testcase;
	cin >> testcase;

	while (testcase--)
	{
		cin >> N;
		memset(memo, -1, sizeof(board));
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				cin >> board[i][j];

		if (Solution(0, 0))
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
	}

	return 0;
}

 

 

알고리즘 200일 프로젝트 - 48 day

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

알고리즘 문제해결전략 예제:삼각형 위 최대경로 (ID: TRIANGLEPATH)  (0) 2020.05.26
알고리즘 문제해결전략 문제8.2 와일드카드 (ID: WILDCARD)  (0) 2020.05.25
알고리즘 문제해결전략 문제7.4 울타리 잘라내기 (ID: FENCE)  (0) 2020.05.09
알고리즘 문제해결전략 문제7.2 쿼드 트리 뒤집기 (ID: QUADTREE)  (0) 2020.05.09
알고리즘 문제해결전략 문제6.8 시계 맞추기(ID: CLOCKSYNC)  (0) 2020.04.10

[문제 링크]

algospot.com :: FENCE

울타리 잘라내기 문제 정보 문제 너비가 같은 N개의 나무 판자를 붙여 세운 울타리가 있습니다. 시간이 지남에 따라 판자들이 부러지거나 망가져 높이가 다 달라진 관계로 울타리를 통째로 교체하기로 했습니다. 이 때 버리는 울타리의 일부를 직사각형으로 잘라내 재활용하고 싶습니다. 그림 (b)는 (a)의 울타리에서 잘라낼 수 있는 많은 직사각형 중 가장 넓은 직사각형을 보여줍니다. 울타리를 구성하는 각 판자의 높이가 주어질 때, 잘라낼 수 있는 직사각형의 최대

algospot.com

분할정복은 문제를 부분 문제로 뚝 자르고 잘라져서 나온 조각에 대해 똑같이 처음 했던 것처럼 뚝 자르기를 반복하여 정답을 찾아내는 방식인거같다.

다만 완전탐색과 조금 다른점이 있다면 문제마다 구현해야할 기저사례, 점화식을 깊게 생각해봐야하고, 이를 구현하는 것이 까다롭다는 것이다. 대강 원리는 이해했으니 문제를 많이 풀어보면서 문제 유형에 익숙해지고 구현력을 키워야겠다.

#include <iostream>

#include <vector>

using namespace std;

 

vector<int> fence;

inline int max(const int a, const int b)

{

    return a > b ? a : b;

}

inline int min(const int a, const int b)

{

    return a < b ? a : b;

}

int Solution(int left, int right)

{

    if (left == right) return fence[left];

    int mid = (left + right) / 2;

    int ret = max(Solution(left, mid), Solution(mid + 1, right));

    int lt = mid, rt = mid+1;

    int height = min(fence[lt], fence[rt]);

    ret = max(ret, height * 2);

 

    while (left < lt || rt < right)

    {

        if (rt < right && (left == lt || fence[lt-1] < fence[rt+1]))

        {

            rt++;

            height = min(height, fence[rt]);

        }

        else

        {

            lt--;

            height = min(height, fence[lt]);

        }

        ret = max(ret, height * (rt - lt + 1));

    }

    return ret;

}

 

int main(void)

{

    int testcase;

    cin >> testcase;

    while (testcase--)

    {

        int num, w;

        cin >> num;

        for(int i =0; i<num; i++)

        {

            cin >> w;

            fence.push_back(w);

        }

        cout << Solution(0,num-1) << endl;

        fence.clear();

    }

}

Colored by Color Scripter

 

 

알고리즘 200일 프로젝트 - 35day

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

알고리즘 문제해결전략 문제8.2 와일드카드 (ID: WILDCARD)  (0) 2020.05.25
알고리즘 문제해결전략 예제: 외발 뛰기 (ID: JUMPGAME)  (0) 2020.05.22
알고리즘 문제해결전략 문제7.2 쿼드 트리 뒤집기 (ID: QUADTREE)  (0) 2020.05.09
알고리즘 문제해결전략 문제6.8 시계 맞추기(ID: CLOCKSYNC)  (0) 2020.04.10
알고리즘 문제해결전략 문제6.5 게임판 덮기(ID: BOARDCOVER)  (0) 2020.04.09

[문제 링크]

 

algospot.com :: QUADTREE

쿼드 트리 뒤집기 문제 정보 문제 대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리(quad tree)란 것이 있습니다. 주어진 공간을 항상 4개로 분할해 재귀적으로 표현하기 때문에 쿼드 트리라는 이름이 붙었는데, 이의 유명한 사용처 중 하나는 검은 색과 흰 색밖에 없는 흑백 그림을 압축해 표현하는 것입니다. 쿼드 트리는 2N × 2N 크기의 흑백 그림을 다음과 같은 과정을 거쳐 문자열로 압축합니다. 이 그림의 모든

algospot.com

분할정복 알고리즘 부분은 교재에 나와있는 소스코드와 동일하다.

다만 책에서 설명이 안되어있는데, 매개변수로 반복자를 참조하기 위해서는 비 const 반복자를 전달해야한다.

tree.begin() 이 반환하는 반복자는 const 반복자이므로 따로 비 const 반복자를 선언하고 tree.begin()으로 초기화해줘야 한다는 점만 주의하면 될 것 같다.

#include <iostream>
#include <string>
using namespace std;

string Reverse(string::iterator& iter)

{

    char head = *iter;

    iter++;

    if (head == 'w' || head == 'b') return string(1, head);

 

    string upperLeft = Reverse(iter);

    string upperRight = Reverse(iter);

    string lowLeft = Reverse(iter);

    string lowRight = Reverse(iter);

 

    return string("x") + lowLeft + lowRight + upperLeft + upperRight;

}

int main(void)

{

    int testcase;

    cin >> testcase;

    string tree;

    while (testcase--)

    {

        cin >> tree;

        string::iterator iter = tree.begin();

        cout << Reverse(iter) << endl;

    }

}

Colored by Color Scripter

 

알고리즘 200일 프로젝트 - 34day

저작자표시 비영리

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

알고리즘 문제해결전략 예제: 외발 뛰기 (ID: JUMPGAME)  (0) 2020.05.22
알고리즘 문제해결전략 문제7.4 울타리 잘라내기 (ID: FENCE)  (0) 2020.05.09
알고리즘 문제해결전략 문제6.8 시계 맞추기(ID: CLOCKSYNC)  (0) 2020.04.10
알고리즘 문제해결전략 문제6.5 게임판 덮기(ID: BOARDCOVER)  (0) 2020.04.09
알고리즘 문제해결전략 문제6.3 소풍(ID: PICNIC)  (0) 2020.04.09

+ Recent posts

티스토리툴바