Browse Tag: edx

[edx]6.00.1x Computational Thinking

참 좋은 강의이다.

문제가 아직 남았지만 교수님이 하는 강의자체는 다 들은 시점에서 참 좋은 강의라고 느낀다.

이 강의를 따라 가면서 전산과 출신이 아닌 사람으로써 Computational Thinking 을 위한 다양한 연습을 하고 도구들을 배우므로써

주어진 문제에 대해 좀 더 Computational Thinking 할 수 있게 되었다고 생각한다.

마지막 wrap up 강의에서 기억 나는 두가지는

  1. 프로그램을 만들기전 pseudo code 를 작성해서 문제 해결을 위한 추상화, 알고리즘 등을 먼저 생각해보는 것
  2. 문제를 작고 간단한 단위로 나눠서 recursive 하게 생각하는것

이 두가지는 짧은 경력이지만 2년간 개발을 하면서 전혀 하지 않았던 행동들인데 앞으로 연습해서 좋은 습관으로 만들어야겠다.

이제 남은 문제까지 잘 마무리하자

마무리 후에는

6.00.2x  수강 예정

https://courses.edx.org/courses/course-v1:MITx+6.00.2x_4+3T2015/courseware/b33b3ed61da74919872a3d5ac354c512/

[edx]Lecture13 데이터 구조 tree

13강은 데이터 구조 중 트리에 관한 강의이다.

트리 구조는 쉽다. root가 있고 자식이 있고 각각의 step을 노드로 부른다.

하지만 트리구조는 list 나 dictionary 처럼 key 나 index 로 search 할 수  없다.

그래서 트리 search를 위한 두가지 알고리즘이 존재한다. ( 강의 에서 바이너리 트리만 다뤘으므로 이 글에서의 트리는 기본적 바이너리 트리이다.-자식이 두개인 트리)

  1. depth-first
    depth-first 알고리즘은 트리를 탐색할 때 왼쪽 자식부터 탐색하는것이다. 왼쪽 탐색을 마치면 부모의 오른쪽 자식을 탐색한다.
  2. breadth-first
    breadth-first 알고리즘은 레벨 별로 탐색하는 것이다. root 부터 자식, 자식, 자식 순으로 탐색한다.

특별히 두가지 알고리즘의 장단점은 없다.(depth-first 알고리즘이 복잡한 연산에서 더 빠른것 처럼 이야기하던데…)

그리고 Decision Tree가 나오는데 주어진 조건에 대해 가능한 경우의 수를 트리 구조로 표현한 것 이라고 이해하면 될 것 같다.

Decision Tree 를 만든 후에는 주어진 문제를 해결하기 위한 다양한 방법을 적용할 수 있었다.

주어진 문제는 knapsack problem 인데 무게와 가치를 고려해서 가방에 최대한으로 담을 수 있는 아이템을 찾는? 그런 문제였다.

 

강의가 마무리 된건 아니지만 강의 후반부에서 느끼는 건 이번 강의를 통해서 문제를 해결하는데 다양한 관점으로 생각할 수 있게 된점이 잘된점인 것 같다.

Search 를 할때 그 데이터 구조가 list 인지 tree 인지 를 고려해서 binary search 인지 merged search 인지 등 복합도를 계산해서 최적의 알고리즘을 찾거나 tree경우 decision tree 를 만들어서 문제를 해결하는 방법을 찾는 등 좋은 강의인것 같다.

알고리즘을 공부하는데 있어서 가장 큰 벽은 수학이고 두번째는 제귀적으로 생각하는 연습이 부족한 것 같다. solution 이 나와 있어도 제귀적으로 풀었다면 그것을 이해하는데 꽤 시간이 걸린다.

제귀적으로 생각하는 연습을 하는게 큰 도움이 될 것 같다.

이 강의가 끝나면 알고리즘 책 같은걸 사서 공부해야하나?

[edx]MITx: 6.00.1x -Week6 Lecture12

객체 지향 프로그래밍에 관한 이야기이다.

상속이 나오고 부모 클래스와 자식 클래스간의 오버로딩의 경우 어떤게 실행되는가에 대해서도 나온다

영어가 부족해서 문제가 잘 이해가 안되서 못풀고 있는데

그렇게 어려운 내용은 아니다.

하지만 뒤에 나오는 Python 의 제너레이터 ( yield )는 이해하기가 힘들다.

Python 에는 특별한 클래스가 있다. 제너레이터이다.

프로시져에 yield 라는 예약어를 사용 하면 해당 프로시져는 제너레이터가 되는데

특이한게 제너레이터는 next() 메소드를 가지는데 실행하면 yield 지점 까지 실행된 후 해당 결과를 return 하고 정지된다.

이런 제너레이터를 사용하는 이유가 대용량 리스트 연산의 경우 리스트를 저장하기 위한 메모리를 할당해야하는데 대용량 데이터를 실행때마다 저장하는것이 비효율적이기 때문에 제너레이터를 사용해서 하나씩 빼서 연산 한다 정도로 이해된다.

강의 후에 구글링을 해봤는데 정확히 이해하고 글을 쓴사람은 찾기 힘들었다 ㅠ

쫌더 찾아본 결과 (제너레이터는 스택영역에 쌓이지 않고 별도의 스택을 만들어서 동작하도록 한다) 라고 나온다.

여튼 결론적으로 대용량 리스트의 연산시 제너레이터를 사용하는 것이 효율적이다.

[EDX]Introduction to Computer Science and Programming Using Python-Week5(2)

week5 – lecture 10

Search 알고리즘에 관한 강의이다

먼저 Simple한 방법이 소개되는데 search를 위해서 주어진 L(L은 list라고 가정한다)의 길이만큼 for문을 돌면서 일치하는 것이 존재하는지 찾는 방법이다. 심플 검색의 복잡도는 O(len(L)) 이된다.  선형 의 복잡도는 엄청 나쁘지는 않지만 더 나은 방법을 고려해본다.

“I need to know, can I do better?”

*이하 len(L)은 N으로 표현한다

이분검색(Binary Search)를 이용한다면 검색 알고리즘은 O(log(N))로 향상 될 수 있다.  하지만 Binary Search의 경우는 정렬(sorting)이 되어야 가능하다는 문제가 잇다. 그렇다면? sorting 을 위한 cost는 어떤가? 그래서 sorting 알고리즘을 알아본다.

sorting 알고리즘에는 다양한 방법이 있지만(아마 정보처리기사 공부하면서 봤던 기억이….) 이번 강의에서는 선택정렬(selection sort)와 합병정렬(merge sort)가 등장한다.

먼전 선택정렬이다. 이제 Big O 표기법을 배운이상 존재하는 알고리즘에 대해서는 복잡도를 계산해서 Big O 표기법으로 표시한다. 그래서 어떤 알고리즘이 효율적인지 비교하는데 선택정렬은 복잡도가 O(N^2) 이다. 이런…

그럼 sorting 하고 검색하면 O(N^2) + O(log(N)) … 그냥 심플한 방법으로 O(N)이 낫다.

그럼 여기서 끝인가?

개발 경력 2년밖에 안되지만 좋은 개발자가 되기 위해서는 항상 물어봐야한다고 생각한다.

“I need to know, can I do better?”

합병정렬(merge sort)의 복잡도는 얼마인가? 합병정렬은 L을 쪼개서 각각 sorting한다음에 합치는 방법인데 결론만 이야기하면 O(N*log(N))이다.

그렇다면???

합병정렬로 sorting 하고 검색하면?   O(n*log(n)) + O(k*log(n))  – k는 검색 횟수

그렇다. 심플 검색 O(N)보다 합병정렬이후 이분검색이 더 효율적인 알고리즘이다.

특히 검색을 여러번 실행해야 할 경우 sorting 을 위한 cost는 amortize cost(상환비용)이다. 

그럼 위의 방법보다 더 나은 방법은 없는가?

Hash 가 나온다.

Hash 란 key 를 가지는 데이터 구조인데 key를 int로 변환해서 index로 사용한다. 따라서 Hash 로 저장된 데이터의 경우 검색 복잡도는 O(1)이다.

이런

앞선 방법 보다 비교할 수 없을 만큼 효율적이다.

어떤 검색 알고리즘을 사용해야할 지는 알아서 판단하자.

“I need to know, can I do better?”

 
Continue Reading

[EDX]Introduction to Computer Science and Programming Using Python-Week5

Week 5

시간 복합도에 관한 강의였다.

시간 복합도는 프로그램이 실행되는 시간에만 집중한 것으로  Input에 따라 Best Case, Worst Case, Average Case로 계산 될 수 있다.

이후 Random Access Model 이 나온다. Random Access Model 이란 Count Machine 같은 모델인데 컴퓨터가 실행하는 코드를 순서대로 count 하는 것이다. 이 때  실행시간(CPU 의 성능, OS의 성능,python 이나 java 같은 언어의 성능)은 무시되고 오직 step 만을 계산하는것이다.

위의 가정하에서 Random Access Model 에서는 시간 복합도를 input 의 크기 n 에 대해 a*n +b 나 n^2+4 처럼 나타낼 수 있는데 강의에서는 Worst Case에 집중한다.

Worst Case(input N이 굉장히 클때)에서는 a*n+b 에서 계수 a나 상수 b는 의미없는 수이다. 마찮가지로 a*n^2 +5 에서 계수 a나 상수 5는 의미없고 n^2만이 의미를 가지게 된다.

이럴때(Worst Case에서) 시간 복합도를 표현하기 위해 빅 O표현법(Big O Notation)을 사용하는데 a*n^2 +5의 경우 O(n) 으로 n^2+4의 경우 O(n^2)로 나타낼수 있다.

Instance N 에 따라(정확히 무슨말인지 모르겠다 ㅠ) 알고리즘은 아래와 같이 빅 O로 표현될 수 있는데

as_1-loudon23

위 의표는 그 알고리즘을 나타낸 표이다.

효율성의 측면에서 상수형으로 표현되는 알고리즘이 가장 좋은 알고리즘이고 지수형으로 표현 되는 알고리즘이 최악의 알고리즘이다.(하지만 경우에 따라 지수형으로 표현 할 수 밖에 없는 알고리즘도 존재한다 ex. 하노이의 탑)

N이 굉장히 클때 그 차이는 굉장히 크기 때문에 가능하다면 찾을 수 있다면 로그형이나 선형 알고리즘을 찾아 해결하는 것이 시간복합도 측면에서 효율적인 알고리즘이라 할 수 있다.

 

강의가 진행될수록 뭔가 수학적 개념이 자주 나오고 이해하기 어려워지고.. 쉽지 않구만

위의 표는 http://skmagic.tistory.com/164 에서 퍼왔다. 이 분 블로그 타이틀이 무섭더라.

“자기개발을 멈추면 죽는다.”