이마닷의 블로그

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/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 1. 문제분석 - 주어진 수들을 순차적으로 다르게 배열한 모든 경우의 수만 제시하면 되는 비교적 간단한 형태의 BackTracking 문제이다. 2. 주의할 점 - 꽤나 간단한 문제이기는 하지만, 꽤 많은 양을 출력해야 하므로 출력과 관련한 시간초과 문제를 조심해야 한다. - 기존에 사용하던 자료구조(스택, 큐, 그래프 등)를 구현한 라이브러리(LinkedList, ArrayL..

0. 문제 https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 1. 문제분석 - N개의 퀸을 체스판에 배치하는 모든 경우의 수에 대해 판단해야 하므로 Brute Force방식으로 각 좌표에 queen이 있는 상황을 다 따져보아야 한다. - N개의 queen이 있는 상황에 대해 조건 만족을 판단하기 위해 체스판을 설정한 뒤에는, 다시 또 다른 경우의 수를 판단하기 위해 체스판의 설정을 되돌려놓은 후 다른 경우의 수를 탐색해야 한다. 따라서 BackTracking 알..

0. 문제 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 1. 문제분석 - 현재 위치에서 다른 위치로 이동하는 경우의 수가 여러가지이고, 이 때에 최단거리를 구하라는 점에서 BFS 알고리즘을 활용해야 함을 알 수 있다. 하지만 본 문제는 일반적인 BFS 문제와는 다르게 다른 위치로 이동하는 비용이 각자 다르고 그 비용이 모두 0 또는 1 이라는 점에서 기존의 BFS 알고리즘에서 더 나아간 0-1 BFS 알고리..