greedy algorithm

[1120] 문자열

https://www.acmicpc.net/problem/1120 1120번: 문자열 길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다. 두 문자열 A와 B가 주어진다. 이때, A의 � www.acmicpc.net 🔎 해결 방법 현재 순간에서 가장 최선의 경우만 고려하는 그리디 알고리즘의 특성을 이용하면 생각보다 코드도 짧고 간단한 문제였다. 예를 들어 A = "adaabc", B = "aababbc" 라면 먼저 (B[0], A[0]), (B[1], A[1]), (B[2], A[2]) ... 이런식으로 비교를 한 다음, 다른 경우에만 gap을 증가시켜 주면 된다. ..

그리디 알고리즘(Greedy Algorithm, 탐욕법)

[1541] 잃어버린 괄호

https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. www.acmicpc.net 수식의 값을 최소로 만들기 위해서는, '-'와 '-' 사이에 있는 숫자들을 모두 괄호 안에 집어넣으면 된다! ex) 1+2-3+4+5-6+7 인 경우, 1+2-(3+4+5)-(6+7) 이렇게 괄호를 치면 된다. 이때, 연산자가 '-'인 경우에만 continue를 해주면 되는 이유는 tmp = 55 또는 tmp = +55 인 경우에 s..

[11399] ATM

https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 🔎 해결 방법 오랜만에 한번에 맞은 문제 ㅋㅋ 문제를 읽어보면 바로 어떻게 풀어야 하는지 감을 잡을 수 있다. 줄을 [2, 5, 1, 4, 3] 순서로 세우는 것은 결국 돈을 인출하는데 걸리는 시간을 [1, 2, 3, 3, 4] 와 같이 오름차순으로 정렬하겠다는 소리이다. 그래서 중첩 for문을 사용해서 그냥 다 더해주면 끝~ 💡 내 코드(C++) // [11399] ATM // https://www.acmicpc.net/pr..

[11047] 동전 0

https://www.acmicpc.net/problem/11047 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 그리디 알고리즘을 사용하는 문제! 그냥 간단한 문제였다. 💡 내 코드(C++) // [11047] 동전 0 // https://www.acmicpc.net/problem/11047 // 그리디 알고리즘 #include using namespace std; int main(void) { int n, k; // 준규가 가지고 있는 동전의..

[1931] 회의실배정

https://www.acmicpc.net/problem/1931 1931번: 회의실배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 그리디 알고리즘을 사용하는 문제.... dp문제를 많이 풀다가 그리디 알고리즘 문제를 풀려고 하니 자꾸 dp식으로 접근하는 바람에 시간초과가 계속 났었다. 그리디 알고리즘이란, 현재 상태에서 가장 최선의 선택인 것만 골라서 진행하는 알고리즘이다. 즉 다른건 아무것도 생각하지말고 그냥 현재 상태에만 집중하면 되는 것이다. 🔎 해결방법 1. 회의 시작 시간을 기준으로 오름차순 정렬, 시작 시간이 같다면 끝나는 시간이 빠른 것부터 정렬(sort 함수 사용) 2. tmp을 회의가 가장 늦게 시작하는 시간으로 초기화 3. ..