이번 포스팅에서는 파이썬 자료형들에서 많이 사용하는 연산들의 시간 복잡도를 정리해보겠습니다. 이 시간 복잡도를 바탕으로 파이썬 자료형들을 사용할 때 얼마나 효율적으로 하는지를 떠올릴 수 있을 것 같습니다. 리스트 (동적 배열) 연산 예시 시간복잡도 접근 list_1[0], list_1[0] = 5 O(1) 추가 list_1.append(2) O(1) (분할 상환) 맨 뒤 삭제 list_1.pop() O(1) (분할 상환) 길이 확인 len(list_1) O(1) 삽입 list_1.insert(3, "성태호") O(n) 삭제 del list_1[0], list_1.pop(3) O(n) 탐색 "이재하" in list_1 O(n) deque (더블리 링크드 리스트) 연산 예시 시간 복잡도 맨 앞 삭제 dequ..
출근하는방법I.py # 시간 복잡도 O(n) def staircase(n): # 여기에 코드를 작성하세요 a, b = 1, 1 for i in range(n): temp = a a = b b = temp + b return a # 테스트 코드 print(staircase(0)) print(staircase(6)) print(staircase(15)) print(staircase(25)) print(staircase(41)) 해결과정 계단의 높이가 4인 경우를 생각해보면 0 → 1 → 2 → 3 → 4 0 → 1 → 2 → 4 0 → 1 → 3 → 4 0 → 2 → 3 → 4 0 → 2 → 4 매번 오를 수 있는 계단의 수는 1 또는 2이다. 따라서 계단으로 가기 위해선 결국 3번째 계단 또는 2번째 계단..
1. 해시 테이블 - 해시 테이블을 이용하면 key-value 데이터를 저장할 수 있다. - 해시 테이블에는 데이터 간 순서 관계를 나타낼 수 없다. - 해시 함수는 특정 값을 넣었을때 원하는 범위의 자연수를 리턴하는 함수다. - Direct Access Table을 이용하면 key - value 데이터를 시간 효율적으로 저장하고 찾을 수 있다. - 해시 함수는 원하는 범위의 자연수를 빠르게(O(1)으로) 리턴하면 좋다. 2. 해시 테이블 충돌과 Chaining - 충돌은 해시 테이블에서 한 인덱스에 두 개의 key - value 쌍을 저장해야 되는 경우이다. - 충돌이 일어나면 해시 테이블을 제대로 사용하기 위해 Chaining이나 Open addressing 등을 이용해 충돌을 해결해야 한다. - C..
1. 링크드 리스트 - 배열과 같이 데이터를 순서대로 저장해주는 자료 구조다. - 각 노드가 다음 노드에 대한 레퍼런스만 저장하는지, 아니면 다음과 전 노드에 대한 레퍼런스를 모두 저장하는지에 따라 싱글리 링크드 리스트와 더블리 링크드 리스트로 구별할 수 있다. - 링크드 리스트 노드들은 메모리에 연속적이거나 순서대로 저장되지는 않는다. 메모리 이곳저곳 아무 데나 저장돼 있을 수 있다. - 싱글리 링크드 리스트는 처음에 크기를 정하지 않아도 그냥 새로운 노드를 만들어서 기존 노드들에 연결만 시켜주면 계속해서 새로운 데이터를 더해줄 수 있다. - 파이썬에서는 노드 클래스를 정의하고, 인스턴스들을 만들어서 연결하면 링크드 리스트를 구현할 수 있다. 2. 싱글리 링크드 리스트와 더블리 링크드 리스트 연산 - ..
파이썬 hash 함수 파이썬 언어도 내부적으로 hash라는 함수를 제공합니다. 근데 이건 우리가 방금 배운 해시 함수랑 조금 다른데요. 파이썬 해시 함수는 파라미터로 받은 값을 그냥 아무 정수로만 바꿔주는 함수입니다. 저희가 배웠던 해시 함수와는 달리 특정 범위 안에 있는 정수가 아니라 아무 정수로 바꿔주죠. 정수형, 소수형, 문자열 타입에 hash 함수를 호출했을 때 나오는 결과를 살펴보겠습니다. # 정수 값 print(hash(12345)) # 12345 print(hash(12345)) # 12345 # 다른 정수 값 print(hash(12346)) # 12346 # 소수 값 print(hash(15.1234)) # 284541027336970255 print(hash(15.1234)) # 284..
이번 포스팅에서는 해시 함수에 대해서 조금 더 알아보고 해시 함수를 구현할 수 있는 가장 간단한 방법들에 대해서 살펴보겠습니다. 101호: 최지웅 204호: 강영훈 302호: 성태호 711호: 김현승 942호: 손동욱 먼저 주어진 key를 원하는 범위의 자연수로 바꿔서 리턴해주는 것 말고 다른 해시 함수의 조건들을 볼게요. 한 해시 테이블의 해시 함수는 결정론적이어야 된다. 똑같은 key를 넣었을 때는 항상 똑같은 결과가 나와야 한다는 건데요. 942를 해시 함수에 넣을 때 어쩔 때는 5이 나오고 어쩔 때는 10이 나오고 이러면 안 된다는 거죠. 942를 넣으면 항상 똑같은 결과가 나와야 됩니다. 결과 해시값이 치우치지 않고 고르게 나온다. 그러니까 해시 함수에 101, 204, 302, 711, 942..
삼송전자주식분석.py def max_profit(stock_list): # 여기에 코드를 작성하세요 profit_list = [] profit = 0 for i in range(len(stock_list)-1): profit = max(stock_list[i+1:]) - stock_list[i] profit_list.append(profit) return max(profit_list) ########################################################## # 모범 답안 : 시간복잡도 O(n) def max_profit(stock_list): # 현재까지의 최대 수익 max_profit_so_far = stock_list[1] - stock_list[0] # 현재까지의 최..
투자귀재규식이III.py def sublist_max(profits): max_profit_so_far = profits[0] # 반복문에서 현재까지의 부분 문제의 답 max_check = profits[0] # 가장 끝 요소를 포함하는 구간의 최대 합 # 반복문을 통하여 각 요소까지의 최대 수익을 저장한다 for i in range(1, len(profits)): # 새로운 요소를 포함하는 구간의 최대합을 비교를 통해 정한다 max_check = max(max_check + profits[i], profits[i]) # 최대 구간 합을 비교를 통해 정한다 max_profit_so_far = max(max_profit_so_far, max_check) return max_profit_so_far # 테스..
투자귀재규식이II.py def sublist_max(profits, start, end): # 여기에 코드를 작성하세요 # base case: 범위에 하나의 항목밖에 없으면, 그 항목 리턴 if start == end: return profits[start] # 중간 인덱스 mid = (start + end) // 2 # 상황별로 최대 수익을 구한다 max_left = sublist_max(profits, start, mid) max_right = sublist_max(profits, mid + 1, end) max_cross = max_crossing_sum(profits, start, end) # 위 세 경우 중 가장 큰 결괏값을 리턴한다 return max(max_left, max_right, ma..
중복되는항목찾기I.py def find_same_number(some_list): # 여기에 코드를 작성하세요 seen_element = [] for i in range(len(some_list)): seen_element.append(some_list[i]) if some_list[i+1] in seen_element: return some_list[i+1] # 중복되는 수 ‘하나’만 리턴합니다. print(find_same_number([1, 4, 3, 5, 3, 2])) print(find_same_number([4, 1, 5, 2, 3, 5])) print(find_same_number([5, 2, 3, 4, 1, 6, 7, 8, 9, 3])) 해결과정 먼저 Brute Force 를 이용해 모든 ..
