이마닷의 블로그

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 알고리..

0. 문제 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 1. 문제분석 - 그리드 상의 수를 누적해 구하는 문제로, 좌상단에서부터 누적된 수를 토대로 그리드 상 현재 위치의 누적된 값을 구해야한다는 점에서 DynamicProgramming을 사용해야 하는 전형적인 문제이다. 2. 주의할 점 - 비교적 쉬운 문제이기는 하지만, dp[i][j] 값에 대한 정의를 분명히 하고 부분합을 구하기 위한 i, j..

0. 문제 https://www.acmicpc.net/problem/1728 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m www.acmicpc.net 1. 문제분석 - 자료구조 시간에 배운 KMP 알고리즘을 사용해야 하는 전형적인 문제이다. 2. 주의할 점 - 자료구조 책을 펼치고 KMP 알고리즘을 다시 공부하자. - 블로그에 설명이 참 잘되어 있다. bowbowbow.tistory.com/6 KMP : 문자열 검색 알고리즘 문자열 검색이 뭐지? 워드프로세서를 사용할 때 찾기 기능을 사용한적 있을 겁니다. 브라우저에서도 Ctrl..

0. 문제 https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 1. 문제분석 - 처음에는 맨 처음 숫자를 눌러 가장 가까운 채널로 이동해 +, - 버튼에 따라 목표지점에 도달하는 최단 거리만 구하면 된다고 생각해서 BFS로 쉽게 풀 수 있을 것이라 생각했다. 하지만, 가장 가까운 채널로 이동하기 위해 가장 가까운 채널을 구하는 방법이 꽤나 복잡해져서 포기했다. 결국에는 이동 가능한 모든 채널로 이동해보고 해당 채널에서 목표지점까지 ..