4luv1015

https://www.acmicpc.net/problem/5502 5502번: 팰린드롬 팰린드롬이란 대칭 문자열이다. 즉, 왼쪽에서 오른쪽으로 읽었을때와 오른쪽에서 왼쪽으로 읽었을때 같다는 얘기다. 당신은 문자열이 주어졌을때, 최소 개수의 문자를 삽입하여 팰린드롬이 www.acmicpc.net 서로 다른 방식의 두 가지 dp로 문제를 풀어보았다. 실행 시간은 1번 방법이 2번 방법보다 두 배 정도 더 빨랐다. 1. LCS를 활용한 방법 당연한 이야기지만 기존 문자열에 문자를 추가해 팰린드롬을 만든다면 추가할 문자는 기존에 존재하는 문자 중 하나에 대응하는(팰린드롬 상에서) 문자일 것이다. 그런데 여기서 문자를 추가하는 것은 추가할 문자에 대응하는 문자를 삭제하는 것과 동일하다. 따라서 최소 횟수를 구하는..

https://www.acmicpc.net/problem/9029 9029번: 정육면체 입력은 표준입력(standard input)을 통해 받아들인다. 입력의 첫 줄에는 테스트 케이스의 개수 T (1 ≤ T ≤ 20) 가 주어진다. 각 테스트 케이스에 대해 원목의 크기를 나타내는 W,L,H (1 ≤ W, L, H ≤ 200) www.acmicpc.net 특별할 것 없는 3차원 dp이다. 높이, 가로, 세로를 차원으로 하는 3차원 dp배열을 만들고 해당하는 높이, 가로, 세로를 가진 블럭을 최소 개수의 정육면체로 나눌 때 그 최소 개수를 배열에 저장하면 된다. 재귀를 통한 탑다운 방식으로 dp를 구현하면 깔끔하게 코드가 짜일 거 같아서 시도해봤는데 예상대로 잘 됐다. 높이, 세로, 가로가 같다면 1을 리턴..

https://www.acmicpc.net/problem/14505 14517번: 팰린드롬 개수 구하기 (Large) 팰린드롬(palindrome)이란 앞에서부터 읽으나 뒤에서부터 읽으나 같은 단어를 말한다. 'aba'나 'a'와 같은 단어는 팰린드롬이며, 'abaccbcb'나 'anavolimilana'와 같은 단어는 팰린드롬이 아니다. 승수는 주 www.acmicpc.net https://www.acmicpc.net/problem/14517 14517번: 팰린드롬 개수 구하기 (Large) 팰린드롬(palindrome)이란 앞에서부터 읽으나 뒤에서부터 읽으나 같은 단어를 말한다. 'aba'나 'a'와 같은 단어는 팰린드롬이며, 'abaccbcb'나 'anavolimilana'와 같은 단어는 팰린드롬이..

https://www.acmicpc.net/problem/1029 1029번: 그림 교환 첫째 줄에 예술가의 수 N이 주어진다. N은 2보다 크거나 같고, 15보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 N개의 수가 주어진다. i번째 줄의 j번째 수는 j번 예술가가 i번 예술가에 www.acmicpc.net 문제의 설명과 N의 최대값이 20전후인 것 때문에 비트마스킹 dp문제가 아닐까 생각했는데 맞았다. 그 중에서도 외판원 순회 문제의 변형에 가깝기 때문에 외판원 순회 문제를 먼저 풀어보는 것을 추천한다. 비트마스킹이란 이진수로 집합을 표현하는 테크닉이다. 아래의 이진수는 10이다. 0 0 0 1 0 1 0 각각의 비트에 인덱스를 다음과 같이 표현해주겠다. 7 6 5 4 3 2 1 0 0 0..