투 포인터란?  투 포인터 알고리즘은 배열이나 리스트에서 사용할 수 있는 탐색 기법이다.주로 정렬된 배열이나 리스트에서 연속적인 구간에서 합이나 원소를 찾아내는데 아주 유용한 알고리즘이다.특정한 두 원소의 합을 구한다고 가정하면 완전 탐색의 경우에는 O(n2)의 시간 복잡도가 발생하지만 투 포인터로 이를 해결하면 O(n)의 시간 복잡도가 발생한다. 투 포인터의 기본 개념 투 포인터는 제목과 비슷하게 배열의 양 끝에 두개의 포인터를 이용하는 기법이다.좌우 의 포인터는 양 끝에서 시작해서 특정 원소를 찾을때 까지 가운데로 이동하며 진행한다.배열이나 리스트의 요소가 정렬 되어 있어야 사용이 가능하다. 투 포인터 사용 예시 배열의 여러 숫자 원소가 담겨있고 해당 원소 중 두 수의 합과 특정한 숫자가 일치하는 경..

그리디 알고리즘이란? 그리디 알고리즘은 매 순간 가장 최적의 선택을 하는 방식의 알고리즘이다.계산이 빠르고 구현이 간단하다.DP(동적 계획법)에서 사용했던 타뷸레이션이나 메모이제이션과 같은 안전장치가 없기 때문에 결과적으로 최선의 답을 보장하지는 못한다.탐욕 선택 속성(Greedy Choice Property)과 최적 부분 구조(Optimal Substructure)를 만족하는 문제에 적용이 가능한 알고리즘이다.   그리디 사용 예제 그리디 알고리즘은 길 찾기(다익스트라) 문제나 동전 거스름돈 문제, 혹은 최적의 적재 무게를 찾는 문제와 같이 최적의 선택이 최적의 해로 이어지는 문제들에 적합하다.  회의실 문제 예시 코드 해당 문제는 회의실을 예약을 희망하는 여러 인원 중 회의실에서 최대한 많은 회의를 ..

동적 계획법이란 ?  동적 계획법은 어떤 문제가 여러 단계의 반복되는 부분 문제로 이루어져 있을때, 각 단계의 부분 문제의 답을 기반으로 전체 문제의 답을 구하는 방법이다.복잡한 하나의 문제를 간단한 하위 문제들로 나눠서 푸는 최적화 기법이다.동적 계획법을 사용하려면 문제의 유형이 최적 부분 구조(Optimal Substructure) 이거나,중복되는 부분 문제(Overlapping Subproblems) 로 이루어 져야 한다.  동적 계획법과 분할 정복의 차이점  동적 계획법과 분할 정복은 큰 문제를 작은 여러 문제로 나눈다는 점에서는 비슷하다.하지만 문제 접근 방식이나 사용되는 문제의 유형에 있어서는 확연한 차이를 보여준다. 요소동적 계획법(DP)분할 정복(Divide and Conquer)하위 문제..

이진 탐색 이란 ?  이진 탐색(이분 탐색) 은 정렬된 데이터에서 사용하는 탐색 알고리즘이다.해당 알고리즘은 탐색 탐색 범위를 반으로 계속해서 줄여나가는 방식으로 진행된다. 이진 탐색의 순서   데이터 중앙에 있는 요소를 선택한다.중앙 요소의 값과 목표 값을 비교한다.목표 값이 중앙 요소의 값 보다 작으면 데이터의 왼편으로, 크다면 데이터의 오른편으로 이진 탐색을 새로 진행한다.원하는 값을 찾을때 까지 1~3의 과정을 반복한다.   코드 예제 이진 탐색의 코드는 비교적 간단하게 구현이 가능하다.  static int BinarySearch(int[] array, int target) { int left = 0; // 왼쪽 끝 인덱스 int right = array.Length - 1; //..

그래프 탐색 알고리즘 그래프에서 모든 정점을 순회하는 방법에는 크게 두가지가 있다. (DFS/BFS) DFS(Depth First Search) 는 '깊이 우선 탐색' 이라는 뜻으로 그래프의 정점을 방문할 때 하나의 분기를 완전히 탐색한 후 다음 분기로 넘어가는 방식이다. BFS(Breadth First Search) 는 '너비 우선 탐색' 이라는 뜻으로 깊이의 길이가 같은 모든 정점을 방문 한 후 다음 깊이로 넘어가서 방문할 정점이 없을 때 까지 탐색하는 방식이다.      깊이 우선 탐색(DFS)   깊이 우선 탐색 방식은 미로 찾기와 비슷한 방법으로 진행된다. 한 정점에서 시작하여 분기를 하나 선택하고 하나의 분기를 완전히 탐색하고 빠져나온다. 이후 다음 분기 에서도 똑같이 탐색을 진행한다.    ..

완전 탐색 기법 이란?   완전 탐색 기법은 가능한 경우의 수를 전부 나열하여 해답을 찾는 방식이다. 직관적이고 구현이 간단하다는 점이 장점이지만 계산해야 할 배열의 요소나 원소의 수가 조금만 증가해도 시간복잡도가 기하급수적으로 증가한다.    완전 탐색 알고리즘의 종류  1) 단순 Brute - Force  반복문과 조건문의 반복으로 결과값을 찾는 단순한 방식. 배열의 요소를 고려하지 않고 반복문을 반복하기에 시간복잡도가 상당히 비효율적일 확률이 높음.   2) 백트래킹 (Backtracking) 현재의 상태에서 가능한 모든 해를 탐색하면서 조건에 맞지 않으면 탐색을 조기에 중단하여 불필요한 탐색을 줄이는 형태의 알고리즘이다. 함수를 재귀적으로 호출하고 이 절차를 반복하는 특징이 있다.   분할 정복*..

정렬(Sort) 이란?  데이터의 집합을 특정 순서에 따라 배열하는 방법. 데이터의 집합의 순서를 최대 값, 최소 값 등 필요한 기준에 따라 재 배열하는 행위. 정렬에는 여러 종류의 정렬이 있고 각 정렬마다 다른 시간 복잡도와 데이터에 따라 적합한 방식의 정렬이 다르다.   정렬의 종류    버블 정렬 (Bubble Sort)      인접한 두 요소를 비교하고 정렬이 필요하면 두 데이터를 교환하는 작업을 반복 하는 정렬 방식 가장 간단하지만 시간 복잡도적인 측면에서 비효율적이다 이미 정렬이 된 데이터도 교환하는 일이 발생하며 배열의 모든 요소에 한번씩은 접근해야 함   C# 예시 코드  public void BubbleSort(int[] array) // 버블 정렬 함수{ int n = array..

Sort최악(Worst)평균(Average)최선(Best)버블 정렬O(N2)O(N2)O(N2)선택 정렬O(N2)O(N2)O(N2)퀵 정렬O(N2)O(N * logN)O(N * logN)힙 정렬O(N * logN)O(N * logN)O(N * logN)병합 정렬O(N * logN)O(N * logN)O(N * logN)삽입 정렬O(N2)O(N2)O(N)셸 정렬O(N2)O(N1.5)O(N)기수 정렬O(N)O(N)O(N)카운팅 정렬O(N)O(N)O(N)