문제 https://algospot.com/judge/problem/read/STRJOIN algospot.com :: STRJOIN 문자열 합치기 문제 정보 문제 프로그래밍 언어 C 의 큰 문제점 중 하나는 언어 차원에서 문자열 변수형을 지원하지 않는다는 것입니다. C 에서는 문자 배열로 문자열을 표현하되 \0 (NULL) 로 문자 algospot.com 풀이 종만북 난이도: 중 난이도는 중인 그리디 문제이지만 C++ STL의 우선순위 큐(priority_queue)와 같은 컨테이너 라이브러리를 안다면 쉽게 해결할 수 있다. 일단 예를 들어 4개의 문자열(str1, str2, str3, str4)을 순서대로 합친다고 생각해보자. 첫번째로 합쳐진 문자열의 길이는 len1(str1+str2), 두번째는 l..

문제 www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net 풀이 solved.ac 난이도: Gold3 그리디 알고리즘 문제이지만 DP문제에서 많이 본 유형이라 문제 분류를 몰랐다면 DP로 접근했을 듯한 문제였다. 해당 문제의 그리디 알고리즘은 다음과 같다. 일단 추를 무게의 오름차순으로 정렬했다 가정하자. 지금까지 idx번째의 추까지 사용하여 만들 수 있는 무게들 중 가장 큰 것을 end_num라고 하자. 다음 추 idx+1를 추가적 이용하여 만들 수 있는 무게들은 0,1,..

문제 www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 풀이 solved.ac 난이도: Silver1 이전에 풀었던 회의실 배정 문제와 유사한 그리디 문제. 일단 입력의 크기가 N(1 ≤ N ≤ 100,000)로 굉장히 크기 때문에 O(N^2) 시간복잡도를 가지는 알고리즘으로 해결하긴 힘들다. 따라서 아래와 같은 그리디 방식으로 접근하자. 일단 서류심사의 기준으로 pair 배열을 정렬하자. 예제가 입력이 아래와 같이 주어지면 3 6 7 3..

*문제들의 난이도 분류는 종만북 혹은 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번째 사건을 ..