그리디

1. 문제 https://www.acmicpc.net/problem/1817 1817번: 짐 챙기는 숌 첫째 줄에 책의 개수 N과 박스에 넣을 수 있는 최대 무게 M이 주어진다. N은 0보다 크거나 같고 50보다 작거나 같은 정수이고, M은 1,000보다 작거나 같은 자연수이다. N이 0보다 큰 경우 둘째 줄에 책 www.acmicpc.net 책을 담을 수 있는 최소 상자의 갯수를 구하는 문제이다. 순서대로 책을 담았을 때 상자가 담을 수 있는 무게를 초과한다면 다음 상자를 꺼내야 한다. 2. 풀이 현재 상자에 담을 수 있는 무게를 current라고 하자. 담으려고 하는 책의 무게가 current 이하라면 담을 수 있을 것이고, 초과 한다면 새 상자를 준비해야 한다. current 이하라면 담으면 되니까..

1. 문제 https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 각 지원자의 서류심사 성적, 면접 성적의 순위가 주어진다. 서류심사 성적, 면접 성적 둘 모두가 다른 지원자보다 낮은 지원자가 있다면, 그 지원자는 선발 될 수 없다. 이 조건을 만족시키면서 선발할 수 있는 최대 인원수를 출력하는 문제이다. 2. 풀이 STEP1. 각 지원자의 서류심사 성적, 면접 성적의 순위를 벡터에 받아 저장한다. 그리고 sort()를 활용하여 ..

1. 문제 https://www.acmicpc.net/problem/1141 1141번: 접두사 접두사X 집합이란 집합의 어떤 한 단어가, 다른 단어의 접두어가 되지 않는 집합이다. 예를 들어, {hello}, {hello, goodbye, giant, hi}, 비어있는 집합은 모두 접두사X 집합이다. 하지만, {hello, hell}, {giant, www.acmicpc.net N개의 단어가 주어졌을때, 접두사X 집합의 최대 크기를 구하는 문제이다. 즉, 어떤 단어가 다른 단어의 접두사가 되지 않는 단어의 갯수를 찾으면 된다. 2. 풀이 접두사를 찾는 문제라는 것을 인지하니 정렬이 떠올랐다. sort()를 활용하여 정렬을 하면, 사전처럼 접두사가 될 수 있는 단어가 다른 단어들의 앞에 정렬되기 때문이다..

1. 문제 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net N개의 회의에 대해서 회의의 시작 시간과 종료 시간이 주어졌을 때, 각 회의가 겹치지 않게 회의실을 이용할 수 있는 최대 회의의 개수를 구하는 문제이다. 회의실의 수는 1개이고, 회의가 종료되는 것과 동시에 다음 회의가 시작될 수 있다. 2. 풀이 먼저 시작하더라도 늦게 끝난다면 그 회의는 선택될 수 없다. 즉, '종료 시간'이 이 문제의 주인공임을 알 수 있다. 남은 회의 중 종료 시간이 가장 빠른 회의의 시작 시간이 직전 회의의 종료 시간 이후라면 그 회의를 선택해 주면 된다. 우선, 각 회의의 시..

1. 문제 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 숫자와 부호들이 번갈아 가면서 등장하는데, 적절하게 괄호를 쳐서 만들 수 있는 최솟값을 구하면 된다. 가장 처음과 마지막은 숫자이고, 연속해서 두 개 이상의 연산자가 나타나지는 않는다. 예외처리는 고려하지 않아도 될 것 같다. 2. 풀이 마이너스가 한 번이라도 등장하면 그 뒤는 괄호 쳐서 다 마이너스 처리하면 되는 거 아닌가? 라고 생각했다. 여기까지는 쉽게 생각했는데 문제는 문자..

대망의 첫번째 포스팅이다. 꾸준하게 포스팅 할 것을 생각해서 무리하게 많은 내용을 담기보다는 조금씩 확실하게 포스팅 하자. Greedy(탐욕스러운) 그리디 알고리즘은 현재 상황에서 지금 당장 좋은 것만을 고르는 알고리즘을 의미한다. 지금 당장 최적인 답만 고르기 때문에, 현재의 선택이 나중에 미칠 영향 따위는 고려하지 않는다. 마시멜로 실험을 떠올리면 이해가 빠를 것 같다. 아이들은 15분동안 마시멜로를 먹지 않으면, 15분 후에 2개의 마시멜로를 먹을 수 있다. 그리디 알고리즘을 사용한다는 것은 지금 당장 눈 앞에 있는 마시멜로를 먹는다는 것이다. 하지만 이는 "15분 후에 2개를 먹는다"라는 최적의 해에 도달하지 못한다. 이렇듯, 그리디 알고리즘은 전체 문제의 최적해를 찾지 못하는 경우도 발생한다. ..