- [ 공부/알고리즘 ][알고리즘] 그리디 알고리즘2024-01-12 09:49:14그리디 알고리즘 Greedy 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 중 최선이라고 가정하는 알고리즘 단점으로 최적의 해를 보장하지 않는다. 그리디 동작 ① 현재 상태에서 가장 최선이라고 생각되는 해를 선택(해 선택) ② 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사(적절성 검사) ③ 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사, 전체 문제를 해결하지 못한다면 1번부터 다시 반복 관련 문제 보기 백준 11047번 동전 0 백준 1541번 잃어버린 괄호
- [ 공부/알고리즘 ][알고리즘] 이진탐색2023-12-29 09:12:51이진탐색 Binary search 데이터가 정렬되어 있는 상태에서 원하는 데이터를 탐색할 때 사용하는 가장 일반적인 알고리즘 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는다 O(logN) 시간 복잡도를 가진다 이진 탐색 동작 # 정렬 기준 오름차순 ① 현재 데이터셋의 중앙값을 선택 ② 중앙값 > 타깃 데이터 → 중앙값 기준으로 왼쪽 데이터셋 선택 ③ 중앙값 < 타깃 데이터 → 중앙값 기준으로 오른쪽 데이터셋 선택 ④ 1~3 과정을 반복하다가 중앙값 == 타깃 데이터일 때 탐색 종료 → 정렬 기준이 내림차순일 땐 2~3번 조건 반대로 실행 N개의 데이터에서 log(N)번의 연산으로 원하는 데이터의 위치를 찾을 수 있다 관련 문제보기 백준 1920번 수 찾기
- [ 공부/알고리즘 ][알고리즘] BFS 너비 우선 탐색2023-12-27 16:06:28너비 우선 탐색 Breadth-First Search 그래프를 완전 탐색하는 방법 중 하나 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘 FIFO 선입선출 방식으로 탐색하므로 Queue 자료구조 이용하는 특징을 가지고 있다 O(노드 수 V + 에지 수 E)의 시간 복잡도를 가진다 탐색 시작 노드와 가까운 노드를 우선하여 탐색하므로 목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장 BFS 동작 방문했던 노드는 다시 방문하지 않으므로 방문한 노드를 체크하기 위한 배열 필요 그래프를 인접 리스트로 표현 탐색을 위해 스택이 아닌 큐를 사용 1. BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화 BFS를 위해 필요한 초기 작업 인접 리스트로 그래프 표현..
- [ 공부/알고리즘 ][알고리즘] DFS 깊이 우선 탐색2023-12-26 17:57:15깊이 우선 탐색 Depth-First Search 그래프의 모든 노트를 탐색하는 그래프 완전 탐색 기법 중 하나 그래프 시작 노드에서 출발하여 탐색할 한쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘 재귀함수 구현, 스택 자료 구조 이용하는 특징을 가지고 있다 O(노드 수 + 엣지 수)의 시간 복잡도를 가진다 유의할 점은 실제 구현 시 재귀함수를 이용하므로 스택 오버플로에 유의해야 한다 DFS 동작 한 번 방문한 노드를 다시 방문하면 안 되므로 노드 방문 여부를 체크할 배열이 필요함 그래프는 인접 행렬이나 인접 리스트로 표현, 대부분 인접 리스트로 표현 1. DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화 DFS를 위해 필요한 초기 작업 인접..
- [ 공부/알고리즘 ][알고리즘] 퀵 정렬2023-12-25 09:58:03퀵 정렬 기준값 pivot을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬하는 알고리즘 기준값이 어떻게 선정되는지가 시간복잡도에 많은 영향을 미치고 평균 시간복잡도는 O(nlogn)이며 최악의 경우 O(n^2) 퀵 정렬 과정 기준값을 중심으로 계속 데이터를 2개의 집합으로 나누면서 정렬하는 것이 핵심 쿽 정렬의 시간 복잡도는 비교적 준수한 편 데이터를 분할하는 pivot을 설정 pivot을 기준으로 데이터를 2개의 집합으로 분리 start가 pivot보다 작으면 start를 오른쪽으로 1칸 이동 end가 pivot보다 크면 end를 왼쪽으로 1칸 이동 start가 pivot보다 크고, end가 pivot보다 작으면 start, end 데이터를 swap하고 start는 오른쪽, ..
- [ 공부/알고리즘 ][알고리즘] 삽입 정렬2023-12-23 11:08:51삽입 정렬 이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방식 O(N^2)로 느린 편이지만 구현하기 쉽다. 삽입 정렬 과정 선택 데이터를 현재 정렬된 데이터 범위 내에서 적절한 위치에 삽입하는 것이 삽입 정렬의 핵심 ① 현재 인덱스에 있는 데이터 값을 선택 ② 현재 선택한 데이터가 정렬된 데이터 범위에 삽입될 위치를 탐색 ▶ 탐색 부분에서 이진트리 등 탐색 알고리즘 사용 시 시간복잡도를 줄일 수 있다 → O(logN) ③ 삽입 위치부터 인덱스까지 shift 연산 수행 ④ 삽입 위치에 현대 선택한 데이터를 삽입하고 인덱스++ ⑤ 전체 데이터의 크기만큼 인덱스가 커질 때까지, 즉 선택할 데이터가 없을 때까지 반복
- [ 공부/알고리즘 ][알고리즘] 선택정렬2023-12-23 10:02:57선택 정렬 대상 데이터에서 최대나 최소 데이터를 데이터가 나열된 순으로 찾아가며 선택하는 방법 구현 방법이 복잡하고 시간복잡도가 O(N^2)로 효율적이지 않음 선택 정렬 과정 최솟값, 최댓값을 찾고 남은 정렬 부분의 가장 앞에 있는 데이터와 swap ① 남은 정렬 부분에서 최솟값 또는 최댓값을 찾는다 ② 남은 정렬 부분에서 가장 앞에 있는 데이터와 선택된 데이터를 swap ③ 가장 앞에 있는 데이터의 위치를 변경해 남은 정렬 부분의 범위를 축소 ④ 전체 데이터 크기만큼 index가 커질 때까지, 즉 남은 정렬 부분이 없을 때까지 반복 선택 정렬 시간복잡도 구하기 선택정렬을 하기 위한 데이터가 n개일 때 n개 탐색 n-1개 탐색 n-2개 탐색 n-3개 탐색 ... n-n개 탐색 ▶ 총 n^2만큼 탐색 관련..
- [ 공부/알고리즘 ][알고리즘] 버블정렬2023-12-23 09:09:36정렬 버블 데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬 선택 대상에서 가장 크거나 작은 데이터를 찾아가 선택을 반복하면서 정렬 삽입 대상을 선택해 정렬된 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬 쿽 pivot값을 선정해 해당 값을 기준으로 정렬 병합 이미 정렬된 부분 집합들을 효율적으로 병합해 전체를 정렬 기수 데이터의 자릿수를 바탕으로 비교해 데이터를 정렬 버블 정렬 두 인접한 데이터의 크기를 비교해 정렬하는 방법 시간 복잡도는 O(n^2) 다른 정렬 알고리즘보다 느린 편 버블 정렬 과정 ① 비교 연산이 필요한 루프 범위를 설정 ② 인접한 데이터 값을 비교 ③ swap 조건에 부합하면 swap ④ 루프 범위가 끝날 때까지 2~3 반복 ⑤ 정렬 영역 설정, 다음 루프..