Let's Begin Programming

www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 회의의 수 N과 N만큼의 회의 정보(회의 시작 시간, 종료 시간)가 주어지면 최대한 많은 회의를 가지는 것이 목표이다. 특수한 경우는 시작과 종료가 같은 경우도 존재한다는 것이었다. 가장 먼저 든 생각은 종료 시간이 빨라야 더 많은 스케줄을 채울 수 있다는 것이었다. 시작 시간이 아무리 빨라도 종료 시간이 크면 그 만큼 할 수 있는 회의도 줄어들었다. 입력이 무작위로 주어지기 때문에 일단 정렬을 해야했다. 파이썬 정렬은 신기했다. list.sort(key = lambda x: [x[1], x[0]]) 람다를 이용해서 함수 안에..

개발 공부 (알고리즘) 2021. 1. 20. 05:49

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 그리디 알고리즘의 첫 문제이다. 그리디 알고리즘을 간단하게 말하면 현재 상황에서 가장 이득이 되는 결정을 하는 알고리즘이다. 미래에 대한 걱정은 하지 않고 현재 부딪힌 상황만 보고 판단하는 것이다. 이 문제는 주어진 돈의 종류를 최소한으로 써서 입력으로 들어오는 돈의 액수를 0으로 만드는 것이 목표이다. 우리가 거스름돈을 거슬러 줄 때를 생각하면 ..

개발 공부 (알고리즘) 2021. 1. 20. 05:29

https://www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 www.acmicpc.net 문제가 겉보기에는 쉬워보여서 처음에 시도했다가 두 번이나 실패를 받았다. 처음에는 단순하게 666부터 1000씩 곱하는 방법을 시도했다. 666 -> 1666 -> 2666 -> 3666 -> ... 그러나 중간에 맨 앞에 자리가 6이 되었을 때가 문제였다. 6066, 6166, ... 60660 이런 경우가 생기는 것이었다. 그래서 숫자를 하나씩 확인하는 방법을 생각했다. 숫자를 문자열로 바꾸..

개발 공부 (알고리즘) 2021. 1. 18. 07:42

https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 브루트 포스 문제는 모든 경우의 수를 시도하면서 결과를 구하는 것을 말한다. 모든 알고리즘 문제가 그렇지만 이 문제가 브루트 포스 알고리즘 문제라고 생각하면 쉽지만 만약에 사전에 주어진 것 없이 문제만 나왔다면 더 효율적인 방법이나 알고리즘을 찾으려고 괜히 더 생각했을 것 같다. 물론 더 좋은 방법이 있을 것이다. 내가 푼 방법은 모든 경우의 수를 시도해 보는 방법이다. 문제에서 준 힌트는..

개발 공부 (알고리즘) 2021. 1. 18. 05:19

[참고]https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 정수를 소인수분해하는 프로그램을 작성하는 문제였다. 처음에는 단순하게 소인수분해를 하는 과정을 그대로 프로그래밍했다. 정수를 입력받고 2부터 정수까지 나누어 떨어지면 그 피연산자를 출력하고 나누어 떨어지지 않으면 피연산자를 증가시키는 형태였다. 그러나 처음에는 "시간초과"가 뜨면서 실패했다. 두 번째 시도하면서 여러 가지 고민을 했다. 시간이 초과가 된 이유는 아마 반복문에 있을 것이다. 무한루프에 빠지는 경우의 수가 있거나 출제자가 의도한 대로 하지 않아 나누어보지 않아도 되는 경우에도 반복문에 들어간 것이..

개발 공부 (알고리즘) 2021. 1. 14. 05:12

[문제 출처]https://www.acmicpc.net/problem/10757 10757번: 큰 수 A+B 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. www.acmicpc.net 두 정수를 입력 받아 덧셈을 하는 간단한 사칙연산 프로그램 문제였다. 그러나 입력의 조건이 10의 1만 제곱 미만까지 가능하므로 unsigned int(0 ~ 2의 32제곱)도 소용이 없다. 단순히 더 큰 자료형을 찾으라는 문제는 아닌 것 같아서 결국 입력을 받는 자료형은 문자열밖에 없다는 생각을 했다. 일단 입력을 문자열로 받은 후 덧셈을 하는 과정을 똑같이 따라하면 되겠다고 생각했다. 노가다인 것 같았지만 다른 해결방법이 생각나지 않았다. 먼저 입력받은 두 문자열에서 뒤에서 부터(1의 자리..

개발 공부 (알고리즘) 2021. 1. 14. 02:48