Stargazer

문제: 접근: 그냥 하나씩 접근해서 비교하여 푸는 방식으로 하면, 시간내로 풀지 못한다. 따라서 점화식을 이용해서 풀면 된다. 즉, DP로 풀면 시간내로 풀린다. 전략: 시간을 최소로 사용해야하기 때문에 데이터를 메모라이징하여서 저장한다. 점화식은 구간 [i,j] 가 있을때, i==j(구간길이 1)이면 true, 구간길이가 2일때, 입력데이터 input[i] == input[j] 가 같으면 true 아니면 false로 저장하고, 나머지 구간은 dp[i,j] = dp[i+1, j-1] && input[i] == input[j] 이면 된다. (이전 데이터를 이용해서, 양옆 한번만 비교하면 된다.) 코드: #include #include using namespace std; int n,m; vector su;..

접근: DP(Dynamic Programming)을 이용해서 푸는 문제. 발상은 행렬 곱셈이 이루어진 후에 두 행렬이 하나의 행렬로 이루어지기 때문에 작은 문제를 뭉쳐서 큰 문제를 해결 할 수 있음을 암시한다. 전략: 전체 행렬의 곱을 큰 문제로 보았을 때, 두 행렬의 곱으로 나눌 수 있고(구간 단위로), 이는 작은 문제로 나누어서 해결한다는 뜻이다. 그 행렬을 구할 수 있는 모든 경우의 수 중에 가장 연산이 가장 작으려면, 구간을 어떻게 나누었을 때 가장 곱 연산이 작은 지를 알면된다. 따라서 구간을 잘게 쪼개어 DP적으로 해결한다. 맨 아래(기본 행렬 곱)에 도달 했을 때, 두 행렬의 곱 연산 수를 구하여서 그 값을 저장한다. 이를 쌓아서 올리면 전체 곱셈 순서를 구할 수 있게 된다. -> 행렬을 나..

솔직히 DP는 매번 접근법을 잘 모르겠다... 대충 느낌은 DP 일거라 생각이 들지만 어떻게 해야할 지는 상세히는 모르겠다. (열심히 공부하자..ㅠㅠ) 접근: 이전 결과를 이용하여 현재 결과를 결정하는 방식으로 풀 수 있기 때문에 DP로 풀면된다. 전략: 이전 정보를 저장하는 dp[101][10000] 배열을 만들고, 매 앱을 하나씩 확인하면서, 이전 상태를 참고하여 앱의 cost를 선택하거나 선택하지 않았을때의 최대 확보 할 수 있는 메모리를 비교한다. 끝에는 모든 앱을 비교한 상태들 중 cost가 가장 작은 것을 선택한다. 코드: #include #include using namespace std; int n,m; struct App{ int mem; int cost; }; vector app; in..

DP는 정말 매번 할 때마다 새로운 느낌이라고 해야할까 접근 방식을 찾는게 가장 중요한 알고리즘이다. 본인도 실버인 문제임에도 불구하고 접근방식이 한번 꼬여서 2시간을 계속 시도 했는데, 예시는 잘되는 상황이다 보니 좀 더 할 것 같다는 생각에 계속 붙잡고 돌고 돌았던 문제였다. 접근: 본인은 접근 자체를 스티커를 선택할 수 있는 경우를 셌었다.(선택x, 첫째줄, 둘째줄) 그러나 이런 접근 보다 더 간단한 접근이 있었다. 우선 조건은 상하좌우를 스티커를 뗄 수가 없다는 점에서 감안하면, 이전 결과가 현재 결과에 영향을 준다는 점에서 DP를 사용하면 좋겠다는 생각을 했다. 일단 몇단계를 손수 해보면, 상하좌우가 막히면, 다음 단계는 대각선으로 스티커를 선택 할 수 있게되는데, 이 스티커를 선택해도 되는가는..

접근: 일반적으로 계산하면 시간 초과가 뜨는 문제이다. 반복적으로 더해주는 작업을 하는 것이기 때문에 DP로 접근하여서 푸는 것이 적절해 보인다. 전략: 구간 합을 입력 받을 때 마다 (0,0) 부터 (x2,y2)를 구해주어 2차원 배열로 저장하고, 구간 합이 주어지면 구해준 구간 합의 조합{(0,0) ~ (x2,y2)}으로 해결해주면 된다. (x1 - 1 , y1 - 1) (x1 - 1, y2) (x2 , y1 - 1) (x2 , y2) 구하고자 하는 값이 (x1,y1)부터 (x2,y2) 까지의 구간 합 이므로, (x2, y2) - (x1-1 ,y2) - (x2 ,y1-1) + (x1 - 1 , y1 - 1) 이런식으로 구해준 값으로 겹치는 영역을 빼고 더해주면 원하는 구간의 값이 나온다. 구현: #i..

접근 이름부터 플로이드 이지만, 단순히 문제만 바라보면, 도시의 가장 빠른 길을 찾는데, 모든 도시를 대상으로 찾아야 한다. 이렇게 모든 대상에 대해서 최단 경로를 구하려면, 플로이드 워셜(Floyd-Warshall) 알고리즘을 이용하면 된다. 그렇지만 나는 이 알고리즘을 제대로 이해하지 못해서 다른 방식으로 해결했다. 전략 플로이드 워셜 알고리즘의 전략은 각 정점을 조사해서 해당 정점을 사이로 지나는 두 정점을 찾아서 만약 더 짧은 거리이면 짧은 거리로 갱신한다(두 정점의 직접 경로가 없는 건 ∞ 로 가정) 본인은 잘못 이해 해서 시간 복잡도가 조금 더 증가했다. 각 도시 간 거리를 매트릭스의 형태로 저장해서 각 행에 대해서 조사를 하는데, 만약 경로가 있는 도시가 있다면, 그 도시로부터 다른 도시를 ..