Browse Tag: 알고리즘

[알고리즘]알고리즘 설계의 다섯가지 접근법

코딩인터뷰 완전분석 (게일 라크만 맥도웰 지음 ) 을 공부하면서 작성하는 글입니다.

알고리즘 문제를 풀기위한 설계는 5가지의 접근법이 있다.

  1.  예증
    일반적 규칙을 유도해내서 문제를 해결한다.
    ex) 거리, 시간 그리고 속도에 관한 문제 해결
  2. 패턴매칭
    기존의 문제와 유사한 문제를 떠올리고 그 문제의 해답(가령 알고리즘)을 수정해서 적용한다.
  3. 단순화와 일반화
    자료형이나 데이터 양과 같은 제약조건을 변경해서 문제를 단순화 해본다.
    단순화 된 버전의 문제를 해결한다면 최종적으로 일반화해서 찾은 알고리즘을 복잡한 형태로 다듬어 간다.
  4. 초기사례로부터의 확장
    초기사례(n=1)에 대해 문제를 푼다. 후에 n=2에 대한 문제를 풀어보고 n=3를 풀어본다.
    이후 N-1을 안다면 N을 어떻게 찾을 수 있을지 고민해보고 규칙을 찾아 문제를 해결한다.
  5. 자료구조 브레인스토밍
    일련의 자료구조를 차례대로 적용해보고 적절한 알고리즘을 찾아나가는 방법이다.
    연결리스트? 이진트리? 힙? 처럼 여러 자료구조를 이해하고 적응시킬 수 있는 능력이 중요하다.

이렇게 5가지 접근법으로 문제를 풀어나가 보자. 물론 기본적인 자료구조에 대한 이해는 반드시 필요하다.

출처 : 코딩인터뷰완전분석

2급수표

코딩인터뷰 완전 분석이라는 책을 보면 2급수표를 먼저 외우라고 요구한다.

2의 10승 까지야 보통은 외우고 있을 테지만..

그 후에 2의 16이 64K이고 2의 20승이 1MB 이며 2의 30승이 1GB 이라는 점은 외워두자

x 2^x 근사값 메모리 요구량(Bytes)
7 128
8 256
10 1,024 1,000(천) 1K
16 65,536 64K
20 1,048,576 1,000,000(백만) 1MB
30 1,073,741,824 1,000,000,000(십억) 1GB
32 4,294,967,296 4GB
40 1,099,511,627,776 1,000,000,000,000(조) 1TB

 

 

*출처 : https://github.com/loustler/data-structure-algorithm/wiki/2%EA%B8%89%EC%88%98%ED%91%9C(Power-of-2)

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

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