Jonyo Programming

[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..

[BOJ 14003(G1)리뷰] 가장 긴 증가하는 부분수열 문제 시리즈를 풀었다. 이 문제들을 푸는데 필요한 알고리즘인 LIS알고리즘을 정리해놓았다. 이 문제는 시리즈 중 가장 어려운 문제이다. 입력데이터가 1,000,000이므로 O(N²)로는 풀수가 없고 lower bound를 이용하여 O(NlogN)으로 풀어야 한다. 게다가 이 문제는 부분 수열까지 출력해야 하는 조건이 있다. 부분 수열을 출력하기 위하여 trace라는 스택에 각 값의 lower bound를 기록했다. 만약 {10,20,10,30,20,50} 이라면 lower bound는 {1,2,1,3,2,4} (인덱스 1부터 시작) 가 된다. 그리고 가장 긴 증가하는 부분수열의 길이는 4가 된다. 이제 뒤에서부터 > val; arr.push_ba..

LIS(Longest Increasing Subsequence) 알고리즘은 '가장 긴 증가하는 부분 수열' 알고리즘으로도 불린다. 주로 그리디 알고리즘이나 다이나믹 프로그래밍의 예시로 등장한다. LIS는 수열 내 증가하는 부분 수열 중 가장 긴 수열을 말한다. 예를들어 아래와 같은 수열이 존재할때 3 1 5 2 4 2 이때 가장 긴 증가하는 부분 수열은 {1,2,4}이며 길이는 3이다. 3 1 5 2 4 2 아래의 예시에서는 가장 긴 증가하는 부분 수열은 {10,20,30,50} 이며 길이는 4가 된다. 10 20 10 30 20 50 이제 이 알고리즘을 이용하는 문제를 해결해 보자. BOJ : 11053 가장 긴 증가하는 부분 수열 이 문제를 어떻게 풀어야할까? 이 문제는 동적계획법을 이용하여 O(N²..

[BOJ 1138(S2) 리뷰] 아 그리디 너무 어렵다 .. 그리디인걸 알고 풀어도 잘 안풀리는데 코테에서 그리디임을 발견하고 풀 수 있을지 모르겠다. 키가 1부터N까지인 사람들이 있다. 이 사람들은 각각 왼쪽에 자기보다 키 큰 사람이 몇명있었는지 기억한다. 우리는 그 정보를 토대로 줄을 세워야 한다. 입력이 2 1 1 0 으로 주어지면 1보다 키 큰사람이 왼쪽에 2명, 2보다 키 큰사람이 왼쪽에 1명, 3보다 키 큰사람이 왼쪽에 1명, 4보다 키 큰사람이 왼쪽에 0명 이고 이때 올바르게 줄을세우면 4 2 1 3이 된다. 이제 이걸 어떻게 푸느냐가 문제다. 물론 완전탐색으로도 풀 수있으나 문제의 본질은 아니라 생각한다. 이 문제는 키가 가장 작은 1부터 시작한다. 1보다 키가 작은 사람은 없으므로 1의 ..