*문제들의 난이도 분류는 종만북 혹은 solved.ac 출처임을 밝힙니다.* ★ 문제는 작성자가 다시 풀어보고 싶은 문제 혹은 어려웠던 문제입니다. +가 붙은 문제는 해당 문제에서 중요하게 생각하는 부분입니다. 연습 문제 링크 [백준] 회의실배정(1931) - Silver 2 [백준] 신입사원(1946) - Silver 1 [백준] 주식(11501) - Silver 2 [알고스팟] 문자열 합치기(STRJOIN) - 중 [백준] 저울(2437) - Gold 3 [백준] 과제(13904) - Gold 3 [백준] 단어 수학(1339) - Gold 4 [백준] 통학버스(2513) - Gold 3 [백준] 빵집(3019) + DFS - Gold 2 [백준] 뉴스 전하기(1135) + 트리 - Gold 1 [백준..

문제 www.acmicpc.net/problem/1931 1931번: 회의실배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 풀이 solved.ac 난이도: 실버2 종만북의 그리디 알고리즘 파트에 등장하는 회의실 예약 문제와 동일한 문제. 하지만 본 문제에서는 회의의 시작시간과 끝나는 시간이 같을 수도 있기 때문에 유의하여 풀어야한다. 단순히 모든 경우를 탐색해보기에는 입력의 크기가 너무 크니 아래의 그리디 알고리즘으로 접근해보자. 항상 빨리 끝나는 회의 만을 선택하고 다음 회의로는 이전 회의와 겹치지 않는 가장 빨리 끝나는 회의를 선택하자. 이를 구현하기 위해서 회의의 시작 시간과 끝시간을 pair로 저장하여 끝나는 시간을 기준으로 정렬하자. ..

문제 https://algospot.com/judge/problem/read/POLY algospot.com :: POLY 폴리오미노 문제 정보 문제 정사각형들의 변들을 서로 완전하게 붙여 만든 도형들을 폴리오미노(Polyomino)라고 부릅니다. n개의 정사각형으로 구성된 폴리오미노들을 만들려고하는데, 이 중 세로 algospot.com 풀이 종만북 난이도: 중 폴리오미노 중에서도 세로로 단조인 것의 개수를 구해야 하는 문제. 일단 폴리오미노는 한 변이라도 붙어이어야 하기 때문에 모든 정사각형은 이어저 있어야 한다. 또한 세로로 단조이기 위해서는 같은 세로줄이라면 모두 이어져야 한다. 따라서 위의 세로줄부터 num개의 사각형을 이어 붙이고 남은 사각형(remain_squ)으로 다음 세로줄을 몇 개의 사..

문제 https://algospot.com/judge/problem/read/ASYMTILING algospot.com :: ASYMTILING 비대칭 타일링 문제 정보 문제 그림과 같이 2 * n 크기의 직사각형을 2 * 1 크기의 타일로 채우려고 합니다. 타일들은 서로 겹쳐서는 안 되고, 90도로 회전해서 쓸 수 있습니다. 단 이 타일링 방법은 algospot.com 풀이 이전 문제인 타일링 문제를 풀고 오자. 타일링 문제는 아래의 점화식으로 간단히 해결이 가능하다. cache_tiling[i] = cache_tiling[i-1] + cache_tiling[i-2] 이번 문제는 이러한 타일링의 수에서 대칭으로 놓인 경우의 수를 빼주면 된다. 대칭이 가능한 경우는 크게 두 가지로 나누어진다. 1. n이..

문제 algospot.com/judge/problem/read/TRIPATHCNT algospot.com :: TRIPATHCNT 삼각형 위의 최대 경로 수 세기 문제 정보 문제 9 5 7 1 3 2 3 5 5 6 위 형태와 같이 삼각형 모양으로 배치된 자연수들이 있습니다. 맨 위의 숫자에서 시작해, 한 번에 한 칸씩 아래로 내려가 맨 아래 algospot.com 풀이 종만북 난이도: 중 난이도는 중인 DP문제이지만 이전 단계를 풀었다면 쉬운 문제이다. 일단 이전 단계 문제인 삼각형 위의 최대 경로를 풀고오자. 최대 경로의 값을 구하는 문제는 아래와 같은 재귀함수로 해결이 가능하다. 1 2 3 4 5 6 7 8 9 10 11 int TriMaxSum(int r,int c){ int& ret = cache..

문제 https://algospot.com/judge/problem/read/QUANTIZE algospot.com :: QUANTIZE Quantization 문제 정보 문제 Quantization (양자화) 과정은, 더 넓은 범위를 갖는 값들을 작은 범위를 갖는 값들로 근사해 표현함으로써 자료를 손실 압축하는 과정을 말한다. 예를 들어 16비트 JPG 파일 algospot.com 풀이 종만북 난이도: 중 1000이하의 자연수로 이루어진 수열을 S종류의 1000이하의 정수 값을 사용하여 양자화할 때, 오차 제곱의 합의 최솟값을 구하는 문제이다. 1~1000까지의 모든 수에서 10가지만 선택하는 조합의 경우의 수만 해도 너무나 크다. 따라서 미리 사용할 S(quan_num)개의 수를 선택해서 모든 값과 ..

문제 https://www.acmicpc.net/problem/2618 2618번: 경찰차 첫째 줄에는 동서방향 도로의 개수를 나타내는 정수 N(5≤N≤1,000)이 주어진다. 둘째 줄에는 처리해야 하는 사건의 개수를 나타내는 정수 W(1≤W≤1,000)가 주어진다. 셋째 줄부터 (W+2)번째 줄까지 www.acmicpc.net 풀이 solved.ac 난이도: Platinum-5 최단 이동 거리를 구하는 것과 어느 순서대로 경찰차를 이동시켜야 최단 이동 거리가 나오는지까지 구해야 하는 문제. 일단 최단 이동 거리를 구하는 재귀함수부터 구현해보자. int MovePatrolCar(int incident_idx,int patrol1_pos, int patrol2_pos ) incident_idx번째 사건을 ..

문제 https://algospot.com/judge/problem/read/JLIS] algospot.com :: JLIS 합친 LIS 문제 정보 문제 어떤 수열에서 0개 이상의 숫자를 지운 결과를 원 수열의 부분 수열이라고 부릅니다. 예를 들어 '4 7 6'은 '4 3 7 6 9'의 부분 수열입니다. 중복된 숫자가 없고 오름 차순으로 algospot.com 풀이 일단 이전 단계 문제인 LIS(최장 증가 부분 수열) 문제를 확인하고 옵시다. LIS보다 까다로워진 문제입니다. 단순히 생각했을 때 두 수열의 LIS의 길이를 더하면 된다고 생각할 수 있지만 1 4 9 4 -> lis length: 3 3 4 4 7 -> lis length: 3 위의 예제에서는 JLIS는 1 3 4 7 9인 5이지만 각각의 ..

문제 algospot.com/judge/problem/read/LIS algospot.com :: LIS Longest Increasing Sequence 문제 정보 문제 어떤 정수 수열에서 0개 이상의 숫자를 지우면 이 수열의 부분 수열 (subsequence) 를 얻을 수 있다. 예를 들어 10 7 4 9 의 부분 수열에는 7 4 9, 10 4, 10 9 등이 있다. algospot.com 풀이 대표적인 DP문제 중 하나인 최대 증가 부분 수열(LIS, Longest Increasing Sequence)을 구하는 문제이다. 단순히 아래의 예제에서 모든 경우의 수를 찾는다고 생각해보자. 1 5 4 3 4 6 7 1번째 수, 1에서부터 재귀 함수로 LIS를 찾는다고 가정하면 1보다 큰 모든 수를 하나하나..

문제 https://www.acmicpc.net/problem/1509 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net 풀이 일단 이전 단계인 문제 팰린드롬?을 풀고 오자. 이전 문제에서 우리는 start에서 end까지 팰린드롬을 이루는지의 여부를 is_palin[start][end] 저장해 문제를 해결하였다. 이번 문제에서도 해당 저장 값을 그대로 이용하자. 첫 글자(1)에서 현재 위치 (i)까지의 팰리드롬 개수의 최솟값을 dp[i]에 저장..