가비지 컬렉션 이란 ? 가비지 컬렉션(Garbage Collection, GC)은 메모리 관리를 자동화하는 기능. 더 이상 사용되지 않는 객체를 자동으로 찾아서 메모리를 해제하는 역할을 함. 스택 메모리의 경우 함수의 실행 순간부터 종료까지 공간 사용량을 추적한다. 하지만 힙 메모리는 C++과 같은 경우에는 메모리 관리가 수동으로 이루어지기 때문에 생성자와 소멸자를 명시적으로 정의해야 함. C#은 가비지 컬렉션을 통해 자동으로 메모리를 관리하기 때문에 생성자는 필요하지만, 소멸자는 대부분의 경우 필요하지 않다.       가비지 컬렉션의 동작 방식  마킹(Marking) : 가비지 컬렉터는 루트 참조부터 시작하여 모든 접근 가능한 객체를 마킹함.분류, 재배치 (Relocate) : 사용되지 않는 개체들을..

동적 계획법이란 ?  동적 계획법은 어떤 문제가 여러 단계의 반복되는 부분 문제로 이루어져 있을때, 각 단계의 부분 문제의 답을 기반으로 전체 문제의 답을 구하는 방법이다.복잡한 하나의 문제를 간단한 하위 문제들로 나눠서 푸는 최적화 기법이다.동적 계획법을 사용하려면 문제의 유형이 최적 부분 구조(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)