본문 바로가기
반응형

알고리즘/BOJ

1720번 1720번 - 타일 코드 http://m.blog.daum.net/rhaoslikesan/369?tp_nil_a=2 위의 블로그에서 풀이 과정을 참고하였다. 도통 설명된 풀이를 찾을 수가 없었는데 감사합니다. 일단 이 문제는 타일 채우기 문제랑 똑같은데 대칭을 없애야 했다. 그 과정을 참고했는데, 참.. 어떻게 저런 생각을 할 수 있을까 하는 생각이 들었다. 풀이 과정 ↓↓↓ 우선 원래 타일을 그냥 채우던 방식대로 재귀함수를 만들었다. 그렇다면 D[N]= D[N-1] + 2*D[N-2] D 배열 에는 대칭이 중복되서 들어간 모든 타일채우는 방법의 수가 들어있다. 근데 우리는 중복을 하나로 취급해야 한다. 즉 " 전체 타일 개수 = 중복1 + 중복 2 + 중복아닌 것들 " 로 구성이 되는 것을 알 수가 있.. 더보기
2228번(다시..) 2228번 - 구간 나누기 처음에 나는 맨 마지막 값을 선택한다, 안한다까지는 맞췄지만, 선택할 때, 맨 마지막 값을 그룹으로 처리하는 방법 까지는 생각 못했었다. 그룹으로 처리하면 점화식은 쉽게 나왔다. D[N][M] = max( D[N-1][M] , D[k-1][M-1] + v[k] +... + v[N-1] ) 즉 D[N][M] 은 N개에서 M그룹을 만들 때 최대값. 문제를 풀긴 했는데, 뭔가 기저 조건이 찜찜하게 느껴진다... 아직 완벽하게 내 문제로 소화하지 못한 것 같다 다시 풀어 봐야지 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263.. 더보기
1328번 1328번 - 고층 빌딩 점화식 D[N][L][R] = N개의 건물을 봤을 때 왼쪽에서 L개 오른쪽에서 R개인 경우의 수 사실 점화식을 세웠지만, 이 식을 다른 N,L,R 과 연관시키는게 사실 너무 어려웠다. 나도 결국 다른 사람들의 풀이에서 힌트를 얻고 문제를 풀 수 있었다. (다시 풀어봐야겠다) 이 문제는 결국 높이 1의 빌딩을 어느 곳에 놓을 것인가 하는 문제로 끝이난다. 어떻게 다른 사람들은 이걸 생각했는지 참 신기하다... 높이 1의 건물을 맨 왼쪽에 뒀을 때, 맨 오른쪽에 뒀을 때, 그리고 나머지 부분에 뒀을 때로 나뉘게 된다. 가장 작은 건물이기 때문에 맨 왼쪽에 두면 N 과 L 이 1씩 증가. 맨 오른쪽에 두면 N과 R이 1씩 증가. 나머지 부분에 두면 N은 증가하지만 L과 R은 변화가 없.. 더보기
2240번 2240번 - 자두나무 이 문제를 재귀로 풀었는데, 처음에는 뒤에서부터 줄여오는 방식으로 문제를 풀었다. 그러다보니 생기는 문제가, 처음에 시작점이 1이라는 것. 나는 이점을 어떻게 해야할 지 잘 모르겠다... (방법 해결 - 아래 코드로 추가) 그래서 아예 시작점에서부터 커지는 재귀, 마치 iterative DP 모양으로 문제를 풀었다. 그 다음 중요한 점은 정답을 구할 때, max(go(0, 0, 1),go(0,1,2)) 이런 형식으로 정답을 구해야 했다. 0초인 움직일 수 있기 때문이다. D[t][w][now] = t 초에 w번 움직이고, 현재 위치가 now 일 때, 먹은 자두의 최댓값 움직일 때와 움직이지 않을 때로 구해주고, 이럴 때 현재 자두를 먹을 수 있으면 1을 더해주는 방식으로 코드를 짰.. 더보기
2410번 2410번 - 2의 멱수의 합 동전2 문제랑 완전히 똑같은 문제. 하지만 이 문제는 2의 멱수 중 하나가 1이기 때문에, 안만들어질 수 있는 경우는 없다. 따라서 그냥 초기값을 0으로 두고 풀어도 되는 문제. 문제를 풀 때 pow를 쓰거나 그냥 P배열을 만들어서 값을 사용해도 된다. (100만은 2^20 보다 작기 때문에 20이라는 숫자를 사용함) 위의 정답 코드랑 아래 코드는 개념상으로는 거의 동일하다. 위의 코드는 내림차순으로, 아래 코드는 오름차순으로 구하는데.. 내 생각에는 아래 코드가 틀리다면 시간초과가 발생해야 할 것 같다. ( 예를 들면 7을 구할 때, 위의 코드는 4 2 1 부터, 아래 코드는 1 1 1 1 1 1 1 부터 구하기 때문에) 그런데 왜 틀렸습니다 가 나오는 것일까...? 12.. 더보기
2294번 2294번 - 동전 2 DP 문제를 풀면서, 이게 정말 왜 안풀리지라는 고민을 엄청 많이했다. 보통의 DP와 비슷하게 접근하고, 정말 맞았다고 생각하는데도 계속 시간초과가 발생했다. 처음에는 다시 풀어야겠다 라고 넘어갔었지만, 1520번 문제를 풀면서 갑자기 머리가 땡 하면서 문제가 해결 됐다. 1520문제와 같이 memoization 의 초기값 설정 문제였다. DP 라는 것은 결국 같은 문제를 풀 때, 이미 저장된 값을 이용해서 문제를 빠르게 풀도록 도와주는 memoization 을 사용한다. 그럼에도 계속 시간 초과가 났던 이유는 1520 문제와 비슷하게, 이 문제는 정답이 무조건 있는게 아니라, 어떠한 경우는 정답이 발생하지 않는다는 점이었다. 처음에 짰던 틀린 코드를 보자. 캐시값의 초기값은 98.. 더보기
1520번 1520번 - 내리막 길 전형적인 DP문제인데 한가지 조심해야 할 점은 , 바로 memoization 의 초기값 설정이었다. 보통 0이나 -1 로 선택해서 하게 되는데, 나 같은 경우에는 캐시에 값을 더해주는 문제의 경우에는 0을 주로 사용하긴 한다. (그래야 값이 변하지 않으므로) 근데 이 문제에서는 더 이상 갈 수 없는 경로가 존재하기 때문에 캐시값이 0이 되는 경우가 발생한다. 따라서 초기에 캐시값 설정은 -1로 해주는 것이 좋다. 그런데 이제 문제는 값이 더해지는 문제이기 때문에 -1이 되어있으면 안된다는 점이었다. 즉, 캐시값에 값을 더하는 것인데 초기값이 0 이면 1을 더하든 2를 더하든 상관없지만, 초기값이 -1 이므로 1이나 2등을 더하면 원래 제값이 안나오게 된다. 그래서 방문한 지점을 .. 더보기
1509번 1509번 - 팰린드롬 분할 이 문제는 생각이 좀 부족해서 다른 설명을 보고 풀었다. 일단 점화식은 D[i]=i번 문자열까지 팰린드롬 분할했을 때, 최소갯수 솔직히 이 점화식까지는 생각했지만, 이를 어떻게 활용할지는 생각이 나지 않았다. 근데 여기서 점화식에는 포함되지 않는 변수 j 를 문자열 중간에 삽입하면 모든 퍼즐이 완성된다. 즉, 변수 j번 문자열부터 i번 문자열까지는 팰린드롬 수라고 가정한다면, D[i] = min(D[i],D[j-1]+1) 이라는 식을 세울 수 있게된다. 뒤에서부터 짤라가는 과정이라고 생각하면 된다. 1. 뒤에서 부터 만들 수 있는 가장 긴 팰린드롬을 만든다. 2. 그 팰린드롬을 잘라낸 앞 부분에서 다시 위의 과정을 시작한다. j의 범위는 0부터 i 까지 나타낼 수 있다. 예를.. 더보기
반응형

티스토리툴바