[240213] 알고리즘 리부트 5일차 - 백준 10158 자바

[Part1-Chapter02-Clip01]

 

시간복잡도란 입력 크기와 알고리즘 간의 관계를 나타내는데 우리는 주로 Big-O 표기법으로 나타낸다. 문제에서 정의된 입력 데이터 중 가장 최악의 상황을 포함한 시간의 상한선을 말한다. 입력된 값과 연산을 고려했을 때 도출되는 시간복잡도 중 상수는 제외한다. 즉, O(3N+2)일 경우 3과 2는 제외하고 시간 복잡도는 O(N)이라고 말할 수 있다. 이는 입력된 값에 비례하는 시간복잡도를 가졌다는 것을 의미한다. 이를 통해 우리는 입력 크기에 대해 우리가 작성한 프로그램의 동작시간을 가늠해볼 수 있다. 아래 그래프는 n의 크기에 따른 실행속도 N을 보여주며, 표는 입력값의 범위에 따라 최대 허용되는 시간 복잡도를 대략적으로 유추한 참고 값이다.

코딩테스트에서 시간 제한이 빡빡하게 있는 경우 최악의 테케도 통과할 수 있는 코드를 작성해야 하는 것이다. 우리는 편의상 1초에 약 1억 번 연산을 한다고 가정하면 좋다. 하지만 알아두어야 할 것은 시간 복잡도는 상대적 지표라는 점. 

 

예시)

최댓값을 찾는 방법에는 1) 모든 요소를 반복문을 통해 순회하며 최댓값을 찾는 법(O(N)), 2) Arrays.sort()를 통해 정렬한 후 맨 뒤 요소를 도출하는 법(O(NlogN) 또는 O(N^2)) 3) 아래의 방법이 있다. 일정 수 이상으로 커지면 시간 복잡도를 고려해 1번으로 진행할 것이고 만약 수가 그리 크지 않다면 구현하기 편한 방식으로 진행할 것이다. 그런데 강사님은 아래 방식을 알고 있다면 이 방법이 제일 좋다고 하는데 아래 메서드도 알아보기!

 

참고. java의 경우 인터프리터 동작시간도 있어 컴파일 방식만 있는 C/C++ 계열보다 실행 속도가 느린 편이다. 그래서 코딩테스트에서 java를 사용해 치르는 경우 보정값이 적용되기도 한다.

 

 

[Part1-Chapter02-Clip02]

 

- 백준 10158 개미

 

 

 

 

 

첫번째 풀이에서는 모든 경우를 다 돌아보려고 했기에 최악의 경우 2억번을 돌게 되고 0.15초 제한에서는 당연히 시간초과.. 주기를 구했을 때 최악의 경우 16억번을 돌아야 한번의 주기를 알 수 있어서 풀리지 않을 것 같지만 그래도 구현한 것이 아래 왼쪽 풀이이다.

 

도저히 모르겠어서 강의를 스킵하며 본 장면에서 '행과 열의 주기'를 보고 바로 닫고 구현해봤다. 행과 열을 분리해서 보니 순서가 보이더라.. 반복되는 값을 몇번 계산해보니 경계에 해당하는 인덱스에서 일정 배수의 순서를 가지는 것을 확인했다. 그대로 수학적으로 논리를 적용해보니 정답.. 너무 간단해서 속이 다 상할 지경.. 그런데 다른 사람들 풀이랑은 다소 달라서 그것도 고민할 예정

 

 

 

강의에서의 풀이 인사이트는 아래와 같다. 아래의 풀이는 모듈러를 활용해 주기성을 제외하고 한 칸 씩 이동해 최대 4만번의 연산을 수행하는 풀이이다. 행과 열의 경계에 대해서 각 행과 열의 2배의 주기를 가진다는 것을 파악했기 때문에 모듈러를 활용해 X(T) = X(T%2W) 임을 알 수 있다. 여기서 4만이 최대라서 가능한 부분이지 만약 시간 제한을 넘는 입력값이 주어진다면 또 다시 시간초과가 발생한다.

 

 

위를 보완하기 위한 풀이로서 시간 복잡도 O(1)을 가지는 풀이이다. P가 아니라 0에서 시작한다고 했을 때의 P+T의 시간 후의 위치를 구하면 된다.