목록파이썬 (92)

시작이 반

[백준] 2004번 (python 파이썬)

nCr = n!/(n-r)!r! 을 이용하면 된다. 하지만 단순 팩토리얼을 이용하여 풀면 n, m 이 20억이될 수 있기 때문에 시간초과, 또는 메모리 초과가 될 것이다. 끝자리가 0이라는 것은 2 와 5의 곱으로 이루어 졌으면 0이 된다. 만약 xxxxx00 이면 2가 2개 5가 2개의 곱으로 이루어 졌다는 것이다. 즉, 2, 5의 쌍을 구하면 0의 갯수를 구할 수 있다. 하지만 이것도 반복문으로 돌리다보니 계속 시간초과가 났다... 도저히 모르겠어서 답을 본 결과... def two_count(n): two = 0 while n != 0: n = n // 2 two += n return two 이런식으로 2의 갯수를 구하는 것을 알 수 있었는데.... 사실 이 식만봤을때 뭔소린지 이해를 못했다... ..
알고리즘/백준 2021. 3. 3. 23:36
[백준] 2981번 (python 파이썬)

수학적 이론이 필요한 문제이다. M 을 찾아야한다. A = M * a + R B = M * b + R C = M * c + R 여기서 R을 제거하면 A - B = M ( a - b ) B - C = M ( b - c ) 이런 식이 나온다. 즉, M은 A-B, B-C의 공약수이다 즉 최대공약수를 구하면 된다. 최대 공약수를 구하고 해당 수의 1을 제외한 약수를 출력하면된다. 이때 최대 공약수를 구하고 약수를 구할때 반복문을 최대공약수 까지 돌려버리면 숫자 범위가 1,000,000,000까지기 때문에 엄청난 시간이 걸린다. 그래서 공약수를 구할때 18 % 2 = 0 ( 2 = 약수) 18 // 2 = 9 ( 9 = 약수) 이 2개를 한번에 구한다 이러면 반복횟수를 최대공약수의 제곱근 까지 줄일수 있다. 마지..
알고리즘/백준 2021. 3. 1. 19:42
[백준] 1541번 (python 파이썬)

그리디 문제라고 나와있지만 그리디 보다는 문자열 처리 문제같다... -가 나오면 다음 - 가 나올때까지 숫자를 더해주고 더한 숫자를 list에 저장하고를 반복한다. list에 저장된 숫자를 다 더한후 음수로 만들고 맨 처음 숫자를 더해준다. express = input() split = list() result = list() start = 0 for i in range(len(express)): if express[i] == '-' or express[i] == '+': split.append(int(express[start:i])) split.append(express[i]) start = i + 1 split.append(int(express[start:])) start = 0 for i in ra..
알고리즘/백준 2021. 3. 1. 01:54
[백준] 11399번 (python 파이썬)

시간 순으로 오름차순으로 정렬을 한뒤 시간이 빨리 끝나는 것부터 처리해준다. n = int(input()) time = list(map(int, input().split())) time.sort() result_list = list() result = 0 for i in range(n): result += time[i] result_list.append(result) print(sum(result_list))
알고리즘/백준 2021. 2. 28. 22:10
[백준] 1931번 (python 파이썬)

그리디 문제이다. 회의가 끝나는 시간을 기준으로 오름차순으로 정렬을 한 후 그 안에서 시작 시간을 기준으로 정렬을 다시한다. 그 후 제일 먼저 끝나는 회의를 선택하고 다음으로 선택했던 회의 시간의 끝나는 시간보다 큰 시작 시간을 선택한다.(이미 끝나는 시간으로 정렬이 되어있기 때문에 고려안해두됨) n = int(input()) input_list = list() result_list = list() for i in range(n): start, end = map(int, input().split()) term = end - start input_list.append((start, end, term)) input_list.sort(key=lambda x: (x[1], x[0])) for i in range..
알고리즘/백준 2021. 2. 28. 21:50
[백준] 11047번 (python 파이썬)

그리디 문제의 기초이다. 최소의 동전개수로 해당 가격을 만드는 문제 주어진 제일큰 동전부터 시작하여 만들려고 하는 가격을 나눴을때 몫이 있다면 동전의 개수를 해당 몫만큼 더해주고 나머지를 가지고 다음 계산을 이어간다. ( 가장 큰 동전부터 선택하여 구하는 것 ) n, k = map(int, input().split()) a = list() for _ in range(n): a.append(int(input())) result = 0 def coin_zero(): global k, a, result for i in range(n-1, -1, -1): quotient = k // a[i] remainder = k % a[i] if quotient > 0: result += quotient k = remain..
알고리즘/백준 2021. 2. 27. 15:53
[백준] 12865번(python 파이썬)

knapsack알고리즘 문제이다. 1. 배낭에 물건을 넣는다. - 물건을 넣기전 상태에서 (가방 무게 - 해당 물건 무게)의 가치 + 해당 물건 가치 2. 배낭에 물건을 넣지 않는다. - 이전 값을 그대로 사용한다. ex) 물건 개수 : 4 가방에 들어갈 수있는 최대 무게 : 7 1번 물건 : 6 13 2번 물건 : 4 8 3번 물건 : 3 6 4번 물건 : 5 12 dp[i][j] 1. 물건을 넣는다 : dp[i-1][j - 해당 물건 무게] + 해당 물건 가치 2. 물건을 넣지 않는다 : dp[i-1][j] 1, 2중 최대값을 넣는다. 가방무게 물건 0 1 2 3 4 5 6 7 1번 물건 0 0 0 0 0 0 13 13 2번 물건 0 0 0 0 8 8 13 13 3번 물건 0 0 0 6 8 8 13 ..
알고리즘/백준 2021. 2. 26. 21:49
[백준] 1912번(python 파이썬)

연속된 숫자를 몇개 선택해서 더했을때 가장 큰 합을 구하는 것이다. 이는 양수는 계속 더해주고 음수일때 선택을 해야한다. 연속해서 더할 것인지 더하지 않을 것인지 정해야한다. 만약 숫자가 6 -5 1 2 3 -4 5 이렇게 있다면 1 2 3 은 더해서 6을 만든다. 이때 연속된 수로 -4가 나오게 되는데 계속 더해줄 것인지 빼고 다음 숫자부터 다시 시작할 것인지... 그렇다면 어떻게 정할까? 음수를 더했을때 보다 해당 음수 보다 클 경우 더해주면 된다. 1 + 2 + 3 = 6 (6 + -4 = 2 ) > -4 이기 때문에 계속 더해준다. 이런식으로 하면 1 2 3 -4 5 를 선택했을때 제일 큰 수 7이 나온다. 만약 음수를 기준으로 더하고 말지를 정한다면 ( 처음에 생각한 방법) 1 2 3 를 선택한..
알고리즘/백준 2021. 2. 26. 18:45
이전 Prev 1 ··· 5 6 7 8 9 10 11 12 Next 다음