본문 바로가기
반응형

알고리즘/Algospot

LIS LIS 최대 증가 부분수열(Longest Inceasing Sub-sequence) 문제. 증가하는 부분 수열은 완전 탐색으로 풀 수 있지만, 수열의 길이가 증가할수록 엄청나게 연산 시간이 증가하게 된다. 최대 증가 수열 같은 경우에는 배열에서 계속 오른쪽으로 이동하면서 부분 문제가 줄어든다. 그리고 왼쪽의 배열 값들은 고려할 필요가 없기 때문에, 최적 부분 구조를 이루므로 동적 계획법을 이용한 풀이가 가능하다. cache[X] = X 에서 시작하는 부분 수열의 최대 길이 라는 점화식을 이용하면 결국 각 인덱스에서 구할 수 있는 부분 수열의 최대 길이가 구해지게 된다. for문을 이용해서 X 다음 인덱스인 X+1 부터 돌면서 , Cache[X] 보다 값이 큰 인덱스를 찾아가면서 재귀함수를 수행한다. 그러.. 더보기
TRIANGLEPATH TRIANGLEPATH 기본적인 DP 문제. 시간 복잡도는 한줄 밑으로 내려갈 때마다 2배씩 증가하므로 2^n-1 이 된다. 따라서 n의 최대값이 100이 시간 내에 구할 수 없게 되므로 DP 를 이용해야 한다. cache[x][y] 는 x,y 에서 얻을 수 있는 최대 점수 cache[x][y] = map[x][y] + max(cache[x+1][y] , cache[x+1][y+1]) 현재 자신의 값 + MAX((x+1,y) 에서 얻을 수 있는 최대값 (x+1,y+1)에서 얻을 수 있는 최대값) 가 되므로 이를 재귀 함수를 이용해서 구현할 수 있다. 굳이 cache 값을 -1로 초기화 하지 않은 이유는, 조건에서 map에 들어가는 값은 1이상 이기 때문에 123456789101112131415161718.. 더보기
WILD CARD WILD CARD 헷갈리는 부분이 은근히 많았다... 뭔가 제대로 정리를 하지 않고 풀었다. 종만북에서 DP문제로 정해져있지만, 완전탐색을 이용해도 시간내에 해결할 수 있는 문제이다. 이 문제에서 핵심은 * 를 어떤식으로 해결하느냐이다. 나는 for문을 이용해서 *을 0칸부터 비교할 string의 끝칸까지 돌리는 방법으로 문제를 해결했다. //하나씩 비교 (맨마지막까지) if (wc[wc_idx] == '*') { for (int i = str_idx; i tc; for (int t = 1; t > wc; cin >> n; for (int i = 0; i > str; go(0, 0); if (chk) ans.push_back(str); } sort(ans.begin(), ans.end()); for (i.. 더보기
JUMPGAME(C언어) JUMPGAME 그냥 풀면 시간초과가 발생하기 때문에, DP로 접근해서 문제를 풀어야했다. 계속 문제에서 틀렸던 부분이 있었는데 원래 아래 처럼 작성했을 때에는 계속 오답이 발생했다. *ret = jump(cache,map, x + move, y, n) + jump(cache,map, x, y + move, n); 하지만 아래처럼 바꿀경우 정답이 통과되었는데... 그 이유를 모르겠다. *ret = jump(cache,map, x + move, y, n) || jump(cache,map, x, y + move, n); 원인해결 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455.. 더보기
DICTIONARY DICTIONARY 다시 풀어본 문제, 좀 고민했지만 위상정렬 문제. 옛날 풀이가 위상정렬을 공부하고 풀었기 때문에 더 깔끔하게 푼 것 같다. 아무튼 위상 정렬에는 DFS 로 푸는 방법과 BFS로 푸는 방법이 있는데, 나는 이제 BFS로 익숙해져있다. C언어로도 한번 바꿔봐야 겠다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511.. 더보기
CLOCKSYNC(C언어) CLOCKSYNC 처음에는 CLOCK 값을 증가시키면서 , CLOCK을 12시에 맞추고 다음 CLOCK 으로 이동하고 이런 방식을 생각했었는데 이런식으로는 계속 문제가 꼬여가서 풀 수 없다고 생각해서 다시 생각해보았다. BUTTON 중심으로 접근하다 보니, 0~9번 까지의 버튼을 몇번 누르는지에 대한 재귀 접근으로 풀 수 있었다. 그리고 가장 중요한 방법은 최소값을 구하는 것이고, 한 버튼을 0번 누르나 4번 누르나 똑같다는 점이었다. 따라서 최소값을 구하기 위해서는 버튼은 최대 3번까지만 누르는 방식으로 재귀함수 코드를 구현할 수 있었다. 또 모든 버튼을 3번씩 누르면 최대 3*16=48번의 버튼을 누를 수 있기 때문에, 기존의 ans 값을 50으로 설정하였다. search_button 함수를 통해서 .. 더보기
BOARDCOVER(C언어) BOARDCOVER C++ 이 아닌 C로 코드를 짜려고 하니까 함수의 인자도 많아지고, 변수도 전부 앞에 선언하고 해서 복잡해졌다. 완전 탐색임에도 불구하고, 아이디어를 생각하고 구현하는데 좀 시간이 걸렸다. 문제를 푼 키워드는, 맨왼쪽상단의 값에서 시작한다고 생각한다는 점이었다. 맨 왼쪽 상단이 비어있는 곳에서 4가지의 블럭 경우를 생각하며 채워넣어 갔다. ㄴ 모양, ㄱ 모양, 그리고 이 두 모양의 좌우로 뒤집은 모양을 dx, dy 를 이용해서 담았다. 그리고 한칸씩 검사해나가면서 그 칸이 차있는지 그렇지 않은질르 탐색하면서, 비어있으면 채우고, 아니면 그냥 지나가도록 재귀함수를 만들었다. 가로로 쭉 탐색하였을 경우 다음 줄로 넘어가는 부분을 재귀함수의 if (y==w) 를 통해서 구현했고, 맨 마지막.. 더보기
PICNIC (C언어) PICNIC 문제를 C언어로 풀어보았다. 예전에 PS 처음할때는 정말 어려웠던 문제였다. C 연습하려고 포인터를 이용해서 문제를 풀었다. 완전탐색을 이용해서 문제해결, 단 중복되는 경우를 없애야한다. 자기보다 번호가 큰 사람만을 보는 방법으로, 한 방향을 정해서 중복을 없앨 수 있었다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071#include void init(int(*isfriend)[11], int* havefriend);void matching(int k, int n, int(*isfriend)[11], .. 더보기
반응형

티스토리툴바