얄루의 개발일기🥑

(이코테 2021 강의 몰아보기) 6. 다이나믹 프로그래밍 [한빛미디어] 이것이 취업을 위한 코딩 테스트다 with 파이썬 (나동빈 저) 이 영상은 라이브 강의 때 진행했던 내용을 보완하여 1080 HD로 재녹화한 버전이며, 타임라인은 다음과 같습니다. 28강: 다 youtu.be #DP 테이블의 값을 갱신한다고 생각하고 진행한다. #개미 전사 n = int(input()) #식량창고의 개수 array = list(map(int,input().split())) #식량창소에 저장된 식량의 개수 K #dp 테이블 초기화 d = [0] * 100 #다이나믹 프로그래밍 진행(보텀업) d[0] = array[0] d[1] = max(array[0], array[1]) for i in range(2, n): d[i..

다이나믹 프로그래밍 - 다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다. - 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. - 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(탑다운 보텀업)으로 구성된다. / 하향식, 상향식(보텀업) 알고리즘에서 사용되는 다이나믹 프로그래밍에서 다이나믹은 별다른 의미 없이 사용된 단어이다. 1. 최적 부분 구조(Optimal Substructure) - 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다. 2 중복되는 부분 문제(Overlapping Subproblem) - 동일한 작은 문제를 반복적으로 해결해야 한다. - 앞에 있는 ..

https://youtu.be/94RC-DsGMLo?list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&t=750 - 필요한 떡의 크기이상의 값을 얻을 땐 모두 결과를 저장. # 떡볶이 떡 만들기 n, m = map(int,input().split()) # n=떡의 개수 / m=떡의 길이 array = list(map(int,input().split())) start = 0 end = max(array) #젤 큰 값이 끝값 result = 0 while(start mid: total += i-mid # 떡의 양이 부족한 경우 더 많이 짜르기(왼쪽 부분 탐색) if total < m: end = mid - 1 # 떡의 양이 충분한 경우 덜 자르기(오른쪽 부분 탐색) else: resul..

이진 탐색 알고리즘이란? 정렬되어 있는 리스트에서 특정한 데이터를 빠르게 탐색할 수 있게 해주는 탐색 알고리즘이다. - 기본적으로 별다른 말이 없다면 순차 탐색을 이용한다고 본다. - 이진 탐색은 정렬되어 있는 리스트에서 절반씩 범위를 줄여가며 데이터를 탐색하는 방법으로 빠르게(=시간 복잡도가 낮다) 진행 가능하다. - index[0] 시작점 - index[4] 중간점 - index[9] 끝점 #이진 탐색 소스코드 구현( 재귀 함수를 이용해서 ) def binary_search(array,target,start,end): if start > end: return None mid = start + end // 2 #중간점 #찾고자하는 값이 중간값일 경우 if array[mid] == target: retu..

#두 배열의 원소 교체 n, k = map(int,input().split()) a = list(map(int,input().split())) b = list(map(int,input().split())) a.sort() #오름차순 정렬수행 b.sort(reverse = True) #내림차순 정렬수행 #첫 번째 인덱스부터 확인하며, 두 배열의 원소를 최대 K번 비교 for i in range(k): if a[i] < b[i]: a[i], b[i] = b[i], a[i] else: break print(sum(a)) # 배열 A의 모든 원소의 합을 출력

선택 정렬(Selection sorting) 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 정렬법이다. array = [7,5,9,0,3,1,6,2,4,8] for i in range(len(array)): #i는 매번 앞쪽으로 보내는 맨 앞의 자리라고 생각하면 min_index = i #가장 작은 원소의 인덱스. for j in range(i+1,len(array)): if array[min_index] > array[j]: min_index = j array[i],array[min_index] = array[min_index],array[i] #스왑 print(array) 삽입 정렬(Insertion sorting) 처리되지 않은 데이터를 하나씩 골라 적절한 위..

https://youtu.be/7C9RgOcvkvo?list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&t=2563 - 연결 문제 찾기 #DFS로 특정 노드를 방문하고 연결된 모든 노드들도 방문 def DFS(x,y): #주어진 범위를 벗어나는 경우에는 즉시 종료 if x=n or y=m: return False #현재 노드를 아직 방문하지 않았다면 if graph[x][y] == 0: #해당 노드 방문 처리해주기 graph[x][y] = 1 #상하좌우 위치들도 모두 재귀적으로 호출 DFS(x-1, y) DFS(x,y-1) DFS(x+1, y) DFS(x,y+1) return True return False n,m = map(int,input().split()) #2차원 리스트의 맵 ..

https://youtu.be/7C9RgOcvkvo?list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&t=2113 - 큐 자료구조를 이용한다는 것이 특징이다. - 인접 노드를 한 번에 큐에 넣고 방문처리 한다는 것이 너비 우선 탐색 BFS의 특징이다. - 특정 조건에서의 최단경로를 찾는 방법에서 가장 효과적으로 쓰이는 알고리즘이다. - 무방향 그래프 Step 1 시작 노드인 1을 큐에 삽입하고 방문 처리를 한다. Step 2 큐에서 노드 1을 꺼내 방문하지 않은 인접 노드 2, 3, 8을 큐에 삽입하고 방문 처리 한다. Step 3 큐에서 노드 2를 꺼내 방문하지 않은 인접 노드 7(1은 이미 방문했기 때문에 방문하지 않는다.)을 큐에 삽입하고 방문 처리 한다. from collec..

https://youtu.be/7C9RgOcvkvo?list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&t=1585 - 무방향 그래프 - 그래프에서는 대부분 번호가 낮은 인접 노드부터 시작한다는 것이 많다. 1 -> 2 -> 7 -> (6 or 8)일 때 가장 깊은 6 -> 다른 노드가 없기 때문에 노드 6을 꺼내주면 된다. -> 8 -> 3 -> 4 -> 5 #DFS def dfs(graph,v,visited): #현재 노드를 방문 처리 visited[v] = True print(v,end=' ') #현재 노드와 연결된 다른 노드를 재귀적으로 방문 for i in graph[v]: if not visited[i]: dfs(graph, i, visited) # 각 노드가 연결된 정보를..

https://youtu.be/7C9RgOcvkvo?list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&t=831 def recursive_function(): print('재귀 함수를 호출합니다.') recursive_function() recursive_function() - 이런 경우 오류가 난다. 한정된 크기만큼의 자원을 가지고 있는 컴퓨터에 계속해서 메모리를 쌓아 올리는 경우와 같기 때문이다. - 재귀에는 제한이 꼭 필요하다. 그 방법은 종료조건을 넣어주어 프로그램이 정해진 값을 반환해줄 수 있게 해야 한다. #종료 조건을 명시한 재귀 함수 def recursive_function(i): #100번째 호출을 했을 때 종료되도록 종료 조건 명시 if i == 100: retur..