2020.02.18 algospot / LIS 풀이 수열이 맨 왼쪽부터 하나씩 들어온다고 했을 때,다음 숫자가 들어왔을 때 그보다 작은 숫자들 중 최대인 녀석을 찾고 거기에 +1 한 값과 DP에 써져있는 값을 비교해서 큰 녀석을 DP에 update 한다. 이와 같은 풀이를 진행하면 C = 50, N = 500, 모든 수가 1~ 100000을 다 지나간다고 했을 때 대략 50 * 500 * 100000 정도의 시간복잡도가 될 거고 이는 25억이 되어 시간초과가 발생할 거라 생각했다. update하면서 가장 큰 최댓값을 기억해두고 마지막에 이를 출력한다. 해당 숫자를 맨 오른쪽 끝으로 하는 수열의 길이를 DP에 적어둔다. 1번의 알고리즘에서 들어온 숫자를 DP에 update하는 알고리즘은 동일하지만 들어온 ..

2020.02.17 TRIANGLEPATH 풀이 행을 한칸씩 이동할 때, 아래와 오른쪽 대각선 아래 두가지 경우의 수가 있다. 재귀함수를 이용해서 마지막 행에 도착하는 순간 그때의 최대 거리를 리턴하는 getResult 함수를 만들었다. 처음에 메모이제이션을 마지막에 도달했을 때 최댓 거리를 DP 행렬에 기록하려고 시도했었다. 우연히 정답이 나왔으나 이는 같은 결과가 나올 수 없었다. 경로가 달라질 때마다 마지막에 도달하는 거리는 달라진다. 같은 지점에 대해 같은 결과가 나오는 것에 대해 메모이제이션을 활용해야 하는데 잘못된 알고리즘을 구상한 것이다. 잘못된 메모이제이션 활용 //! 2020.02.17 // TODO AS_TRIANGLEPATH.cpp // Dynamic Programming #inclu..

2020.02.17 WILDCARD 풀이 기본적으로 input1, input2를 입력받으면서 바로 비교하도록 함수를 구현하였고 비교해서 조건을 만족하면 결과 벡터에 푸시하였다. 마지막으로 compare와 함께 결과를 sort 해서 출력하였다. *, ?, 문자 경우를 나누어 재귀함수를 이용해 idx1,idx2를 증가, 그대로 두며 완전탐색하도록 만들었다. 동적계획법 문제인데 먼저 완전탐색으로 확인하여 시간초과가 나면 DP를 어떻게 적용할지 고려해보려 했는데 시간초과없이 통과해버렸다.. 코드 //! 2020.02.17 // TODO AS_WILDCARD // Brute Force (Dynamic Programming) #include #include #include #include using namespac..