CodeAngie

문제주어진 구간이 팰린드롬인지 빠르게 판단해 1 혹은 0을 출력하는 문제이다.풀이DP를 사용해 각 구간이 팰린드롬인지 미리 계산하면, 명우의 질문에 대한 답을 빠르게 구할 수 있다.길이가 1인 경우: 모든 숫자는 무조건 팰린드롬이다.길이가 2인 경우: 두 숫자가 같은 경우만 팰린드롬이다.길이가 3 이상인 경우: 양 끝의 두 숫자가 같고, 내부 숫자들이 팰린드롬일 때만 팰린드롬이 성립한다.팰린드롬의 길이가 3인 경우부터 차례로 DP를 사용해 팰린드롬 여부를 계산하면, 내부 구간을 비교할 수 있다.이후 a에서 b까지의 구간에  대해 DP 테이블을 참조해 팰린드롬 여부를 빠르게 출력할 수 있다.Python 코드import sysinput = sys.stdin.readlinen = int(input())arr ..

문제 n*n 크기의 새 집이 있다. 집 수리를 위해 파이프를 옮겨야 하는데, 파이프는 무겁기 때문에 밀어서 이동시켜야 한다. 파이프는 2개의 연속된 칸을 차지하는 크기이며 3가지 방향으로 회전이 가능하다. 파이프를 밀 수 있는 방향은 →, ↘, ↓ 방향 총 3가지가 있으며, 회전은 45도만 가능하다. 따라서 다음 그림과 같이 가로일 때 2가지, 세로일 때 2가지, 대각선일 때 3가지가 있다. 또한 벽(1)으로는 파이프를 이동시킬 수 없다. 가장 처음에는 파이프가 가로 방향으로 왼쪽 상단에 위치해 있다. 파이프의 한쪽을 (n,n)으로 이동시키는 방법의 개수를 구하여라. 풀이 DP를 사용해 문제를 풀 수 있다. 마지막 위치(n,n)에 파이프가 도달할 수 있는 경우의 수 문제를 (i,j)에 파이프가 도달할 수..

문제 n가지 종류의 동전이 있다. 각 동전의 가치가 제시될 때, 그 가치의 합이 k원이 되도록 하는 경우의 수를 구하는 문제이다. 이때 순서가 달라도 구성이 같다면 같은 경우의 수이다. 풀이 이 문제는 dp를 사용해 풀 수 있다. 가치의 합이 k원(1 ≤ k ≤ 10,000)이 되도록 하는 경우의 수 문제를 나누어 가치의 합이 y(1 ≤ y ≤ k)가 되도록 하는 경우의 수를 구하는 부분 문제로 볼 수 있다. 동전 x1을 사용하여 y가 될 수 있는 경우가 성립하는지 확인하는 것이다. 다시 말해 y - x1을 만들 수 있는 조합이 있다면 해당 경우의 수만큼 x1을 가지고 y값을 만들 수 있다. 이를 통해 다음과 같은 식을 세울 수 있다. dp[y] = dp [y] + dp [y-x1] 알고리즘 dp 리스트..

문제 S의 문자들을 골라 T를 만들 수 있다. S에서의 순서대로 이어 붙여 새 문자열을 만드는 것을 반복하여 만들 수 있는 T의 최대 개수를 구하는 문제이다. 풀이 S에서의 순서가 유지돼야 함을 유의한다. S문자열에서 차례대로 문자를 살펴보며 T를 만들 수 있는 개수를 별도의 리스트에서 셀 수 있다. 예를 들어 S가 adabccb 이고 T가 abc일 때, 다음과 같이 셀 수 있다. T에 해당하는 알파벳이 순서대로 개수가 확보되어 있는지 확인할 수 있는 리스트를 생성한다. S의 1번째 a 문자는 T에 포함되며 이전 문자의 개수가 무한으로 현재 문자(a) 개수보다 많기 때문에 현재 문자에 1을 더한다. 2번째 문자인 d는 T에 포함되지 않으므로 넘어간다. 3번째 문자인 a는 첫번째와 마찬가지이기 때문에 a에..

문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 문제이다. 풀이 DP를 사용하여 LIS를 구하는 기존 문제에 부분 수열의 길이뿐만 아니라 부분 수열을 요소까지 출력하는 문제이다. 따라서 증가하는 부분 수열의 요소를 담는 것을 함께 구현해야 한다. 증가하는 부분 수열의 요소를 담는 리스트를 생성하고 dp가 증가할 때 함께 업데이트 되도록 한다. 알고리즘 n과 a 수열을 입력받는다. 1로 초기화된 dp를 생성한다. 부분 수열의 요소를 담을 b 리스트를 생성한다. A 수열에서 뒤의 요소가 앞의 요소보다 크고 부분 수열의 길이도 더 길어질 때, 부분 수열의 길이를 업데이트 하면서 부분 수열의 요소도 업데이트 해준다. 가장 긴 부분 수열의 길이를 찾아 출력하고, 해당 위치와 동일한 부분 수열의..

문제 새로운 언어로 암호화된 문장을 해석하는데 드는 비용의 최솟값을 구하는 문제이다. 이 문장은 연속된 단어의 연결로 이루어져 있으며, 단어는 0번 이상 쓰일 수 있다. 또한 각 단어는 알파벳의 순서를 바꾸어 암호화되었을 수 있다. 이러한 문장을 해석하는 비용은 원래 단어의 위치와 다른 위치에 있는 알파벳 개수만큼 든다. 예를 들어 원래 단어가 one 이라면, oen은 비용이 2만큼, neo는 비용이 3만큼 든다. 풀이 암호화는 한 단어 내에서 알파벳의 위치만 변한 것이다. 따라서 문장 내에 주어진 단어가 포함된다면 그 단어의 길이만큼 문장을 잘랐을 때, 주어진 단어의 알파벳을 정렬한 결과와 문장에서 잘린 부분의 알파벳 정렬 결과가 동일해야 한다. 정렬 결과가 같다면 주어진 단어를 만들 수 있음으로 해석..

문제 각각의 일을 끝내는 데 걸리는 시간(일)이 담겨 있는 A 배열이 주어졌을 때, 일의 순서를 바꾸어 헬스장에 갈 수 있는 경우는 YES, 갈 수 없다면 NO를 출력하는 문제이다. 문제 조건 오늘은 월요일이다. 금요일에 일을 끝내야 헬스장에 간다. 풀이 일주일은 7일이기 때문에 월요일부터 일요일을 0에서 6으로 둔다. 월요일에 일을 시작해서 금요일에 끝나려면 7로 나누었을 때 나머지가 4인 날이 있는지 확인하면 된다. 따라서 숫자의 조합에 따라 합계를 7로 나눈 나머지가 4가 되는 경우가 있는지 살핀다. 시간에 대한 연산과 나머지에 대한 연산의 결과가 같다는 것을 활용한다. ex) (15+ 9) % 7 = (1 + 2) % 7 = 3 A 배열의 요소(a)들을 모두 순회하면서 먼저 계산된 나머지와 연산을..