알고리즘과 자료구조

퀵 정렬은 1960년에 찰스 앤터니 리처드 호어(C.A.R hoare)가 처음 제안한 방법으로 이후 많은 사람들이 수정 보완하여 완성된 정렬 알고리즘이다. 이 알고리즘은 처음 소개된 이후로 반세기가 넘었지만 현존하는 가장 빠른 정렬 알고리즘 중에 하나이다. 퀵 정렬은

배열의 가운데 있는 항목을 비교하여 크면 오른쪽 부분을 검색하고, 작으면 왼쪽 부분을 검색하여서 검색부분을 점차 축소해가면서 값을 탐색하는 것그렇기 때문에 데이터가 정렬된 상태에서 사용해야함분할과 정복 기법 사용시간 복잡도 : O(long(n))

병합 정렬은 데이터들을 쪼갠 다음 하나로 합치면서 정렬하는 방법이다.Divde and Conquer 기법분할 (Divide) : 배열을 2개의 배열로 재귀를 통해 계속 분할한다.정복 (Conquer) : 분할된 배열을 정렬결합 (Combine) : 정렬된 부분을 다시

기수 정렬은 다른 정렬과 다르게 서로 비교하여 정렬하지않습니다.기수 정렬은 각 데이터의 자리수와 자리수의 값을 이용해 반복적으로 Counting Sort(계수 정렬)를 수행하여 전체 배열을 정렬하는 방식입니다.원소간 비교하지않고 각 원소가 몇개 등장하는지 갯수를 세서

힙 정렬은 힙, 바이너리 힙, 이진 힙이라고 부르는 자료구조를 이용하는 정렬 알고리즘입니다.최솟값이나 최댓값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 하는 트리이진 트리는 모든 노드의 자식 노드가 2개 이하인 노드를 말합니다. 완전 이진 트리는 루트 노드부터

segment tree 혹은 구간 트리라고도 부른다.보통 구간합으로 예시를 많이 들지만 세그먼트 트리는 주어진 쿼리에 대해 빠르게 응답하기 위해 만들어진 자료구조입니다.쿼리주어진 요구사항에 대해 맞는 결과물을 제시배열에서 어떤 구간의 최솟값이나 합을 찾아야할 때, 간단

입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가빅-오 표기법을 사용해 시간복잡도를 나타냄시간 복잡도: 알고리즘의 수행시간을 평가공간 복잡도: 알고리즘 수행에 필요한 메모리 양을 평가입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에

주어진 문제를 여러 개의 하위 문제로 나누어 풀고, 하위 문제들의 해결 방법을 결합하여 최종 문제를 해결하는 문제 해결 방식을 말합니다.큰 문제를 작은 문제로 나눌 수 있고, 작은 문제가 중복해서 발견된다 (Overlapping Sub-problems)작은 문제에서 구

n개 중에서 일부를 선택하여, 순서를 생각하지않고 나열하는 것을 조합이라고 합니다.중복 순열n개 중에서 일부만을 선택하여 나열하는 것을 순열이라고 합니다. 순열은 순서를 지키며 나열해야합니다.의무과정만 다 나왔다면 다 아는 개념이니.. 많은 문제를 풀어서 익숙해보도록하

두 수 A와 B 공통된 약수 중에서 가장 큰 정수유클리드 호제법의 기본 원리는 num1를 num2로 나눈 나머지를 r이라고 했을 때, GCD(num1, num2) = GCD(num2, r)과 같다는 것이다두 수, 공통인 배수 중 가장 작은 수주어진 집합의 모든 부분집합

다익스트라 알고리즘은 대표적인 최단 경로 탐색 알고리즘입니다. 하나의 시작 정점에서 다른 모든 정점까지 최단 경로를 구합니다. 이때 음의 가중치를 갖는 간선은 허용하지않습니다.다익스트라 알고리즘은 동적 프로그래밍(DP)를 활용한 최단 경로 탐색 알고리즘입니다. DP인

다익스트라 알고리즘은 하나의 정점을 출발점으로, 모든 정점까지 최단 경로를 구하는 알고리즘이었습니다. 이번 플로이드-와샬 알고리즘은 각각의 정점을 출발점으로 해서 모든 정점까지 최단 경로를 구하는 알고리즘입니다.모든 정점에 대한 경로를 계산하기 때문에 거리를 저장할 자

벨만 보드 알고리즘은 다익스트라 알고리즘과 같이 한 정점으로부터 다른 모든 정점으로 최단경로를 찾는 알고리즘입니다. 차이점은 음수 간선이 포함된 상황에서 최단 거리를 계산할 때 사용합니다.A => C로 갈때 두 가지 경로가 존재합니다.A => B => C : 3A =>

탐색(search)란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정대표적 그래프 탐색 알고리즘 DFS & BFS먼저 들어온 데이터가 나중에 나가는 형식의 자료구조(선입후출)입구와 출구가 동일한 형태로 스택을 시각화할 수 있음삽입과 삭제 둘로 이루어짐먼저 들어 온

정렬 : 데이터를 특정 기준에 따라 순서대로 나열하는 것처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복시간복잡도선택정렬은 N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야함빅오 표기법 O(N^2)처리되지 않은 데이터를

순차 탐색: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법이진 탐색: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 \- 이진 탐색은 시작점, 끝점, 중간점을 이용해 탐색범위를 설정시간 복잡도단계마