aeightchill

버블 정렬 (Bubble Sort)버블 정렬은 선택 정렬과 유사한 알고리즘으로 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘. 버블 정렬하면 배열의 뒤에서부터 정렬된다.배열의 첫 번째 요소부터 n번째 요소까지 오름차순으로 버블 정렬을 수행하면 해당 범위의 최댓값이 n번째에 위치하게 된다.  배열의 n번째 요소를 정렬하는데 n-1번을 비교하므로 배열의 모든 요소를 정렬하려면 (n-1) + (n-2) + ... + 2 + 1 = n(n-1) / 2 만큼 연산을 수행한다. 시간 복잡도 : O(n^2)  def bubble_sort(arr): for i in range(len(arr)): for j in range(len(arr) - i - 1)..

Dynamic Programming (동적 계획법)Dynamic Programming(DP, 동적 계획법)은 복잡한 문제를 작은 하위 문제로 나누어 해결한 후, 결과를 저장하여 중복 계산을 피하는 최적화 기법→   한 번 계산한 값을 저장해두고, 필요할 때 다시 사용함으로써 연산량을 줄이는 기법  조건DP를 사용하기 위한 조건 1. 최적 부분 구조 (Optimal Substructure)큰 문제를 작은 문제로 나누었을 때, 작은 문제의 최적해를 이용해 큰 문제의 최적해를 구할 수 있어야 한다. 예시)피보나치 수열f(N) = f(N−1) + f(N−2)    →    f(N-1)과 f(N-2)을 구하면 f(N)도 구할 수 있다.2. 중복되는 부분 문제 (Overlapping Subproblems)동일한 작..

우선순위 큐(Priority Queue)우선순위 큐는 가장 중요한(우선순위가 높은) 요소가 먼저 처리되는 자료구조→   일반적인 큐(Queue)는 선입선출(FIFO, First In First Out)→   우선순위 큐는 우선순위가 높은 요소가 먼저 나오는 구조  특징자동 정렬요소를 삽입할 때마다 내부적으로 정렬하고 꺼낼 때 항상 최우선 요소가 반환된다.힙(Heap) 자료구조 활용일반적으로 이진 힙(Binary Heap)을 사용하여 O(logN)의 시간복잡도로 삽입/삭제 가능최소 힙(Min Heap) / 최대 힙(Max Heap)최소 힙(Min Heap, default)  :  값이 작은 요소가 먼저 반환된다.최대 힙(Max Heap)  :  값이 큰 요소가 먼저 반환된다.  Python heapq 모듈..

그리디 알고리즘 (탐욕 알고리즘)그리디 알고리즘은 매 단계에서 가장 최적이라고 판단되는 선택(Local Optimal Solution)을 반복하여 최종적으로 전체 문제의 최적해(Global Optimal Solution)를 구하는 기법→   가장 좋은 선택을 하는 방식으로 동작하며 최적해를 보장하는 경우가 많다.그리디 알고리즘의 조건Greedy Choice Property (탐욕적 선택 속성)현재 단계에서의 최적 선택(전체적인 최적해)이 이후 단계에서도 최적 선택이 되어야 한다.Optimal Substructure (최적 부분 구조)문제를 작은 부분 문제로 나누었을 때, 각 부분 문제의 최적해를 모아서 전체 문제의 최적해를 구성할 수 있어야 한다.예제 1.  거스름돈 문제 (동전 최소 개수)거스름돈을 줄..

Two Pointers리스트에 순차적으로 접근할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘시작점과 끝점 2개의 점으로 접근할 데이터의 범위를 표현할 수 있다. (응용문제) _ 특정한 합을 가지는 부분 연속 수열 찾기문제 설명N개의 자연수로 구성된 수열이 있다.합이 M인 부분 연속 수열의 개수를 구하라수행 시간 제한은 O(N)문제 해결 아이디어시작점(start)과 끝점(end)이 첫 번째 원소의 인덱스(0)를 가리키도록 한다.현재 부분 합이 M과 같다면, 카운트한다.현재 부분 합이 M보다 작다면, end += 1현재 부분 합이 M보다 크거나 같다면, start += 1모든 경우를 확인할 때까지 2번부터 4번 과정을 반복한다.  참고이것이 코딩 테스트다 with Python

DFS 루트 노드 혹은 임의 노드에서 다음 브랜치로 넘어가기 전에, 해당 브랜치를 모두 탐색하는 방법(스택 or 재귀 함수를 통해 구현)가능한 한 깊이 내려가면서 탐색을 진행한다.특정 경로를 찾거나, 그래프의 모든 노드를 방문하는 데 유용하다..def dfs(graph, v, visited): visited[v] = True for i in graph[v]: if not visited[i]: dfs(graph, i, visited)visited = [False] * ndfs(graph, 1, visited)BFS 루트 노드 혹은 임의 노드에서 인접한 노드부터 먼저 탐색하는 방법인접한 노드를 먼저 탐색한다.최단 경로를 찾는 데 유용하다.def bfs(graph, start, visited): queu..

Disjoint Set(서로소 집합)은 서로 겹치는 요소가 없는 집합들을 저장하고 관리하는 자료구조.주로 Union-Find 알고리즘을 사용하여 구현하며, 아래와 같은 작업들을 지원Union(합집합 연산): 두 개의 서로소 집합을 하나의 집합으로 합친다.Find(대표자 찾기 연산): 특정 원소가 속한 집합의 대표자를 찾는다.같은 집합 여부 확인: 두 원소가 같은 집합에 속해 있는지 확인한다. (대표자가 동일한지 확인)예제사람들 간의 친구 관계를 관리하는 시스템새로운 친구 관계 추가: x가 y의 친구가 된다. (집합에 새로운 요소 추가)특정 두 사람이 직접적 또는 간접적으로 친구인지 확인한다.예시a, b, c, d, e, f, g, h, i, j 총 10명의 사람이 있다고 가정한다. 다음과 같은 친구 관계..