본 글은 "나동빈"님의 [이것이 코딩 테스트다]를 참고하여 작성하였으며, 필자가 직접 문제를 풀며 관련된 문제들을 찾아 정리하였습니다. 시리즈 보기 [코테 알고리즘] 파이썬 기본 / 관련 문제 [코테 알고리즘] 파이썬 주요 라이브러리 / 관련 문제 [코테 알고리즘] 그리디 / 관련 문제 [코테 알고리즘] 구현 / 관련 문제 [코테 알고리즘] DFS, BFS / 관련 문제 [코테 알고리즘] 정렬 / 관련 문제 [코테 알고리즘] 다이나믹 프로그래밍 / 관련 문제 [코테 알고리즘] 최단 경로 / 관련 문제 [코테 알고리즘] 그래프 이론 / 관련 문제 그리디 현재 상황에서 지금 당장 좋은 것만 고르는 방법 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구 단순히 현재 상황에서 가장 좋아보이는 것..

문제요약 (13164번. 행복 유치원) 13164번: 행복 유치원 입력의 첫 줄에는 유치원에 있는 원생의 수를 나타내는 자연수 N(1 ≤ N ≤ 300,000)과 나누려고 하는 조의 개수를 나타내는 자연수 K(1 ≤ K ≤ N)가 공백으로 구분되어 주어진다. 다음 줄에는 원생들 www.acmicpc.net 풀이를 위한 부연 설명 아이디어를 떠올리는 것이 중요한 문제이다. 먼저 유치원생들 간의 키 차이를 diff에 저장한다. 인덱스 에러에 주의한다. n-k개의 diff 값을 더하면 구하려는 값이 나온다. 그리디와 정렬에 대한 자세한 개념 설명과 연관 문제는 다음 링크를 참고하면 된다. [코테 알고리즘] 그리디 / 관련 문제 본 글은 "나동빈"님의 [이것이 코딩 테스트다]를 참고하여 작성하였으며, 필자가 직..

문제요약 (1931. 회의실 배정) 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 그리디 알고리즘을 사용해야한다는 생각을 반드시 해야한다. 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 풀이를 위한 부연 설명 회의..

문제요약 ( 1541. 잃어버린 괄호 ) 주어진 수식에 적절히 괄호를 추가하여 식의 계산 결과값이 최소가 되도록 한다. ex. 55-50+40의 경우 55-(50+40)으로 만들어주면된다. 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 풀이를 위한 부연 설명 - 뒤에 붙는 숫자들은 다음 - 가 나올 때 까지 최대한 많이 묶어서 더한다. 더 좋은 풀이에서는 이 점을 이용하기 위해 split 함수를 사용했다. 주어진 수식을 연산자와 숫자로 나눠준다. 연산자를 하나씩 살펴보며 - 가 나올때를 기준으로 문제를..

문제요약 (1744. 수 묶기) 주어진 수열을 적절히 묶거나 더해서 그 합이 최대가 되도록 한다. 이때 수열의 모든 수는 한 번만 묶거나 묶지 않아야 한다. ex. 어떤 수열이 {0, 1, 2, 4, 3, 5} 일 때, 그냥 이 수열의 합을 구하면 0+1+2+4+3+5 = 15이다. 하지만, 2와 3을 묶고, 4와 5를 묶게 되면, 0+1+(2*3)+(4*5) = 27이 되어 최대가 된다. 수열에 음수인 수가 있을 때 처리를 중심으로 생각하는 것이 중요하다. 그리고 생각지도 못한 숫자가 하나 있을 수 있으니 주의하자. 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤..

문제요약 (1715. 카드 정렬하기) 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다. 매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10..

문제요약 (11047. 동전 0) 원하는 돈의 가치를 만들기 위해 필요한 동전의 최소 갯수를 구해 출력하라 다양한 경우의 수가 있지만 최소 갯수를 구해야한다. 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 풀이를 위한 개념 그리디에 대한 자세한 개념 설명과 연관 문제는 다음 링크를 참고하면 된다. [코테 알고리즘] DFS, BFS / 관련 문제 본 글은 "나동빈"님의 [이것이 코딩 테스트다]를 참고하여 작성하였으며, 필자가 직접 문제를 풀며 관련..