BOJ

[문제] https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net [풀이] 이 문제는 피보나치 값이 아닌, 특정 값의 피보나치를 구하기 위해 호출되는 fibonaaci(0)과 fibonacci(1)의 호출 횟수를 구하는 것이다. 피보나치 문제는 문제 답 저장 후 해당 부분이 필요한 경우 저장된 결과를 사용하는 동적 계획법 으로 풀었다. fibonacci(n)을 구하기 위해서는 fibonacci(n-1)와 fibonacci(n-2)을 더해야 하기 때문에 fibonacci(n)을 호출할 경우 실행되는 fibonacci(0)과 fibonacci(1)은 '..

[문제] https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net [풀이] 입력되는 내용을 딕셔너리 타입의 book에 key : value 값을 각각 {번호 : 이름}, {이름 : 번호} 로 저장한 뒤 key 값을 이용해 value 를 찾아 출력한다. [코드] import sys if __name__ == '__main__': input = sys.stdin.readline n, m = map(int, input().spli..

[문제] https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net [풀이] 누적 합 누적 합은 구간의 누적 합을 구하는 문제이다. 일반적으로 리스트에 값을 저장하고, 인덱스로 한개씩 더하는 방식은 최악의 경우 O(n^2)의 시간복잡도를 갖기 때문에 입력의 범위가 클 때는 사용할 수 없다. 하지만 Prefix sum 방식을 사용하면 O(n)의 시간복잡도로 해결할 수 있다. 누적합은 문제에서 수열이 주어지고 어떤 구간의 값의 합을 구..

[문제] https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net [풀이] 끝자리가 0이 되려면 2와 5를 곱했을 경우에만 10이 나와 끝에 0이 추가된다. 따라서 소인수분해 했을 때 2와 5의 최소값을 구하면 되는 문제인데 숫자가 커질수록 5가 2보다 적게 나와 5의 개수만 구해도 되겠다는 생각이 들었다. 따라서 n이 5 이상일 동안 cnt에 5로 나눴을 때의 몫을 더한 후 출력한다. [코드] import sys if __name__ == '__main__': n = int(sys.stdin.readline()) cnt = 0 while..

[문제] 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 [풀이] 문제 조건이 큰 동전은 모두 작은 동전의 배수이기 때문에 이 문제는 그리디 알고리즘으로 풀 수 있다. 만약 800원의 가치를 만들어야 하는데, 500원 400원 100원으로 주어지는 경우는 그리디 알고리즘을 쓰면 안된다. 동전 문제에 그리디 알고리즘을 적용하는 것은 쉽다. 동전의 액면가만 보고 판단하면 되기 때문에 ..

[문제] https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net [풀이] 문제를 읽었을 때 딱 봐도 제곱 반복 수행 -> 문제 답 저장 후 해당 부분이 필요한 경우 저장된 결과를 사용 -> 동적 계획법!!! 그렇다면 이제 문제에 사용되는 규칙을 찾아야 한다. 0 1 2 3 4 5 6 7 8 1 0 1 2 3 1 5 6 7 8 2 0 1 2 3 1 2 3 4 2 3 0 1 2 3 1 2 3 0 0 4 0 1 2 3 1..

[문제] https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net [풀이] 엥? 골드 5 치고는 너무 쉬워 보이는데? 하고 풀었는데 문자열 처리 부분이 까다로웠다. 일단.. 아래 코드 부분에 pop(0)을 할 일이 있길래 popleft()를 사용하기 위해 deque를 사용하기로 했다. 입력 중 배열에 들어가 있는 수를 처리하는 부분이 조금 까다로운데, "[1, 2, 3]" 이렇게 큰 따옴표 안의 모두를 입력받는다. 그러나 처리는 정수 (1, 2, 3)만 해야 하기 때문에 대괄호를 지우고, 쉼표로 구분을 해줘야..

[문제] https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net [풀이] 문제는 쉬운데 출력 비교하는 게 어려웠음 ㅎㅎㅋ 집합이기 때문에 set 자료형을 사용하였고, set은 자동으로 중복이 없어지기 때문에 중복을 신경 쓰지 않아도 된다. add, remove, check, toggle은 x라는 파라미터가 필요하지만 all과 empty는 파라미터가 없기 때문에 입력을 operation 변수에 한 번에 받고, operation이 'all'이나 'empty'이 아닌 경우, operation..

[문제] https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net [코드] import sys if __name__ == '__main__': target = int(sys.stdin.readline().strip()) m = int(sys.stdin.readline()) if m: # 고장난 버튼이 있을 경우 broken = set(sys.stdin.readline().split()) else: broken = set() ans = a..