백준

문제1509번: 팰린드롬 분할 (acmicpc.net) 풀이팰린드롬 확인문자열을 팰린드롬으로 분할하기 위해서는 우선 분할된 문자열이 팰린드롬인지 확인해야 합니다. `isPalindrome[start][end]` 를 이용하여 주어진 문자열의 start번 부터 end번 까지가 팰린드롬을 이루는 지 `true`, `false`로 판단하여 저장하겠습니다. start부터 end까지 팰린드롬을 이루기 위한 조건이 무엇이 있을까요?가장 먼저 문자열의 start 번과 end번의 문자가 같아야 합니다. 그 다음은 start +1 번 문자부터 end -1 번 문자까지의 문자열이 팰린드롬을 이루면 됩니다.다시 말해, `isPalindrome[start+1][end-1] = true` 이어야 합니다. 즉,isPalindrom..

문제 2186번: 문자판 (acmicpc.net) 2186번: 문자판 첫째 줄에 N(1 ≤ N ≤ 100), M(1 ≤ M ≤ 100), K(1 ≤ K ≤ 5)가 주어진다. 다음 N개의 줄에는 M개의 알파벳 대문자가 주어지는데, 이는 N×M 크기의 문자판을 나타낸다. 다음 줄에는 1자 이상 80자 이하의 www.acmicpc.net 풀이 문자판을 십자 방향으로 DFS 탐색하며 DFS 탐색의 깊이가 영단어의 길이와 일치할 때 주어진 영단어와 일치하는지 확인하는 작업이 필요합니다. 하지만 DFS 탐색만으로 해결하려 한다면 불필요한 경우도 중복 탐색하게 되어 연산 시간이 오래 걸리게 됩니다. 중복은 다이나믹 프로그래밍으로 줄일 수 있습니다. DFS 탐색을 한다면 메모이제이션으로 불필요한 재귀 호출을 줄일 수 ..

문제 1806번: 부분합 (acmicpc.net) 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 풀이 N 이 최대 100,000이 될 수 있기 때문에 $O(n)$ 시간 복잡도안으로 해결해야 합니다. 연속된 수들의 부분합을 $O(n)$ 시간 안으로 구하기 위해서는 두 포인터로 구현하면 됩니다. `begin` : 연속된 수 중 첫 인덱스 `end` : 연속된 수 중 마지막의 다음 인덱스 `sum` : `begin` 번재 부터 `end-1` 번째 까지 수들의 합 `cnt` : 연속된 수들의 개수 e..

문제 14502번: 연구소 (acmicpc.net) 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이 연구소 내 최대 안전구역을 확보하기 위해 3개의 벽을 어떻게 설치할지 결정하는 문제입니다. N x M 의 칸 중 3개를 선택하는 조합(combination)입니다. 다행히도 벽을 꼭 3개를 세워야 하므로 전체 경우의 수는 많지 않습니다. 그렇기 때문에 완전탐색으로 문제를 해결할 수 있습니다. 벽을 어떻게 세울지 결정하였다면 그래프 탐색 알고리즘을 이용하여 바이러스가 닿지 않는 안전구역의 칸 수를 확인해주면 됩니다. 완전..

문제 https://www.acmicpc.net/problem/12919 12919번: A와 B 2 수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈 www.acmicpc.net 풀이 다른 방법 없이 모든 경우의 수를 확인해야 합니다. 문자열 S에 대해서 2가지 연산이 가능합니다. S를 T로 만들기위해 2가지 연산을 반복해서 하다보면 최악의 경우 $2^{50}$ 개의 경우의 수가 발생하게 됩니다. 어마어마한 경우의 수이기 때문에 시간초과가 발생합니다. 반대로 T에서 S를 만드는 경우로 생각이 가능합니다. 조건에 맞게 T의 문자..

문제 https://www.acmicpc.net/problem/3108 3108번: 로고 로고는 주로 교육용에 쓰이는 프로그래밍 언어이다. 로고의 가장 큰 특징은 거북이 로봇인데, 사용자는 이 거북이 로봇을 움직이는 명령을 입력해 화면에 도형을 그릴 수 있다. 거북이는 위치와 www.acmicpc.net 풀이 거북이를 조종하기 위한 여러가지 명령어가 있지만 해당 문제에서 신경쓸 것은 없습니다. 단지 연필을 올리고 내리는 것만 신경쓰면 되죠. 문제에서 같은 거북이는 같은 선을 여러번 그릴 수 있기 때문에 겹쳐진 사각형은 한번 연필을 내렸을 때 모두 그릴 수 있습니다. 겹쳐진 사각형을 같은 집합으로 묶고 그 집합의 수를 세어주면 거북이가 연필을 들어올리는 명령(PU)의 최소값을 구할 수 있습니다. 두 사각형..

문제 https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 풀이 메모리 M 이상을 확보하기 위해서 필요한 비용의 최소값을 구해야 하는 문제입니다. 즉, 메모리 M 이상을 확보하기 위해 앱을 비활성화 했을 경우의 수들 중에서 비용의 최소값을 구해야 합니다. 문제를 그대로 받아들이고 해결하려 한다면 상당히 어렵습니다. 문제를 재정의 해보죠. 메모리의 관점이 아닌 비용의 관점으로 생각해봅시다. 그렇다면 발생할 수 있는 상황들을 비용이 K 일때 확보할 수 있는 메..

문제 https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 풀이 최단거리를 구하는 문제인데 출발점이 주어지지 않았습니다. 그렇다면 모든 노드에서 거리를 확인해보아야 하는데 이때 사용할 알고리즘은 플로이드-워셜 알고리즘이 적합해보입니다. 플로이드-워셜 알고리즘 설명 특별하게 이 문제에서는 출발점으로 다시 돌아오는 것까지 계산해야 합니다. 특정 노드까지의 거리를 구한 뒤 다시 출발점으로 돌아오는 경우까지 고려하여 최단 ..