반응형 알고리즘19 분할정복을 이용한 거듭제곱 계산 알고리즘 분할정복을 이용해서 거듭제곱을 계산하면 연산횟수 감소를 통해서 시간 기하급수적으로 시간을 단축시킬 수 있습니다. 아이디어는 다음과 같습니다. 점화식 및 코드 C의 n승은 지수법칙에 의해서 다음과 같은 점화식으로 바꿀 수 있습니다. 위는 n이 짝수일 때의, 아래는 n이 홀수일 때 점화식입니다. 위의 점화식을 파이썬 코드로 표현하면 다음과 같습니다. def divideConquer(base, exp): if exp == 0: # 지수가 0인 경우 return 1 if exp % 2: half = divideConquer(base, (exp - 1) // 2) result = (half * half * base) else: half = divideConquer(base, exp // 2) result = (h.. 2023. 6. 6. 동적 프로그래밍(Dynamic Programming) 동적 프로그래밍은 메모리에 이미 계산된 결과를 저장하여 효율성을 향상하는 기법입니다. 이게 왜 Dynamic과 어떤 관계가 있길래 dynamic이라는 이름이 붙었냐면.. 그냥 이름이 멋있어서 붙였다고 합니다(...) 조건 동적 프로그래밍을 사용하기 위해서는 최적 부분 구조와 중복되는 부분 문제라는 2가지 조건을 만족시켜야 합니다. 최적 부분 구조: 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 정답을 모아서 큰 문제 해결 가능 중복되는 부분 문제: 동일한 작은 문제를 반복적으로 해결해야 함. 이 두가지 조건을 만족시키는 가장 대표적인 예시가 바로 피보나치입니다. 메모이제이션 DP는 메모이제이션이라는 기법을 사용합니다. 메모라는 워딩에서 알 수 있듯이 한 번 계산한 결과를 메모리에 저장해 두었다가 .. 2023. 6. 6. [프로그래머스 LV2] 연속된 부분 수열의 합 이번에 풀어본 문제는 연속된 부분 수열의 합이라는 문제입니다. 아래는 해당 문제에 대한 설명입니다. 문제 설명 비내림차순으로 정렬된 수열이 주어질 때, 다음 조건을 만족하는 부분 수열을 찾으려고 합니다. 기존 수열에서 임의의 두 인덱스의 원소와 그 사이의 원소를 모두 포함하는 부분 수열이어야 합니다. 부분 수열의 합은 k입니다. 합이 k인 부분 수열이 여러 개인 경우 길이가 짧은 수열을 찾습니다. 길이가 짧은 수열이 여러 개인 경우 앞쪽(시작 인덱스가 작은)에 나오는 수열을 찾습니다. 수열을 나타내는 정수 배열 sequence와 부분 수열의 합을 나타내는 정수 k가 매개변수로 주어질 때, 위 조건을 만족하는 부분 수열의 시작 인덱스와 마지막 인덱스를 배열에 담아 return 하는 solution 함수를 .. 2023. 5. 7. [프로그래머스 LV2] 두 원 사이의 정수쌍 이번 문제는 좌표평면 위의 원이 두 개가 주어지고, 해당 원 사이의 정수쌍인 좌표의 개수를 구하는 문제입니다. 처음 봤을 땐 진짜 어이없게 문제를 풀어보았는데, 당연히 틀렸고요. 여러 번 트라이를 한 이후에 풀 수 있었습니다. 그중에서 2가지 풀이를 소개해드리려고 하는데, 첫 풀이는 시간 초과가 나온 풀이법이고, 다음 풀이법은 정답처리된 풀이법입니다. 시간초과 풀이법 시간초과 풀이법은 브루트포스 방식으로 무식하게 풀려고 했습니다, 먼저 코드를 보도록 하겠습니다. for i in range(r2**2): if x**2 + y**2 >= r1**2 and x**2 + y**2 = r1**2 and y > 1: y -= 1 elif (x+1)**2 + y**2 >= r1**2 and x < r2: x += 1.. 2023. 4. 30. 이전 1 2 3 4 5 다음 반응형
