본문 바로가기
반응형
[코딩 테스트] 11. 심화 자료구조 Index 1. 우선순위 큐와 힙 2. 트리 3. 바이너리 인덱스 트리 4. 참고자료 1. 우선 순위 큐와 힙 우선순위 큐 - 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조 - 데이터를 우선 순위에 따라 처리하고 싶을 때 사용 - 삽입/삭제시 O(logN) - heap 정렬은 O(NlogN) 구현 종류 1) 리스트 이용해 구현 2) heap을 이용해 구현 Heap - 완전 이진 트리 자료구조: root 노드부터 시작하여 왼쪽 자식 노드, 오른쪽 자식 노드 순서대로 데이터가 삽입되는 tree - Heap에서는 항상 root 노드를 제거 - Min Heap / Max Heap 힙 정렬 def heap_sort(iterable): h = [] result = [] for val in iterabl.. 2023. 10. 17.
[알고리즘] 10. 기타 알고리즘 Index 1. 소수 판별 2. 에라토스테네스의 체 3. 투 포인터 4. 구간 합 5. 최소 공통 조상 5. 참고자료 1. 소수 판별 소수(Prime Number) - 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어 떨어지지 않는 자연수 # 시간 복잡도: O(N) def is_prime(x): for i in range(2, x): if x % i == 0: return False return True # 시간 복잡도: O(sqrt(N)) import math def is_prime(x): for i in range(2, int(math.sqrt(x)) + 1): if x % i == 0: return False return True 2. 에라토스테네스의 체 에라토스테네스의 체 - 특.. 2023. 10. 5.
[알고리즘] 9. 기타 그래프 이론 Index 1. 서로소 집합 자료구조 2. 서로소 집합을 활용한 사이클 판별법 3. 최소 신장 트리(크루스칼 알고리즘) 4. 위상 정렬 5. 추천 문제 6. 참고자료 1. 서로소 집합 자료구조 Disjoint Sets - 공통 원소가 없는 두 집합 서로소 집합 자료구조(= Union Find) - 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 - 두 종류의 연산을 지원 - - Union: 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산 - - Find: 특정한 원소가 속한 집합이 어떤 집합인지 - 연결성을 통해 집합의 형태를 확인 (동작 과정) 1) Union 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인 - A와 B의 루크 노드 A', B'를 각각 찾기 - .. 2023. 10. 5.
[알고리즘] 8. 최단 경로 알고리즘 Index 1. 최단 경로 문제 2. 다익스트라 최단 경로 3. 플로이드 워셜 4. 벨만 포드 5. 추천 문제 6. 참고자료 1. 최단 경로 문제 최단 경로 문제 - 가장 짧은 경로를 찾는 알고리즘 - 각 지점은 그래프에서 node로 표현, 지점 간 연결된 도로는 edge로 표현 (최단 경로 유형) - 한 지점에서 다른 한 지점까지의 최단 경로 - 한 지점에서 다른 모든 지점까지의 최단 경로 - 모든 지점에서 다른 모든 지점까지의 최단 경로 2. 다익스트라 최단 경로 Djikstra - 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산 - 음의 간선이 없을 때 정상적으로 동작 - 매 상황에서 방문하지 않은 가장 적은 비용이 드는 노드를 선택(그리디) - 한 단계당 하나의 노드에 대한 최단.. 2023. 10. 5.
[알고리즘] 7. 그래프 탐색 Index 1. 스택과 큐 2. 재귀 3. 유클리드 호제법 4. DFS 5. BFS 6. 추천 문제 7. 참고자료 - Search란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 - 그래프 탐색 알고리즘으로 DFS/BFS가 있음 1. 스택과 큐 Stack - FILO(First In Last Out)의 자료구조 - 입구와 출구가 동일 stack = [] # 삽입 stack.append(val) # 삭제 stack.pop() # 최상단 원소 확인 print(stack[-1]) Queue - FIFO(First In First Out)의 자료구조 - 입구와 출구가 양쪽으로 나있는 터널 형태 queue = [] # 삽입 queue.append(val) # 삭제 queue.pop(0) # 최하단/최상단 원.. 2023. 10. 5.
[알고리즘] 6. 이진 탐색 Index 1. 순차 탐색 2. 이진 탐색 3. 이진 탐색 라이브러리 4. 파라메트릭 서치 5. 추천 문제 6. 참고자료 1. 순차 탐색 순차 탐색(Sequential Search) - 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 2. 이진 탐색 이진 탐색(Binary Search) - 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 - O(log N) (재귀적 구현) def binary_search(arr, target, start, end): if start > end: return None mid = (start + end) // 2 if arr[mid] == target: return mid elif arr[mid] > target: return bin.. 2023. 10. 5.
[알고리즘] 5. 동적 계획법 Index 1. 다이나믹 프로그래밍 2. 추천문제 3. 참고자료 1. 다이나믹 프로그래밍 Dynamic Programming - 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법 - 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않음 - 점화식 : 인접한 항들 사이의 관계식 - Memoization: 한 번 계산한 결과를 메모리 공간에 메모하는 기법(=Caching), - Top-down(메모이제이션) 방식과 Bottom-up 방식이 존재 - Bottom-up 방식을 사용시 결과 저장용 리스트는 DP 테이블 이용 - 분할 정복은 부분 문제의 중복이 없음 (조건) 1) Optimal Substructure(최적 부분 구조) - 큰 문제를 작은 문제로 나눌.. 2023. 10. 5.
[알고리즘] 4. 그리디 && 구현 Index 1. 그리디 2. 구현 3. 추천 문제 4. 참고자료 1. 그리디 Greedy Algorithm - 현재 상황에서 지금 당장 좋은 것만 고르는 방법 - 정당성 분석, 반복적 선택시 최적의해 보존되는지 검토 (Exam) - 거스름 돈: 가장 큰 동전의 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없음 2. 구현 Implementation - 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정(problem->thinking->solution) - 2차원 공간을 다룰 경우 Matirx(행렬)을 사용 - 시뮬레이션 및 완전 탐색의 경우 2차원 공간에서의 방향 벡터가 활용 dx = [0, -1, 0, 1] dy = [1, 0, -1, 0] for i in range.. 2023. 10. 5.
[알고리즘] 3. 정렬 Index 1. 정렬 2. 버블 정렬 3. 삽입 정렬 4. 선택 정렬 5. 퀵 정렬 6. 병합 정렬 7. 계수 정렬 8. 추천 문제 9. 참고자료 1. 정렬 정렬(Sort) - 데이터를 특정한 기준에 따라 순서대로 나열하는 것 2. 버블 정렬 버블 정렬(Bubble Sort) def bubble_sort(arr: list): for i in range(len(arr)): for j in range(len(arr)-1): if (arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] return arr 3. 삽입 정렬 삽입 정렬(Insertion Sort) - 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입 - 선택 정렬에 비해 더 효율적, 데이터가 정렬되.. 2023. 10. 5.
[알고리즘] 2. 코딩테스트를 위한 파이썬 라이브러리 Index 1. 내장 함수 2. itertools 3. heapq 4. bisect 5. collections/math 6. 참고자료 1. 내장 함수 내장 함수 - 기본 입출력 함수부터 정렬 함수까지 기본적인 함수들을 제공 - sum(list), min(list), max(list), eval(문자열 수식), sorted(list, reverse=True, key=lambda x: x[1]) 2. itertools itertools - 반복되는 형태의 데이터를 처리하기 위한 기능 제공 - 순열과 조합 기능 제공 - 순열: 서로 다른 n개에서 서로 다른 r개를 선택하여 일렬로 나열하는 것 - 조합: 서로 다른 n개에서 순서에 상관 없이 서로 다른 r개를 선택하는 것 # 순열 import itertools .. 2023. 10. 5.
반응형

티스토리툴바