Jonyo Programming

[BOJ 2098(G1)리뷰] 컴퓨터 분야에서 TSP 라고 불리는 굉장히 유명한 문제라고 한다. 한 도시에서 출발하여 N개의 도시를 모두 방문하였을 때 최소비용을 구해야 한다. 처음에 그냥 간단한 최소 스패닝 트리를 구성하는 문제거나, 최단거리를 구하는 문제인 줄 알았는데 모든 도시를 방문해야 하며(방문이 가능할 경우) 다시 도착점으로 돌아와야 한다는 등의 조건때문에 결국 완전탐색을 해야 한다. 하지만 이 문제의 N의 최대값은 16이므로 완전탐색으로 구현하게 되면 16!이라는 어마어마한 시간복잡도를 가지게 된다. 따라서 다이나믹 프로그래밍을 이용하여 시간효율을 증가시켜야 한다. 그리고 이 때, DP를 효율적으로 사용하기 위하여 비트마스킹 이라는 개념을 사용한다. 나도 이 문제에서 처음사용해봤는데 굉장히 ..

[BOJ 11062(G3)리뷰] 언뜻보면 시뮬레이션 문제처럼 보이기도 하고, 그리디 문제처럼 보이기도 하지만 DP문제이다. 항상 가장 오른쪽,왼쪽에 있는 카드만 가능할 수 있다는 점 때문이다. 만약 [1,2,5,2]라는 카드가 있을 때, 근우가 더 큰 2라는 카드를 가져가게 되면 최종 점수는 3점밖에 얻지 못한다. 그 이유는 명우 역시 최선의 전략으로 플레이하기 때문이다. 그렇기에 첫 턴에서 근우가 1이라는 카드를 가져가야 다음턴에 5라는 카드를 가져갈 수 있고 6이라는 최대 점수를 얻을 수 있다. 이렇게 문제를 이해하고 나서도 코드를 짜는게 굉장히 어려웠다. 이걸 어떻게 짜야할까 고민을 많이 했다. 그래서 머리에 구상한 그대로, 근우가 게임을 플레이하는 함수와 명우가 게임을 플레이하는 함수 두개를 구현..

[BOJ 17069(G5)리뷰] 오랜만에 푼 DP문제다. 오랜만에 DP풀려니까 역시 힘들었다. 이 문제는 예전에 풀려고하다 도중에 포기했던 문제지만, 이번엔 한번에 풀어서 기분이 좋다. 코드를 보면 알겠지만 문제에 주어진 조건을 그대로 구현하여 재귀함수로 처리하면 된다. 나는 미리 맵의 벽을 그린다음에 이동할 수 있는지 없는지 확인하고 이동이 가능하면 다음 함수를 실행하도록 했다. 맵의 최대크기가 엄청 크기에 dp를 사용하지 않으면 시간초과가 난다. 가고자 하는 경로가 이미 목적지에 도착한적이 있던 경로라면 굳이 가지 않고서도 도착할 수 있음을 알수있다. 이를 이용하여 실행시간을 단축해야 한다. /* 21.01.05 BOJ : 17069 파이프 옮기기 2 (https://www.acmicpc.net/pr..

[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 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를 기준으로 왼쪽은 오름차순, ..