문제 https://www.acmicpc.net/problem/10165 10165번: 버스 노선 첫 번째 줄에는 버스 정류소의 개수 N(3 ≤ N ≤ 1,000,000,000)이 주어지고 두 번째 줄에는 버스 노선의 수 M(2 ≤ M ≤ 500,000)이 주어진다. 각 버스 노선은 1부터 M까지의 번호로 구분된다. 그 다음 M개 www.acmicpc.net 풀이 solved.ac 난이도: Platium 5 정렬을 해서 푸는 것까지는 생각해냈지만 0을 지나는 노선의 처리하지 못하여 틀린 그리디 문제. 해당 문제는 0을 지나지 않는 노선(line_v)와 0을 지나는 노선(cross_line_v)로 나누어 해결해야 한다. 1. 0을 지나지 않는 노선(line_v) 해당 노선들은 시작점(start)을 기준으로..

문제 https://www.acmicpc.net/problem/2513 2513번: 통학버스 첫째 줄에는 세 개의 양의 정수 N, K, S가 빈칸을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 아파트 단지의 수이며 2second)); else right_v.push_back(make_pair( abs(school_pos - it->first),it->second)); } Colored by Color Scripter cs 그 후 먼 곳부터 정렬되도록 left_v, right_v를 내림차순으로 정렬해준다. 이제 먼 곳부터 방문하면서 정원을 채우는 코드를 구현한다. 1. 남은 자리(left_sit) 보다 해당 위치(apt_idx)에서 태울 학생 수가 적다면 모두 태우고 해당 위치의 학생 수는 0으로,..

문제 https://www.acmicpc.net/problem/11501 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 풀이 solved.ac 난이도: Silver 2 간단한 그리디 알고리즘 문제. 주식은 낮을 때 사서 높을 때 팔아야하는 것처럼 해당 문제도 같은 방식으로 풀 수 있다. 주가를 입력받은 stock_value을 역순으로 진행하면서 두가지를 확인하면 쉽게 구할 수 있다. 1. 현재(day)의 주가가 지나온 주가 중에서 최대 주가(max_stock)보다 작다면 해당 주식은 구매해서 ma..

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