문제 https://www.acmicpc.net/problem/7570 7570번: 줄 세우기 입력은 2 개의 줄로 이루어져 있다. 첫 줄에는 어린이 수를 나타내는 정수가 주어진다. 둘째 줄에는 처음에 줄서있는 어린이들의 번호가 차례대로 주어진다. 주어진 번호들 사이에는 공백이 하 www.acmicpc.net 풀이 solved.ac 난이도: Gold 4 탐욕법과 동적계획법을 이용해야하기 때문에 까다로웠던 문제이다. 풀이는 마이구미님의 게시글을 참고하였다. 문제를 풀기 전에, 이전 단계 문제라고 볼 수 있는 백준 - 줄 세우기(2631)을 함께 풀어보면 좋다. 2631번 줄 세우기 문제에 사용되는 동적계획법의 알고리즘은 LIS(최장 증가 부분 수열)이다. 해당 문제는 어느 위치로든 이동시킬 수 있으므로 L..

문제 https://www.acmicpc.net/problem/13904 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 풀이 solved.ac 난이도: Gold 3 그리디(탐욕법) 문제이지만 브루트 포스도 이용하여 문제를 해결하였다. 일단 pair의 first에 남은 일자를, second에 점수를 저장하고 남은 일자를 기준으로 내림차순 정렬을 하자. 문제의 예제는 아래와 같이 정렬된다. 6 5 4 60 4 40 4 10 3 30 2 50 1 20 기간이 많이 남을 수록 앞쪽으로 정렬되기 때문에 최대 기한인 6일을 기준으로 day_cnt를 하루하루 줄이면..

문제 https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 풀이 solved.ac 난이도: Gold 4 아이디어는 단순했지만 구현하기가 까다로워서 코드가 엉망 친창이 되어버렸다.. 문제를 파악했다면 높은 자릿수에 자주 나오는 알파벳일 수록 큰 수를 대입해 주면 된다는 것을 알 수 있을 것이다. 예를 들어 아래와 같은 입력이 주어졌다고 생각해보자. ACA BCC 여기서 100의 자리 수는 A와 B 두 가지가 존재한다. 그렇다면 A와 B 중에서 어..

문제 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 번째 수 중..

문제 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)으로 다음 세로줄을 몇 개의 사..