나동빈4 이것이취업을위한코딩테스트다 - Chapter 03 1.당장 좋은 것만 생각하는 그리디 이전 글: 이것이취업을위한코딩테스트다 - Chapter 01 코딩테스트 개요 3. 시간과 메모리 측정 주제 그리디 알고리즘에 대해 알아보자. 이름에서 알 수 있듯이 어떠한 문제가 있을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘이다. 내용 탐욕적이라는 말은 '현재 상황에서 지금 당장 좋은 것만 고르는 방법'을 의미한다. 그리디 알고리즘의 문제 유형은 앞으로 다루게 될 알고리즘과 비교했을 때 '사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형'이라는 특징이 있다. 반면 이후에 공부할 정렬, 최단 경로 등의 알고리즘 유형은 이미 그 알고리즘의 사용 방법을 정확히 알고 있어야만 해결이 가능한 경우가 많다. 예제 3-1 거스름돈 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, .. 2021. 7. 28. 이것이취업을위한코딩테스트다 - Chapter 01 코딩테스트 개요 3. 시간과 메모리 측정 이전 글: 이것이취업을위한코딩테스트다 - Chapter 01 코딩테스트 개요 2. 복잡도 - 공간 복잡도 (tistory.com) 주제 알고리즘의 소요 시간을 확인하는 방법을 알아보자. 내용 파이썬에서는 프로그램 수행 시간과 메모리 사용량을 측정할 수 있다. 실질적으로 알고리즘의 소요 시간을 확인해야 자신이 제대로 알고리즘을 작성하고 있는지 체크할 수 있다. 다시 말해 실제 프로그램의 수행 시간을 측정하는 것은 알고리즘의 효율성을 측정하는 가장 기본적인 방법이다. import time start_time = time.time() # 측정 시작 # 프로그램 소스코드 end_time = time.time() print("time :", end_time - start_time) # 수행 시간 출력 수행 시간 .. 2021. 3. 28. 이것이취업을위한코딩테스트다 - Chapter 01 코딩테스트 개요 2. 복잡도 - 공간 복잡도 주제 복잡도는 알고리즘의 성능을 나타내는 척도이며, 공간 복잡도에 대해 알아보자. 내용 공간 복잡도를 표기할 때도 시간 복잡도를 표기했던 거처럼 빅오 표기법을 이용한다. 즉, 공간 복잡도 또한 O (Nlog), O(N^2) 등으로 표기한다. 다만, 앞서 시간 복잡도에서 1초라는 절대적인 제한이 있던 것처럼, 메모리 사용량에도 절대적인 제한이 있다. 일반적으로 메모리 사용량 기준은 MB 단위로 제시된다. 코딩 테스트 문제는 대부분 리스트(배열)를 사용해서 풀어야 한다. 정수형 자료형인 INT를 기준으로 리스트 크기에 따른 메모리 사용량을 확인해보자. - int a[1000]: 4KB - int a[1000000]: 4MB - int a[2000][2000]: 16MB 코딩 테스트에서는 보통 메모리 사용량을.. 2021. 3. 28. 이것이취업을위한코딩테스트다 - Chapter 01 코딩테스트 개요 1. 복잡도 - 시간 복잡도 주제 복잡도는 알고리즘의 성능을 나타내는 척도이며, 시간 복잡도에 대해 알아보자. 내용 시간 복잡도: 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지는 의미한다.공간 복잡도: 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미한다. 효율적인 알고리즘을 사용한다고 했을 때 보통 시간 복잡도와 공간 복잡도는 일종의 거래 관계(trade-off)가 성립한다.메모리를 조금 더 많이 사요아는 대신에 반복되는 연산을 생략하거나 더 많은 정보를 관리하면서 계산의 복잡도를 줄일 수 있다. 시간 복잡도 알고리즘 문제를 풀 때 단순히 '복잡도'라고 하면 보통은 시간 복잡도를 의미한다. 코딩 테스트에서는 작성한 프로그램이 모든 입력을 받아 이를 처리하고 실행 결과를 출력하는 데까지 걸.. 2021. 3. 27. 이전 1 다음