풀어야 할 입출력 문제 2557, 1000, 2558, 10950, 10951, 10952, 10953, 11021, 11022, 11718, 11719, 11720, 11721, 2741, 2742, 2739, 1924, 8393, 10818, 2438, 2439, 2440, 2441, 2442, 2445, 2522, 2446, 10991, 10992 🧨 백준 11719 문제 출처 : 백준 11719번 - 그대로 출력하기 문제 난이도 : 브론즈 문제 링크 : www.acmicpc.net/problem/11719 11719번: 그대로 출력하기 2 입력이 주어진다. 입력은 최대 100줄로 이루어져 있고, 알파벳 소문자, 대문자, 공백, 숫자로만 이루어져 있다. 각 줄은 100글자를 넘지 않으며, 빈 줄이 ..
🧨 백준 1946번 문제 출처 : 백준 1946번 - 신입사원 문제 난이도 : 실버1 문제 링크 : www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 🧨 알고리즘 선택 및 C++ 코드 이 문제 자체를 이해하는 게 힘들었다. 정확히 얘기하자면 선발된 지원자들 안에서 조건을 따지는게 아니라 지원자들 전체에서 조건을 모두 따져서 서류와 면접 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발하는 것이다. 다시 말해, 매 지원자에 대해 모..
🧨 백준 11399번 문제 출처 : 백준 11399번 - ATM 문제 난이도 : 실버3 문제 링크 : www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 🧨 알고리즘 선택 및 C++ 코드 이 문제 푸는데 OS의 프로세스 순서 정하는 알고리즘이 문득 생각났다.. 수행시간이 짧은 걸 먼저 실행시키면 starvation(기아)이 발생할 수밖에 없다는 문제가 있었는데,, 어쨌든 그리디로 풀어보았다. 각 자리수까지의 sum을 저장할 배열을 또 만들 수도 있지만 괜히 저장공간을 더 쓰고싶지 않았다. #..
🧨 백준 11047번 문제 출처 : 백준 11047번 문제 난이도 : 실버1 문제 링크 : 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++ 코드 동전문제야말로 대표적인 그리디 알고리즘이다. 가장 큰 동전단위부터 내림차순으로 내가 원하는 금액 K를 채워나가면 된다. 마치 stable sorting과 비슷한 느낌이랄까.. (x, y 순으로 정렬하려면 y먼저 정렬하고 x ..
📌 탐욕적 알고리즘 Greedy Algorithm 탐욕적 알고리즘(Greedy Algorithm)은 동적 프로그래밍(Dynamic Programming) 얘기를 빼놓고서는 할 수 없다. 동적 프로그래밍은 나중에 또 하겠지만 간단히 설명하자면 전체 문제를 여러 개의 하위 문제로 나누어 풀고, 하위 문제들의 해결방법을 결합해 최종 문제를 해결하는 방법이다. 즉, 동적프로그래밍은 사실상 문제를 해결하는 모든 방법을 탐색하므로 정확하지만 속도가 느릴 수 밖에 없다. 동적 프로그래밍의 느린 속도를 보완하고자 등장한 개념이 탐욕적 알고리즘이다. 탐욕적(Greedy), 말 그대로 현재 상황에서 당장 좋은 것만을 고르는 방법이다. 그 순간에 최적이라고 생각하는 결정을 한다. (미래를 전혀 고려하지 않음) 덕분에 그리디..
🧨 백준 2490번 문제 출처 : 백준 2490번 - 윷놀이 문제 난이도 : 브론즈3 문제 링크 : www.acmicpc.net/problem/2490 2490번: 윷놀이 우리나라 고유의 윷놀이는 네 개의 윷짝을 던져서 배(0)와 등(1)이 나오는 숫자를 세어 도, 개, 걸, 윷, 모를 결정한다. 네 개 윷짝을 던져서 나온 각 윷짝의 배 혹은 등 정보가 주어질 때 도(배 한 www.acmicpc.net 🧨 알고리즘 선택 및 C++ 코드 0, 1로 된 윷놀이 상태를 출력하는 코드였다. 조건문만 쓰면 되는 문제.. #include using namespace std; int main() { int a, b, c, d; int sum = 0; for(int i = 0; i < 3; i++) { for(int ..
🧨 백준 1085번 문제 출처 : 백준 1085번 - 직사각형에서 탈출 문제 난이도 : 브론즈3 문제 링크 : www.acmicpc.net/problem/1085 1085번: 직사각형에서 탈출 한수는 지금 (x, y)에 있다. 직사각형의 왼쪽 아래 꼭짓점은 (0, 0)에 있고, 오른쪽 위 꼭짓점은 (w, h)에 있다. 직사각형의 경계선까지 가는 거리의 최솟값을 구하는 프로그램을 작성하시오. www.acmicpc.net 🧨 알고리즘 선택 및 C++ 코드 직사각형 내에서 직사각형의 경계까지의 거리이므로 간단하게 구현할 수 있다. #include #include using namespace std; int main () { int x, y, w, h; scanf("%d %d %d %d", &x, &y, &w,..
🧨 백준 1330번 문제 출처 : 백준 1330번 - 두 수 비교하기 문제 난이도 : 브론즈4 문제 링크 : www.acmicpc.net/problem/1330 1330번: 두 수 비교하기 두 정수 A와 B가 주어졌을 때, A와 B를 비교하는 프로그램을 작성하시오. www.acmicpc.net 🧨 알고리즘 선택 및 C++ 코드 간단한 두 수 비교 문제로 if - else 구문을 이용했다. #include using namespace std; int main () { int a, b; scanf("%d %d", &a, &b); if(a < b) { printf(""); } else { printf("=="); } return 0; } 🧨 백준 2525번 문제 출처 : 백준 2525번 - 오븐시계 문제 난이..
