viamemine

DP 사용조건- 큰 문제를 작은 문제로 나눌 수 있음- 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일함  탑다운(Top-Down) 방식- 작은 문제를 재귀적으로 해결d = [0] * 100 # 한 번 계산된 결과를 memoization하기 위한 list 초기화def fibo(x): # 피보나치 함수를 재귀함수로 구현 (탑다운) if x == 1 or x == 2: return 1 if d[x] != 0: # 이미 계산한 적 있는 문제라면 그대로 반환 return d[x] d[x] = fibo(x - 1) + fibo(x - 2) # 아직 계산하지 않은 문제라면 점화식에 따라 결과 반환 return d[x]print(fibo(99))  ..

선택 정렬 - 매번 가장 작은 것을 선택하여 맨 앞과 교체하는 방법- 시간 복잡도: O(N^2)for i in range(len(array)): min_index = i for j in range(i+1, len(array)): if array[min_index] > array[j]: min_index = j array[i], array[min_index] = array[min_index], array[i]  삽입 정렬- 데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입하는 방법- 시간 복잡도: O(N^2), 데이터가 정렬되어 있는 경우 O(N)for i in range(1, len(array)): for j in range(i, 0, -1)..

내장 함수- evalresult = eval("(3+5) * 7") # 56 - sortedresult = sorted([9,1,8,5,4]) # [1,4,5,8,9]result = sorted([9,1,8,5,4], reverse=True) # [9,8,5,4,1]result = sorted([('홍길동', 35), ('이순신', 75), ('아무개', 50)], key=lambda x: x[1], reverse=True) # [('이순신', 75), ('아무개', 50), ('홍길동', 35)] - .sort(): 내부 값이 바로 변경됨data = [9,1,8,5,4] data.sort() # [1,4,5,8,9]   itertools- permutations(순열): 서로 다른 n개 중에 r개를 선..

문제: https://www.acmicpc.net/problem/1918  풀이 오늘은 stack, queue, deque의 문제 유형인 후위 표기식을 풀어보겠습니다. 연산자 우선순위1. () 2. * /3. + - stack을 이용하여 연산자의 우선순위를 고려하여 문제를 해결해보도록 하겠습니다.  리스트에 식전체를 넣어 for문을 통해 한 문자씩 확인합니다.1. ()를 확인2. * / 인지를 확인하고, 먼저 들어온 같은 우선순위에 있는 * /는 모두 출력 문자열에 추가3. 현재 연산자를 stack에 추가4. + - 인지를 확인하고, + - 보다 낮은 우선순위의 연산자가 없기 때문에 자신보다 우선순위가 높은 연산자들을 모두 출력 문자열에 추가5. )를 발견하면 ( 와 ) 사이에 있는 모든 연산자들을 출력..