최댓값 찾기 알고리즘 (with Python3)

최댓값 찾기

최댓값을 찾는 알고리즘 상당히 간단한 알고리즘이다. (하나하나 비교하면 됨)

하나씩 비교를 하다보니 시간복잡도는 O(n)이 된다.

코드

본 글에서는 unittest를 이용하여 알고리즘을 풀이합니다. 로직이 달라지는것은 아닙니다.

사실 파이썬에는 max() 라는 내장함수를 제공해주는데, max([5, 3, 2]) 안에 숫자로 구성된 리스트를 넣어주면 알아서 최댓값을 반환해준다.

# -*- coding: utf-8 -*-

import unittest


class Exam02(unittest.TestCase):

    @classmethod
    def setUpClass(cls) -> None:
        cls.items = [10, 92, 4, 7, 44, 80, 98, 50, 74, 32]

    ...생략...

    def test_find_max2(self):
        """max() 메소드 이용하기"""
        self.assertEqual(98, max(self.items))


if __name__ == "__main__":
    unittest.main()

 

하지만, 알고리즘을 살펴보기 위해 max() 메소드를 사용하지 않고 풀어보면,

 

Case 1. 최댓값 찾기

# -*- coding: utf-8 -*-

import unittest


class Exam02(unittest.TestCase):

    @classmethod
    def setUpClass(cls) -> None:
        cls.items = [10, 92, 4, 7, 44, 80, 98, 50, 74, 32]

    def test_find_max(self):
        """최댓값 찾기"""
        max_num = self.items[0]  # 첫번째 원소를 default 값으로 가짐
        for item in self.items[1:]:  # n-1 번 수행하기 때문에 시간복잡도는 O(n-1) = O(n) 이다.
            if max_num < item:
                max_num = item
        self.assertEqual(98, max_num)


if __name__ == "__main__":
    unittest.main()

• 첫번째 원소를 기본값으로 한다. max_num = self.items[0]
• for문을 이용하여 값을 하나씩 비교한다.
  • 단, 첫번째 원소는 비교할 필요 없기 때문에 첫번째 원소부터 반복문 실행 한다. self.items[1:]
• 비교하면서 더 큰 값이 있으면 max_num 을 갱신한다. max_num = item

시간복잡도는 O(n-1) = O(n) 이 된다.

 

Case 2-1. 최댓값의 인덱스 찾기

# -*- coding: utf-8 -*-

import unittest


class Exam02(unittest.TestCase):

    @classmethod
    def setUpClass(cls) -> None:
        cls.items = [10, 92, 4, 7, 44, 80, 98, 50, 74, 32]

    def test_find_max_idx(self):
        """최댓값의 인덱스 찾기"""
        max_idx = 0
        for idx in range(1, len(self.items)):
            if self.items[max_idx] < self.items[idx]:
                max_idx = idx
        self.assertEqual(6, max_idx)


if __name__ == "__main__":
    unittest.main()

마찬가지로 시간복잡도는 O(n-1) = O(n) 이다.

Case 2-2. 최댓값의 인덱스 찾기 2

# -*- coding: utf-8 -*-

import unittest


class Exam02(unittest.TestCase):

    @classmethod
    def setUpClass(cls) -> None:
        cls.items = [10, 92, 4, 7, 44, 80, 98, 50, 74, 32]

    def test_find_max_idx2(self):
        """최댓값의 인덱스 찾기 - enumerate() 이용하기"""
        max_idx = 0
        for idx, item in enumerate(self.items):
            if self.items[max_idx] < item:
                max_idx = idx
        self.assertEqual(6, max_idx)


if __name__ == "__main__":
    unittest.main()

enumerate() 메소드 이용하면 리스트의 인덱스와 값을 같이 이터레이터로 사용할 수 있어서 편리하다.

시간복잡도는 O(n) 이다.