CS50 2강 알고리즘

📅 TIL #147

📅 TIL 💻 CS




🎯 Achievement Goals

Topic1: 입력한 자료를 출력하려면 어떤 과정이 필요할까요?
Topic2: 알고리즘을 이해하기 쉽게 표현하는 방법이 있을까요?
Topic3: 자료를 맨 처음부터 하나씩 비교하면서 찾는 방법은 무엇이라고 하나요?
Topic4: 인접한 두개의 자료를 차례로 비교하면서 정렬하는 것을 무엇이라고 하나요?
Topic5: 자료 중 가장 작은 것을 찾아 순서대로 정렬하는 방법은 무엇일까요?
Topic6: 정렬된 부분, 정렬되지 않은 부분 나누어 정렬하는 방법은 무엇일까요?
Topic7: 정렬 알고리즘의 효율성을 높이기 위해서는 무엇을 고려해야 할까요?
Topic8: 많은 자료를 분해하고 다시 합쳐 정렬하는 것을 무엇이라고 할까요?
Topic9: 정렬된 데이터에서 원하는 값 쉽고 빠르게 찾는 방법은 무엇일까요?







Intro.

오늘은 CS50 2강 알고리즘 강의를 다 들었다!! 알고리즘의 완전 기초적인 내용이여서 이해하는데 어려움이 없었다. 만약 코드 스테이츠를 수강하기 전에 들었더라면 어렵게 느꼈을 수도 있었겠다..


1강에는 생각해보기 문제들과 토픽 문제들에 대해서 나의 생각을 블로깅했었다. 2강의 토픽 문제들은 각 토픽의 제목 맞추기 수준이여서 생각해보기 문제들만 블로깅할 생각이다!!





알고리즘 - Topic1: 입력한 자료를 출력하려면 어떤 과정이 필요할까요?


김밥을 만드는 절차를 세분화해서 김밥 만드는 과정을 알고리즘으로 어떻게 표현할 수 있을까요?

  1. 김밥 재료와 필요한 도구를 가져온다.
  2. 김발위에 순서대로 김을 놓고 밥을 김 면적에 맞게 놓아준다.
  3. 이후에 김밥 재료(햄, 시금치, 단무지 등등)들을 놓는다.
  4. 김발을 사용해서 돌돌 말아준다.


1부터 100까지의 모든 숫자를 암산으로 더해봅시다. 각자 어떠한 방법으로 답을 찾아냈나요?

1 + 100 = 101, 2 + 99 = 101, 3 + 98 = 101, …. 이러한 방식으로 맨 처음과 맨 끝을 좁혀가면서 더해주면 101이 50개가 나온다.

그래서 101*50을 해주면 정답은 5050이 된다.





의사코드 - Topic2: 알고리즘을 이해하기 쉽게 표현하는 방법이 있을까요?


코드 작성법을 알고 있는데도 왜 의사 코드를 사용하나요? 의사 코드를 사용하면 어떤 이점이 생기나요?

의사코드는 문법 걱정 없이 알고리즘을 표현할 수 있는 유용한 방법이며 프로그램의 논리를 이해하는데 더 효과적인 방법이다.

그리고 알고리즘을 코드로 작성하기 전, 작성하는 사람의 명확한 의도를 나타낼 수 있고 의미 전달을 자유롭게 할 수 있는 이점이 있다.


의사 코드는 늘 텍스트 기반으로 작성되어야 하나요? 문제 해결 과정에서 의사 코드를 다른 방식으로 사용할 수 있나요?

의사 코드는 목적에 따라 작성할 수 있다. 꼭 텍스트 기반이 아니여도 프로그래밍 언어로도 충분히 표현할 수 있다. 작성자가 자유롭게 의도를 전달할 수 있다.





선형 탐색 - Topic3: 자료를 맨 처음부터 하나씩 비교하면서 찾는 방법은 무엇이라고 하나요?


언제 선형 탐색을 사용하는 것이 유용할까요? 유용하지 않은 경우는 어떤 경우일까요?

데이터가 정렬되어 있지 않을 때 사용하는 것이 가장 유리하다. 만약 데이터가 약 1억개가 넘는 엄청난 양이라면 지양하는 것이 좋다.





버블 정렬 - Topic4: 인접한 두개의 자료를 차례로 비교하면서 정렬하는 것을 무엇이라고 하나요?


bubblesort


버블 정렬이 효율적인 경우는 어떤 경우인가요? 반대로 어떤 경우에 비효율적이게 될까요?

장점 : 인접한 값만 계속해서 비교하는 방식으로 구현이 쉬우며, 코드가 직관적이다. n개 원소에 대해 n개의 메모리를 사용하기에 데이터를 하나씩 정밀 비교가 가능하다.
단점 : 최선이든 최악이든 O(N^2)이라는 시간복잡도를 가진다.


버블 정렬을 이용하여 4, 30, 49, 11, 5 를 정렬해 봅시다.

1번째 시도: 4,30,11,5,49
2번째 시도: 4,11,5,30,49
3번째 시도: 4,5,11,30,49

총 3번의 작업으로 정렬을 할 수 있다.





선택 정렬 - Topic5: 자료 중 가장 작은 것을 찾아 순서대로 정렬하는 방법은 무엇일까요?


selectsort


선택 정렬이 버블 정렬보다 선호되는 경우는 어떤 경우인가요?

n개 원소에 대해 n개의 메모리를 사용하기에 데이터를 하나씩 정밀 비교가 가능하며 정렬을 위한 비교 횟수는 많으나 교환 횟수는 상당히 적다는 것이 장점인 정렬 방식이다.

버블 정렬보다 선택 정렬이 swap을 더 자주 하지 않기때문에, 성능면에서 더 유리하다. 메모리가 제한적이며, 데이터의 양이 적으면 적을수록 선택 정렬이 더 유리하다.


선택 정렬을 이용하여 4, 30, 49, 11, 5 를 정렬해 봅시다.

1번째 시도: (4를 제외하고 가장 작은 수 5와 30을 교환한다.) 4, 5, 49, 11, 30
2번째 시도: (11과 49의 위치를 교환한다.) 4, 5, 11, 49, 30
3번째 시도: (30이 49보다 앞에 와야하므로 두 요소를 교환한다.) 4, 5, 11, 30, 49

3번의 교환으로 끝이 난다. 하지만 모든 요소에 대해 현재 요소가 그 다음으로 작은 요소인지 다른 요소들과 비교하는 과정이 많다.





삽입 정렬 - Topic6: 정렬된 부분, 정렬되지 않은 부분 나누어 정렬하는 방법은 무엇일까요?


insertsort


삽입 정렬이 다른 정렬 방법에 비해 갖는 장점과 단점은 무엇인가요?

버블 정렬, 선택 정렬과 비교 했을 때, 최선의 경우에는 O(n)의 시간 복잡도를 가진다. 또, 버블 정렬의 경우 비교 대상의 메모리 값이 정렬되어 있더라도 비교연산을 진행하나, 삽입 정렬은 버블 정렬의 비교횟수를 줄이고 크기가 적은 데이터 집합을 정렬하는 알고리즘을 작성할 때 효율이 좋다. 삽입 정렬은 자체만으로 효율이 좋기 때문에 버블 정렬이나 선택 정렬의 일부로 사용되는 경우도 있다.


삽입 정렬이 이전에 학습한 다른 정렬 방법보다 선호되는 경우는 언제인가요?

대부분의 원소가 정렬되어 있는 경우, 버블 정렬이나 선택 정렬보다 매우 효율적이다. 안정 정렬(stable sort)에 속하며, 상대적으로 빠르다.





시간 복잡도 - Topic7: 정렬 알고리즘의 효율성을 높이기 위해서는 무엇을 고려해야 할까요?


프로그램이 소비하는 자원을 측정하는 방법에는 어떤 것이 있을까요?

Big-O 표기법, Big-Ω 표기법이 있다. 최악의 경우를 나타낼 때는 Big-O 표기법을, 최선의 경우를 나타낼 때는 Big-Ω 표기법을 사용한다.


우리가 컴퓨터 프로그래머로써 어떤 코드를 작성하기 전에 어떻게 시간 복잡도를 분석할 수 있을까요?

탐색 방법이나 정렬, 알고리즘, 메소드(method)마다 시간 복잡도가 있다. 예를 반복문같은 선형 탐색은 O(n)의 시간복잡도이고, 이진 탐색은 O(logN)을 가진다. 버블 정렬, 선택 정렬, 삽입 정렬은 O(n^2)의 시간 복잡도를 가진다.

이처럼 각각 시간 복잡도가 있고 이를 통해 최악의 시간 복잡도, 또는 최선의 시간 복잡도를 분석할 수 있다.

코드로도 분석하는 방법이 있는데, 자바스크립트 같은 경우는 new Date().getTime()을 활용하여 개발자 도구에서 확인하는 방법이 있다.





합병 정렬 - Topic8: 많은 자료를 분해하고 다시 합쳐 정렬하는 것을 무엇이라고 할까요?


합병 정렬은 확실히 더 빠릅니다. 하지만 알고리즘이 어떻게 동작하는지 생각해보면, 그에 따른 단점이 떠오릅니다. 다른 정렬에는 없었던, 합병 정렬에서의 가장 큰 단점은 무엇일까요?

합병 정렬은 배열을 반으로 나누어가면서 나눈 값들을 임시 배열에 저장을 한다. 즉, 공간이 계속 늘어난다. 시간적인 측면에서는 좋지만, 추가적인 메모리가 필요하다는 것이 합병 정렬의 가장 큰 단점이다.


우리가 지금까지 다뤄본 알고리즘 중에 가장 마음에 드는 것은 무엇인가요? 그 이유는 무엇인가요?

지금까지 CS50을 통해 버블 정렬, 선택 정렬, 삽입 정렬 그리고 합병 정렬을 배웠다. 가장 마음에 드는 것은 합병 정렬이다. 구현 방식이 다른 정렬들에 비해 조금 까다롭지만, 다른 정렬들은 최악과 최선에 따라 시간 복잡도가 다르지만, 합병 정렬은 무조건 절반으로 분할하기에 성능이 달라지는 경우가 없다. 따라서 항상 O(N * logN)이라는 시간복잡도를 가지게 된다. 이 부분이 선택한 이유이다.





이진 탐색 - Topic9: 정렬된 데이터에서 원하는 값 쉽고 빠르게 찾는 방법은 무엇일까요?


어떤 조건일 때 이진 탐색을 하는 것이 선형 탐색을 하는 것보다 효율적인가요?

보통 알고리즘 문제를 풀 때 입력의 크기가 제한 되는 경우가 있다. 자바스크립트 기준으로 입력값의 크기가 1억이 넘어가는 경우 이진 탐색을 활용한다. 이처럼 방대한 양의 데이터가 주어진 경우 이진 탐색이 더 효율적이다.


64개, 4096개, 4294967296개의 데이터에 이진 탐색을 수행하는데 최대 몇 번의 과정을 거쳐야 할까요?

let n = 64 or 4096 or 4294967296;
let i = 0;
  while(n > 1) {
	  n = n / 2;
	  i++
  }
console.log(i)







마무리.


지금까지 CS50의 1강과 2강 강의를 모두 들었다. 3강까지는 기초적인 부분이라 어려움 없이 들었다. 기본적인 개념이여도 한 번 또 들어보니 개념들이 확실하게 정리되는 기분이 들었다.


2강에서 배운 정렬들 모두 코드 스테이츠 수강을 하면서 직접 구현한 경험이 있다. 하지만 알고리즘을 풀 때는 sort메소드만 사용했었다. 지금 생각해보면 직접 정렬을 구현할 일은 없지만, 원리를 알고 있는 것도 컴퓨터 원리를 공부하는데에 큰 도움이 된다고 생각한다.




edwith X 커넥트재단: CS50 강의 들으러 가기




← Previous Post Next Post →