Archive: 2018

2018
0
computer sciencealgorithms

백준[7569] - 토마토2

문제백준 7569 문제 보기 접근 방법7576번 문제와 동일하지만 다른 점은 아래와 위까지 진행된다는 점이다. 이전 토마토 문제와 같이 bfs를 활용하되 토마토 배열을 3차원으로 활용하여 위, 아래면까지 검사를 진행한다. 코드#include <iostream> #include <queue> #include <algorithm> using n

0
computer sciencealgorithms

백준[2583] - 영역 구하기

문제백준 2583 문제 보기 접근 방법map 배열에 먼저 직사각형을 의미하는 좌표를 -1로 저장한다. 이후 map 배열를 검사하면서 직사각형 영역이 아니라면 완전탐색을 실시한다. 코드#include <iostream> #include <vector> #include <algorithm> using namespace std; stru

0
computer sciencealgorithms

백준[1520] - 내리막 길

문제백준 1520 문제 보기 접근 방법아직은 bottom-up 방식이 익숙치가 않아 거의 모든 다이나믹 문제를 top-down으로 접근하고 있다. 이번 문제도 마찬가지로 top-down 방식으로 접근했다. 동서남북으로 검사하되 범위 안에 있고 내리막일 경우 계속 진행하는 식으로 문제를 풀었다. 제대로 푼것 같았지만 제출했을때 시간초과가 났다. 이유는 길이

0
computer sciencealgorithms

백준[10942] - 팰린드롬?

문제백준 10942 문제 보기 접근 방법질문의 갯수가 최대 1000000이고 배열을 부분적으로 검사까지 진행해야하니 이는 다이나믹으로 해결해야한다. 일단 팰린드롬은 숫자가 범위 구간내에 대칭이 이루어져야 하므로 이 점을 고려해 점화식을 세워야한다. bottom-up 방식으로 먼저 길이가 1일 경우는 모두 팰린드롬이므로 dp[i][i] = 1을 저장한다.

0
computer sciencealgorithms

백준[1890] - 점프

문제백준 1890 문제 보기 접근 방법그냥 완전탐색으로 문제를 풀 경우 시간 초과가 났다. 따라서 중간 중간 메모이제이션을 활용해 값을 저장했다. 코드#include <iostream> #include <algorithm> #include <cstring> using namespace std; int N; int map[100][100];

0
computer sciencealgorithms

백준[11048] - 이동하기

문제백준 11048 문제 보기 접근 방법다아나믹프로그램을 활용해서 문제를 해결할 수 있다. 먼저 조건을 보면 이동하는 경우는 총 3가지로 오른쪽, 아래, 대각선 방향으로 이동이 가능하다.가장 위쪽 행과 가장 왼쪽 열은 이전 사탕의 갯수를 그대로 더하고 나머지 가운데 부분은 접근 가능한 방향에서의 최대값을 가지는 식으로 코드를 작성했다. 가장 위쪽dp[i]