문제 https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 solved.ac 난이도: Gold 5 자료구조, Stack을 활용하는 그리디 문제. 그리디 문제들에는 특히 자료구조를 이용하는 경우가 많은 것 같다. 취업을 위해 치르는 코딩 테스트들에도 그리디 문제가 특히 많이 출제되는데, 그 배경에는 자료구조에 얼마나 익숙한지 보기위함도 없잖아 있지 않을까? 라는 생각이든다. 스택을 이용한 풀이를 떠올리지 못하여 N~N-K 번째 수중에 가장 큰 것(idx)을 고르고, 다시 그 수부터 idx ~ idx - k +1 번째 수 중..

문제 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..

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

문제 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://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]에 저장..

문제 https://www.acmicpc.net/problem/1328 1328번: 고층 빌딩 상근이가 살고있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼 www.acmicpc.net 풀이 난이도: Gold 1 곰곰이 생각해보아도 점화식이나 재귀 함수로도 구현이 잘 되지 않아 풀기 힘들었다. 해결 풀이는 재미지님의 징검다리 블로그 게시물을 참조하였다. [ BOJ 백준 1328번 - 고층 빌딩 ] 해설 및 코드 - 징검다리 빌딩은 N개이며 같은 높이를 가지지 않기 때문에 1~N의 높이를 가진다. 3차원 배열을 선언하여 dp[idx][l][r]에 idx번째 수(큰 수부터 내림..

문제 www.acmicpc.net/problem/13398 13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이 누적 합과도 연관된 DP문제. 연속합1 문제의 경우 해당 숫자를 합에 더하거나 해당 숫자에서 다시 연속 합 계산을 시작하는 두 경우를 비교하여 O(n)시간에 가장 큰 연속합을 구할 수 있다. 본 문제에서는 수열 중에서 한 숫자를 제외하거나 하지 않는 연속합들 중 최댓값을 찾아야 한다. 연속합1과는 다르게 2차원 배열 dp[100000][2]를 이용한다. 1. dp[i][0]에는 숫자가 제외되지 않은 경우..

문제 www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 풀이 팰린드롬이란 거꾸로 읽어도 동일한 회문을 의미한다. start번째 수부터 end번째 수까지가 팰린드롬임을 확인하려면 일단 arr[start]와 arr[end]가 같아야 한다. 그 후 arr[start+1]에서 arr[end-1] 까지가 팰린드롬이라면 해당 수열은 팰린드롬임을 알 수 있다. 즉, arr[start]에서 arr[end]까지를 확인할 때 arr[start+1]에서 arr[end-1] 까지가 팰린드롬의 여부를 확인하므로 결과 값을..

문제 https://www.acmicpc.net/problem/2482 2482번: 색상환 첫째 줄에 N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003 (10억 3) 으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 순열 조합과 비슷한 DP문제. 개인 적으로는 결국 조합의 경우 수 모두 찾아보기 때문에 배낭 알고리즘(Knapsack)과 비슷한 부분이 있는 것 같다. 해당 문제에서도 배낭 문제처럼 idx번째 색을 선택한 경우와 선택하지 않는 경우를 아래와 같이 표현할 수 있다. 1. idx 색을 선택: dp[idx-2][k-1] 인접 칸을 한 칸 띄워 idx-2로, 색 한 개를 선택하였으므로 남은 선택 색상 개수를 -1 해..