NAVER 부스트코스 CS50 - 4. 알고리즘

4. 알고리즘

 

4-1 검색 알고리즘

배열은 한 자료형의 여러 값들이 메모리상에 모여 있는 구조이다.

어떤 값이 배열 안에 속해 있는지를 찾아 보기 위해서는 배열이 정렬되어 있는지 여부에 따라

다음과 같은 방법을 사용할 수 있다.

 

선형검색: 배열의 인덱스를 처음부터 끝까지 하나씩 증가시키며 그 값이 속하는지 확인

이진검색: 배열이 정렬되어 있다면, 배열 중간 인덱스부터 시작해 찾고자 하는 값과 비교하며

    그보다 작은 인덱스 또는 큰 인덱스로 이동을 반복

 

4-2 알고리즘 표기법

O( ): 알고리즘 실행 시간의 상한을 나타낸 것

Ω( ): 알고리즘 실행 시간의 하한을 나타낸 것

Θ( ) : 알고리즘 실행 시간의 평균 시간

좋은 알고리즘은 Big-O 값이 좋은 알고리즘.

 

4-3 선형검색

strcmp( ) : 문자열을 비교하는 함수. 두 문자열이 같다면 0을 반환.

      양수를 반환하면 첫 번째 문자열이 알파벳 기준으로 큰 경우. 음수면 반대의 경우

typedef struct: 구조체를 정의해서 여러가지 자료형을 담는 그릇을 만드는 것 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4-4 버블 정렬 O(n^2)

두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법

정렬이 되어 있는지 여부에 관계 없이 루프를 돌며 비교 해야 하므로 실행 시간의 상한과

하한 모두 n^2이 된다. 

정렬되어 있는 리스트를 받을 경우 하한시간은 n 

 

4-5 선택 정렬 O(n^2)

배열 안의 자료 중 가장 작은 수를 찾아 첫 번째 위치의 수와 교환해주는 방식의 정렬

버블 정렬과 마찬가지로 루프를 돌며 값을 비교 해야 하므로 실행 시간의 하한도 n^2가 된다

 

4-6 정렬 알고리즘의 실행시간

https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html

정렬 알고리즘의 시각화 페이지

 

https://youtu.be/es2T6KY45cA

부스트코스 슬랙에서 다른 팀 리더분이 공유해 주신 유튜브 영상. 다양한 알고리즘 계산복잡도를 시각화 해서 보여준다.

 

4-7 재귀

함수가 본인 스스로를 호출해서 사용하는 것

재귀적 정의: 눈에 보이는 혹은 가상의 물체의 구조를 그 물체의 자체를 이용해서 설명하는 것 

조건문으로 의도치 않게 반복되는 것을 막아야 함

 

4-8 병합 정렬

원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가며 정렬을 하는 방법

실행 시간의 상한과 하한 모두 n*log n

 

 

// 4주차는 알고리즘이라 그런지 미션이 코딩테스트? 같은 형식으로 나왔는데, 꽤 재밌게 풀었다. 물론 모든 문제를 풀진 못했지만.. 

그리고 4주차 동기부여 영상은 딥러닝과 머신러닝에 관한 내용이여서 굉장히 흥미롭게 봤다. 그리고 딥러닝에 관한 다양한 자료들을 얻을 수 있는 곳들도 알게 됐는데 이를테면

 

edwith [부스트코스] 텐서플로우로 시작하는 딥러닝 기초. 

논문을 읽고 강의하는 모임인 PR12(Paper Readers 12) - 유튜브를 통해 공개 돼 있다.

텐서플로우 코리아 - 국내 최대 AI커뮤니티(페이스북)

 

등이 있다. 코딩 뉴비 챌린지가 끝나는대로 파이썬을 사용해 진행하는 데이터 사이언스 강의 2개를 들을 예정이다.

 

그리고 미션우수제출팀으로도 선정되고 내가 제출한 답안이 우수사례로 뽑혀 다른 팀에게도 코드가 공유 됐는데, 굉장한 동기부여가 됐다.

주어진 정렬을 사용하지 않고 그냥 내가 생각나는대로? 편한대로 풀었는데 아마 주석을 잘 달아놓은게 가장 큰 이유였던 것 같다.

주석을 적어 놓으니 나중에 볼 때도 이해가 더 잘 됐고, 아마 다른 사람이 봤을 경우엔 더 그러지 않았을까 싶은데

글을 적는 습관을 만드는 데 일부라고 생각하고, 논리적으로 생각하는 습관도 기를 겸 주석 활용을 잘 해야 겠다.