'분류 전체보기' 카테고리의 글 목록 (49 Page)

ASYMTLING

알고리즘/algospot 2015. 2. 21. 12:31

내가 스스로 풀때는 n개를 채울 때 대칭인 경우와 비대칭인 경우로 나누어서접근하려고 했는데 그렇게 풀 필요가 전혀 없었다.책에서 양 끝에서부터 채워가는 방식을 읽고 정말 놀랬다 ㄷㄷㄷㄷ이렇게 생각하면 정말 쉽게 풀리는 구나... 재귀함수의 매력에 놀랬고 저자의 천재성에 감탄하고 나의 부족함을 다시한번 깨달았다 ㅠㅠ양끝이 대칭이면 내부는 비대칭이어야 하고양끝이 비대칭이면 내부는 대칭이어야 한다. 이 경우로 모든 경우의 수를 만들 수 있었다...dp로 문제를 해결하는 두 가지 조건- 모든 경우의 수를 포함해야 하며- 중복되는 경우가 있어선 안된다를 다시 한번 실감하는 순간이었다

NUMB3RS

알고리즘/algospot 2015. 2. 21. 12:15

동적 계획법을 이용하면 풀기 편하다.d[마을수][지난날수]로 자료형을 잡고if(connected[현위치][마을])d[현위치][날짜] += d[마을][날짜-1]/deg[마을]로구할 수 있다.그런데 제출하면 왜 틀리다고 나오는지 모르겠다;책에있는데로 그대로 따라하는데... 알고스팟 뭔가 좀 이상하다.... 물론 나한테 문제가 있는거지만 ㅠ

2631

알고리즘/acmicpc 2015. 2. 17. 19:13

알고리즘 문제들은 서로 다른 문제 같아도 같은 개념을 사용하고 있음을 이해하면문제풀기가 편하다.줄세우기문제는 앞으로 옮기고 뒤로 옮기고 해서 어려워 보이지사실은 증가하는 순열중 가장 긴 순열을 찾으라는 문제와 같다.옮기는 횟수는 전체 배열의 크기에서 증가하는 순열중 가장 긴 순열의 개수를 뺀 것과 같다.아.. 이렇게 빠르게 이해됫으면 얼마나 좋을까

1958

알고리즘/acmicpc 2015. 2. 17. 18:38

세개의 문자에 대해서 LCS를 찾는것d[][][] 3차원배열을 만들고 점화식은 같다사실 공간에 취약해서 왜 이렇게 답이되는지 증명하라면 좀 시간 걸릴것 같다하지만 LCS 문제를 푸는데 착안해서 풀었다.

9252

알고리즘/acmicpc 2015. 2. 17. 18:09

LCS 살짝 변형한 문제다문자열에대한 dp[][]배열을 만들어주면 된다.

9251

알고리즘/acmicpc 2015. 2. 17. 17:18

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]) 요렇게

2599

알고리즘/acmicpc 2015. 2. 15. 23:35

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

2436

알고리즘/acmicpc 2015. 2. 15. 23:27

공약수문제...너무 소수를 구하는데 얽매여서 에나로스의 체를 구해서 소수 만들고 하다보니 메모리 초과 뜨고 ㄷㄷㄷ너무 소인수분해 하는데에 얽매여서 문제를 풀었던 것 같다.좀 더 단순히 생각했어야 하는데 다른 사람이 푼 코드를 보니 아 이렇구나.... 6, 180이 주어져있으면180/6 = 30이 남는다결국 30을 어떻게 쪼개느냐가 중요한건데나는 30을 소인수 분해해서 2 3 5 를 어떻게 분해할 것인가로 문제를 풀었는데다른사람은 아예 1~30까지 탐사해서 각각의 경우에 최대 공약수가 원래의 값과 일치하는지를 보았다 ㄷㄷ 바보같이 쓸데 없느데 얽매이다보니 푸는게 너무 늦어졌다;;

ABOUT ME

아는 개발자 아는 개발자

티스토리툴바