반응형

알고리즘 3

[Algorithm] 알고리즘 별 시간 복잡도 비교해보기

문제 [-7, 4, -3, 6, 3, -8, 3, 4]로 이루어진 1차원 배열이 있을 때 합이 최대인 부분 구간을 찾는 알고리즘을 만들어보도록 하겠다. 최대 합을 갖는 구간은 [4, -3, 6, 3]으로 합이 10이다. ※python 언어를 사용하여 구현함. BruteForce 알고리즘 : O(N^2), O(N^3) inefficient_max_sum()함수는 주어진 배열의 모든 부분 구간을 순회하면서 그 합을 계산하는 알고리즘이다. 이 알고리즘은 O(N^2)개의 후보 구간을 검색하고, 각 구간의 합을 구하는데 O(N)의 시간이 걸리기 때문에 이 함수의 총 알고리즘 시간 복잡도는 O(N^3)이 된다. better_max_sum()함수는 위의 함수를 조금 변형하여서 O(N^2)의 시간 복잡도를 나타낸다. ..

[Algorithm] 코딩과 디버깅에 관하여

읽기 쉬운 코드 코딩 테스트에서 좋은 성적을 내기 위한 비결을 당장 빨리 코드를 작성하는 것이 아니라 읽기 쉬운 코드를 작성하는 것이다. 복잡하고 읽기 어려운 코드는 디버깅에 있어서 어려움이 있고, 한 번에 정확하게 작성하기도 어렵기 때문이다. 아래는 특별히 중요한 몇 가지 원칙들에 관하여 설명한다. 전역 변수의 광범위한 사용 전역 변수를 많이 사용하면 프로그램의 흐름을 파악하기 어려워지고 때문에 대개 사용을 지양한다. 하지만 짧은 시간 안에 알고리즘을 평가하는 코딩 테스트의 경우에는 작성하는 코드의 구조가 매우 단순하고 각 변수를 읽고 쓰는 부분이 어디인지 비교적 명확하기 때문에 전역 변수를 사용하더라도 잃는 것이 많지 않다. 적극적인 코드 재사용 간결한 코드를 작성하기 위한 가장 직접적인 방법은 코드..

[Python] python으로 알고리즘을 공부해야 하는 이유

파이썬은 처음 배우기 좋은 언어로 많이들 추천하는 언어이다. 파이썬은 초보 프로그래머가 어려운 문법에 허우적거리게 만들지 않고 프로그래밍의 핵심적인 개념을 정말 쉽게 배울 수 있게 만드는 훌륭한 언어이다. 파이썬을 통해서 좋은 프로그래밍 스타일을 한번 배워두면 다른 언어를 습득하는 것이 무척 쉬울 뿐만 아니라 다른 언어로 만든 프로그램마저도 고급스러워지는 효과를 발휘하곤 한다. 파이썬은 컴퓨터 프로그래밍 교육을 위해 많이 사용하지만, 기업의 실무를 위해서도 많이 사용하는 언어이다. 그 대표적인 예가 바로 구글이다. 필자는 구글에서 만든 소프트웨어의 50% 이상이 파이썬으로 작성되었다는 이야기를 들었다. 이외에도 많이 알려진 예를 몇 가지 들자면 온라인 사진 공유 서비스 인스타그램(Instagram), 파..

Language/Python 2019.10.09
반응형