Algorithm/알고리즘 이론

이진 탐색 데이터가 정렬되어 있는 상태에서 원하는 값을 찾아내는 알고리즘 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾음 시간 복잡도 $O(logN)$ 💡 이진 탐색 과정 ① 현재 데이터셋의 중앙값(mid)을 선택 ② 중앙값 > 타깃 데이터(mid>target)일 때 중앙값 기준으로 왼쪽 데이터셋을 선택(end=mid-1) ③ 중앙값 target: # target이 중간점보다 작으면 왼쪽부분 탐색 return binary_se..

깊이 우선 탐색(DFS; Depth-First search) 그래프의 시작 노드에서 출발하여 탐색할 한쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘 재귀 함수로 구현 스택 자료구조 이용 시간 복잡도(노드 수: V, 에지수: E) $O(V + E)$ 풀 수 있는 문제: 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 1. DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기 인접 리스트로 그래프 표현하기 방문 리스트 초기화하기 시작 노드 스택에 append()로 삽입하기 2. 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입하기 pop()으로 노드 꺼내기 꺼낸 노드를 탐색 순서에 기입 인접 리스트의 인접 노드를 스택에 삽..

버블 정렬(bubble sort) 두 인접한 데이터의 크기를 비교해 정렬하는 방법 시간 복잡도 $O(N^2)$ 다른 정렬 알고리즘보다 속도가 느린 편 루프를 돌면서 인접한 데이터 간의 swap 연산으로 데이터 정렬 💡 버블 정렬 과정 ① 비교 연산이 필요한 루프 범위 설정 ② 인접한 데이터 값을 비교 ③ swap 조건에 부합하면 swap 연산을 수행 ④ 루프 범위가 끝날 때까지 ②~③을 반복 ⑤ 정렬 영역을 설정. 다음 루프를 실행할 때는 이 영역을 제외함 ⑥ 비교 대상이 없을 때까지 ①~⑤를 반복 선택 정렬(selection sort) 대상 데이터에서 최대 또는 최소 데이터를 데이터가 나열된 순으로 찾아가며 선택하는 방법 구현 방법이 복잡함 시간 복잡도 $O(N^2)$ 코딩 테스트에서는 많이 사용하지 ..

스택(stack) 삽입과 삭제 연산이 후입선출(LIFO)로 이뤄지는 자료구조 LIFO(Last In Frist Out) 가장 마지막에 삽입된 데이터가 가장 먼저 나오는 구조 삽입과 삭제가 한쪽에서만 일어남 💡 파이썬 스택(stack) 연산 s.append(n): top 위치에 새로운 데이터(n)를 삽입 s.pop(): top 위치에 현재 있는 데이터를 삭제하고 확인 s[-1]: top 위치에 현재 있는 데이터를 단순 확인하는 연산 큐(Queue) 삽입과 삭제 연산이 선입선출(FIFO)로 이뤄지는 자료구조 FIFO(First In First Out) 가장 먼저 삽입된 데이터가 가장 먼저 나오는 구조 삽입과 삭제가 양방향에서 이뤄짐 💡 파이썬 큐(queue) 연산 s.append(n): rear 위치에 새로..

투 포인터 2개의 포인터로 알고리즘의 시간 복잡도를 최적화함 [문제 006] 연속된 자연수의 합 구하기 N의 최댓값이 10,000,000으로 매우 크므로 O(nlogn)의 시간 복잡도 알고리즘을 사용하면 제한 시간을 초과하므로 O(n) 시간 복잡도 알고리즘을 사용해야 함 ⇒ 이런 경우 자주 사용하는 방법이 투 포인터 💡 투 포인터 이동 법칙 sum > N: sum = sum-start_index; start_index++; sum < N: end_index++; sum = sum+end_index; sum = N: end_index++; sum = sum+end_index; count++; start_index를 오른쪽으로 한 칸 이동하는 것은 연속된 자연수에서 왼쪽 값을 삭제하는 것 end_index를..

구간 합 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘 구간 합의 핵심 이론 구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야 함 합 배열 S 정의 S[i] = A[0] + A[1] + A[2] + … + A[i-1] + A[i] # S[i]는 A[0]부터 A[i]까지의 합 인덱스 0 1 2 3 4 5 배열 A 15 13 10 7 3 12 합 배열 S 15 28 38 45 48 60 합 배열 S를 만드는 공식 S[i] = S[i-1] + A[i] i에서 j까지 구간 합을 구하는 공식 S[j] - S[i-1] ex) A[2]부터 A[5]까지의 합 = A[0]부터 A[5]까지의 합 - A[0]부터 A[1]까지의 합 = S[5] - S[1] [문제 003] 구간 합 구하..