Jonyo Programming

[BOJ 2457(G4) 리뷰] 전형적인 그리디 문제라지만 나에겐 너무 어려웠다 ㅠ.. 날짜를 저장하는 방식과 꽃을 선택하는 방식에 대해 이해는 했지만 막상 코드로 짜려니 막막했다. 알고리즘은 다음과 같다. 현재 날짜를 기준으로 현재 일보다 이전에 핀 꽃들중 가장 오랫동안 피는 꽃을 선택해야 한다. 공주는 3월1일부터 꽃이 피어있어야 한다 했으므로 3월1일을 기준으로 3월1일 이전에 핀 꽃들 중 가장 오랫동안 피는 꽃을 선택하면 된다. 예를들어 3월1일부터 6월3일까지 핀다면 다음 꽃은 6월3일 이전에 피는 꽃 중 가장 오랫동안 피는 꽃을 선택해야 한다. 위 알고리즘으로 11월 30일까지 꽃이 피어있도록 하고, 11월 30일이 지나면 반복문을 종료하고 정답을 출력하면 된다. 말로 설명하면 쉽지만 경계조건..

[BOJ 2096(G4) 리뷰] 전형적인 DP문제처럼 보였으나 메모리 제한이 걸려있다. 가장 쉽게 풀기 위해서는 DP[3][100001]을 선언하며 각 위치에 대해 DP계산을 해주면 되지만 이렇게 하면 불필요한 메모리 공간때문에 메모리 초과를 맞게 된다. 따라서 우리는 계산 후 불필요한 데이터는 굳이 메모리에 저장하지 않도록 해야 한다. 그러기 위해서 입력받는 순간 MAX DP, MIN DP값을 계산하며 단계를 거듭할때마다 값을 복사하여 한정된 메모리를 통하여 DP계산이 가능하게 했다. 결국 실질적으로 사용하는 메모리는 MAXDP[2][3], MINDP[2][3]이 된다. /* 20.09.01 BOJ : 2096 내려가기 (https://www.acmicpc.net/problem/2096) 다이나믹 프로..

[BOJ 1937(G3) 리뷰] 이 문제는 내리막 길 문제와 굉장히 유사하다. 언뜻 보기에는 단순한 BFS,DFS문제로 보이지만 만약 모든 경우에 대해 탐색하려 한다면 당연히 시간초과가 날 것이다. 따라서 이 문제 역시 이미 팬더가 지나갔던 길에 대해서는 다시 탐색할 필요가 없게 해야 한다. 예를들어 아래와 같은 맵이 존재할때 14 9 12 10 1 11 5 4 7 15 2 13 6 13 16 8 (1,2)인 9가 존재하는 위치에서 팬더의 최대 생존일은 9->11->15 3일이다. 따라서 만약 다른 위치에서 (1,2)를 다시 방문하게 된다면 이미 그곳에서의 최대 생존일을 알고 있으므로 다시 한번 탐색을 진행하지 않아도 된다. 이를 DP배열을 통해 관리하면 된다. 위 로직을 이해 하고 코드를 본다면 바로 ..

[BOJ 2225(G5) 리뷰] 이 문제는 처음에 규칙이 잘 보이지 않았다. 일단 고려해야 할 점은 0을 더할 수 있다는것이다. 나는 집적 경우의 수를 나열하며 규칙을 찾았다. 각 행은 정수 K를 나타내고 각 열은 N까지의 경우의 수를 나타낸다. 예를들어 N=3,K=2라면 0,1,2,3중 숫자 2개를 사용하여 3을 나타내는 경우의 수 이다. 이때의 경우의 수는 0+3, 3+0 ,1+2 ,2+1 로 총 4개이다. 여기서 만약 K가 3이라면 어떻게 될까? 맨앞이 0이고 나머지 숫자 2개를 이용하여 3을 나타내는 경우의 수 + 맨앞이 1이고 나머지 숫자 2개를 이용하여 2를 나타내는 경우의 수 + 맨앞이 2이고 나머지 숫자 2개를 이용하여 1을 나타내는 경우의 수 + 맨앞이 3이고 나머지 숫자 2개를 이용하여..

[BOJ 1520(G4) 리뷰] 언뜻보면 그냥 BFS,DFS문제로 보이지만 DP를 이용하여 풀지 않으면 시간초과가 난다. 따라서 목적지 까지 갔던 경로를 기억해야 하고 지금 가고있는 경로가 이미 목적지에 도착했던 경로라면 굳이 목적지 까지 갈필요가 없다. 이를 DP배열을 통해 구현했다. 목적지에 도착했을때에만 1을 반환하도록 하면 결국 DP[1][1]에는 목적지 까지 도착한 경로의 갯수만이 저장될것이다. #include using namespace std; int N, M; int board[501][501]; int dp[501][501]; int dx[4] = { 1,0,-1,0 }; int dy[4] = { 0,1,0,-1 }; int dfs(int r, int c) { if (r == N && c..

[BOJ 11048(S1) 리뷰] 이번 DP문제는 Top-down 방식과 Bottom-up 방식 두가지로 풀어보려고 한다. 문제는 N*M 행렬이 주어지고 각각의 좌표마다 value가 존재할때 (1,1)부터 (N,M)까지 갈때의 최대값을 구해야 한다. 다음 좌표로 이동할땐 (R+1,C) , (R,C+1) , (R+1,C+1)로 이동이 가능하다. 즉 아래,오른쪽,오른쪽 대각선 아래로만 이동을 해야 한다. 먼저 Top-down의 코드이다. #include using namespace std; int arr[1001][1001]; int dp[1001][1001]; int N, M; int solve(int r, int c) { if (r + 1 > N && c + 1 > M) return arr[r][c]; ..

[BOJ 9465(S2) 리뷰] DP문제다. 우리는 점수가 적인 2*N개의 스티커를 떼었을때 최대값이 되는 크기를 출력해야 한다. 다만 스티커를 뗄때는 다음과 같은 조건이 붙는다. 떼고자 하는 스티커와 변을 공유하는 스티커는 찢어지기에 다음번에 그 스티커는 뗄 수 없다. 50 30 20 20 10 30 이라는 스티커가 있을때 만약 50이라는 스티커를 떼게되면 오른쪽에 있는 30과 아래에 있는 20은 뗄 수 없다. 이러한 조건을 만족하며 스티커를 뗐을때의 최대값을 구하면 된다. 천천히 생각해 보자. N이 1이라면 50 20 당연히 두개의 스티커 중 더 큰 값을 떼어내야 한다. N이 2라면 50 10 30 10 이 경우에는 50+10=60, 30+10=40 이므로 50과 10의 스티커를 떼어내야 한다. 이제..

[BOJ 1932(S1) 리뷰] DP문제다. 역시 DP문제는 너무 어렵다. 삼각형 위에서 아래로 내려가며 가장 큰 최대값을 찾는 문제이다. 내려갈땐 대각선 왼쪽, 대각선 오른쪽에 위치한 값으로만 내려갈 수 있다. 크기가 작다면 완전탐색으로도 가능했을테지만, 이 문제는 DP를 이용하지않으면 시간초과를 맞게 된다. 각 위치마다 할 수 있는 선택은 왼쪽으로 가냐 오른쪽으로 가냐이다. 당연히 우리는 두개의 방향 중 끝까지 내려갔을때 최대값이 되는 방향으로 가야 한다. 그러나 우리는 미래를 내다볼 수 없으므로 현재의 위치에서 바로 왼쪽으로 갈지 오른쪽으로 갈지 결정할 수가 없다. 따라서 아래쪽 삼각형부터 값을 확인하며 위로 올라가는 방법을 택했다. DP배열을 통해 각 삼각형의 위치마다, 아래에서 위로 올라올때마다..

[BOJ 11054(G3) 리뷰] 이 문제는 LIS알고리즘을 통해 풀 수 있다. 다만 기존에는 가장 긴 증가하는 부분 수열의 길이를 출력했다면 이 문제는 "수열 S가 어떤 수 Sk를 기준으로 S1 Sk+1 > ... SN-1 > SN "라는 조건을 만족해야 한다. {10,20,30,25,20}과 같이 30이라는 수를 기준으로 왼쪽에는 오름차순 정렬이 되있으며 오른쪽은 내림차순이다. 우리는 주어진 수열에서 위 조건을 만족하는 가장 긴 바이토닉 수열의 길이를 찾아야 한다. 만약 {1 5 2 1 4 3 4 5 2 1}라는 데이터가 주어졌다면 이 데이터에서 가장 긴 증가하는 바이토닉 수열은 {1 5 2 1 4 3 4 5 2 1}이 된다. 5를 기준으로 왼쪽은 오름차순, ..

[BOJ 11055(S2) 리뷰] 먼저 이 문제를 풀기전에 LIS알고리즘 의 개념에 대해 알고 있어야 한다. 동적계획법을 통해 문제를 해결 할 수 있으며 기존에 크기에 대하여 계산하던 것을 합에 대하여 계산하도록만 바꾸어주면 된다. #include using namespace std; int arr[1001]; int dp[1001]; int main(void) { int N; cin >> N; for (int i = 0; i > arr[i]; dp[i] = arr[i]; } int ans = 0; for (int i = 0; i arr[j]) { temp..