Victoree's Blog

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

Concept & Idea 처음에는 굳이 DP로 풀어야하나?라는 의문이 들어서 그냥 생각대로 풀었다. 수학문제 해결하듯이 풀어낸 코드는 다음과 같다. #include #include using namespace std; int n; int main() { cin>>n; int cnt=0; while(n!=0) { int t=int(sqrt(n)); n-=t*t; cnt+=1; } cout

Concept & Idea 연속합이라고해서 투포인터 개념을 이용해 문제를 해결하려 했는데, 그냥 간단한 이중 포문으로 해결하였다. 처음엔 아무 조건없이 이중포문으로만 해결하니, 시간초과를 마주하였는데 간단한 res>n; for(int i=1; i>map[i]; dp[i]=map[i]; } for(int i=1; i

Concept & Idea 조건은 생각보다 간단하다. 우선 증가하는지 보면되고, dp배열에 여태까지 기록한 가장 큰 증가 부분 수열의 값을 저장해놓으면 된다. 가장 큰 증가 부분 수열을 찾으면, 그 값에 자기 자신을 더한 값을 DP[i]에 저장하면 된다. Code #include using namespace std; int n; int map[1001]; int dp[1001]; int res=0; int main() { cin>>n; for(int i=1; i>map[i]; } for(int i=1; i

Concept & Idea 문제 접근을 어떻게 할까 하다가 앞에 요소를 체크하려 했는데, 결국 과거의 값을 되돌아 생각해보는 것으로 생각해보니 해결되었다. row가 0일 경우에, row가 1이고 && col이 자기 자신보다 -1,-2인 값중 큰 값을 누적하여 더한다.row가 1일 경우에, row가 0이고 && col이 자기 자신보다 -1,-2인 값중 큰 값을 누적하여 더한다. DP배열에는 누적으로 최대값을 쌓아가고, 최종적으로 마지막 col의 최댓값을 출력하면 해결되는 문제였다. Code #include using namespace std; int t; int map[2][100001]; int cnt=0; int dp[2][100001]; int main() { cin>>t; for(int i=0; i..