Python/알고리즘 기초4 시간복잡도와 공간복잡도 계기 및 목표 알고리즘 문제를 풀다보면 효율성 테스트에서 막히는 경우가 꽤 된다. 알고리즘의 효율성을 높이기 위해 어떤 부분에 집중해야하는지에 대해서 알기위함 알고리즘의 효율성 = 시간복잡도를 낮춘다 && 공간복잡도를 낮춘다 시간복잡도란? 공간복잡도란? 복잡도(Complexity)란? 알고리즙의 성능, 효율성을 나타내는 척도 크게 시간 복잡도(time complexity) 와 공간 복잡도(space Complexity)로 나눌 수 있다. 각 알고리즘이 주어진 특정 크기의 입력(n)을 기준으로 수행시간(연산) 혹은 사용공간이 얼마나 되는지 객관적으로 비교할 수 있는 기준을 제시 복잡도를 나타내는 방법으로는 최악의 경우를 대비할 수 있는 Big-O 표기법을 주로 사용한다. 수행시간 = 시간복잡도 메모리사용량.. 2024. 1. 14. 파이썬(Python) - 이분탐색(이진탐색) / bisect 이진 탐색(이분 탐색) 정렬된 상태의 리스트에서 탐색범위를 반으로 줄여가며 데이터를 탐색하는 방법 리스트가 반드시 정렬된 상태여야만 한다. lst = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] # 오름차순으로 정렬된 상태 num = 7 # 정렬된 상태를 유지하며 배열에 추가할 요소 left = 0 # 왼쪽 기준 인덱스 right = len(lst)-1 # 오른쪽 기준 인덱스 while left= num: right = mid - 1 result = mid else: left = mid + 1 print(result) # 7 각 양끝의 인덱스를 기준으로 잡고 가운데 인덱스를 비교값을 삼아 범위를 반씩 줄여나가는 방식 절반씩 범위를 줄여가기에 O(logN)이 성립! bisect - .. 2022. 4. 12. 파이썬(Python) - 문자열에서 여러 문자 바꾸기 Method replace() : 문자열에서 한 문자를 다른 문자로 변경 re.sub() / re.subn() : 문자열에서 정규식에 맞는 문자들을 모두 변경 maketrans() / translate() : 1대1형식으로 여러 문자를 변경 및 삭제 →문자열은 인덱스로 조회는 가능하지만 직접적인 수정 및 삭제는 불가능하므로 위와 같은 방법으로 수정한다. replace() 특정문자를 대체할 때 문자열.replace(문자열에서 교체할 문자, 일치하는 문자를 대체할 문자 , [교체할 횟수]) string = "hello hi hello good" string2 = string.replace("hello", "Nope") print(string2) # "Nope hi Nope good" string3 = str.. 2022. 3. 31. 파이썬(Python) - 딕셔너리(dictionary) 원소 검색/추가/삭제 딕셔너리(dictionary)의 구조 중괄호({ })로 감싸진 키(key)와 요소(value)의 1대1 매칭으로 구성됨 콜론을 기준으로 앞이 key, 뒤가 value값 아래의 dict의 key값 : 이름, 나이, 다루는 언어 dict = {"이름" : "홍길동", "나이" : 28, "다루는 언어" : ["Python", "Java"]} 각 key와 value 쌍은 쉼표(,)로 구분한다 key의 값이 겹칠경우 하나 외에는 모두 무시되므로 key는 중복X 하나의 key에 여러 값을 매칭하고 싶을 경우 value를 리스트형태로 지정할 수 있다. key값은 변하지 않는 값으로만 지정이 가능하다!! ex) 튜플형태는 가능하나 리스트는 불가능하다. 딕셔너리(dictionary) 검색 key값 조회 ( dict.k.. 2022. 3. 29. 이전 1 다음
