시간복잡도1 시간 복잡도를 믿고, 나를 의심하기 알고리즘과 관련된 코딩을 하다보면, 시간 복잡도 O(n), O(n^2) 이런 것들을 고려해 접근하게 된다. 예시로 함께 해보자. 5x5의 격자에서 랜덤한 위치에 광물이 1개씩 놓여 있다 가정해보자. 이때 한번에 1x3의 크기만을 탐색할 수 있다면, 어떤 부분에서 최대의 광물 수를 확인할 수 있을까? 나는 뒤도 돌아보지 않고 2중 for문을 이용해 가능한 모든 직사각형을 탐색할 것이다. 물론 가로로 긴 직사각형만을 가정하자! 코드로 확인해본다면, for i in range(0, 5): for j in range(0, 3): //체크 세로는 위와 같이 j 인덱스는 5 끝까지 체크하지 않을 것이고, 가로로는 직사각형 가로의 길이 즉 길이 3이 벗어나지 않는 시작점인 2까지만 체크를 해볼 것이다. 이렇게 하는 .. 2024. 4. 7. 이전 1 다음