알고리즘/문제풀이 - 백준

백준 1541 잃어버린 괄호

문제 : https://www.acmicpc.net/problem/1541 서론 쉬운문제였는데 혼자 풀어내지 못했다. 풀이를 볼 때 조금 더 생각하지 않았음에 오는 아쉬운 문제가 있고 보길 잘했다는 생각이 드는 문제가 있다. 풀이를 빠르게 볼지 말지를 선택하는것은 어려운 일이다. 아이디어 그리디 알고리즘 문제라서 규칙성이 있을거라는 생각은 했지만 찾지 못했다. 모든 경우의 수를 일단 계산해볼까 생각했으나 이것도 쉬운일은 아니었다. 간단하게 '-'가 나올때까지 입력값을 tokenization 해주면 된다. 입력값이 55-50+40 이면 괄호를 50-(50+40) 해주면 되고 100-20-10이면 100-(20)-(10) 100-30+20-40+10이면 100-(30+20)-(40+10)이다. 직관적으로 음..

2019. 7. 15. 20:18
알고리즘/문제풀이 - 백준

백준 2217 로프

문제 : https://www.acmicpc.net/problem/2217 서론 그리디 알고리즘 문제. 아이디어 예상되는 예제 몇개를 뽑아봤다. 1. 입력 : 10, 15 / 출력 : 20 2. 입력 : 10, 15, 20 / 출력 : 30 3. 입력 : 10, 15, 40 / 출력 : 40 4. 입력 : 10, 30, 40 / 출력 : 60 5. 입력 : 10, 20, 30, 40, 50 / 출력 : 90 각 예제에서 로프 하나가 버틸 수 있는 최대 하중의 최소인 10*n이 정답이 아님을 볼 수 있다. 예제 5에서 20*n은 안된다. 10의 하중의 줄이 버틸 수 없다. 5번 예제는 견딜 수 있는 최대 하중이 10*5 = 50 (10,20,30,40,50 사용) 20*4 = 80 (20,30,40,50 ..

2019. 7. 15. 17:05
알고리즘/문제풀이 - 백준

백준 11399 ATM

문제 : https://www.acmicpc.net/problem/11399 서론 분류가 그리디 알고리즘으로 되어있는데, 그리디 알고리즘에 대한 개념이 없어도 문제에 어떻게 풀어야하는지 친절하게 설명해주고 있다. 문제 알고리즘 내용이 운영체제 job scheduling 방식 중 이론적으로 optimal한 방식으로 배웠던것 같다. 프로세스의 소요시간을 정확히 예측할 수 없어서 어디까지나 이론이라고 들었던것 같다. 아이디어 인출하는데 걸리는 시간이 가장 빠른 사람부터 먼저 처리하는 그리디 알고리즘. p를 오름차순 정렬한 후에 각 사람의 대기시간은 앞 사람들과 나의 소요시간을 모두 더한다. 대기열의 사람들의 대기시간을 전부 더해서 출력한다. 구현 // c++ #include #include using name..

2019. 7. 9. 19:32
알고리즘/문제풀이 - 백준

백준 1931 회의실배정

문제 : https://www.acmicpc.net/problem/1931 서론 그리디 알고리즘. 시작시간을 기준으로 가능한 모든 경우의 수 탐색 -> 시간초과 종료시간을 기준으로 그리디 알고리즘 -> 통과 배낭문제와 함께 그리디 알고리즘의 대표적 문제. 아이디어 1. 종료시간을 기준으로 오름차순 정렬한다. 종료시간이 같다면 시작시간을 기준으로 오름차순 정렬한다. 2. 정렬한 배열에서 회의를 하나 가져오고 회의 수를 +1 해준다. 3. 정렬한 배열을 탐색하여 가져온 회의의 종료시간 이후에 회의가 시작하면 회의를 가져오고 회의 수를 +1 해준다. 4. 3을 반복한다. 구현 // c++ #include #include #include using namespace std; bool compare(paira, ..

2019. 7. 9. 18:56
알고리즘/문제풀이 - 백준

백준 11047 동전 0

문제 : https://www.acmicpc.net/problem/11047 서론 그리디 알고리즘 문제. 동전들이 배수관계여서 그리디 알고리즘의 결과가 최적해를 가지는것같다. 아이디어 k값에 더할 수 있는 동전 중 가장 큰값을 반복해서 더해준다. 더해줄때마다 횟수를 체크해서 출력한다. 예제 k=4200에서 4200 = 1000 + 1000 + 1000 + 1000 + 100 + 100 구현 //c++ #include using namespace std; int coin[10]; int main() { int n, k; cin >> n >> k; for (int i = n-1; i >= 0; i--) cin >> coin[i]; int sum = 0; int cnt = 0; while (sum != k) ..

2019. 7. 9. 14:40