선택 정렬이란?선택 정렬은 정렬되지 않은 데이터들에 대해 `가장 작은 데이터를 찾아` 가장 앞의 데이터와 교환해나가는 방식이다. 최솟값의 자리를 변수에 저장해놓고 그 자리의 값과 나머지 값들을 비교하며 최종 최솟값을 찾는 반복문이 끝나면 그때 스왑해준다. 선택 정렬 장점과 단점장점구현이 쉽다.내림차순으로 정렬되어있는 요소를 오름차순으로 재정렬할 때 효율이 좋다.비교 횟수는 많지만, 실제로 교환하는 횟수는 적다. 교환이 많이 일어나는 자료상태라면 효율적이다.(버블정렬과 비교했을 때, 똑같은 O(n2) 의 시간복잡도를 갖지만, 시간을 측정해보면 버블정렬보다 시간이 짧게 소요됨.)단점서로 떨어져 있는 요소를 교환하기 때문에 안정적이지 않다.(중복된 값이 2개 있을 때 요소의 순서가 바뀔 수 있음.)이미 정렬된..

버블 정렬이란?버블 정렬은 원소를 비교하는 과정에서 연탄 나르기와 비슷하다. 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하는 정렬 알고리즘이다. 시간 복잡도가 O(n²)로 상당히 느리지만, 소스코드가 직관적이고 구현이 매우 간단하다는 장점이 있다. 버블 정렬 장점과 단점버블 정렬 장점구현이 매우 간단하고, 소스코드가 직관적이다.정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않다. ➡ 제자리 정렬(in-place sorting)버블 정렬 단점시간복잡도가 최악, 최선, 평균 모두 O(n²)으로, 굉장히 비효율적이다.정렬 돼있지 않은 원소가 정렬 됐을 때의 자리로 가기 위해서, 교환 연산(swap)이 많이 일어나게 된다. 시간 복잡도알고리즘Bes..

DFS(Depth-First-Search)란?그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정해서 최대깊이까지 탐색을 마친 후, 다른쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다. 또한 DFS는 그래프 완전 탐색(모든 노드를 방문)이며, 주로 스택(Stack) 자료구조를 사용하거나 재귀 호출을 통해 구현된다. DFS 장점과 단점DFS 장점현 경로상의 노드들만 기억하면 되므로 저장공간 수요가 비교적 적음목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있음DFS 단점해가 없는 경로가 깊을 경우 탐색시간이 오래 걸릴 수 있음얻어진 해가 최단 경로가 된다는 보장이 없음 그래프 표현 방법우선 탐색하기 전 연결의 정보인 그래프를 표현부터 해야할 것이다. 그래프를 표현하는 방법에는 인접 행렬과,..

카데인 알고리즘이란?카데인 알고리즘(Kadane’s Algorithm)은 연속된 부분 배열의 최대 합을 찾을 때 사용된다. 주로 배열이나 리스트에서 연속된 원소들의 합이 최대가 되는 부분 배열을 효율적으로 찾는 경우에 유용하다. 예를 들어, 주어진 배열의 각 원소가 양수, 음수, 또는 0일 때 그 배열에서 연속적인 부분 배열의 최대 합을 구하고자 할 때 카데인 알고리즘을 사용하면 O(n)의 시간 복잡도로 문제를 해결하며, 동적 계획법(Dynamic Programming) 접근법을 사용한다. 이 알고리즘은 매 반복마다 현재 부분 합과 최대 부분 합을 갱신해 가며 최적의 해답을 찾아가는 방식이다. 카데인 알고리즘의 원리카데인 알고리즘은 현재까지의 최대 부분 배열의 합을 유지하면서, 각 요소를 순차적으로 탐색..

싱글톤 패턴이란 단 하나의 유일한 객체를 만들기 위한 코드 패턴이다. 즉, 메모리 절약을 위해, 인스턴스가 필요할 때 똑같은 인스턴스를 새로 만들지 않고 기존의 인스턴스를 가져와 활용하는 기법을 말한다.우리가 전역 변수라는 걸 만들어 이용하는 이유는, 똑같은 데이터를 메서드마다 지역 변수로 선언해서 사용하면 무의미하기도 않고 낭비이기 때문에, 전역에서 한번만 데이터를 선언하고 가져와 사용하면 효율적이기 때문이다.이러한 개념을 그대로 클래스에 대입한 것이 싱글톤 패턴이라고 이해하면 된다. 따라서 보통 싱글톤 패턴이 적용된 객체가 필요한 경우는 그 객체가 리소스를 많이 차지하는 역할을 하는 무거운 클래스일때 적합하다. 싱글톤 패턴의 기본 구현에는 다음 세 가지 조건이 반드시 충족되어야 한다.1. 싱글톤으로 ..

Dicision Tree란?Dicision Tree는 분류 및 회귀 작업에 사용되는 지도 머신 러닝 알고리즘의 한 유형이다. Dicision Tree를 구성하는 알고리즘에는 ID3, C4.5, CART(분류 및 회귀 트리) 등 여러 가지가 있지만 여기서는 ID3에 대해서 알아본다. 내부 노드는 특징 테스트 또는 결정점을 나타내고, 분기는 해당 테스트의 결과를 나타내며, 리프 노드는 최종 클래스 레이블 또는 목표 값을 나타내는 순서도와 같은 구조이다.불순도는 데이터 내에서 여러 카테고리가 섞여 있어, 원하는 표본을 뽑을 확률이 적을 수록 커지는 개념이다. 다양한 과일들의 비율이 높아질수록 불순도는 증가한다. 이 불순도를 지표로 만든 것을 엔트로피(Entropy)라고 하는데 Dicision Tree는 Sam..