![]()
일주일동안 공부했던 알고리즘과 해결했던 문제들을 정리하고 어떤 알고리즘이 약한지 , 어떤 알고리즘이 더 중요하고 필요한지 생각해봐야 할 것 같다. 01. 퀵 정렬 https://spongecake.tistory.com/20 [크래프톤 정글] | 8일 🗒️ Quick sort 이상적인 퀵 정렬의 모습 global a a = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8] def quick(a,start,end): if start >= end : return pl = start + 1 # 피벗 오른쪽 부터 start pr = end # 배열 끝 pivot = start # 피봇 인덱스 while pl spongecake.tistory.com 02. BFS https://spongecake.tistor..
![]()
🕹️ 가운데를 말해요 from sys import stdin as s import heapq leftHeap = [] rightHeap = [] s= open('input.txt','rt') n = int(s.readline()) arr = list(map(int,s.readlines())) for i in range(n): if len(leftHeap) > len(rightHeap): heapq.heappush(rightHeap,arr[i]) else : heapq.heappush(leftHeap,-arr[i]) if len(leftHeap) != 0 and len(rightHeap) != 0 and -leftHeap[0] > rightHeap[0] : left = -hea..
![]()
🗒️ 우선순위 큐 - 큐는 먼저 들어온 데이터가 먼저 처리되는 자료구조이지만, 우선 순위 큐는 우선 순위가 높은 데이터부터 처리하는 자료구조이다. 배열, 연결리스트, 힙으로 모두 구현할 수 있지만 보통 시간복잡도가 적은 힙을 사용한다. 💡 우선순위큐 from queue import PriorityQueue q = PriorityQueue() # 삽입 q.put(3) q.put(2) q.put(1) # 삽입시 우선순위 지정 q.put((5,"banana")) q.put((1,"apple")) q.put((3,"FINE")) # 반환 print(q.get()) # 1 print(q.get()) # 2 print(q.get()) # 3 # 사이즈 print(q.qsize()) # 튜플 값만 print(q.ge..
![]()
👥 이진 탐색 - 배열이 정렬되어 있어야 하며, 하나의 배열에서 반반 쪼깨서 값을 찾는 탐색이다. - 시간 복잡도는 O(logN)이다 이진 탐색의 기본 틀 from sys import stdin as s s = open('input.txt','rt') N, M = list(map(int,s.readline().split())) arr = list(map(int,s.readline().split())) def binary_search(array, target,start,end): if start > end: return None mid = (start + end) //2 if array[mid] == target: return mid elif array[mid] >target: return binary_s..
![]()
18111번 _ 마인크래프트 문제 N, M ,B = list(map(int,s.readline().split())) array = [list(map(int,s.readline().split())) for _ in range(N)] listMax = max(map(max,array)) listMin = min(map(min,array)) result = int(1e9) resultH = 0 for k in range(listMin,listMax+1): ans = 0 block = B for i in range(N): for j in range(M): if array[i][j] > k : ans +=(array[i][j] - k) * 2 block += 1 else: ans +=abs(array[i][j] ..
![]()
🗒️ 시간 복잡도, 공간 복잡도(Big-Oh Notation) - 시간 복잡도에는 O(n) - 시간의 상한(최악의 경우), Ω(n) - 시간의 하한(최선의 경우), Θ(n) - 평균적인 경우 - 시간은 한계치가 명확한 반면 공간은 최근 대용량 시스템이 보편화 되면서, 공간 복잡도 보다는 시간 복잡도가 우선이 된다. 그래서 시간 복잡도가 더 중요하게 생각된다. - 공간 복잡도를 줄이는 방법은 배열의 크기, 동적할당, 재귀호출 수 등으로 줄일 수 있습니다. 🗒️ Quick sort, Insertion sort, merge sort, heap sort - O(n log n) : 퀵 정렬(quick), 힙 정렬(heap), 병합 정렬(merge) - O(n^2) : 삽입 정렬(insertion) Quick so..
