1. 문제설명 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다. 전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함..
분류 전체보기
1. 문제설명 하노이 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있습니다. 게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것입니다. 1. 한 번에 하나의 원판만 옮길 수 있습니다. 2. 큰 원판이 작은 원판 위에 있어서는 안됩니다. 하노이 탑의 세 개의 기둥을 왼쪽 부터 1번, 2번, 3번이라고 하겠습니다. 1번에는 n개의 원판이 있고 이 n개의 원판을 3번 원판으로 최소 횟수로 옮기려고 합니다. 1번 기둥에 있는 원판의 개수 n이 매개변수로 주어질 때, n개의 원판을..
동적 프로그래밍이란? 큰 문제를 작은 단위로 쪼개서 반복 분할하여 푸는 접근 방식입니다. 네 맞습니다. DFS와 같은 개념입니다. 기본적으로 DFS문제는 재귀함수를 사용해서 풀어가는 방식이 일반적입니다. 그럼 동적프로그래밍은 DFS와 같은 것인가?? 결론부터 말씀드리면, 답은 No입니다. 동적 프로그래밍은 작은 하위 문제의 해결 방법을 계산하여 저장하고, 이를 이용하여 큰 문제의 해결 방법을 도출합니다. DFS와 동적프로그래밍의 차이점!! 여기 숫자가 들어있는 정삼각형 구조가 있습니다. 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 리턴하는 문제입니다. 문제를 처음 접하게되면 기본적으로 DFS로 문제를 풀어야겠다는 생각이 들 것입니다. DFS로 접근하게 되면, 7+3+8+2+..
재귀 알고리즘이란? 재귀 알고리즘은 하나의 함수에서 자기 자신을 다시 호출하여 작업을 수행하는 알고리즘이다. 재귀 함수는 반복문(for, while문)으로도 충분히 대체 가능하다. 재귀 함수는 언제 사용할까? - 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우 - 반복문이 많이 중첩되거나 중첩 횟수를 예측하기 어려운 경우 - 변수의 사용을 줄여 메모리를 비교적 간소화하고 프로그램 오류가 발생할 가능성을 줄이고자 하는 경우 - 단, 재귀함수가 모든 경우에서 반복문보다 좋은 것은 아니다. 대표적인 예로는 피보나치 수열, 팩토리얼 계산, 탐색 트리의 순회 등이 있다. 재귀 알고리즘의 사용 1. 피보나치 수열 피보나치 수열이란, F(0) = 0 F(1) = 1 F(2) = F(0) + F(1) F(3)..
1. 순차탐색(Sequential Search) 찾고자 하는 값과 배열의 원소를 순서대로 비교해서 찾으면 해당 인덱스를 반환, 값이 없다면 -1 또는 null을 반환합니다. 시간복잡도 = O(n)번 public int SequentialSearch(int data, List list) { if (list.Count == 0) return -1; for (int i = 0; i < list.Count; i++) { if (list[i] == data) { return i; } } return -1; } 2, 이진탐색(Binary Search) 배열을 크기 순으로 정렬합니다. 정렬된 배열에서 정중앙에 위치한 값을 찾습니다. 찾고자 하는 값을 정중앙의 값과 비교해서 다음에 비교할 구간을 찾습니다. 위 과정을 ..
최근 정렬알고리즘을 공부한 것을 바탕으로 문제를 풀어보았습니다. 최대한 매서드를 사용하지 않고 정렬 알고리즘을 사용해 풀어보았습니다. 1. 문제설명 배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다. 예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면 array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다.1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다.2에서 나온 배열의 3번째 숫자는 5입니다. 배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결..
힙 정렬 내림차순을 기준으로 정렬. 완전 이진 트리의 일종으로 우선 순위 큐를 위하여 만들어진 자료구조. 최댓값, 최솟값을 쉽게 추출할 수 있는 구조. 내림차순 정렬을 위해서는 최대 힙을 구성, 오름차순 정렬을 위해서는 최소 힙을 구성하면 됨. 배열을 최대 힙으로 만듦(내림차순 정렬). 배열의 뒤부터 하나씩 저장. 삭제되는 원소들을 순서대로 정렬(오름차순 정렬). 힙 정렬 C# 코드 public void Heap_Sort(List list) { for (int i = (list .Count- 1)/2; i >= 0; i++) { My_Heap(list, i, list.Count); } for (int i = list.Count - 1; i > 0; i++) { int temp = list[0]; list..
병합 정렬 오름차순을 기준으로 정렬. 비교적 안정 정렬에 속하며, 분할 정복 알고리즘 중 하나. 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 봄. 정렬되지 않은 리스트를 낱개가 될 때까지 절반씩 반복적으로 두 부분 리스트로 나눔. 재귀함수를 통해 병합 정렬을 진행. 병합 정렬 C# 코드 public List DivideArr(List list) { if (list.Count leftIndex && rightList.Count > rightIndex) { if (leftList[leftIndex] leftIndex) { for (int i = leftIndex; i < leftList.Count; i++) { mergedList.Add(leftList[i]); } } else if (rightLis..
셸 정렬 오름차순을 기준으로 정렬. 삽입정렬을 보완한 알고리즘. 배열을 일정한 기준의 간격으로 분류(부분 리스트를 생성). 부분 리스트에서 삽입정렬을 수행. 이 과정을 간격이 1일때까지 반복 수행. 셸 정렬 C# 코드 public void Shell_Sort(int[] array) { //1.매개변수 배열의 크기의 절반만큼 갭을 만든다. int gap; for (int i = array.Length / 2; i > 0; i = i / 2) { gap = i; //갭이 짝수면 갭+1. ex)배열크기=11. 갭=5,3,1 if (gap % 2 == 0) { gap++; } for (int k = 0; k < gap; k++) { Shell_Insert_Sort(array, k, gap); } } } publ..
퀵 정렬 오름차순을 기준으로 정렬. 불안정 정렬에 속함. 매우 빠른 수행 속도를 자랑하는 방법. 기준이 되는 원소(Pivot)을 잡고 해당 원소보다 작은 값을 왼쪽, 큰 값을 오른쪽에 배치해주며 정렬하는 방법. 퀵 정렬 C# 코드 void SortQuick(int[] _arr, int _first, int _last) { if (_first < _last) { int pivot = GetPivot(_arr, _first, _last); SortQuick(_arr, _first, pivot - 1); SortQuick(_arr, pivot + 1, _last); } } int GetPivot(int[] _arr, int _first, int _last) { int pivot = _arr[_first]; i..
