[TIL 24.05.05~06] 5주차 강의-알고리즘 기초, 정렬 알고리즘

5주차 강의의 내용은 특히나 어렵기 때문에 원하는 만큼 조금씩 쪼개서 자세히 탐구한 후에나 하나씩 올리려 한다. 우선 오늘은 2일에 걸쳐 일요일에는 알고리즘 기초, 월요일에는 정렬 알고리즘에 대해 공부하고 이에 대한 TIL을 작성했다. 정렬은 이전에 배치고사 때 가볍게 훑어보았지만, 씹어먹지 않았기에 다시 정리했다.

 

+)스파르타 TIL 제출란에 잘못 올려서 4주차 대신 이게 맨 위에 올라와있길래 그냥 월요일에 4주차를 재업했으니 둘이 바꿔서 생각해주시면 좋을 것 같아요...ㅇㅅㅇ 이게 액셀에서 하루에 여러 개 올리면 처음 올린 것만 링크가 연결되더라고요. 잘못 올린걸 내릴 수도 없고ㅠㅠ

목   차

 

---

알고리즘 기초

알고리즘(Algorithm)

• 문제를 해결하기 위한 단계적인 방법
• 입력을 받아 원하는 출력을 생성하기 위한 절차
• 입력, 출력, 명확한 단계, 실행 가능성의 특성을 가짐.
• 주어진 입력에 대해 정확하고 일관된 결과를 제공해야 함.
• 컴퓨터 프로그래밍 뿐만 아니라 여러 분야에서 사용됨.

Big O 표기법

본문내용넣기

시간 복잡도 (Time Complexity)

본문내용넣기

공간 복잡도 (Spae Complexity)

본문내용넣기

---

정렬 알고리즘

정렬 알고리즘이란?

정렬 알고리즘: 주어진 데이터 세트를 오름차순/내림차순으로 정리하는 방법.

 

이 아래의 예시들은 임의의 배열 [3, 7, 2, 4, 6, 0, 1] 을 기준으로 작성한다. 코드는 일전에 올린 적 있으니 원리 위주로 이해하고 다음에 내가 정렬 복습을 할 때 이 한글 가이드 라인을 보고 코드를 짤 수 있나 확인도 해볼 예정이다.

선택 정렬

1. 배열에서 가장 작은 숫자를 골라 맨 앞에 배치한다. (0, 3, 7, 2, 4, 6, 1)
2. 그 다음으로 작은 숫자를 골라 그 다음에 배치한다. (0, 1, 3, 7, 2, 4, 6)
3. 이 과정을 반복한다.

힌트: for문 2개와 if문을 사용한다.

삽입 정렬

1. 두 번째 숫자를 그 앞의 수와 비교해 순서를 정렬한다. (3, 7, 2, 4, 6, 0, 1)
2. 세 번째 숫자를 그 앞의 수들과 비교해 정렬한다. (3, 2, 7, 4, 6, 0, 1) -> (2, 3, 7, 4, 6, 0, 1)
3. 정렬이 끝날 때까지 이 과정을 반복한다.

힌트: for문 2개를 이용한다.

퀵 정렬

1. pivot 하나를 배열의 요소들 중 하나로 정해서 이 pivot을 기준으로 큰 수와 작은 수를 각각의 배열로 나눈다.
   •  (2, 0, 1) (3: pivot) (7, 4, 6)
2. 쪼개진 배열들을 같은 방법으로 쪼개준다.
   •  (0, 1)  (2:pivot1) / (3) / (4, 6) (7:pivot2)
3. 모든 리스트의 크기가 0 또는 1일 때까지 반복한다.
   •  (0) (1) (2) (3) (4) (6) (7)
4. 정리 끝.

힌트: QuickSort함수에서 pivot을 Partition 함수로 구한 후 자기자신을 재귀호출한다. 인자는 배열, 왼쪽, 오른쪽.

힌트2: Partition이라는 보조 함수가 필요하다. 이 함수가 약간 이해가 안된다...

 

병합 정렬

1. 배열을 반으로 나누어 mid를 기준으로 0 ~ mid를 앞쪽 배열, mid+1~max를 뒤쪽 배열로 한다. 
   • ( 3, 7, 2, 4 ) , ( 6, 0, 1 )
2. 이 과정을 각 배열의 크기가 0 또는 1일때까지 반복한다. 
   • 3 / 7 / 2 / 4 / 6 / 0 / 1
3. 배열의 크기가 1이면 정렬이 된 것으로 간주하고, 두 정렬된 리스트를 앞에서부터 비교하면서 더 작은 요소를 새로운 리스트에 추가하는 방식으로 병합한다.
   • (3, 7) , (2, 4) , (4, 6) , (0, 1)
   • (2, 3, 4, 7) , (0, 1, 4, 6)
4. 반복한다.

힌트1: 아휴 모르겠다 증말. 그냥 몸으로 직접 코드 다시 보면서 떼워야지...

(+) 버블 정렬

1. 맨 앞의 두 수를 비교 후, 앞의 수가 더 크면 교환한다. (3, 7, 2, 4, 6, 0, 1)
2. 그 바로 다음의 두 수를 비교한다. (3, 2, 7, 4, 6, 0, 1)
3. 마지막 두 수까지 이 과정을 반복한다. (3, 2, 4, 7, 6, 0, 1), (3, 2, 4, 6, 7, 0, 1), (3, 2, 4, 6, 0, 7, 1), (3, 2, 4, 6, 0, 1, 7)
4. 오름차순이 될 때까지 이 1~3을 반복한다. 

힌트: for문 2개와 if문 한 개면 풀 수 있다.

C# Sort 메서드

// 정수 배열 정렬 예제
int[] numbers = { 5, 2, 8, 3, 1, 9, 4, 6, 7 };
Array.Sort(numbers);
Console.WriteLine(string.Join(", ", numbers));

// 문자열 리스트 정렬 예제
List<string> names = new List<string> { "John", "Alice", "Bob", "Eve", "David" };
names.Sort();
Console.WriteLine(string.Join(", ", names));

---

 

마무리

무슨 버그인지는 모르겠지만 내용이 날아감. 수정이 안됨. 나한테 왜 그러는거야..

그리고 정렬은 전에도 느꼈지만 정말 너무, 너무, 너무, 너무 어렵다...ㅠㅠㅠㅠㅠㅠ

차라리 탐색을 하지 왜 이렇게 이해가 안되는지... 코드를 읽는 것만으로도 힘들어죽겠다. 볼 때마다 내 머리가 나쁜가 싶고... 그래도 계속 자주 들여다보면 언젠가 이해할 거라는 희망은 잃지 말자.

 

....컴퓨터를 껐다 켰더니 계속 있던 오류가 사라졌다. 사실 여기 뿐만 아니라 다른 인터넷들도 일부는 되고 일부는 안되고 자기 멋대로였는데, 정확히 어떤 이유로 나한테 이런 시련을 주었는지는 영원이 할 수 없을 것이다...