Algorithm/자료구조, 알고리즘34 [코딩 + 알고리즘 완주반] 19일차. 그래프 이해와 자료구조 # 그래프 실제 세계의 현상이나 사물을 정점( 또는 노드)와 간선으로 표현 # 그래프 관련 용어 노드 (Node) : 정점(Vertex) , 위치 간선 (Edge) : 위치 간의 관계를 표시한 선으로 노드를 연결한 선 (link 또는 branch) 인접 정점 (Adjacent Vertex) : 간선으로 직접 연결된 정점 (또는 노드) 정점의 차수(Degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수 진입 차수(In-Degree) : 방향그래프에서 외부에서 오는 간선의 수 진출 차수(Out-Degree) : 방향 그래프에서 외부로 향하는 간선의 수 경로 길이 (Path Length) : 경로를 구성하기 위해 사용된 간선의 수 단순 경로(Simple Path) : 처음 정점과 끝 정점을 제외하.. 2021. 4. 5. [코딩 + 알고리즘 완주반] 19일차. 이진탐색( Binary Search ), 순차탐색 ( Sequential Search ) # 이진 탐색 탐색할 자료를 둘로 나누어 해당 데이터가 있을만한 곳을 탐색하는 방법 # 분할 정복 알고리즘 divide : 문제를 하나 또는 둘 이상으로 나눈다 conquer : 나눠진 문제가 충분히 작고 해결이 가능하다면 해결하고, 그렇지 않으면 다시 나눈다 # 이진탐색 divide : 리스트를 두 개의 서브 리스트로 나눈다 conquer : 검색할 숫자 > 중간값이면 뒷부분의 서브 리스트에서 검색할 숫자를 찾는다 검색할 숫자 < 중간값이면 앞부분의 서브 리스트에서 검색할 숫자를 찾는다 # 알고리즘 구현 def binary_search(data, search): print (data) if len(data) == 1 and search == data[0]: return True if len(data) .. 2021. 4. 5. [코딩 + 알고리즘 완주반] 18일차. 병합정렬 (merge sort) # 병합 정렬 재귀 용법을 사용한 정렬 알고리즘 리스트를 반으로 잘라 나눈 후 재귀적으로 병합 정렬 부분 리스트를 다시 하나의 정렬된 리스트로 합병 # 알고리즘 구현 # 병합하기 def merge(left,right): lp = 0 rp = 0 merged=list() # left,right 둘다 데이터 있을 때 while len(left) >lp and len(right) >rp : if left[lp]>right[rp]: merged.append(right[rp]) rp+=1 else: merged.append(left[lp]) lp+=1 # left에만 데이터 남아있을 때 while len(left) > lp : merged.append(left[lp]) lp+=1 # right에만 데이터 남아있을.. 2021. 4. 4. [코딩 + 알고리즘 완주반] 18일차. 퀵 정렬 # 퀵 정렬 기준점을 정해서 기준점보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽으로 모으는 함수 작성 각 왼쪽, 오른쪽은 재귀 용법을 사용해서 반복 return qsort(left) + [pivot] + qsort(right) #퀵 정렬 구현 def qsort(data): if len(data) data[index]: left.append(data[index]) else: right.append(data[index]) return qsort(left) + [pivot] + qsort(right) # 리스트 컴프리헨션 사용 def qsort(data): if len(data) item ] right = [ item for item in data[1:] if pivot 2021. 4. 4. [코딩 + 알고리즘 완주반] 17일차. 재귀용법, 동적계획법과 분할정복 # 재귀 용법 함수 안에서 동일한 함수를 호출 # 일반적인 형태 # 일반적인 형태1 def function(입력): if 입력 > 일정값: # 입력이 일정 값 이상이면 return function(입력 - 1) # 입력보다 작은 값 else: return 일정값, 입력값, 또는 특정값 # 재귀 호출 종료 # 일반적인 형태2 def function(입력): if 입력 2021. 3. 31. [코딩 + 알고리즘 완주반] 16일차. 정렬 알고리즘(버블 정렬, 선택 정렬, 삽입 정렬,공간복잡도) # 정렬 어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 것 # 버블 정렬 두 인접한 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 정렬 알고리즘 큰 숫자를 뒤로 보내기 def bubblesort(data): for index in range(len(data) - 1): swap = False for index2 in range(len(data) - index - 1): # 한번 실행할 때마다 뒤에 하나씩 정렬됨- index 뺀 횟수만큼 실행 if data[index2] > data[index2 + 1]: data[index2], data[index2 + 1] = data[index2 + 1], data[index2] swap = True if swap ==.. 2021. 3. 30. 이전 1 2 3 4 5 6 다음 반응형