본문 바로가기
728x90

코딩테스트25

다이나믹 프로그래밍 - 백준 1463 [Python] 큰 문제를 작은 문제로 나눠서 푸는 알고리즘 두 가지 속성을 만족해야 다이나믹 프로그래밍으로 문제를 풀 수 있다. Overlapping Subproblem Optimal Substructure 모든 문제를 풀어야 하고, 모든 문제는 1번만 풀어야 한다는 것을 생각하고 해결해야 한다. 따라서 시간 복잡도는 문제의 개수 * 문제 1개를 푸는 시간이 된다. 구현에는 Top-down (재귀), Bottom-up (반복문) 방식으로 구성되어 있다. 점화식을 구성한 다음 문제를 작게 만들 수 있는 방법을 찾아야 한다. Problem) https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmi.. 2021. 8. 3.
브루트 포스 - 백준 15650 [Python] 재귀함수로 풀 수 있는 브루트 포스 순서 : N가지가 있을 때 M를 순서대로 뽑을 경우 O(N!) 선택 : N가지에 대해서 선택/선택하지 않는 것 O(2^N) Problem) https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net Solution) 재귀 : 어떤 위치에 올 수 있는 수를 결정해 주는 것 선택 : 그 위치에 있는 것을 선택할지 말지 결정하는 것 Answer) import sys n,m = map(int,input().split()) c.. 2021. 7. 29.
브루드 포스 - 백준 1107 [Python] Problem) https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net Solution) 숫자버튼을 먼저 누른 다음, +/- 버튼을 눌러 채널을 이동하는 방식으로 접근한다. 이때, 어떤 채널로 이동해야 하는지 알 수 없기 때문에 브루드 포스 방식으로 접근해야한다. 이동할 채널 C를 정한다. 고장난 버튼을 파악한다. 고장난 버튼이 포함되어 있지 않다면 |C-N|을 계산해 +/- 버튼을 몇번 눌러야 하는지 계산한다. Answer) n = .. 2021. 7. 28.
브루드 포스 - 백준 1476 [Python] Problem) https://www.acmicpc.net/problem/1476 1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타 www.acmicpc.net Solution) 이 문제 같은경우 지구, 태양, 그리고 달에 대한 모든 경우의 수가 많지 않기 때문에 모든 경우의 수를 다 찾아서 해결하는 방법으로 접근해도 된다. Answer) E, S, M = map(int, input().split()) e,s,m = 1,1,1 year = 1 while True: if e == E and s == S and m == M: print(year) .. 2021. 7. 28.
728x90

티스토리툴바