Computer Science/자료구조, 알고리즘 10

1. 분할 정복(Divide and Conquer)큰 문제를 작은 부분 문제로 분할하고, 각각의 작은 부분 문제를 해결하여 전체 문제의 해답을 구하는 알고리즘문제의 크기가 커서 직접적인 해결이 어려운 경우 유용하다.대표적인 예로, 정렬 알고리즘인 병합 정렬(Merge Sort)과 퀵 정렬(Quick Sort)이 있다. 2. 동작 방식문제를 작은 부분 문제들로 분할한다.분할된 부분 문제들을 각각 재귀적으로 해결한다.부분 문제들의 해답을 결합하여 전체 문제의 해답을 얻는다. 3.  시간 복잡도시간 복잡도는 일반적으로 부분 문제의 개수, 분할된 문제의 크기, 분할과정의 복잡도에 따라 결정된다.대부분의 경우, 분할 정복 알고리즘은 재귀적인 방법으로 문제를 해결하므로, 재귀 호출의 깊이에 따라 시간 복잡도가 결정..

완전 탐색알고리즘에서 사용되는 기법 중 하나로 '모든 가능한 경우의 수를 탐색'하여 '최적의 결과를 찾는 방법'을 의미합니다.💡 미 완전 탐색은 무엇일까?- 모든 경우의 수를 고려하지 더 이상 탐색이 필요 없는 경우 그 루트를 끊어버리는 것을 의미합니다.- 예를 들어서 재귀함수가 함수를 모든 경우의 수를 탐색하다 결과를 찾아서 탐색을 중지하는 경우 루트를 끊는 경우를 자치기(Pruning)라고 합니다. 이를 수행하면 불필요한 탐색을 줄일 수 있습니다.1. 브루트 포스(Brute-Force)난폭한 힘, 폭력 => 무식하지만 확실한 방식을 의미이는 수행하는데 오래걸리는 데다 자원이 많이 소요되지만 이론적으로 가능한 수를 모두 검색하기에 예상된 결과를 얻을 수 있습니다.'모든 경우를 다 탐색'하면서 결과를 ..

1.  이진 탐색이진 탐색은 탐색의 범위를 절반씩 좁혀가며 데이터를 탐색하는 알고리즘입니다. 이진탐색 알고리즘은 리스트 내 데이터가 어느 정도 정렬되어 있어야만 사용 가능하며 데이터가 무작위로 정렬되어 있다면 사용할 수 없습니다. 이진 탐색 알고리즘은 입력 데이터가 많거나(e.g., 1,000만 개 이상) 탐색 범위의 크기가 매우 넓을 때(e.g., 1,000억 이상) 효과적으로 문제를 해결할 수 있습니다.2.  이진 탐색의 동작 과정이진 탐색은 특정 데이터를 찾기 위해 리스트 내 기준점으로서 시작 인덱스, 중간 인덱스, 마지막 인덱스를 사용합니다.  이진 탐색의 동작 순서는 아래와 같습니다. 1️⃣ 시작 인덱스와 마지막 인덱스 사이의 중간 값에서 소수점 이하를 버려 중간 인덱스를 정합니다.2️⃣ 중간 ..

플로이드 워셜플로이드 워셜 알고리즘을 쓰는 문제의 경우, 노드의 개수가 500개 이하일 경우가 많다.하지만 노드가 500개라고 해도 500 * 500 * 500 은 1억이 넘어가기 때문에 시간제한이 넉넉하지 않다면 시간초과에 걸릴 수도 있다.1. 플로이드 워셜 알고리즘 개요모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다.플로이드 워셜(Floyd-Warshall) 알고리즘은 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 알고리즘을 수행한다.다만 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾는 과정이 필요하지 않다.플로이드 워셜은 2차원 테이블에 최단 거리 정보를 저장한다.플로이드 워셜 알고리즘은 다이나믹 프로그래밍 유형에 속한다.2. 플로이드 워셜 알..

최단 경로 문제최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘을 의미한다. cf. 다양한 문제 상황한 지점에서 다른 한 지점까지의 최단 경로한 지점에서 다른 모든 지점까지의 최단 경로모든 지점에서 다른 모든 지점까지의 최단 경로각 지점은 그래프에서 노드로 표현한다.지점 간 연결된 도로는 그래프에서 간선으로 표현한다. 방향그래프 예시 1. 다익스트라 최단 경로 알고리즘 개요특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산한다.다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작한다.현실 세계의 도로(간선)은 음의 간선으로 표현되지 않는다.다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류된다.매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복한다. 2..

DP 다이나믹 프로그래밍은 다음 조건을 만족할 때 사용할 수 있다.최적 부분 구조(Optimal Substructure): 큰 문제를 작은 문제로 나눌 수 있다.중복되는 부분 문제(Overlapping Subproblem): 동일한 작은 문제를 반복적으로 해결한다. DP 예시대표적인 문제로는 피보나치 수열이 있다.(cf. 점화식: 인접항들의 관계식을 의미한다.)// 피보나치 수열1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 ...  * 피보나치 수열의 점화식  단순 재귀를 통한 피보나치 수열 구현* [Python] 단순 재귀를 통한 피보나치 수열# 피보나치 함수를 재귀함수로 구현def fibo(x): if x == 1 or x == 2: return 1 return fib..

알고리즘을 풀면서 문제를 맞추어도 효율이 안좋은 경우가 종종 있다.시간복잡도를 최대한 줄여 효율을 끌어올려야 겠다고 생각이 들어 시간복잡도를 정리해본다.삽입(insert,pop), 제거(delete, remove) , 탐색(check ==,≠) 포함여부 확인( containment(in, not in))의 경우 List는 전부 O(N)이다. Set,Dict은 O(1)혹은 O(len)의 시간을 가지고 있다.-> 삽입,삭제,탐색,포함여부 확인등의 문제는 list보다 set,dict을 사용하는게 효율면에서 뛰어나다고 생각한다. List SetDictionary

1. 해시테이블해시테이블이란 해시함수를 이용해 키를 값에 매핑하는 자료구조구현충돌아무리 좋은 해시 함수라도 충돌을 피하기는 어렵다.예측 가능한 범위 내에서 해시값이 나오고, 데이터와 짝지어지는 것이기 때문에 해시값이 중복될 수 있다. 👉🏻 입력값이 달라도 똑같은 결과가 나오면 충돌이를 다루는 방식은 체이닝(Chaining), 오픈 어드레싱(Open Addressing) 이 있다.오픈 어드레싱은 탐사를 통해 ‘빈 공간을 찾아나서는’ 방식체이닝은 충돌 발생 시 ‘연결’해가는 것오픈 어드레싱 O(1)체이닝 O(n)오픈 어드레싱은 값이 뭉치는 클러스터링이 발생할 수 있고,체이닝은 메모리 오버헤드와 길어질 경우 탐색이 느려진다는 단점그래서 각 언어 별로 해시테이블의 구현 방식이 다른데요. C++, Java, ..