방송대 알고리즘 학점 및 후기- 아주 아주 솔직한 리뷰 및 기출문제 풀이

▧ 중간고사 기말고사 난이도

→ 어렵지 않다. 시험은 어렵지 않다. 과목 자체는 엄청 어렵다. 난 후회했다. 왜 이걸

듣고 있는 걸까라는 생각이 많이 들었다...ㅠ_ㅠ

하지만, 전산쟁이라면 기본적으로 들어야 한다고 해서 들었다.

→ 과목 자체가 매우 어려운 과목이다, 하지만, 공부하면 좋은 성적이 나온다

→ 즉, 시험문제가 쉽게 나온다. 기출만 풀 줄 알면 좋은 성적이 나온다

(밑에 기출문제랑 풀이랑 있으니까 참고 하기 바란다)

밑에 개념을 정리해봤다. 지금 다시 봐도 아찔하다. 전산과 전산이론을 좋아한다면 당신

을 위한 과목이다. 나처럼 나름의 방식으로 막코딩 하는 사람이라면 추천하지 않는다...ㅠ_ㅠ

왠지 천재들을 위한 과목이라는 생각이 많이 들게 한 과목이었다.ㅋㅋㅋㅋ

▧ 예상 성적

→ 아래 기출을 모두 이해하고 풀었다면 최소 B+ 이상 나온다. 내가 그랬다. ㅎㅎㅎ

▧ 수업 난이도: 미친듯이 어렵다. 전산을 잘 한다고 해도, 알고리즘이라는 것이 특수한 경우가 아니면, 현업이나 학문적으로 많이 접하는 대중적인 분야가 아니어서 어렵다. 평소에 많이 접하지 않아서 어렵다. 평소에 접하지 않아도 대충 쉬운 과목도 있는데, 이건 아니다. 이 과목은 진짜로 어렵다. 평소에 접하지 않아서 이해하기 어렵고, 그리고 원래 어려워서, 그래서 진짜로 어렵다. 전산을 잘하건 말건, 현업 경험이 있건 없건, 수학을 잘하고, 알고리즘 이론을 많이 접하지 않았다면 미친듯이 어렵다. 나는 정보처리기사랑 리눅스 기사 자격증이 있고, 여러 언어를 대충 해봤고, 플레이스토어에 게임도 출시 해보는 등 대충의 경험이 있는 컴린이에서 컴중급 사이에서 컴중급에 더 가까운 사람이라고 생각했는데, 알고리즘 수업들으면서는 컴린이에 더 가까운 사람이라는 생각이 처절하게 들었다. 전산의 사용자 혹은 개발자 보다는 이론을 설립하고 적용하는 아주 비싼 전산설계사(?)에게 어울리는 수업이다. 나는 전산의 펀더멘털을 이해하기 보다는 전산의 사용자에 가까운 사람이고 그것을 추구하는 사람이라는 것을 처절하게 느끼게 해준 수업이었다. 전산의 참맛을 느끼고 싶은 사람만 도전하기를 바란다. ㅠ_ㅠ

■■■■■■■■■■■기출문제 풀이 링크 ■■■■■■■■■

https://blog.naver.com/checrealname/223478488268

■■■■■■■■■■■■■■■개념 익히기 ■■■■■■■■■■■■■■■■■

■■■■■■■■■■■■■■■■ 234 트리 시작■■■■■■■■■■■■■■■■■■

개념 이해하기 - 234 트리 (주의!!! 차근 차근 이해해야 한다)

아래는 234 트리의 개념을 세상에서 가장 쉽게 설명한 것이다. 읽고 꼭 이해하고 첨부된 문제도 꼭 풀어보기 바란다.

* 234 트리는 이진탐색트리가 최악의 시간복잡도를 나타내는 문제, 즉 자료가 이진 탐색 트리에서 한쪽으로 치우치는 상황을 개선하기 위해 나온 탐색 알고리즘이다. (이진 탐색 트리의 평균 시간 복잡도는 O(logn) 인데, 최악의 경우 O(n)이 될 수 있다)

✓ 첫번째 중요 개념

234 트리에서 노드는 2 3 4 중에 하나만 될 수 있다.

* 234 트리 이것만 보면 이해 할 수 있다!!! 차근 차근 보기 바란다.

자 위의 트리(?)처럼 생긴걸 234 트리라고 한다. 이름을 이해해야 이후의 문제풀이가 가능하다.

234는 노드를 의미하고 저위에 트리에서 하얀점, 숫자 사이에 하얀점을 노드라고 한다. 다시 말해서 234 트리는 2,3,4개의 노드만 갖을 수 있다. 왜 계속 설명하는지는 이것을 이해 하지 못하면 뒤에 문제 풀이가 안되서 그렇다. 다시 말해 숫자 앞뒤로 있는 것을 노드라고 하고 이 노드는 막대기 처럼 쭉 뻣어있다. 3노드라고 되어 있는 부분에 값이 있다. 키라고도 하고 키값이라고도 하고 값이라고도 한다. (문제마다 다르니까 꼭 알아둬야 한다.) 참고로 빨간색으로 써진 글자는 반드시 이해해야 한다. 자, 이제 3노드라고 되어 있는 부분을 루트 노드라고 부른다. 이 3노드 맨앞에 있는 첫번째 노드는 키값 30보다 작은 값으로 구성 되어야만 한다. 실제로 5, 10, 20으로 구성되어 있는 것이 보인다. 루트 노드의 2번째 노드, 즉 30과 60사이에 있는 노드는 30과 60사이의 값을 가져야 한다. 실제로 40이 적절하게 배치되어있다.

✓ 두번째 중요 개념

값 탐색 하는법

ex) 40을 탐색하는 경우,

1st: 아래에서 루트 노느의 첫번째 갑을 비교한다.

2nd: 30보다 크기에 오른쪽 값을 체크한다. 60보다 작기에 30과 60의 흰점(노드)를 타고 검색한다. ==> 작은 값은 값의 왼쪽에 큰값은 값의 오른쪽에 위치한다.

3rd: 다행히 두번째 레벨에서 40이 검색되었다.

✓ 두번째 중요 개념

삽입 하는법

234(노드)트리에서 삽입 과정을 이해나는 것이 매우 중요한데, 삽입을 위한 원칙이 있기 때문이다. 아래 이미지에서 나온것처럼 삽입을 하기 위해, 먼저 위치 탐색을 해야 하는데, 이때, 삽입을 할 대상을 만났을 때, 만약, 4노드를 만나면(=키값이 3개 라면) 무조건, 항상 노드 분할을 해야 한다.

삽입 하는법

중간값을 부모 노드로 이동 시킨다.

✓ 세번째 중요 개념

노드 분할의 유형

1) 첫번째 유형

아래 그림 맨위의 경우, 탐색중에 두번째 레벨에 4노드(=키값 3개)를 만나면, 노드 분할을 하는데

중간값이 20을 부모노드(=키값 40 레벨)로 올린다. 이때, 중간값 20이 40보다 작으니깐 왼쪽에 위치 시킨다. 중요한건 지금부터인데, 중간값이 올라가면 각 값을 부모노드의 첫번째 및 두번째로 연결한다. 이때, 앞서 배운 값의 크기에 따라 왼쪽 오른쪽에 위치 시킨다.

1) 두번째 유형 (중간) 및 마지막 유형도 동일한 원칙으로 실시한다.

✓ 네번째 중요 개념

노드를 분할가고 삽입하는 경우, leaf 노드(마지막 레벨 / 바닥레벨)에 삽입한다

문제풀기) 아래 키값을 234 트리로 삽입 해보자

답) 아래와 같지 않다면 위의 중요 개념을 위배한 것이다(처음 해보면 쉽지 않다)

자 위의 개념을 이해 했다면 기출문제 한개 풀수 있다. 이거 가성비가 너무 떨어지는데, 이해하는데 5시간, 물론 자료 찾아보는데 많은 시간이 흐르긴 했지만, 또 이해할까 말까 대충 이해 할까 하는데 많은 시간이 흐르긴 했지만, 역시 가성비 엄청 떨어진다. 어째건 아래 기출 문제 한개를 이젠 풀수 있다.

정답은 몇번인가 ?1번이지. 아까 원칙중에 4노드(=키값 3개)를 만나면 삽입하기 전에 분할 한다고 한것이 기억이 나는가? 문제를 풀기 위해 실제 분할 할 필요는 없지만, 개념은 이해를 하고 있어야 한다.

■■■■■■■■■■■■■■■■■234 트리 끝■■■■■■■■■■■■■■■■■■

■■■■■■■■■■■■■■■■■■클래스 NP 시작■■■■■■■■■■■■■■

클래스 NP란?

■■■■■■■■■■클래스 NP 끝■■■■■■■■■■■■■■■■■■

■■■■■■■■■■■■■■■■■정렬알고리즘 시작■■■■■■■■■■

정렬알고리즘 특징 정리(시간복잡도 등)

정렬방식	안정	제자리	평균	최악	알고리즘
선택 정렬	불안정	제자리	-	O(n^2)	비교 기반 정렬
버블 정렬	안정	제자리	-	O(n^2)	비교 기반 정렬
삽입 정렬	안정	제자리	-	O(n^2)	비교 기반 정렬
셸 정렬	불안정	제자리	-	O(n^2)	비교 기반 정렬

퀵 정렬	불안정	제자리	nlogn	n^2	비교 기반 정렬
합병 정렬	안정	제자리 아님	-	nlogn	비교 기반 정렬

힙 정렬	불안정	제자리	-	nlogn	비교 기반 정렬
계수 정렬	안정	제자리 아님	-	O(n + k)	분포 기반 정렬
기수 정렬	안정	제자리 아님	-	O(nk)	분포 기반 정렬
버킷 정렬	안정	제자리 아님	-	O(n + k)	분포 기반 정렬