Code_Jins

탑 다운부터 생각하고 그 다음 바텀 업!!피보나치 DP 예제피보나치 수열 점화식F(n)=F(n−1)+F(n−2)탑 다운 : 메모이제이션 활용(Memoization)이미 계산된 값은 저장해 두어 중복 계산을 피한다.피보나치 수열에서는 dp={} 딕셔너리를 활용한다.탑다운 방식은 재귀를 통해 문제를 풀어내기 때문에 계산이 필요한 경우에만 수행됩니다. 하지만 재귀 호출의 오버헤드가 발생할 수 있으므로 호출이 많은 경우에는 비효율적일 수 있습니다.import sysn = sys.stdin.readline()dp={}def fibo(n): if n==0: return 0 if n==1: return 1 if n in dp: return dp[n] ..

카데인 알고리즘배열 내 연속된 부분 배열(subarray) 중에서  가장 최대 합을 찾는 알고리즘이다. DP(Dynamci Programming)를 적용한 방식완탐시 O(N^2) 걸리는 거를 O(N)으로!핵심은 각각의 최대 부분합은 이전 최대 부분합이 반영된 결과값이다. MAX(자기 자신 , 바로 이전의 부분합)  파이썬 코드 및 예제def maxSubArray(nums): max_current = max_global = nums[0] for i in range(1, len(nums)): max_current = max(nums[i], max_current + nums[i]) max_global = max(max_global, max_current) ret..

코드# 부모 경로 구하기def bfs(adj,s): parent = [None for _ in adj] parent[s] = s level = [[s]] while len(level[-2]) > 0: level.append([]) for u in level[-2]: for v in adj[u]: if parent[v] is None: parent[v] = u level[-1].append(v) return parent# 가장 짧은 거리 경로 구하기def unweighted_shortest_path(adj, s, t): parent = ..

신장 트리 (Spanning Tree)그래프 내의 모든 정점을 포함하는 트리그래프의 최소 연결 부분 그래프.최소 연결 : 간선의 수가 가장 적다n개의 정점을 가지는 그래프 = 최소 간선의 수는 n-1개 = n-1개의 간선으로 연결 = 트리 형태DFS, BFS을 이용하여 그래프에서 신장 트리를 찾을 수 있다.탐색 도중에 사용된 간선들을 모음하나의 그래프에는 많은 신장 트리가 존재정점(Vertex) : 모두 포함사이클 : X (트리임)최소 신장 트리(MST)란?가장 간선의 가중치 합이 가장 작은 트리를 의미한다. (최소 비용)MST 사용 사례통신망, 도로망, 유통망에서 길이, 구축 비용, 전송 시간 등을 최소로 구축하려는 경우도로 건설도시들을 모두 연결하면서 도로의 길이가 최소가 되도록 하는 문제전기 회로단..

위상 정렬(Topology Sort)순서가 정해져 있는 작업을 차례로 수행해야 할 때 그 순서를 결정해 주기 위해 사용하는 알고리즘이다.조건으로 해석 sw사관학교 정글을 수료하기 위해 신청을 해야하며 시험과 면접을 통과해야 하고 입소 후 주어진 과제들에 열심히 참여하여야(주100시간 밥먹고 똥싸고 개발만하기) 정글을 수료할 수 있다.위상 정렬 특징사이클이 발생하지 않는 방향 그래프이다.DAG : Direct Acyclic Graph : 사이클이 없는 방향 그래프시작점이 존재해야 한다. (전위차수 0)위상 정렬은 스택이나 큐를 이용한다.시간 복잡도 : O(V+E)위상 정렬 알고리즘 동작 과정진입차수가 0인 노드를 큐에 넣는다.큐가 빌 때까지 다음의 과정을 반복한다.큐에서 원소를 꺼내 해당 노드에서 나가는 ..

셸 정렬단순 삽입 정렬(straight insertion sort) 장점은 살리고 단점은 보완하여 더 빠르게 정렬하는 알고리즘단순 삽입 정렬의 장점과 단점장점 : 이미 정렬을 마쳤거나 정렬이 거의 끝나는 상태에서는 속도가 아주 빠르다.단점 : 삽입할 위치가 멀리 떨어져 있으면 이동 횟수가 많아진다.사용방법 (정렬 시에는 모두 단순 삽입 정렬을 이용)ex) 8개 배열 일 때4-정렬 : 서로 4칸씩 떨어진 원소를 4개 그룹으로 나누어정렬하는 방법2-정렬 : 2칸씩 떨어진 원소를 모두 꺼내 두 그룹으로 나누고 정렬 실행1-정렬 : 정렬 되어 나온것들(3,1,4,2,7,5,8,6) 단순 삽입 정렬로 정렬총 7번의 정렬 실행2개 원소에서 4-정렬 수행 (4그룹, 4번)4개 원소에서 2-정렬 수행 (2그룹, 2번)..

단순 삽입 정렬 (straight insertion sort)주목한 원소보다 더 앞쪽에서 알맞은 위치로 삽입하며 정렬하는 알고리즘단순 선택 정렬과 비슷해 보이지만 다르다단순 선택 정렬은 값이 가장 작은 원소를 선택한다.단순 삽입 정렬은 값이 가장 작은 원소가 아니라 선택된 해당 원소가 있어야할 알맞은 위치를 왼쪽 원소와 비교하며 찾아 삽입한다.장점 : 이미 정렬을 마쳤거나 정렬이 거의 끝나는 상태에서는 속도가 아주 빠르다.단점 : 삽입할 위치가 멀리 떨어져 있으면 이동 횟수가 많아진다."알맞은 위치에 삽입" 과정선택된 해당 원소가 작은 원소를 만날 때까지 이웃한 왼쪽 원소를 하나씩 대입하는 작업을 반복한다.멈춘 위치에 해당 원소 대입종료 조건정렬된 배열의 왼쪽 끝에 도달한 경우tmp보다 작거나 키 값이 ..

단순 선택 정렬(straight selection sort)가장 작은 원소부터 선택해 알맞은 위치로 옮기는 작업을 반복하며 정렬하는 알고리즘이다. li = [5,3,8,1,2,7]n=len(li)for i in range(n-1): # 정렬한 부분에서 가장 작은 원소의 인덱스 min_ = i for j in range(i+1,n): if a[j] 시간복잡도 : O(n^2)

병합(머지) 정렬배열을 앞부분과 뒷부분의 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업을 반복하는 알고리즘이다.분할(리스트의 크기가 1이 될 때까지)과 정복(리스트를 정렬된 상태로 병합)쪼갤 때는 한 개까지!병합 할 때에는 정렬이 된 두 개의 배열을 계속해서 병합!stable 안정적이다.대규모 데이터를 정렬할 때, 안정적인 성능이 요구되는 상황에서 많이 사용된다.시간복잡도O(n logn) = 배열 병합의 시간 복잡도 O(n) x 데이터 원소 수가 n일 때 병합 정렬의 단계는 log n만큼 필요 O(log n) = O(n) x O(log n)두 개(a,b)의 배열을 한 개(c)의 배열로 병합 해보기!a=[2,4,6,8,11,13]b=[1,2,3,4,9,16,21]c=[None]*(len(a)+len(b..

버블 정렬이란? What is bubble sort?이웃한 두 원소의 대소 관계를 비교하여 필요에 따라 교환을 반복하는 알고리즘으로, 단순 교환 정렬이라고도 한다.안정적인 정렬(Stable Sort)이다.그림 1번) 1회전 : 5개의 정렬 아이템들이 있으면 4번만 교환하면 정렬이 완료된다. (n-1번)그림 2번) 2회전 : 3번만 교환하면 정렬이 완료된다 (n-2번)총 n-1번 회전을 돌고 회전이 늘어날 때마다 교환시도 횟수는 1번씩 줄어든다a=[7,4,5,1,3] n = len(a) for i in range(n-1): for j in range(n-1-i): if a[j] > a[j+1]: a[j+1],a[j] = a[j],a[j+1] print(a)패스(pass)정렬하며 ..