포시코딩

개요 지금껏 시간복잡도에 대해선 무엇인지, 어떻게 구하는지에 대해서만 알았지 구체적으로 어떤 상황에 쓰이는지는 적절한 상황이 없었는데 코딩테스트를 준비하며 시간 제한, 메모리 제한 등과 함께 같이 제시된 조건들을 기준으로 시간복잡도를 생각해 어떤 알고리즘을 사용할 수 있을지 유추하기도 한다는 정보를 알게 되었다. 시간복잡도 O(1) 상수 시간(Constant time) O(log N) 로그 시간(Log time) O(N) 선형 시간 O(N log N) 로그 선형 시간 O(N^2) 이차 시간 O(N^3) 삼차 시간 O(2^n) 지수 시간 위는 자주 사용되는 시간복잡도로, 위쪽일수록 빠르다. 컴퓨터 과학에서 특정 알고리즘의 시간복잡도가 O(N^k)일 때, 이를 '다항 시간에 동작하는 알고리즘' 이라고 말한다..

예제를 통해 이중 for문의 시간복잡도를 구해보자 algorithm sum(A, n): sum = 0# 1번 for i=0 to n-1 do# n번 for j=i to n-1 do# 아래에서 설명 sum += A[i] * A[j]# 3번 return sum 각 for문의 돌아간 횟수 i j 0 n 1 n-1 2 n-2 ... ... n-1 n-(n-1)=1 식으로 나타내기 for j=i to n-1 do # 여기서 i가 n-1이라면 j=도 n-1이 되고 to n-1 즉, n-1이 n-1이 될 때 까지니까 한 번 돌게 된다. # 규칙을 부여해서 찾는다면 n-(i의 시작 수)가 되니 n-(n-1)이 되어 n-n+1 즉, 1이 되는 방법도 있다. 결국 이중 for문의 횟수는 위 표의 j 밑에 있는 값들을 모두..

2진 탐색 인덱스가 0부터 16까지 있는 array가 있을 때 그 중 정답이 target인 값을 찾으려면 어떻게 해야할까? for문을 통해 처음부터 하나씩 비교하는 방법이 있겠지만 맨 마지막에 정답이 있으면 O(N) 만큼의 시간 복잡도가 걸리게 될 것이다. 이 때, 2진 탐색이라는 방법을 통해 시도 횟수를 확 낮출 수 있다. 딱 가운데 위치하는 값을 정답과 비교해서 정답이 더 크다면 가운데 위치하는 값 이하의 인덱스를 모두 버리고 정답이 더 작다면 가운데 위치하는 값 이상의 인덱스를 모두 버리는 식으로 구하며 이를 반복하면 된다. 이는 알고리즘 문제에서 UP & DOWN 문제로도 자주 나오는 형태이다. 문제풀이 예시 시간 복잡도 O(log N) 총 숫자가 1 ~ N 까지라고 한다면 1번 탐색하면 반절이 ..