Victoree's Blog

Concept & Idea 나무자르기 문제를 내가 직접 풀어냈다는 느낌이 약해서 리뷰를 쓰지 않았다. 이 문제는 이분탐색으로 가장 인접한 두 공유기의 최댓값을 찾는 문제였다. 처음에는 이분탐색으로 설치를 하는 방식을 짜야한다고 생각했고, 어떻게 적절한 위치에 설치를 할지 우선순위를 잡아야하나 고민하였다. 하지만 그 어떤 우선순위에도 확실한 과정이 없어서, 질문검색을 통해 아이디어를 찾았다. 중요한 점은 내가 직접 구간을 설정해서 이 구간이 가능한지 여부를 판단하고, 이분탐색으로 이 구간을 정해나가는 것이다. mid라는 구간만큼 공유기를 설치했을 때, 설치가 가능하면 mid값을 더 키우고 불가능하면 더 줄여서 최적의 값을 이분탐색으로 찾아나가는 것이다. 여기서 가능한지의 여부는 그냥 count를 세면 됬었..

Concept & Idea 최대 배열의 크기가 1002, 1002이기 때문에 백트랙킹으로는 문제를 해결할 수 없다. tmp[2][1002] 배열은 좌측에서 오는 값을 기록, 우측에서 오는 값을 기록하는 배열이다. 이런 방식으로도 메모제이션을 진행할 수 있다는,, 잘 기억해두자!! Code #include #include using namespace std; int map[1002][1002]; int dp[1002][1002]; int tmp[2][1002]; int n,m; int main(){ cin>>n>>m; for(int i=1; i

Concept & Idea 가장 중요한 Concept은 DP[i][j]가 I부터 J까지의 최소 행렬 곱셉 횟수를 메모해놓는 배열이라는 점이다. 간단히 배열값을 바꿔가면서 순차적으로 검색하는 풀이는, 뒤쪽 배열들을 우선적으로 묶었을 때를 고려하지 못한다. 첫번 째 컨셉을 고려해서 문제를 풀기 시작해보자. 최종적으로 구하게되는 값은 DP[1][N]이다. 이 값을 출력하기 이전에, 계산될 과정은 DP[1][N] = DP[1][k] + DP[k+1][n] + map[1][0]map[k][1]map[n][1]; 일것이다. 해당 사진처럼 인덱스를 하나하나 써가며, 풀이를 하면 필요한 작업만 연산할 수 있고, 생각의 정리를 더 잘 할 수 있게 된다. 이런 식으로 연습을 하도록 하자! Code #include usin..

Concept & Idea 1 3 6 10의 수열을 만들고, 1 4 10 20의 수열을 만드는 것은 쉬운 작업이었다. 처음에는 30만 * 30만은 거뜬할거라 생각했는데, 생각해보니까 시간초과가 날 수 밖에 없었다. 사면체 배열의 수 * 30만 만큼만 비교하면 문제를 더 빠르게 해결할 수 있다. Code #include #include using namespace std; int n; long long layer[200]; vector vec; long long dp[300001]; int main(){ cin>>n; for(int i=1; i

Concept & Idea 앞서 공부했던 LIS 알고리즘을 이용하여 문제를 해결할 수 있었다. map은 입력받는 배열이고, p1은 수열을 출력하기 위한 순서를 기록해놓는 배열이다. 또한 LIS 알고리즘을 이용하려면 LIS를 체크하기 위한? 배열이 있어야한다. 내 코드에선 그 배열이 T배열이다. int lowIndex = lower_bound(t+1, t+pIndex, map[i])-t; 이 코드에서 틀렸습니다를 고칠 수 있었다. 나는 배열의 시작을 0부터 하지 않고 1부터 했으며, 이 문제의 입력으로 음수가 들어올 수 있다. 그래서 0과 음수를 비교했을 때, lower_bound에서 오류가 나왔기 때문에 오답을 냈다. 배열의 시작주소를 +1하니 문제를 해결할 수 있었다. 이 문제에서 또 핵심적인 하나의 ..

Concept & Idea LIS 알고리즘에 대해 공부하였다. 벡터는 lower_bound를 찾기 위한 벡터 배열이다.1. 해당하는 벡터 배열의 가장 마지막 요소보다 크기가 더 크면, 배열에 그냥 푸쉬해준다.2. 해당하는 벡터 배열의 가장 마지막 요소보다 크기가 더 작으면, 벡터 배열에 적절한 요소를 찾아 넣어준다. 이때 적절한 위치를 찾는데, 어차피 sort되어있는 배열이기 때문에 lower_bound를 이용하여 index를 찾고 값을 갱신해준다. lower_bound를 사용할 때는, 해당 배열의 첫 주소, 끝 주소, 찾고싶은 값을 매개변수로 넣고 배열의 시작 주소를 빼주어야 index값을 구할 수 있다. Code #include #include using namespace std; int n; lon..

Concept & Idea 다이나믹 프로그래밍적으로 사고하는 것은 맞았다. 내가 i,j에 위치해있을 때, [i-1][j-1], [i][j-1],[i-1][j]를 검사하는 것이 중요했다. 처음에는 max값으로 잡았는데, min값으로 잡아야 했었다. min으로 잡고나니 또 다른 문제가 발생했었는데, dp배열을 내가 계속 갱신해주고 있었던 것이 문제였다. dp[i][j]=t; dp[i-1][j-1]=t; dp[i][j-1]=t; dp[i-1][j]=t; 이 작업을 생략하고, 그냥 dp[i][j]=t 를 해주니 맞았다. Code #include #include using namespace std; string map[1001]; int dp[1001][1001]; int n,m; int res=0; int ma..

Concept & Idea 문제 상황을 좀 더 간결히 해서, int x에 값을 넣음으로 조건문이 되게 간단해 질 수 있었다. 자리가 1자리일 때의 경우와, 2자리가 가능할 때의 경우를 나눠서 생각했으면 빠르게 풀었을 것 같다. 또한 더할 때 dp[i-1]%1000000 라고 풀었었는데, 이렇게 풀면 안된다. 더하고 나서 따로 mod를 취해주어야 한다…😢 Code #include #include using namespace std; string n; int dp[5001]; int main() { cin>>n; int s=n.size(); dp[0]=1; n=" "+n; for(int i=1; i=1 && x=10 && x

Concept & Idea 어찌됫든 수열이다. 어떻게든 풀어보려고 규칙을 찾으려 했더니 간단한 문제였다. 원래는 dp배열을 2차원으로 만들어서, 변을 공유했는지 안했는지 체크하는 3개의 col을 만드려했는데, 규칙이 보이지 않아서 바로 문제를 다시 읽어보았다. 그랬더니 새로 생성되는 수가 그냥, i-2와 i-3의 합으로 해결된다는 것을 알게 되었다. 왜 범위가 int를 넘어가는지 이해가 잘 안간다. 100밖에 안되는데.. 질문검색에도 어느 순간부터 int를 넘어간다는 대답밖에 없었다. 앞으로 dp문제를 풀고 틀리면 그냥 배열 범위를 바꾸어 봐야겠다… Code #include using namespace std; int t; long long p[101]; int main() { cin>>t; p[1]=1..

Concept & Idea 처음 주어진 32의 타일의 경우의 수가 3개이다. 하나 하나 쪼개서 생각해보면, 맨 처음 타일이 왔을 때 뒤에 3개를 다시 붙이면 다른 경우의 수를 만들 수 있다. 그래서 바로 생각할 수 있는 예시가, 3dp[i-2]이다. 그런데 이 3개만으로 끝나지 않고, 새로운 경우의 수가 2개씩 더 생겨난다. 그래서 2dp[i-4]+ 2dp[i-6]등등을 더해가는 것으로 문제를 해결 할 수 있었다. dp[0]을 1로 초기화해 둠으로 해결할 수 있었다. Code #include using namespace std; int n; int dp[31]; int main() { cin>>n; dp[0]=1; dp[2]=3; for(int i=4; i