기타/알고리즘
-
백준 파이썬 9613번 - GCD 합기타/알고리즘 2021. 6. 27. 14:16
9613번: GCD 합 첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진 www.acmicpc.net 포인터 두 개를 이용하여 모든 경우의 수에 대해 GCD를 구하여 answer에 더해나가는 식으로 구하였다 숫자 리스트의 첫 번째 요소가 수의 개수를 나타내므로, 포인터의 인덱스를 1부터 시작하도록 설정했다 def gcd(a,b): if b == 0: return a aa = a%b return gcd(b,aa) t = int(input()) for _ in range(t): a = list(map(int,input().split())) a..
-
백준 파이썬 9417번 - 최대GCD기타/알고리즘 2021. 6. 27. 13:57
9417번: 최대 GCD 첫째 줄에 테스트 케이스의 개수 N (1 < N < 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 양의 정수 M (1 < M < 100)개가 주어진다. 모든 수는 -231보다 크거나 같고, 231 -1보다 작거나 www.acmicpc.net 정수가 여러개 주어졌을 때 모든 두 수의 쌍 중에서 가장 큰 최대공약수를 찾아야 한다 포인터 두 개를 이용하여 모든 두 쌍의 GCD를 구하는 방법을 이용했다 길이가 n인 리스트가 존재한다면 for i in range(n-1): for j in range(i+1,n): 이렇게 처음 반복문은 가장 처음부터 마지막 두 번째 숫자까지 (0 to n-1) 두 번째 반복문은 처음 포인터의 다음 숫자부터 마지막 숫자까지 (i+1 to..
-
백준 파이썬 15486 : 퇴사 2 풀이기타/알고리즘 2020. 12. 26. 23:32
15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net n 1일 2일 3일 4일 5일 6일 7일 T[i] 3 5 1 1 2 4 2 P[i] 10 20 10 20 15 40 200 M 0 0 0 10 30 30 45 dp[i] 0 0 0 10 30 0 45 각각의 날들을 '그날 상담을 시작하는 경우'와 '그날 상담을 시작하지 않는 경우'로 나눌 수 있다 만약 1일이라면 T = 3인 일을 시작할 수도 있고, 시작하지 않을 수도 있는 것이다 상담을 시작한다면, 상담이 끝난 다음 날의 수익이 P..
-
백준 파이썬 11722번 : 가장 긴 감소하는 부분 수열 풀이기타/알고리즘 2020. 12. 25. 10:54
11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net nums 안의 수에 대해 가장 긴 감소하는 부분 수열의 길이를 구하는 문제다. 앞의 수가 다음 수보다 크다면 문제의 조건을 만족한다 각 인덱스에 대해 자신보다 인덱스가 작은 값을 검색하여 조건을 만족하는 수의 개수를 찾는다 앞의 인덱스에서 조건을 만족하는 수의 개수를 찾으면, 다음 계산시에 이를 이용해준다. 예제로 주어진 nums = [10, 30, 10, 20, 20, 10]로 생각해보면..
-
[파이썬] 리트코드 198. House Robber 풀이기타/알고리즘 2020. 12. 24. 23:04
House Robber - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 도둑이 이웃한 두 집을 연속해서 털 수 없을 때, 이익이 최대가 될 때의 값을 출력하는 문제다. 집 1, 2, 3, 4가 이웃해 있다면, 1을 털면 2는 털 수 없는 것이다. 2를 털면 1은 털 수 없다. 집 1,2 중에서 선택이 끝나면 집 3과 4에 대해서도 동일한 과정이 반복된다. 즉, '한 집을 털 것이냐, 털지 않고 다음 집을 털 것이냐'가 연속된 게임인 것이다. 따라서 1. 배열의..
-
[파이썬] 리트코드 39. Combination Sum 풀이기타/알고리즘 2020. 12. 24. 22:53
Combination Sum - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com candidates = [2,3,6,7] 와 같은 식으로 주어졌을 때, candidates안의 요소들을 더하여 target = 7을 만들 수 있는 배열을 출력하는 문제다. 그래프를 탐색하며 각각의 값들을 더해가다가 합한 값이 target이 되었을 때, 여태까지의 경로를 출력하면 되는 것이다. 1. dfs의 변수로 csum(target까지 남은 수), index, path를 이용한다 2..
-
[파이썬] 리트코드 53. Maximum Subarray 풀이기타/알고리즘 2020. 12. 24. 22:46
Maximum Subarray - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com nums이 주어졌을 때, 연속된 배열의 합이 가장 큰 경우의 합을 출력하는 문제다. 각각의 배열에 대해 모든 합을 계산하는 브루트 포스 방식으로는 풀 수 없다. 조금 더 효율적인 다이나믹 프로그래밍을 이용해야 한다. nums = [-2,1,-3,4,-1,2,1,-5,4]으로 주어진다면 포인터를 이동시키면서 배열의 합이나 포인터가 가르키는 숫자 중 큰 것을 cur_mx에 저장해주고 c..
-
[파이썬] 리트코드 78. Subsets 풀이기타/알고리즘 2020. 12. 24. 22:09
Subsets - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com nums = [1,2,3]일 때 부분집합의 개수를 구하는 문제다. 탐색 알고리즘을 실행했을 때, 모든 탐색의 결과가 정답이 된다. 따라서 dfs로 간단하게 풀 수 있다. 1. 인덱스와 경로를 변수로 가지는 dfs를 정의하고 2. 지나온 경로를 결과값에 저장하면서 3. 모든 경로에 대해 탐색을 실행한다 class Solution: def subsets(self, nums: List[int]) -> L..