분류 전체보기62 백준 2718번 타일 문제 state를 cache로 저장하는 DP 4*N타일을 채우는 문제로처음 문제를 접근할때 1번째 타일부터 채우면서 N번째 타일까지 dfs를 하면서 같은 타일 번째의 같은 상태에서 또 계산할 필요가 없어 이 부분을 cache에 저장하는 방법을 상용하려 했는데, 문제의 경우 test case로 여러 케이스를 연달아 풀어야합니다. 위 방법 접근법은 cache의 재활용이 안되므로, dfs를 몇 번째 타일을 접근중이 아닌, 남은 타일의 개수로 셌습니다. 타일 딱 N번째 한줄만 생각했을때 놓을 수 있는 방법의 수가 많지 않고 규칙성도 바로 떠오르지 않으므로 그냥 직접 손으로 몇개 세어줍니다. 여러 타일의 상태에 따라서 놓을수 있는 경우의 수는 총 6개 정도 나오고 각 경우마다 다음 타일에 주는 영향을 상태를 다음 dfs함수에 넘겨줍니다. 상태는 5가지 정도.. 2020. 4. 14. 백준 2352번 nlog(n)으로 풀기, LIS 알고리즘의 이해 (longest increasing Subsequence ) 백준 2352번은 일반적인 DP코드로는 N^2 시간복잡도가 걸립니다. 왜 N^2인지는 밑의 코드 주석에 작성 알고리즘에서 lower_bound라는 함수를 사용했는데, 대단한 함수는아니고 직접 작성하여도 되는 함수이다. lower_bound(첫주소, 마지막주소, 찾는 값) return iter or pointer 주소값 매개변수 인자는, STL의 iterator를 넣어도 되고, 배열의 주소값을 넣어도 됩니다. 이 함수는 이미 오름 차순으로 sort된 배열에서 binary search를 하여 찾고자 하는 값이 있는 인덱스(iter or 주소)를 알려주는 함수입니다. 만약 값이 존재하지 않는다면, 찾는값 보다 큰 수 중에서 작은 값을 찾습니다. (2, 5, 8) 에서 4를 찾는다면 idx 1 (5) 반환 모든.. 2020. 4. 10. 백준 2631 줄세우기 LIS 개념 다이나믹 프로그래밍 줄세우기 문제는 3 7 5 2 6 1 4 라는 수열이 있으면 숫자를 최소로 움직여 정렬 상태로 바꾸는 문제이다. (1 2 3 4 5 6 7) dp문제로 분류되어 있지만 바로 DP를 사용하기에는 감이 잡히지 않았다. 이런 문제를 LIS 문제라고 하는데, 위 문제를 잘 생각해보면 모든 숫자는 한번 움직이기만하면 원하는 위치에 딱 놓을 수 있다. N개 문제가 있다면 N번 안에 무조건 해결 가능하다. 어쩌면 어떤 숫자들은 가만히 있어도 된다. 즉, 최대한 많은 숫자들이 움직이지 않아도 될 수록 좋다는 것 !!! 그리고 건들이지 않아도 되는 숫자들은 , 이미 각 숫자들이 오름차 순으로 있다는 것 그렇다면 우리는 이미 오름차순으로 정렬되어있는 가장 긴 순열 길이를 찾으면 된다. 위 문제에서는 3 7 5 2 6 1 .. 2020. 4. 7. 다이나믹 프로그래밍으로 최적화 하는 DFS, 백준 2253번 점프 백준 2253번 점프 문제는 N이 최대 10000까지 가능한 문제였습니다. 그냥 DFS를 활용해 모든 경우의 수로 점프를 하기에는, 돌담마다 JUMP += -1,0,1 의 세가지 경우가 주어지므로 모든 경우의 수를 찾기에는 지수승의 형태 뜁니다. 일반적인 BFS로 풀기에는 현재 도착한 돌담이, 최단의 점프로 도착했다는 보장은 되지만, 앞으로도 현재 돌담에서 가지고 있는 JUMP의 크기를 가지고 출발한것이 최단으로 목적지같이 도착한다는 보장이 없습니다. 그렇다면 BFS로 visit을 잡을 변수로는 JUMP크기와 돌담 위치를 함께 잡아 주어야합니다. 즉 JUMP크기를 1로 돌담3에 온 경우와 JUMP크기 3으로 돌담3에 온 경우는 구분해 주어야 합니다. 이번 문제는 약간의 변형으로 쉽게 BFS로 풀 수 있습.. 2020. 3. 28. 이전 1 ··· 7 8 9 10 11 12 13 ··· 16 다음