목록알고리즘/백준 (90)

시작이 반

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

나무를 0미터를 가져갈 수 도있고 최대 높이를 가져갈 수도있다. 즉 절단기의 길이는 최대 높이를 자르려면 맨 밑동을 잘라야한다 -> 0 0미터를 가져간다면 가장큰 높이의 나무만큼 절단기 높이를 설정한다 -> max(trees) n, m = map(int, input().split(' ')) trees = list(map(int, input().split(' '))) def binary(): left = 0 right = max(trees) while left 0: height += tree - mid if height >= m: # 잘린 길이가 구하려는 것보다 크면 더 큰높이로 자르기 left = mid + 1 elif height < m: # 잘린 길이가 구하려는 것보다 작으면 더 작은 높이로 자르기 ..
알고리즘/백준 2021. 3. 17. 15:51
[백준] 10816번번 (python 파이썬)

이진탐색 풀이 첫 풀이 방법은 이진탐색을 한뒤 찾으려는 숫자가 있으면 count + 1을 해주고 해당 숫자를 list에서 remove한뒤 다시 그 숫자를 이진탐색하는 방식으로 하였다. 당연하게 시간초과가 나왔다. 두번째 풀이 방법은 찾고자 하는 숫자의 index를 이진탐색으로 찾고 그 index에서 양쪽으로 찾으려는 숫자가 있는지 반복문으로 확인하는 방식으로 하였다. 이또한 시간초과가 나왔다 list에 모든 숫자가 찾고자 하는 숫자이면 반복문이 엄청나게 돌아간다. 최종 풀이방법은 mid에 찾고자 하는 숫자가 나와도 이진탐색을 끝내지 않고 계속 나눠주면서 찾고자 하는 숫자의 양쪽 마지막 index를 반환한다. 2번의 이진탐색을 한다 n = int(input()) cards = list(map(int, in..
알고리즘/백준 2021. 3. 16. 18:20
[백준] 1920번 (python 파이썬)

탐색 문제이다. 파이썬의 in을 써서 풀 수 있지만 이분탐색을 이용하여 문제를 풀었다. index를 기준으로 left right를 나웠고 이분탐색의 탐색 종료 조건은 mid 값이 찾으려는 수랑 같으면 return 을 해주고 찾는 값이 없을때 left가 right보다 커질경우 종료한다. while left
알고리즘/백준 2021. 3. 16. 16:44
[백준] 1629번 (python 파이썬)

A를 B번 곱한 수의 C로 나눈 나머지를 구하는 것이다. A, B, C는 모두 2,147,483,647 이하의 자연수다. 즉 반복문으로는 절대 풀수없다. 때문에 분할 정복을 선택하였다. 첫 풀이 a, b, c = map(int, input().split(' ')) def dnc(length): if length == 1: return a if length % 2 == 0: left = dnc(length // 2) return left * left else: left = dnc(length // 2) return left * left * a print(dnc(b)) 이렇게 푸니까 시간초과가 나왔다.. 검색해보니 오버플로우도 시간초과가 나온다고 한다.???음? 생각해보니 a, b모두 엄청 큰 숫자가 들어오..
알고리즘/백준 2021. 3. 15. 22:31
[백준] 2168번 (python 파이썬)

사실 유클리드 호제법에 관련된 문제이다. 위의 그림을 보고 알 수 있는것은 1. 대각선이 꼭지점을 지나가지 않는 직사각형은 x + y -1 대각선이 꼭지점을 지나가는 직사각형은 x + y -1 - (점의 개수) 이다. 2. 점의 개수는 어떻게 구하냐 x, y의 최대공약수 - 1이다 즉 점이 없는 직사각형들은 (x, y의 최대공약수 - 1) 을하면 0이 나오기 때문에 이도 성립한다 1, 2를 종합해보면 x + y - gcd(x, y) 라는 식을 구할 수 있다. x, y = map(int, input().split(' ')) def gcd(a, b): if b > a: a, b = b, a while True: if b == 0: break a, b = b, a % b return a print(x + y ..
알고리즘/백준 2021. 3. 15. 20:51
[백준] 20003번 (python 파이썬)

NTS 코테를 봤다.. 1번문제가 유클리드 호제법을 활용한 문제였다고한다..(생각도 못함..) 생각나서 gcd관련문제를 풀어봤다...ㅜ 분모들의 lcm과 분자들의 gcd를 구하는 문제이다. gcd를 구하는 방법은 유클리드 호제법을 이용하여 구할 수 있다. def gcd(a, b): if b > a: a, b = b, a while True: if b == 0: break a, b = b, a % b return a 이를 통해서 lcm또한 구할 수 있다. def lcm(a, b): return a * b // gcd(a, b) 전체 코드 기약분수는 fractions 함수를 통해서 쉽게 구할 수 있다. import fractions n = int(input()) ups = list() downs = list..
알고리즘/백준 2021. 3. 14. 23:57
[백준] 1780번 (python 파이썬)

NxN행렬을 검사한뒤 일괄된 숫자가 아니면 9등분 하는 문제이다. 9등분한 행렬을 각각 다시 재귀를 돌려서 검사한다. 백준 1021번 문제와 유사한 문제이다. tmdrl5779.tistory.com/100 [백준] 1021번 (python 파이썬) ex) 10 3 2 9 5 2 queue = 1 2 3 4 5 6 7 8 9 10 왼쪽으로 회전 1번 queue = 2 3 4 5 6 7 8 9 10 1 pop 9 queue = 3 4 5 6 7 8 9 10 1 오른쪽으로 회전 3번 queue = 9 10 1 3 4 5 6 7 8 pop 5 queue = 10 1 3 4 5.. tmdrl5779.tistory.com n = int(input()) graph = [list(map(int, input().spli..
알고리즘/백준 2021. 3. 8. 18:22
[백준] 1992번 (python 파이썬)

백준 2630문제와 같은 문제이다. tmdrl5779.tistory.com/101 [백준] 2630번 (python 파이썬) Divide and Conquer에 대한 문제이다. 1. 해당 종이가 일괄된 색이 아니면 4등분을 한다. 2. 4등분된 종이를 다시 검사한다. 1, 2를 일괄된 색일때까지 반복한다. 처음 푼방법 종이를 모든 수에 대해 검사 tmdrl5779.tistory.com 출력부분만 고려하면 된다. n = int(input()) graph = [list(map(int, input())) for _ in range(n)] def dnc(x, y, n): check = graph[x][y] for i in range(x, x + n): for j in range(y, y + n): if chec..
알고리즘/백준 2021. 3. 6. 22:18
이전 Prev 1 2 3 4 5 6 7 8 ··· 12 Next 다음