들어가기 앞서
오늘 처음 국민취업지원제도의 상담을 하게 되었습니다.
취업을 하고싶다는 생각만 앞서고 아무것도 한게 없다는 느낌을 받았습니다.
아침에 하는 알고리즘 코드카타처럼 하루하루 작게 느껴져도
모이면 커지는 것들을 조금씩 해봐야겠다고 다짐하게 되었습니다.
오늘 배운 것
정렬 알고리즘
-
주어진 데이터를 특정한 기준에 따라 순서대로 나열하는 알고리즘.
-
다양한 방법으로 구현될 수 있으며, 각 알고리즘은 자체적인 특징과 장단점을 가지고 있음.
-
버블정렬 (Bubble Sort)
간단하면서도 효율성이 낮은 정렬 알고리즘 중 하나.
인접한 두 원소를 비교하며 크기가 작은 원소를 앞으로 이동시키는 방식으로 동작.
데이터 크기가 커질수록 정렬에 걸리는 시간이 증가하고, 시간 복잡도가 O(n^2)으로 매우 비효율적이라는 것.- 버블 정렬의 동작 과정
- 배열을 처음부터 끝까지 반복하면서 인접한 원소를 비교
- 만약 왼쪽 원소가 오른쪽 원소보다 크다면, 두 원소를 교환
- 배열의 끝까지 반복하며 최대값이 맨 오른쪽으로 이동
- 다음 반복에서는 맨 오른쪽 원소를 제외하고 위 과정을 반복
- 예시 코드
static void BubbleSort(int[] arr) { int n = arr.Length; for (int i = 0; i < n; i++) { for (int j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) { // 두 원소를 교환 int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } }
-
선택 정렬 (Selection Sort)
주어진 배열에서 최소값을 선택하여 순서대로 정렬된 부분을 채워나가는 방식.
평균 및 최악의 경우 시간 복잡도가 모두 O(n^2)로 비효율적.- 선택 정렬의 동작 과정
- 주어진 배열에서 최소값을 찾음
- 해당 최소값을 배열의 첫 번째 원소와 교환
- 다음으로, 두 번째로 작은 값을 찾아 두 번째 원소와 교환
- 배열의 끝까지 반복하면서 정렬된 부분을 확장
- 예시 코드
static void SelectionSort(int[] arr) { int n = arr.Length; for (int i = 0; i < n - 1; i++) { int minIndex = i; for (int j = i + 1; j < n; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; } } // 최소값과 현재 위치의 값을 교환 int temp = arr[minIndex]; arr[minIndex] = arr[i]; arr[i] = temp; } }
-
삽입 정렬 (Insertion Sort)
정렬되지 않은 부분에서 원소를 하나씩 선택하여 이미 정렬된 부분에 적절한 위치에 삽입해 나가는 방식으로 동작.
작은 데이터셋이나 이미 정렬된 데이터에 대해서는 성능이 꽤 좋을 수 있음.
평균 및 최악의 경우 시간 복잡도가 O(n^2)이기 때문에 대규모 데이터에는 비효율적.- 삽입 정렬의 동작 과정
- 배열을 정렬된 부분과 정렬되지 않은 부분으로 나눔
- 정렬되지 않은 부분에서 첫 번째 원소를 선택하여 이미 정렬된 부분에 적절한 위치로 삽입
- 다음 원소를 선택하고, 해당 원소를 이미 정렬된 부분에서 적절한 위치에 삽입
- 이를 반복하여 정렬이 완료될 때까지 진행
- 예시 코드
static void InsertionSort(int[] arr) { int n = arr.Length; for (int i = 1; i < n; i++) { int current = arr[i]; int j = i - 1; // 현재 원소보다 큰 원소를 오른쪽으로 이동하여 삽입할 위치를 찾음 while (j >= 0 && arr[j] > current) { arr[j + 1] = arr[j]; j--; } // 현재 원소를 찾은 위치에 삽입 arr[j + 1] = current; } }
-
병합 정렬 (Merge Sort)
분할 정복(divide and conquer) 방법을 사용하여 배열을 정렬하는 효율적인 정렬 알고리즘.
배열을 반으로 나눈 뒤, 각 부분을 정렬하고 병합하는 과정을 반복하여 전체 배열을 정렬.
시간 복잡도는 O(n log n)으로 매우 효율적.- 병합 정렬의 동작 과정
- 배열을 반으로 나눔
- 각 하위 배열을 재귀적으로 정렬
- 정렬된 하위 배열을 병합하여 큰 하나의 정렬된 배열을 만듬
- 예시 코드
static void Merge(int[] arr, int left, int middle, int right) { int n1 = middle - left + 1; int n2 = right - middle; int[] leftArray = new int[n1]; int[] rightArray = new int[n2]; Array.Copy(arr, left, leftArray, 0, n1); Array.Copy(arr, middle + 1, rightArray, 0, n2); int i = 0, j = 0, k = left; while (i < n1 && j < n2) { if (leftArray[i] <= rightArray[j]) { arr[k] = leftArray[i]; i++; } else { arr[k] = rightArray[j]; j++; } k++; } while (i < n1) { arr[k] = leftArray[i]; i++; k++; } while (j < n2) { arr[k] = rightArray[j]; j++; k++; } } static void MergeSort(int[] arr, int left, int right) { if (left < right) { int middle = left + (right - left) / 2; MergeSort(arr, left, middle); MergeSort(arr, middle + 1, right); Merge(arr, left, middle, right); } }
-
퀵 정렬 ( Quick Sort )
평균적으로 매우 효율적인 정렬 알고리즘.
분할 정복(divide and conquer) 전략을 사용하여 배열을 빠르게 정렬하는 방법 중 하나.
평균 시간 복잡도는 O(n log n)이며, 최악의 경우에도 O(n^2)보다 낮은 확률로 발생하도록 최적화할 수 있음.- 퀵 정렬의 동작 과정
- 배열에서 하나의 원소를 피벗(pivot)으로 선택
- 피벗을 기준으로 작은 값은 피벗의 왼쪽으로, 큰 값은 피벗의 오른쪽으로 분할
- 왼쪽 부분과 오른쪽 부분에 대해 재귀적으로 퀵 정렬을 수행
- 각 하위 배열이 정렬되면, 전체 배열이 정렬됨
-
예시 코드
static int Partition(int[] arr, int low, int high) { int pivot = arr[high]; int i = low - 1;for (int j = low; j < high; j++) { if (arr[j] < pivot) { i++; int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } int temp2 = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = temp2; return i + 1;}
static void QuickSort(int[] arr, int low, int high)
{
if (low < high)
{
int pivotIndex = Partition(arr, low, high);QuickSort(arr, low, pivotIndex - 1); QuickSort(arr, pivotIndex + 1, high); }}
-
힙 정렬 (Heap Sort)
힙 자료구조를 기반으로 한 정렬 알고리즘.
힙은 특정한 규칙을 만족하는 완전 이진 트리 형태의 자료구조로, 최대 힙이나 최소 힙으로 구성.
최대 힙은 부모 노드가 자식 노드보다 크거나 같은 값을 갖는 힙이며, 최소 힙은 그 반대.- 힙 정렬의 동작 과정
- 주어진 배열을 최대 힙으로 구성, 이 단계를 "힙 구성"이라고 함
- 최대 힙에서 최대값(루트 노드)을 꺼내고, 배열의 맨 뒤로 이동
- 힙 크기를 하나 줄이고, 최대 힙 속성을 유지하기 위해 루트 노드를 재조정
- 과정을 반복하여 전체 배열이 정렬될 때까지 진행
- 예시 코드
static void Heapify(int[] arr, int n, int i) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left < n && arr[left] > arr[largest]) largest = left; if (right < n && arr[right] > arr[largest]) largest = right; if (largest != i) { int swap = arr[i]; arr[i] = arr[largest]; arr[largest] = swap; Heapify(arr, n, largest); } } static void HeapSort(int[] arr) { int n = arr.Length; // 최대 힙을 구성합니다. for (int i = n / 2 - 1; i >= 0; i--) Heapify(arr, n, i); // 루트 노드(최대값)를 추출하여 정렬 for (int i = n - 1; i > 0; i--) { int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; Heapify(arr, i, 0); } }
-
기수 정렬 (Radix Sort)
비교 정렬이 아닌 안정적인 정렬 알고리즘 중 하나.
정렬할 데이터가 숫자나 문자열과 같은 형태일 때 효과적으로 사용.
각 자리수를 기준으로 정렬하는 방식으로 작동.
일반적으로 데이터가 n개이고 k진수인 경우(예: 10진수의 경우 k=10), 기수 정렬의 시간 복잡도는 O(nk).- 기수 정렬의 동작 과정
가장 낮은 자리수부터 가장 높은 자리수까지 순차적으로 정렬하는 것
먼저 가장 낮은 자리수에 따라 정렬하고, 그 다음으로 높은 자리수에 따라 정렬하며, 이를 반복하여 전체 데이터가 정렬될 때까지 진행
- 예시 코드
static void RadixSort(int[] arr) { int n = arr.Length; int max = FindMax(arr); // 배열 내 최대값을 찾음 // 각 자리수마다 정렬을 수행 for (int exp = 1; max / exp > 0; exp *= 10) CountingSort(arr, n, exp); } static int FindMax(int[] arr) { int max = arr[0]; for (int i = 1; i < arr.Length; i++) { if (arr[i] > max) max = arr[i]; } return max; } static void CountingSort(int[] arr, int n, int exp) { int[] output = new int[n]; int[] count = new int[10]; // 각 자리수별로 개수를 셈 for (int i = 0; i < n; i++) count[(arr[i] / exp) % 10]++; // 누적 합을 계산하여 카운트 배열을 업데이트 for (int i = 1; i < 10; i++) count[i] += count[i - 1]; // output 배열에 정렬된 값을 복사 for (int i = n - 1; i >= 0; i--) { output[count[(arr[i] / exp) % 10] - 1] = arr[i]; count[(arr[i] / exp) % 10]--; } // output 배열의 값을 arr 배열로 복사. for (int i = 0; i < n; i++) arr[i] = output[i]; }
- 기수 정렬의 동작 과정
기억 할 것 & 진행 사항
-
분할 정복 : 복잡한 문제를 해결하기 위한 방법 중 하나로, 문제를 여러 개의 작은 부분 문제로 나눈 다음, 각 부분 문제를 해결하여 전체 문제의 해를 구하는 전략.
- 분할(Divide): 복잡한 문제를 더 작은 부분 문제들로 분할
- 정복(Conquer): 작은 부분 문제들을 재귀적으로 해결
부분 문제의 크기가 충분히 작아지면 직접 해결하고, 그렇지 않으면 다시 분할 단계로 돌아가서 문제를 더 작은 부분 문제로 분할 - 결합(Combine): 해결된 부분 문제들을 합쳐서 전체 문제의 해를 얻음
- 대표적인 분할 정복 알고리즘에는 병합 정렬(Merge Sort), 퀵 정렬(Quick Sort), 이진 검색(Binary Search), 카라츠바 곱셈(Karatsuba Multiplication) 등이 있음.
-
파티션 : 주어진 데이터를 분할하는 작업을 의미하는데, 주로 정렬 알고리즘에서 사용.
정렬 알고리즘에서의 파티션은 주로 배열 내에서 하나의 요소를 선택하고, 그 요소를 기준으로 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 이동시키는 과정.
퀵 정렬(Quick Sort)에서 파티션은 피벗(pivot) 요소를 선택하고, 그것을 기준으로 작은 값과 큰 값으로 나누는 과정을 의미.
병합 정렬(Merge Sort)에서도 분할된 배열을 합치는 과정을 파티션으로 볼 수 있음.
-
C# Sort 메서드
메서드는 배열이나 리스트의 요소들을 정렬하는 메서드.
Array.Sort 메서드나 List.Sort 메서드를 사용할 수 있음.
정렬은 오름차순으로 수행되며, 요소들의 자료형에 따라 다양한 정렬 기준을 사용할 수 있음.- 예제 코드
- 배열 정렬
using System; class Program { static void Main(string[] args) { int[] numbers = { 5, 3, 8, 1, 9, 2, 7, 4, 6 }; Console.WriteLine("정렬되기 전 배열:"); Console.WriteLine(string.Join(" ", numbers)); Array.Sort(numbers); // 배열 정렬 Console.WriteLine("정렬된 배열:"); Console.WriteLine(string.Join(" ", numbers)); } } - 리스트 정렬
using System; using System.Collections.Generic; class Program { static void Main(string[] args) { List<int> numbers = new List<int> { 5, 3, 8, 1, 9, 2, 7, 4, 6 }; Console.WriteLine("정렬되기 전 리스트:"); Console.WriteLine(string.Join(" ", numbers)); numbers.Sort(); // 리스트 정렬 Console.WriteLine("정렬된 리스트:"); Console.WriteLine(string.Join(" ", numbers)); } }
현재 진행 사항
- 체크리스트
- 개발 환경 설정
- 기본 코드 구조
- 변수와 자료형
- 연산자 문자열 처리
- 조건문과 반복문
- 배열과 컬렉션
- 매서드와 구조체
- 클래스와 객체
- 상속과 다형성
- 고급 문법 및 기능
- 인터페이스와 열거형
- 예외 처리 및 값형과 참조형
- 델리게이트, 람다 및 LINQ
- 고급 자료형 및 기능
- 알고리즘 기초
- 정렬 알고리즘 -> 여기까지 정리중
- 탐색 알고리즘
- 고급 알고리즘
- 문제해결 전략과 실전 연습 -> 현재 여기까지 강의 수강
내일 할 일
- 하루 계획
- 오전
09:00 ~ 09:30 : 팀 회의09:30 ~ 10:30 : 알고리즘 코드카타10:30 ~ 14:00 :- 오늘 계획 (Task)
• 지급 받은 강의 듣기 (5주차 알고리즘)
• 알고리즘 공부
- 오늘 계획 (Task)
12시-1시: 점심식사
- 집중 코딩
14:00 ~ 18:00
- 저녁
6시-7시: 저녁식사19:00 ~ 20:00 : 집중 코딩 시간 부족한 부분 해결해보기20:00 ~ 21:00: TIL 작성, 마무리 회고 진행21:00 : 내일은 위한 휴식!
- 오전
