반응형

Computer Science/Algorithm 5

[Algorithm] leetcode: Validate Binary Search Tree (python)

주어진 Binary Search Tree가 유효한지를 확인하는 알고리즘입니다. Binary Search Tree는 하나의 root node가 존재할 경우 왼쪽에 있는 모든 노드는 해당 node보다 값이 작아야 하고, 오른쪽에 있는 모든 노드는 root node보다 값이 커야합니다. 때문에 바로 이전의 노드의 값과 비교하여 왼쪽이라면 이전 노드의 값보다 작은 지를 비교하고, 오른쪽으로 가게 되면 이전 노드의 값보다 큰지를 비교하면 됩니다. 하지만 만약 아래와 같은 케이스라면 어떨까요? 3 / \ 1 5 / \ 2 6 2은 5보다 작지만, 5 이전의 node인 3보다도 값이 작게 됩니다. 이는 오른쪽에 있는 node는 모두 기준이 되는 node보다 값이 커야 한다는 rule을 벗어납니다. 이러한 경우는 이전..

[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] 시간 복잡도(time complexity)와 알고리즘 수행 시간

빠른 알고리즘을 만들기 위해 가장 먼저 해야 할 일은 바로 알고리즘의 속도를 측정하는 것이다. 이러한 알고리즘의 속도를 비교하는 가장 직관적인 방법은 각각을 프로그램으로 구현한 뒤 같은 입력에 대해 두 프로그램의 수행 시간을 측정하는 것일 것이다. 하지만 이러한 방법은 일반적인 기준이 되기에는 부적합하다. 프로그램의 수행 시간은 사용한 프로그래밍 언어, 하드웨어, 운영체제, 컴파일러까지 수많은 요소에 의해 바뀔 수 있기 때문이다. 그렇다면 알고리즘의 수행 시간을 어떤 기준으로 측정해야 할까? 반복문이 알고리즘 수행 시간을 지배한다. 한 가지 항목이 전체의 대소를 좌지우지하는 것을 지배한다(dominate)라고 표현한다. 알고리즘에서 이러한 역할을 하는 것이 바로 반복문이다. 물론 입력에 상관 없이 항상 ..

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

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

[Algorithm] Algorithm 문제에 접근하는 방법

문제 해결 능력이란? 알고리즘 문제란 대개 '어떤 값을 읽어 들여 어떤 값을 계산하는 프로그램을 작성하시오.'와 같은 형태를 갖는다. 이러한 문제를 풀기 위해서는 프로그램이 사용할 수 있는 최대 메모리와 시간제한 등 다양한 제약 조건이 있다. 이러한 제약 조건과 요구사항을 이해하고 최선의 방법을 찾아내는 능력을 문제 해결 능력이라고 한다. 문제 해결 능력은 프로그래밍 언어나 알고리즘처럼 실체가 없는 추상적인 개념이다. 그래서 단순한 반복만으로는 능력을 향상시키는데에 어려움이 있다. 좋은 문제 해결자가 되기 위해서는 좀 더 높은 차원의 수련이 필요하다. 이를 위해서는 자신이 문제를 어떤 방식으로 해결하는지를 의식하고 어느 부분이 부족한지, 어떤 부분을 개선해야 할지 파악해야 한다. 문제 해결 과정 1. 문..

반응형