이마닷의 블로그

0. 문제 https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 1. 문제분석 - 이전의 상태(현재 문자열에서 양 끝의 문자열을 제외한 사이의 문자열이 팰린드롬인지)에 따라서 현재의 상태를 결정(현재의 문자열이 팰린드롬인지)한다는 점에서 Dynamic Programming을 사용해 문제를 풀어야 함을 알 수 있다. - dp[i][j] : 주어진 문자열 중, i번째 문자부터 j번째 문자까지로 이루어진 부분 문자열이 팰린드롬인지 (boolean) 2. 주의할 점 - 팰린드롬을 판단하는 부분 ..

0. 문제 https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 1. 문제분석 - 기존의 상태(기존에 종료 또는 종료하지 않은 앱으로 인해 획득한 메모리)에 대해서 기존의 상태를 바꿀 수 있는 경우의 수(기존에 종료한 앱 이외에 새로운 앱을 종료하는 것) 중, 그 최댓값(얻을 수 있는 메모리)을 찾아 조건을 만족하는(주어진 목표 메모리 m보다 크거나 같은) dp 값을 찾아 해당 dp의 2차원 인덱스인 비용의 최솟값을 찾는다는 점에서 Knapsack 알고리즘..

0. 문제 https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 1. 문제분석 - 외판원 순회(TSP, Traveling Salesman Problem)라는 유명한 알고리즘에 관한 문제이다. - 그래프 내 각각의 노드의 방문 상태를 알아야 하고 또 이전의 방문 상태 및 현재 방문 노드를 기준으로 다음 방문하는 노드와 상태가 정해진다는 점에서 각 노드의 방문 상태를 나타내기 위한 bitmask와 dynamic pr..

0. 문제 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 1. 문제분석 - 기존의 상태(기존에 배낭에 넣은 다른 물건들로 인해 결정된 무게)에 대해서 기존의 상태를 바꿀 수 있는 경우의 수(기존 배낭에 새로운 물건을 넣는 것) 중, 그 최댓값을 찾는다는 점에서 Dynamic Programming을 사용해 문제를 풀어야 함을 알 수 있다. - dp[n][w] : n번째 물건까지 ..