본문 바로가기
◀ PREV [1] NEXT ▶
코드 외워야될거 dfs, bfs, 크루스칼, 프림, 다잌 DFS for i in range(m) : a, b = map(int, input().split()) arr[a].append(b) arr[b].append(a) print(f"연결된 간선 정보 \n{arr[1:]}") def dfs(v): visited[v] = True print(v, ' ', end = '') for i in arr[v]: if not visited[i]: dfs(i) BFS def bfs(node): queue = [] visited[i] = 1 queue.append(i) while len(queue) != 0: v = queue.pop(0) print(v) for i in adj_list[v]: if not visited[i]: visi.. 2023. 12. 7.
컴알 기말시험대비 퀵정렬 상향식 이 코드 + 아이패드에 정리하면서 돌려보기 처음에 create heap을 잘 만들어두면 downheap 하기는 쉽다 def downheap(i, size): # print(i) while i*2 = a[k]: break # print(i, k) a[i], a[k] = a[k], a[i] i = k print('다운 힙 : \t', end=' ') print(a[1:]) def create_heap(a): hsize = len(a) - 1 # print("현재 힙 사이즈", hsize) for i in reversed(range(1,hsize//2+1)): # print("현재 i 인덱스", i) downheap(i,hsize) def heap_sort(a): N = len(a) - 1 fo.. 2023. 12. 4.
컴알 14주차 시험내는거 중간 절반 힙정렬 - 제자리정렬(상향식 정렬), 삽입식이 아니라 상향식이다 루트를 삭제하고 힙 속성을 복원하는 것 까지가 한 단계이다 퀵정렬 - 비균등, 시작값과 high 값을 교환한다! avl 인접리스트, 인접행렬로 각각 탐색하는거 인접 행렬은 배열 형태라서 인덱스가 작은 정점부터 돈다 인접리스트는 오름차순, 내림차순 두개 다 된다 실습문제로 푼 문제 다시보기 dfs, bfs는 탐색 결과만 내기 크루스칼 - 최종값만 동일한 가중치가 있을때는 인덱스가 작은 정점 부터 방문, 최종 결과를 물어본다 프림 - 중간 과정도 필요하다 접근을 시작하는 임의의 정점을 주고 연결이 어떻게 되는지, 가중치가 같으면 인덱스가 작은 정점부터 방문 다익스트라자 - 중간 과정도 필요하다 최단거리, 최단 경로가 잇으면.. 2023. 12. 1.
컴알 13주차 최소신장트리 - 무방향 가중치 그래프 끊어지거나 포함안되는 노드가 없음 크루스칼 유니온 - 파인드를 통해서 서로소 집합, 부모를 찾아서 하는 연산 크루스칼 - 회차가 일어나지 않게 모든 정점을 연결한다 정점 0,1은 9의 가중치를 가지는 간선으로 연결 프림 최소가중치, 트리에 연결된 간선의 가중치로 가중치를 계속 갱신하면서 정점을 추가 양방향으로 연결되있다 0번 정점과 1번 정점의 간선은 가중치 9 0번 정점과 2번 정점의 간선은 가중치 10으로 연결 다른 정점들도 이런 식으로 연결되었다 코드에서는 정점의 갯수만큼 루프를 돌면서 방문하지 않은 가중치가 가장 작은 정점을 찾아서 방문하고 방문한 정점과 인접한 정점(리스트에 들어있는 정점)의 가중치를 갱신한다 시험에서는 코드x, 임의의 시작정점을 주고 최소신.. 2023. 11. 24.
10주차 기말에 힙, 퀵, avl 59, 78, 65, 23, 7, 25, 52, 49, 99, 80 10개를 순차적으로 넣을 때 avl 트리 만드는 과정 • DFS 인접 리스트를 이용한 dfs 탐색 adj_list = [[2, 1], [3, 0], [3, 0], [9, 8, 2, 1], [5], [7, 6, 4], [7, 5], [6, 5], [3], [3]] n = len(adj_list) visited = [0] * n def dfs(v): visited[v] = 1 print(v,' ', end = ' ') for i in adj_list[v]: if visited[i] == 0: dfs(i) print("dfs") for i in range(n): if visited[i] == 0: dfs(i) 0~9 .. 2023. 11. 10.
컴알 시험대비 1. 삽입정렬 알고리즘 코드 빈칸문제로 나온다 while 루프 버전 def insertion_sort(a) : n = len(a) for i in range(1,n): j = i -1; key = a[i] while j >= 0 and a[j] > key : a[j+1] = a[j] j -= 1 a[j+1] = key for 루프 버전 def insertion_sort(a) : n = len(a) for i in range(1,n): for j in range(i,0,-1): if a[j-1] > a[j]: a[j-1], a[j] = a[j], a[j-1] 쉘 정렬 4,2,7,1,9 리스트를 나눌 간격인 갭은 전체 리스트 길이 5 // 2 +1인 3으로 시작한다 {4,1}, {2,9}의 부분 리스트를 부.. 2023. 10. 27.
컴알 시험 1220 자료구조 객관식, 알고리즘 주관식 시험문제 알고리즘 수행시간 비교 안나옴 빅오는 안봐도 될듯 알고리즘 이론, 빈칸채우기, 쉘,퀵,힙 정렬 = gap and a[ j] < a[ j-gap]: #삽입 위치를 찾음 a[ j], a[ j-gap] = a[ j-gap], a[ j] #항목 이동 j -= gap print(' Gap =', gap, a) gap = gap//2 data = [5, 3, 8, 4, 9, 1, 6, 2, 7] print("Original :", data) shell_sort(data) print(" Shell :", data) 힙정렬 (파이썬의 힙은 최소힙이다) 힙정렬은 이진힙을 이용해서 하는 정렬이다 완전이진트리 : 모든 레벨의 노드가 채워져있고 마지막 레벨은 왼쪽부터 차있어.. 2023. 10. 20.
컴알 7주차 이진탐색트리 - 각 노드 n의 키가 n의 왼쪽 서브트리에 있는 키들보다 크고, n의 오른쪽 서브트리에 있는 키들보다 작다. 꼭 자식이 2개여야지만 이진탐색 트리인 것은 아니다 노드를 생성할때는 키와 밸류만 가지고 lt와 rt는 none 상태로 초기화하고 삽입 연산을 통해서 이진탐색트리 탐색, 삽입, 삭제 연산 이진탐색트리 순회 전위순회 - 루트부터 방문해서 맨 처음 나오는게 루트 class Node: def __init__(self, key, value, left = None, right = None): self.key = key self.value = value self.left = left self.right = right class BST: def __init__(self): self.root = .. 2023. 10. 13.
컴알 시험대비 삽입, 삭제, 선택정렬은 실습 쉘, 퀵, 힙 정렬은 코드 선택정렬 - 2중 for문 인덱스 기억해서 마지막에 스왑 삽입정렬 - 1번부터 시작하는 i for문, j = i-1로 지정하고 while루프를 j가 0보다 작아지거나 j값이 key값 보다 클때까지 돌면서 값을 한칸씩 뒤로 민다, 마지막에 arr[j+1] = key 버블정렬 i for문은 i 길이만큼 j for문은 len(arr)-i-1로 n-1부터 한칸씩 줄여가면서 돈다, 최적화를 위해 arr[j]와 arr[j+1]이 바뀌지 않으면 바로 종료한다 선택정렬 항상 n**2 삽입정렬 - 역순정렬시 최악 버블정렬 - 역순정렬시 최악 쉘정렬 홀수 gap, j = i하고 반복문 돌면서 j -= gap, 반복문을 다 돌면 gap // 2 해주기 def shel.. 2023. 10. 9.
5주차 5주차 퀵정렬 - 교차되면 멈추고, 피벗과 H 값 스왑, 정렬된 배열의 경우에는 최악 퀵정렬과 셀정렬은 시험에 나올지도? 6주차 탐색 이진 탐색 - 재귀 def binarySearch(arr, key, lt, rt): if lt 2023. 10. 6.
4주차 이진힙 : 완전이진트리 + 부모의 우선순위가 자식의 우선순위보다 높음 최대힙 : 내림차순, 최소힙 : 오름차순 힙 정렬 책에 나온 코드가 좀 복잡해서 gpt 돌린 코드로 이해해보자 def heapify(arr, n, i): largest = i left = 2*i right = 2*i+1 if left arr[largest]: largest = left if right arr[largest]: largest = right if largest != i : arr[i], arr[largest] = arr[largest], arr[i] heapify(arr,n,largest) def heap_sort(arr): n = len(arr) #처음에 최소 힙 만들어주기 for i in range (n // 2, 0,.. 2023. 9. 22.
3주차 문자열 포맷팅 - f스트링 쉘정렬 간격을 나눠서 부분적으로 삽입 정렬, 간격을 홀수로 해 주고 정렬한다 def shell_sort(a) : n = len(a) gap = n // 2 while gap >= 1 : if (gap % 2) == 0 : gap += 1 for i in range(gap, n) : j=i while j >= gap and a[ j] < a[ j-gap]: #삽입 위치를 찾음 a[ j], a[ j-gap] = a[ j-gap], a[ j] #항목 이동 j -= gap # print(' Gap=', gap, a) gap = gap//2 a = [5, 3, 8, 4, 9, 1, 6, 2, 7] print("Original :", a) shell_sort(a) print("Shell .. 2023. 9. 15.
재귀, 정렬 알고리즘 하노이탑 def hanoi(n,fr,tmp,to): if n == 1: print("원반 1을 %s에서 %s로" %(fr, to)) else: #n-1개를 시작점에서 임시 지점으로 옮기기 hanoi(n-1,fr,to,tmp) #남은 1개를 목적지로 print("원판 %d를 %s에서 %s로"%(n,fr,to)) #임시 지점에 있는 n-1개를 목적지로 hanoi(n-1,tmp,fr,to) hanoi(4, 'A', 'B', 'C') 거듭제곱 def pow(x,n): if n == 0 : return 1; elif n % 2 == 0: return pow(x*x, n//2) else: return x*pow(x*x, (n-1)//2) print(pow(2,4)) print(pow(2,5)) 피보나치 순환 def.. 2023. 9. 8.

티스토리툴바