ASYMTLING

알고리즘/algospot 2015. 2. 21. 12:31 Posted by 아는 개발자

내가 스스로 풀때는 n개를 채울 때 대칭인 경우와 비대칭인 경우로 나누어서

접근하려고 했는데 그렇게 풀 필요가 전혀 없었다.

책에서 양 끝에서부터 채워가는 방식을 읽고 정말 놀랬다 ㄷㄷㄷㄷ

이렇게 생각하면 정말 쉽게 풀리는 구나... 

재귀함수의 매력에 놀랬고 저자의 천재성에 감탄하고 나의 부족함을 다시한번 깨달았다 ㅠㅠ

양끝이 대칭이면 내부는 비대칭이어야 하고

양끝이 비대칭이면 내부는 대칭이어야 한다. 이 경우로 모든 경우의 수를 만들 수 있었다...

dp로 문제를 해결하는 두 가지 조건

- 모든 경우의 수를 포함해야 하며

- 중복되는 경우가 있어선 안된다

를 다시 한번 실감하는 순간이었다


728x90

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

카쿠로  (0) 2016.12.11
회전초밥  (0) 2016.08.01
블록게임  (0) 2016.08.01
조합게임  (0) 2016.07.25
ASYMTLING  (0) 2015.02.21
NUMB3RS  (0) 2015.02.21

NUMB3RS

알고리즘/algospot 2015. 2. 21. 12:15 Posted by 아는 개발자

동적 계획법을 이용하면 풀기 편하다.

d[마을수][지난날수]로 자료형을 잡고

if(connected[현위치][마을])

d[현위치][날짜] += d[마을][날짜-1]/deg[마을]로

구할 수 있다.

그런데 제출하면 왜 틀리다고 나오는지 모르겠다;

책에있는데로 그대로 따라하는데... 

알고스팟 뭔가 좀 이상하다.... 물론 나한테 문제가 있는거지만 ㅠ

728x90

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

카쿠로  (0) 2016.12.11
회전초밥  (0) 2016.08.01
블록게임  (0) 2016.08.01
조합게임  (0) 2016.07.25
ASYMTLING  (0) 2015.02.21
NUMB3RS  (0) 2015.02.21

2631

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

알고리즘 문제들은 서로 다른 문제 같아도 같은 개념을 사용하고 있음을 이해하면

문제풀기가 편하다.

줄세우기문제는 앞으로 옮기고 뒤로 옮기고 해서 어려워 보이지

사실은 증가하는 순열중 가장 긴 순열을 찾으라는 문제와 같다.

옮기는 횟수는 전체 배열의 크기에서 증가하는 순열중 가장 긴 순열의 개수를 뺀 것과 같다.

아.. 이렇게 빠르게 이해됫으면 얼마나 좋을까

728x90

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

9463  (0) 2015.02.21
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

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