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

백준 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
알고리즘/문제풀이 - 백준

백준 2565 전깃줄

문제 : https://www.acmicpc.net/problem/2565 서론LIS 문제라는것을 알았는데도 풀이를 떠올리지 못했다.전깃줄을 제거하는게 아니라 역으로 교차하지 않는 전깃줄을 세는것을 알고 난 후 문제의 예제 그림을 통해 이해할 수 있었다. 풀이주어진 입력을 문제의 예제 그림과 같이 만들기 위해 A위치를 기준으로 오름차순 정렬한다.그 후 B 위치를 기준으로 LIS정렬 해주면 된다. 구현//c++ #include #include using namespace std; typedef struct { int first; int second; }st; int dp[102]; st line[102]; bool compare(st a, st b) { return a.first < b.first; } i..

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

백준 11054 가장 긴 바이토닉 부분 수열

문제 : https://www.acmicpc.net/problem/11054 서론 11053 문제에 비해 시간복잡도가 두배(+a) 늘었다. 그래서 같은 방식은 시간초과를 예상했으나 통과했다. 풀이 백준 11053 가장 긴 증가하는 부분 수열 문제 : https://www.acmicpc.net/problem/11053 혼자 풀어내지 못한 문제. 이중 for문을 쓰는것 외에는 푸는 방법이 떠오르지 않았는데, 시간복잡도에 중점을 두는 DP문제라서 이중 for문이 쓰이진 않을것 같� hydroponicglass.tistory.com 위 문제에서 dp를 하나 더 추가한다. 기존이 1->n방향으로 증가시키는 dp1이였다면 n->1 방향으로 증가시키는 dp2를 만든다. 그 후 dp3[i] = dp1[i]+dp2[i]..

2019. 7. 8. 21:13