알고리즘이란? 어떤 문제를 해결하기 위한 방법과 절차 등의 집합체를 말합니다. 문제 해결을 위해서는 여러 알고리즘을 고안하고, 이들의 효율성을 평가한 후 최적의 알고리즘을 사용하는 것이 올바른 접근법입니다. 알고리즘은 아래의 5가지를 모두 만족해야 합니다. 0개 이상의 입력이 존재 1개 이상의 출력이 존재 각 명령어의 의미가 명확해야함(명백성) 한정된 수의 단계 후에는 반드시 종료(유한성) 각 멍령어가 실행 가능해야함(유효성) 알고리즘의 효율성 분석 좋은 알고리즘은 실행 시간이 빠르고, 메모리 사용량이 적은 알고리즘입니다. 하지만 일반적으로 실행시간이 빠르면 그만큼 많은 메모리 공간을 필요로 하고, 메모리 공간을 적게 사용할수록 실행시간이 느립니다. 따라서 우리는 실행 시간과 메모리 사용량 모두 적절하게..

def solution(A): P1 = 0 P2 = sum(A) stack = [] for i in range(1,len(A)): P1 += A[i-1] P2 -= A[i-1] ans = abs(P1-P2) if len(stack) == 0: stack.append(ans) elif stack[-1] > ans: stack.pop() stack.append(ans) return stack[-1] sum의 시간복잡도는 O(n)이기 때문에 반복문에 들어가면 O(n**2)의 시간 복잡도가 나온다. 그러니 단순히 sum을 해주고 n-1까지 더하고 빼기를 반복하면 해결된다.

def solution(A): if len(A) == 1 and A[-1] == 1: return 2 if len(A) == 1 and A[-1] != 1: return 1 A.sort() for i in range(len(A)-1): if A[i+1] != A[i]+1: return A[i]+1 if 1 not in A: return 1 return A[-1] + 1 처음에는 그냥 sort와 반복문을 이용했는데 1이 시작이 아닌 경우와 모든 N+1이 존재할 경우 길이가 하나인데 값이 2인 경우 등을 생각하지 못해 점수가 50이 나왔고 해당 부분을 처리해주니 O(n)에서 O(n log n)의 시간 복잡도가 나왔다.

def solution(X, Y, D): if X==Y: return 0 first = X + D ans = ceil((Y-first) / D) return ans+1 문제의 범위가 1,000,000,000이니 반복문을 사용하면 안된다고 판단했다. 처음 점프를 한 값에서 목표 거리를 뺀 부분을 점프 거리로 나누고 올림을 해주면 필요한 점프 수가 나온다. 이 값을 처음에 점프한 1을 더해주면 값이 나오고 시간 복잡도는 O(1)이다.