1958

알고리즘/acmicpc 2015. 2. 17. 18:38 Posted by 아는 개발자

세개의 문자에 대해서 LCS를 찾는것

d[][][] 3차원배열을 만들고 점화식은 같다

사실 공간에 취약해서 왜 이렇게 답이되는지 증명하라면 좀 시간 걸릴것 같다

하지만 LCS 문제를 푸는데 착안해서 풀었다.

728x90

'알고리즘 > acmicpc' 카테고리의 다른 글

2776  (0) 2015.02.21
2631  (0) 2015.02.17
1958  (0) 2015.02.17
9252  (0) 2015.02.17
9251  (0) 2015.02.17
2599  (0) 2015.02.15

9252

알고리즘/acmicpc 2015. 2. 17. 18:09 Posted by 아는 개발자

LCS 살짝 변형한 문제다

문자열에대한 dp[][]배열을 만들어주면 된다.


728x90

'알고리즘 > acmicpc' 카테고리의 다른 글

2631  (0) 2015.02.17
1958  (0) 2015.02.17
9252  (0) 2015.02.17
9251  (0) 2015.02.17
2599  (0) 2015.02.15
2436  (0) 2015.02.15

9251

알고리즘/acmicpc 2015. 2. 17. 17:18 Posted by 아는 개발자

LCS문제

모두의 부부수열이 되는 수열중 가장긴것을 찾는문제

전형적인 dp문제인데 이때 d배열을 2차원으로 해야한다는 점이 중요

점화식만 잘 만들면 어렵지 않게 해결 할 수 있다.

현재 위치의 dp값을 지정해주려면


if(A[i] == B[i]) dp[i][j] = max(dp[i-1][j-1] + 1, dp[i-1][j], dp[i][j-1])

else dp[i][j] = max(dp[i][j-1], dp[i-1][j])


요렇게

728x90

'알고리즘 > acmicpc' 카테고리의 다른 글

1958  (0) 2015.02.17
9252  (0) 2015.02.17
9251  (0) 2015.02.17
2599  (0) 2015.02.15
2436  (0) 2015.02.15
2533  (0) 2015.02.14

2599

알고리즘/acmicpc 2015. 2. 15. 23:35 Posted by 아는 개발자

이런문제는 틀리면 안된다.

728x90

'알고리즘 > acmicpc' 카테고리의 다른 글

9252  (0) 2015.02.17
9251  (0) 2015.02.17
2599  (0) 2015.02.15
2436  (0) 2015.02.15
2533  (0) 2015.02.14
2469  (0) 2015.02.14

2436

알고리즘/acmicpc 2015. 2. 15. 23:27 Posted by 아는 개발자

공약수문제...

너무 소수를 구하는데 얽매여서 

에나로스의 체를 구해서 소수 만들고 하다보니 메모리 초과 뜨고 ㄷㄷㄷ

너무 소인수분해 하는데에 얽매여서 문제를 풀었던 것 같다.

좀 더 단순히 생각했어야 하는데 다른 사람이 푼 코드를 보니 아 이렇구나....


6, 180이 주어져있으면

180/6 = 30이 남는다

결국 30을 어떻게 쪼개느냐가 중요한건데

나는 30을 소인수 분해해서 2 3 5 를 어떻게 분해할 것인가로 문제를 풀었는데

다른사람은 아예 1~30까지 탐사해서 

각각의 경우에 최대 공약수가 원래의 값과 일치하는지를 보았다 ㄷㄷ


바보같이 쓸데 없느데 얽매이다보니 푸는게 너무 늦어졌다;;

728x90

'알고리즘 > acmicpc' 카테고리의 다른 글

9251  (0) 2015.02.17
2599  (0) 2015.02.15
2436  (0) 2015.02.15
2533  (0) 2015.02.14
2469  (0) 2015.02.14
2467  (0) 2015.02.14