memostack
article thumbnail
블로그를 이전하였습니다. 2023년 11월부터 https://bluemiv.github.io/에서 블로그를 운영하려고 합니다. 앞으로 해당 블로그의 댓글은 읽지 못할 수 도 있으니 양해바랍니다.
반응형

1. 최댓값 찾기

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

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

2. 코드

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

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

<python />
# -*- 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() 메소드를 사용하지 않고 풀어보면,

 

2.1. Case 1. 최댓값 찾기

<python />
# -*- 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) 이 된다.

 

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

<python />
# -*- 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) 이다.

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

<python />
# -*- 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) 이다.

 

반응형
블로그를 이전하였습니다. 2023년 11월부터 https://bluemiv.github.io/에서 블로그를 운영하려고 합니다. 앞으로 해당 블로그의 댓글은 읽지 못할 수 도 있으니 양해바랍니다.
profile

memostack

@bluemiv_mm

포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!