Python_수업 (3)

2024.04.05 (금)

 

오늘 배울 것

• 함수, 스코프
• 재귀함수
• log N 시간 복잡도
• 이분 탐색기

---

 

함수, 스코프

• 이름 공간

a = 3

def func():
	a = 4
	print(a)
		
func()
print(a)

#4
#3

'''
!!!!순서 중요!!!!
Local : ex. a = 4 의 a
Enclosed (함수 안의 함수)
Global : ex. a = 3 의 a / func
Built-in : print, sum...
'''

a = 3

def func():
	global a
		a = 4
		print(a)
		
func()
print(a)

#4
#4

• 스코프 → 함수 기준

a = [1, 2, 3]
print(id(a))

def func(lst):
    print(id(lst))
    lst.append(4)
    print(lst)

func(a)
print(a)

#함수안의 함수 (Enclosed)
def solution():
	a = 3
	def func2():
		nonlocal a   #이렇게 해야 위의 a = 3이 7로 바뀐다.(global X)
		a = 7
		print(a)
	func2()

solution()

[문제] 프로그래머스 _ 중복된 문자 제거

#첫 번째 방법 (좀 어렵)
#중복된 문자 제거 -> set
def solution(my_string):
	answer = ''
	tickets = set(my_string)    #O(N) + 메모리
	for i in my_string:         #O(N)
		if i in tickets:        #O(1)
			answer += i
			tickets.remove(i)
		
	return answer
'''
tickets 만드는데 O(N) + 메모리 좀 든다.
for는 O(N)
여기서 in은 O(1)
'''
		
		
		
#두 번째 방법
def solution(my_string):
	answer = ''
	for i in my_string:      #O(N)
		if i not in answer:  #O(N)
			answer += i
		
	return answer
		
'''
in의 시간복잡도 O(N)
for 도 O(N)
-> 이렇게 되면 N의 제곱이다...
'''

재귀함수

시스템 스택 분석법…!

돌아가는 시스템, 모델링을 머리에 탑재하고 머릿속에서 돌릴 수 있어야한다.

def func(depth):
    if depth == 3:
        return
    
    print(f'{depth}시작!!')
    func(depth + 1)
    print(f'{depth}끝!!')

func(0)

# 0시작!!
# 1시작!!
# 2시작!!
# 2끝!!
# 1끝!!
# 0끝!!

이해해야돼!!!!!

시스템 스택이다!!!!!!

 

cf. -5 ~ 256 는 자주 사용하는 거라 생각해서 같은 숫자의 변수를 다르게 해줘도 id 값은 같다.

log N

밑이 2이다!!!

cf)
N → [3, 7, 4, 1] : 4개 4번을 봐야 최솟값을 알 수 있다. ‘번’이 중요!!
O(N)

이진 검색

N = 8
0 1 2  3  4 5 6 7
   <- mid ->
(0+7)//2 -> 3(mid)

1회 소진

4   5  6 7
<- mid ->

2회 소진

4

3회 소진

log2(8) = 3!!

맹점은 데이터가 정렬된 상태에서 해야한다.

순차검색 → O(N)

정렬검색 → N * logN

순차검색이 나은거 아님???

but 세상에는 그 자체로 정렬된게 많다.

<시간 복잡도 범위>

N → 1억

N^2 → 1만 이하

nums = [1, 2, 3, 4, 5, 6, 7, 8, 9]

def binary_search(low, high, target):
    if low > high:
        return '찾지 못함'

    mid = (low + high) // 2
    if target == nums[mid]:
        return mid
    elif target < nums[mid]:
        return binary_search(low, mid-1, target)
    elif target > nums[mid]:
        return binary_search(mid+1, high, target)

print(binary_search(0, len(nums)-1, 7))

'''
생각해보자!!

특히 '찾지 못함'
'''

순열, 조합

from itertools import combinations, permutations    #조합, 순열

arr = ['a', 'b', 'c']
combi = list(combinations(arr, 2))
permu = list(permutations(arr, 3))
print(combi)    #[('a', 'b'), ('a', 'c'), ('b', 'c')]
print(permu)    #[('a', 'b', 'c'), ('a', 'c', 'b'), ('b', 'a', 'c'), ('b', 'c', 'a'), ('c', 'a', 'b'), ('c', 'b', 'a')]

[문제] 백준_2711_오타맨 고창영

T = int(input())

for i in range(T):
    idx, word = map(int,input().split())    # idx = 4, word = MISSPELL
    idx = int(idx) - 1    #idx = 3
    word = list(word)    #word = ['M', 'I', 'S', 'S', 'P', 'E', 'L', 'L']
    word.pop(idx)      #word = ['M', 'I', 'S', 'P', 'E', 'L', 'L']
    ans = ''.join(word)    #ans = 'MISPELL'
    print(ans)
    
   
#이것도 이해해보자...

[문제] 프로그래머스 _ 숫자 문자열과 영단어

def solution(s):
    nums = {'zero': 0,
            'one': 1,
            'two': 2,
            'three': 3,
            'four': 4,
            'five': 5,
            'six': 6,
            'seven': 7,
            'eight': 8,
            'nine': 9}    #딕셔너리 활용!
    
    for n in nums:  #n은 키 값
        s = s.replace(n, nums[n])   #키 값을 value 값으로 바꿔라!

    return int(s)