펭로그

문제링크 : https://boj.kr/11048 위 그림과 같이 3방향으로 이동하면서 경로 상의 최대 값을 찾는 문제이다. 단계를 계속 진행해서 마지막까지 가게 되면 계산이 가능한 방향은 위 그림처럼 된다.DP 식으로 표현해보면 다음과 같이 표현 가능하다.DP[N][M] = MAX (DP[N-1][M], DP[N][M-1], DP[N-1][M-1]) + 자기자신값 12345678910111213141516171819202122232425262728293031323334// BOJ 11048 이동하기#include #include using namespace std; int max(int a, int b) { return a > b ? a : b;} int max(int a, int b, int c) {..

처음으로 코드포스의 시스템을 경험해보았다.일단 해커랭크처럼 영어로 되어 있기 때문에 해석하는 데에 약간의 시간이 걸리는 것은 어쩔 수 없는 모양.. ㅠㅠ 첫 도전의 결과는 너무 참담했다.. 겨우 2문제B번 문제도 50분만에 겨우 풀었는데 예외 조건을 제대로 생각하지 못해서 시간을 너무 많이 썼다.예외 찾는데만 문제 풀이 시간만큼을 더 써버렸으니.. A. Heist사실 너무 쉬운 문제인데 문제 이해 + 해석 덕분에 약간 시간을 잡아 먹은듯 하다.주어진 숫자를 오름차순으로 정렬한 다음 중간 중간 비어있는 숫자 간격이 몇인지 누적해서 체크하면 쉽게 구할 수 있다. 1234567891011121314151617181920212223242526// Codeforces Round #509 (Div. 2)// A. ..

문제링크 : https://boj.kr 시뮬레이션 문제로 주어진 조건에 맞게 그대로 풀어내려가면 되는 문제이다.문제 접근 방법은 DFS 방식이랑 크게 차이 없지만 DFS로 풀면 스택이 계속 쌓이기 때문에 이렇게 푸는 편이 더 좋지 않을까 생각한다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778// BOJ 14503 로봇 청소기#include #include using namespace std; struct pt{ int x, y, d;}; const int dx[] = {-1, 0, 1, ..

문제링크 : https://boj.kr/7562 (시작점) -> (끝점)까지 나이트가 갈 수 있는 경로의 최단거리를 구하는 문제로 이동 가능한 8방향으로 BFS를 돌리면 풀 수 있다.장애물 없이 오로지 도달만 하면 되기 때문에 방문 체크를 위한 배열 visited만 선언해주었다.방문 조건은 (0,0) ~ (len-1, len-1)의 범위로만 한정하였다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960// BOJ 7562 나이트의 이동#include #include #include using namespace std; const int dx[] = {-2,..

문제링크 : https://boj.kr/9465 DP 문제로 아래의 3가지 케이스로 계산할 수 있다. case 1.o xx o case 2.o x xx x o case 3.x x o xo x x o 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647// BOJ 9465 스티커#include #include int max(int a, int b) { return a > b ? a : b;}int max(int a, int b, int c){ return max(max(a, b), c);} using namespace std; int main() { ios_base::sync_with_stdio(false)..

문제링크 : https://boj.kr/2805 1. 동적계획법(DP)을 이용한 풀이법 : 시간복잡도 O(N)나무의 길이가 제일 큰 것부터 시작하여 한단계씩 내려오면서 누적 합이 입력에서 주어진 값보다 클 때까지 구하는 방법으로 풀었다.입력 받은 값들을 내림차순으로 정렬하고 맨 첫번째 인덱스에 해당하는 값부터 시작하여 1씩 높이를 빼가면서 계산했다. 나무의 높이(arr[N])가 기준 높이(result)보다 높은 부분 까지만 인덱스를 탐색하고 기준 높이 이하(arr[N] - result)가 0 이하인 값들)가 나오면 현재 누적 잘린 나무들의 합이 정답보다 작다면 계속 루프를 진행한다.이때, 높이를 1씩 빼게되면 현재까지 진행해왔던 나무들의 높이가 각각 1씩 추가되기 때문에 sum += ptr 구문을 넣어 ..

문제 링크 : https://boj.kr/2293 1234567891011121314151617181920212223242526272829303132// BOJ 2293 동전1#include using namespace std; int dp[10001]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); freopen("../input.txt", "r", stdin); int num, result; cin >> num >> result; vector coin(num + 1); vector dp(result + 1, 0); for (int i = 1; i > coin[i]; dp[0] = 1; for (int cn :..

문제링크 : https://boj.kr/1463 DP를 사용하면 이전 단계의 계산 결과를 그대로 활용할 수 있는 문제이다.문제에서 힌트로 주어진 10을 연산하는 방법을 생각해보면10 -> 5 -> 4 -> 2 -> 110 -> 9 -> 3 -> 1이런 방법이 나올 수 있을 것이다.10이라는 숫자는 바로 2로 나눌 수 있는 숫자이지만 -1을 한 후에 연산하면 횟수가 더 적은 것을 확인할 수 있다.따라서, 어떤 숫자가 2나 3으로 나눌 수 있을 지라도 -1을 했을 때와 비교한 후 최소 횟수가 어느쪽인지를 취하면 문제를 풀 수 있게 된다. 1을 뺀 후에 연산하는 방법이 어떤 경우에도 허용이 되기 때문에 먼저 1을 빼서 연산한 횟수를 계산한다.현재 숫자에서 1을 뺀 연산은 이전 단계에서 이미 연산이 되었기 때문..

문제 링크 : https://boj.kr/2156 이 문제에서는 연속된 인접 포도주가 최대 2잔까지 허용된다.이 문제에서의 핵심은 포도주를 마시기 위해선 인접한 최대 2개의 노드를 비교했을때 마신 포도주의 위치가 2 이하여야 하는 것이다.포도주를 마신 위치를 1로 하고 안 마신 위치를 0으로 표현하였다. 현재 위치를 기준으로 그 이전 단계를 계산한다면 아래의 경우를 생각할 수 있다.1. 현재 포도주를 먹지 않았을 경우 - 그 앞에 어떤 경우가 와도 상관 없다. 마신경우, 최대 2개까지만 허용 (0+0, 1+0, 1+1+0)2. 현재 포도주를 먹었을 경우 - 바로 전 포도주를 먹지 않았을 수도 있다. (0+1) - 바로 전(-1) 포도주를 먹었다면 반드시 그 이전(-2) 포도주는 먹지 않았어야 한다. (0..

문제 링크 : https://boj.kr/1149 어떤 집을 R, G, B 중 하나로 색칠할 때 인접한 이웃 끼리는 서로 색이 겹치면 안된다. 한 집을 R로 선택하게 되면 그 다음에 올 수 있는 이웃의 값은 G, B 중에 하나만 올 수 있게 된다.그 중에 G를 선택했다면 그 다음 값은 R, B 중에 선택해야 한다.R, G, B의 3가지 값 중에서 하나를 선택하면 그 값을 제외한 2가지를 선택할 수 있다.2가지 선택값 중에서 하나를 선택하면 그 뒤에는 또 2가지를 선택할 수 있는 경우의 수가 주어진다.이 과정을 반복하면 3*2*2*2* .....가지의 경우의 수가 나오며 일반항으로 고쳐보면 3*2^(N-1)가지의 경우를 계산해야 함을 알 수 있다.이를 빅-오 표기법으로 바꿔보면 O(2^N)임을 알 수 있다..