Browse Tag: python

[python]파이썬에서의 for … else 문

파이썬에서는 다른 언어에서 제공하는 for문 기능 외에 다양한 기능들을 제공한다

그 중 for .. else 문에 대해 소개해본다

기본적으로 for문 에 break 가 포함 되어 있을때 사용가능한데

for문을 순회 하던 중 break를 만나면 for문을 빠져나오는건 일반적인 언어와 같지만

break 문을 만나지 않았다면 for문 종료 이후 else 문이 실행된다.

위 의 코드의 결과는

0
1
2
3

이다.

그렇다면 break문을 만나지 않는 for문은 어떻까?

코드 실행 결과는

0
1
2
3
4
else statement is called

이다.

 

위의 경우 처럼 for else 문을 사용한다면 flag 같은 변수를 사용하지 않아도 되서 코드가 훨씬 깔끔해 진다.

[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 에서 퍼왔다. 이 분 블로그 타이틀이 무섭더라.

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