본문 바로가기

분류 전체보기443

[백준 24416번] 알고리즘 수업 - 피보나치 수 1 n = int(input()) dp = [0]*41 count_r = 0 count_d = 0 def fib_recursive(n): # 일반적인 재귀함수 피보나치 수열 계산 global count_r if n==1 or n==2: count_r += 1 return 1 else: return fib_recursive(n-1) + fib_recursive(n-2) def fib_dynamic(n): # 동적계획법을 사용한 피보나치 수열 계산 global count_d if n==1 or n==2: if dp[n] == 0: dp[n] = 1 return dp[n] else: if dp[n] != 0: return dp[n] else: count_d += 1 dp[n] = fib_dynamic(n-1) +.. 2023. 2. 28.
[프로그래머스 Lv.3] 정수 삼각형 이번 문제는 Dynamic Programming 문제의 대표적인 예제인 정수 삼각형로, 대각선 방향으로만 움직일 수 있을 때 거쳐간 숫자의 합이 최대가 되도록 만드는 문제이다. 단순하게 완전탐색(DFS/BFS)로 풀 순 있겠지만, 이 문제의 경우 삼각형의 높이가 한 층씩 높아질수록 경우의 수 가 2배씩 늘어나는 문제로 단순히 완전탐색 알고리즘으로 풀게 되면 문제의 조건(높이는 1이상 500이하) 때문에 O(2^n)의 시간복잡도로 인해 시간초과가 발생할 것이다. 따라서 모든 경우의 수를 전부 구하는 완전 탐색이 아니라, 별도의 자료구조에 정보들을 저장하면서 중복된 연산을 최대한 줄여주는 DP 알고리즘을 사용하여 풀어야만 한다. 먼저 이전에 포스팅한 DP 알고리즘에 대한 내용을 복습할 겸 이 문제가 왜 DP.. 2023. 2. 28.
[DP] Dynamic Programming 알고리즘의 개념 및 코드 1) Dynamic Programming 이란 ? Dynamic Programming은 또 다른 자료구조(메모리)에 계산한 정보들을 저장함으로써 중복되는 연산을 줄이고, 이로써 프로그램의 수행 속도를 개선하는 알고리즘이다. DP는 완전 탐색(BFS, DFS)과 같이 수많은 경우의 수를 따져보아야 할 때, 경우의 수가 수없이 많을 때 메모리 공간을 사용하여 수행시간을 단축시키는 알고리즘이다. 여러 개의 작은 문제들을 먼저 푼 후에 그 결과를 바탕으로 더 큰 문제를 해결하는 알고리즘으로, 한번 계산한 문제는 다시 계산하지 않도록 메모리에 저장하고, 필요한 경우 다시 계산하지 않고 저장된 값을 사용한다.(매 순간 최적의 값을 저장함) 쉽게 설명하면 문제를 해결하기 위한 점화식을 찾아낸 후 점화식의 항을 밑에서.. 2023. 2. 27.
[React] 상태관리 라이브러리 Recoil에 대해 알아보자 0) Recoil 이란 ? Recoil은 React 프로젝트를 위한 많은 전역 상태관리 라이브러리들 중 하나로, 2020년 5월 Facebook에서 출시하였습니다. 그렇기에, 다른 라이브러리(Redux, Mobx)와는 달리 React 전용이며 React에 최적화되어 있다고 할 수 있습니다. Recoil을 통해 전역 상태를 관리하면 코드가 굉장히 간결해지는데, 기존의 context API는 전역 상태를 전달할 때 객체 형태의 value를 사용하기 때문에 객체 안의 값이 하나라도 변경되면 provider로 감싼 모든 하위 컴포넌트들이 리렌더링된다는 단점이 있습니다. Recoil의 경우 각각의 전역 상태에 대한 atom이 생성되고 해당 상태를 구독하는 구성 요소만 리렌더링 됩니다. 따라서 불필요한 리렌더링을 .. 2023. 2. 24.
[백준 13305번] 주유소 import sys input = sys.stdin.readline # n 입력받기 n = int(input()) # 총 비용 total = 0 # n-1개의 거리를 저장하는 리스트 distance = list(map(int,input().split())) # 주유소의 리터당 가격을 저장하는 리스트 price = list(map(int,input().split())) # 남은 거리 수 remain = sum(distance) # 현재 최소 거리 min_price = price[0] # 현재 누적된 거리 sum_distance = distance[0] for i in range(n-1): if i == n-2: total += (sum_distance * min_price) break if min_price 2023. 2. 24.
[백준 2108번] 통계학 import sys input = sys.stdin.readline # n 입력받기 n = int(input()) # n개의 값을 저장하는 리스트 array = [0]*n # 빈도수를 저장하는 리스트 count_list = [] # 최빈값 mode = 0 # 입력받기 for i in range(n): array[i] = int(input()) # 중간 인덱스 mid_index = n//2 # 오름차순 정렬 array.sort() # 집합 자료형 사용 set_n = set(array) # 사전 자료형 사용 dictionary = dict() # 사전 자료형에 숫자 '값 : 빈도수(카운팅)' 저장 => 시간복잡도 최소화 for i in array: if i not in dictionary: dictionar.. 2023. 2. 24.

티스토리툴바