2부터 순회를 하면서 2의 배수를 모두 지워주고, 3부터 순회를 하면서 3의 배수를 모두 지워주고, 4는 이미 지워졌으니 패스하고, 5의 배수를 지우고..
주어진 수의 제곱근까지만 확인해보면 끝난다.
1. python itertools-permutations 활용
from itertools import permutations
def solution(numbers):
nums = []
for i in range(len(numbers)):
nums += [int(''.join(x)) for x in list(permutations(numbers, i+1))]
answers = []
answers += [x for x in nums if (x in [2,3])]
for x in nums:
sqrt = int(x**(1/2))
for i in range(1,sqrt):
if x % (i+1) != 0:
if i+1 == sqrt:
answers.append(x)
continue
else:
break
nums = len(set(answers))
return nums
2. 재귀 알골 이용
def solution(numbers):
answers = []
def permutation(numbers, r):
used = [0 for _ in numbers]
def generate(chosen, used):
if len(chosen) == r:
chosen = int(''.join(chosen))
if (chosen in [2,3]) and (chosen not in answers): #2,3은 sqrt값이 1이므로 이하 for문이 실행되지 않음
answers.append(chosen)
sqrt = int(chosen**(1/2))
for i in range(1, sqrt):
if chosen % (i+1) != 0:
if (i+1 == sqrt) and (chosen not in answers):
answers.append(chosen)
break
continue
else:
break
return
for i in range(len(numbers)):
if not used[i]:
chosen.append(numbers[i])
used[i] = 1
generate(chosen, used)
used[i] = 0
chosen.pop()
generate([], used)
for i in range(len(numbers)):
permutation(numbers, i+1)
answer = len(answers)
return answer
append 하기 전, 중복 제거 필요
'구분자'.join(리스트)
map(''.join, 리스트)로 처리하면 빠름
순열 알고리즘 내에서, 모든 단어를 리스트에 저장하는 것이 아니라, 소수인 것만 filter 해서 저장 ←이때 에라토스테네스의 체
def gen_permutations(arr, n):
result = []
if n == 0:
return [[]]
for i, elem in enumerate(arr):
for P in gen_permutations(arr[:i] + arr[i+1:], n-1):
result += [[elem]+P]
return result
2.2
def permutation(arr,r):
arr = sorted(arr)
used = [0 for _ in arr]
def generate(chosen, used):
if len(chosen) == r:
print(chosen)
return #used[i] = 0로 돌아가는데, 다시 for문 거치는 게 아니라, 바로 이어져서 i값이 유지됨.
for i in range(len(arr)): #arr은 함수 외부에 정해져 있음(상수수)
if not used[i]:
chosen.append(arr[i])
used[i] = 1
generate(chosen, used)
used[i] = 0 #순열 하나 만들고 나서, 다시 0으로 initialize
chosen.pop() #return이 없으므로 for문이 끝난 후에도 if문 다시 돌고, if문 만족 못하므로 for문 새로 시작됨
generate([], used)
좋은 코드라고는 하나 개인적으로 이해하는 데 시간이 걸렸음.
arr: 리스트 r: 리스트 중 뽑을 개수
[for문 안에서] chosen: 순열 구성하는 원소 리스트 used: chosen에 들어간 원소 index 위치에 해당 원소의 사용 여부를 0/1로 알려주는 리스트(즉 arr와 연동됨) (*디폴트는 0으로 채워짐)
함수 정의문에는 return의 위치가 중요함. for문이 모두 종료되었대도 return이 다른 곳에 있다면 다시 iteration 거침.
여기도 for문의 상단 if문을 거쳐야 return되는데, for문이 종료되고 if문으로 돌아갔을 때 if문 조건이 성립되지 않으므로 return이 실행되지 않음. 즉, 다시 for문으로 돌아가 처음부터 실행됨. (물론 이 상황에서 used와 chosen은 이전 로그가 반영된 상태이므로 i값이 슉슉 점프하게 됨.
generate 함수 정의문 내부에 generate가 사용된 재귀형식임.
내부 generate이 실행될 때 if문 만족되면 바로 return 일어나므로, 내부 generate 실행 직전 i값이 그대로 보존된 상태로 used[i]=0 코드로 넘어감.
만약 내부 generate 실행될 때 if문 만족 못 하면 for문으로 넘어가고, 결국 내부 generate가 종료되려면 내부 if문이 만족될 때까지 iter iter iter..
input answers: 1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 ex. [1,2,3,4,5]
return 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아서 ex. [1] *가장 높은 점수를 받은 사람이 여럿일 경우, return하는 값을 오름차순 정렬.
나의 코드
def solution(answers):
n = len(answers)
fir = [1,2,3,4,5]*(n//5)+[1,2,3,4,5][:(n%5)]
sec = [2,1,2,3,2,4,2,5]*(n//8)+[2,1,2,3,2,4,2,5][:(n%8)]
thir = [3,3,1,1,2,2,4,4,5,5]*(n//10)+[3,3,1,1,2,2,4,4,5,5][:(n%10)]
def compare(data):
cnt = 0
for idx, i in list(enumerate(data)):
if i == answers[idx]:
cnt +=1
return cnt
fir_val = compare(fir)
sec_val = compare(sec)
thir_val = compare(thir)
lst = sorted([(1,fir_val), (2, sec_val), (3, thir_val)], key=lambda x: x[1], reverse=True)
answer = [lst[0][0]]
for (idx, val) in lst[1:]:
if val == lst[0][1]:
answer.append(idx)
return answer
모범 코드
def solution(answers):
pattern1 = [1,2,3,4,5]
pattern2 = [2,1,2,3,2,4,2,5]
pattern3 = [3,3,1,1,2,2,4,4,5,5]
score = [0, 0, 0]
result = []
for idx, answer in enumerate(answers):
if answer == pattern1[idx%len(pattern1)]:
score[0] += 1
if answer == pattern2[idx%len(pattern2)]:
score[1] += 1
if answer == pattern3[idx%len(pattern3)]:
score[2] += 1
for idx, s in enumerate(score):
if s == max(score):
result.append(idx+1)
return result
[idea] 리스트 내 원소에 특정 패턴이 반복되는 경우
pattern 변수 통해 반복되는 부분만 따오기
[idx % (패턴의 길이)] 인덱스 처리.
for문 순환하여 세 명의 score 병렬 계산 (어차피 answers와 세 명의 대답 length가 동일함)
score = [0,0,0] 처리 후 한꺼번에 score[x] +=1
마지막 출력 처리하는 건.... 나 왜 저렇게 짰지?🫢 모범코드대로 하는 게 당연할 따름. idx 순서대로 처리되니 더더욱?!
input sizes: 모든 명함의 가로 길이와 세로 길이를 나타내는 2차원 배열 (ex. [[60, 50], [30, 70], [60, 30], [80, 40]]) *원소 개수 최소 1 *명함 가로, 세로는 최소 1, 최대 100
return 지갑의 크기 (ex. 4000)
나의 코드
def solution(sizes):
big = []
small = []
for [x,y] in sizes:
if x >= y:
big.append(x)
small.append(y)
else:
big.append(y)
small.append(x)
answer = max(big)*max(small)
return answer
return : 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 평균이 얼마 *소수점 이하의 수는 버림
*하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리
문제 이해
input: [[0, 3], [1, 9], [2, 6]]
우측보다 좌측의 경우, 프로세스 총소요시간(요청부터 처리될 때까지 총시간)의 평균이 적다.
return: 9 (총 27 // 3)
문제 결론
대기 시간이 없는 경우와 있는 경우를 구분한다.
대기 시간이 있는 경우 if문 내부에서 현재 시각 now를 조절함으로써, '대기 시간이 없는 경우'와 state를 일치시킨다.
현재 시각 now 계산 식 & 프로세스 총 소요시간 계산 식을 if문 외부에서 공유: waitlst의 heappop 처리.
대기 시간이 없는 경우: 소요 시간이 짧은 것을 우선순위로 처리 → heappop (자동 min 정렬)
jobs에서 원소를 하나씩 꺼내어 waitlst에 heappush. 즉 jobs 대신 waitlst를 heap으로 처리.
대기 시간이 있는 경우: jobs에서 가장 이른 것을 꺼내어 waitlst에 heappush.
자주 활용되는 아이디어이므로 확실히 기억할 것
문제 이해 프로세스
1. 작업의 요청부터 종료까지 걸린 시간 = 기다린 시간(변수) + 프로세스 진행 시간(상수)
2. '기다린 시간(변수)'은 해당 프로세스가 요청된 시각이 직전 프로세스 종료 시각보다 '이전인가' '이후인가'에 따라 계산 방법이 다르다.
→ 시각과 시간 구분하자
→ 직전 종료 시각을 어떻게 구하는가..? (생각의 무한루프 ♾️🥲)
→ 초깃값은 어차피 a가 가장 작은 값으로 결정되어 있으니 이후 점화식 잘 세우면 된다 (ps: 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리)
→ 일단 '기다린 시간'을 경우에 따라 나누어보자. (경우 = if문으로 구현)
→ 처음에는 '직전 프로세스 종료 시각'을 end로 지정했는데, 오히려 헷갈려서, 현재 시각 'now'로 대체하였다 **
현재 프로세스: [a,b]
1️⃣ if 현재 시각(now) >= 현재 프로세스 요청 시각:
기다린 시간 = 기존 now - a
프로세스 총 소요시간 = (기존 now-a) + b == (업데이트 완료한 now) - a
프로세스 끝난 후 현재 시각 업데이트 now = 기존 now+b
2️⃣ elif 현재 시각(now) < 현재 프로세스 요청 시각:
기다린 시간 = 0
프로세스 총 소요시간 = b == (업데이트 완료한 now) - a
프로세스 끝난 후 현재 시각 업데이트 now = a+b
3. 그런데 어떻게 정렬하지.. (생각의 무한루프 ♾️🥲 again)
끄적이다 겨우 알아낸 사실:
- 상수인 것을 제외하고 변수인 것을 비교하자.
- 프로세스 소요시간이 짧은 것부터 정렬해야 한다.
- 조건에 의해, 작업을 수행하고 있지 않을 때에는, 먼저 요청이 들어온 작업부터 처리해야 하므로 → 현재 시각 이전에 요청된 프로세스 먼저 처리하고 → 나머지를 처리해야 한다.
- 현재 시각 이전에 요청된 프로세스 즉 대기 중인 프로세스를 waitlst에 저장 1️⃣
- 단, 대기 중인 프로세스가 없는 경우도 있다! 2️⃣
▶ waitlst가 비어 있지 않은 경우 1️⃣
→ jobs 리스트에서 소요시간이 가장 짧은 것을 먼저 waitlst에 heappush
→ 단 waitlst 내부에서는 '소요시간'을 기준으로 정렬해야 하므로, for문 heappush 시 인덱스 위치를 바꾼 채로.
▶ waitlst가 비어 있는 경우(=요청이 가장 이른 다음 프로세스가 현재 시각 이후에 요청될 때) 2️⃣
→ 시각을 옮겨주어 다음 프로세스가 바로 시작될 수 있도록 세팅한다: now = 요청시각
→ 가장 이른 프로세스를 jobs 리스트에서 heappush, 마찬가지 인덱스 위치를 바꾼 채로.
▶ 1️⃣&2️⃣ 거친 후
→ now += 소요시간
→ 프로세스 총 소요시간: now - 요청시각
→ total.append(now - 요청시각)
▶ 서로 다른 계산식을 가지는 1️⃣&2️⃣를 잘 처리함으로써 결과적으로 동일한 state가 되도록 일치시킴
→ now 및 total 계산식을 간단히 공유할 수 있게 됨.
▶ 마무리: int(total / len(jobs)) OR total // len(jobs)
*소수점 이하의 수는 버림 조건 매우 주의
*조건 상 분모가 0이 될 수 없으므로 해당부분은 pass.
나의 코드
from heapq import heapify, heappop, heappush
def solution(jobs):
j_len = len(jobs)
heapify(jobs)
now = 0
total = []
waitlst = [] #waitlst의 위치 중요
while len(total)<j_len:
while jobs and (jobs[0][0] <= now):
next = heappop(jobs)
heappush(waitlst, (next[1],next[0]))
if jobs and waitlst == []:
next = heappop(jobs) #jobs에서 다음 활동 next 직접 꺼내기
now = next[0] #next 진행되도록 시간 세팅
heappush(waitlst, (next[1], next[0])) #next를 waitlst에 직접 추가
x,y = heappop(waitlst)
now += x #프로세스 진행하였으므로 진행시간 포함하여 현재 시간 업데이트
total.append(now-y)
answer = sum(total)//j_len
return answer
현재 시각 now의 업데이트 아이디어 중요 ⭐
indentation & while문 & if문 조건 엄밀하게 설정해야 함 ⭐
리스트를 heap으로 변환 안 하더라도, 리스트 자체로 heappop 바로 쓸 수 있구나.
jobs는 리스트 그대로 두고, wait할 원소를 pop하기만 함 → waitlst에서 사용되지 않은 원소를 jobs로 되돌릴 필요 없음
waitlst가 heap이며, waitlst 내에 새로운 원소가 들어올 때마다 힙정렬. (heappop, heappush 시 자동 힙정렬)
waitlst가 비어있을 때 jobs 리스트 첫번째 원소의 시작 시간으로 now를 맞춤
while len(total)<j_len:
이때 while jobs 하면 안 됨. jobs가 모두 pop되어 빈 리스트가 되더라도, waitlst에는 처리할 작업이 남아 있을 수 있음.
while jobs and (jobs[0][0] <= now):
"jobs 리스트가 비어있지 않고" and "jobs[0][0] <= now" 동안에 계속.
if jobs and waitlst == []:
"jobs 리스트가 비어있지 않고" and "waitlst는 비어있을 때" 한번.
heappush(waitlst, (next[1],next[0]))
heap은 기본적으로 원소의 0index를 기준으로 정렬하므로, 이같이 인덱스 뒤집어 힙정렬 처리 필요.
다른 코드
import heapq
def solution2(jobs):
answer, now, i = 0, 0, 0
start = -1
heap = []
while i < len(jobs):
# 현재 시점에서 처리할 수 있는 작업을 heap에 저장
for j in jobs:
if start < j[0] <= now:
heapq.heappush(heap, [j[1], j[0]])
if len(heap) > 0: # 처리할 작업이 있는 경우
cur = heapq.heappop(heap)
start = now
now += cur[0]
answer += now - cur[1] # 작업 요청시간부터 종료시간까지의 시간 계산
i +=1
else: # 처리할 작업이 없는 경우 다음 시간을 넘어감
now += 1
return answer // len(jobs)
from heapq import heapify, heappop, heappush
from collections import deque
def solution(jobs):
j_len = len(jobs)
heapify(jobs)
end = 0
total = 0
while jobs:
waitlst = []
while jobs[0][0] <= end:
a = heappop(jobs)
waitlst.append(a)
if len(jobs) == 0:
break
if waitlst:
waitlst.sort(key=lambda x: x[1])
waitlst = deque(waitlst)
next = waitlst.popleft()
end+= next[1]
present = (end-next[0])
for i in waitlst:
heappush(jobs, i)
else:
next = heappop(jobs)
end += (next[0]+next[1])
present = next[1]
total += present
answer = int(total/j_len)
return answer
from collections import deque
def solution(prices):
answer = []
idx_prices = deque(enumerate(prices))
for _ in prices:
idx, n = idx_prices.popleft()
t = len(prices)-idx
for i in range(t):
if i == t-1:
answer.append(t-1)
else:
if n > prices[idx+i+1]:
answer.append(i+1)
break
else:
continue
return answer
정답 도출은 쉬웠으나, 시간 효율 문제 개선이 어려웠음.
for _ in range(len(prices)-idx)에서 len 부분이 시간복잡도 심각. 어차피 _ 사용할 거 아니라면, for _ in prices로 대체
하나의 for문 안에 len(prices)-idx를 여러번 사용하였는데, 실행마다 len의 시간복잡도가 거듭되므로, t라는 변수에 저장한 후 t를 호출하는 게 훨씬 나음
list 사용을 최소화할 것! reverse문도 안 먹혔던 이유 → queue와 deque를 이용하자 (pop, popleft..)
enumerate 사용하지 않을 방법 모색해보자.
시간 초과 (실패) 코드
from collections import deque
def solution(prices):
answer = []
idx_prices = deque(enumerate(prices))
for _ in range(len(prices)):
n = idx_prices.popleft()
try:
small_idx = [x[0] for x in idx_prices if x[1]<n[1]][0]
answer.append(small_idx-n[0])
except:
answer.append(len(prices)-n[0]-1)
return answer
- try, except 이하가 애초에 비효율적이긴 하였음: 리스트 모두 완성 후 첫번째 원소만 사용하는 것이기 때문.
- 이외 이유는 상단에 기술.
모범 코드
1. 큐 활용
from collections import deque
def solution(prices):
answer = []
prices = deque(prices)
while prices:
c = prices.popleft()
count = 0
for i in prices:
if c > i:
count += 1
break
count += 1
answer.append(count)
return answer
2. 빠르며 깔끔
def solution(prices):
stack = []
answer = [0] * len(prices)
for i in range(len(prices)):
if stack != []:
while stack != [] and stack[-1][1] > prices[i]:
past, _ = stack.pop()
answer[past] = i - past
stack.append([i, prices[i]])
for i, s in stack:
answer[i] = len(prices) - 1 - i
return answer
[input] bridge_length: 트럭 수 weight: 다리가 견딜 수 있는 무게 truck_weights: 트럭 별 무게
[return] 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지
나의 코드
def solution(bridge_length, weight, truck_weights):
answer = 0
road = [0]*bridge_length
x = truck_weights.pop(0)
sum_weight = 0
while len(truck_weights)>=0:
sum_weight-=road[0]
road.pop(0)
road.append(0)
if sum_weight+x <= weight:
road[-1]=x
sum_weight+=x
answer+=1
if len(truck_weights)>0:
x = truck_weights.pop(0)
else:
answer+=bridge_length
break
else:
answer+=1
return answer
시간초과 문제
sum 함수가 시간초과 요인임! : sum_weights=0 한 후 루프 돌 때마다 weight을 -+= 하는 게 훨씬 좋음.
리스트의 맨 처음 원소를 pop하고 싶을 때, pop(0)은 시간초과 가능하므로 아래 두 가지 대안 1) .popleft() 2) truck_weights.reverse() 이후 .pop()
TypeError: 'NoneType' object is not subscriptable - 코랩에서 if문에 화살표 가리키더라도, 첫 코드부터 혹은 그 코드자체가 처음부터 틀렸다는 게 아니라, 여러 번 루프 돌린 후 해당 if문에 문제가 생겼다는 거 - 문제의 코드: road = road[1:].append(0) → None을 반환함, road[1:] 처리 후, 다음 줄에서 append. 따로 실행해야 함 (최종 코드에는 아예 pop(0)으로 대체) - 본 에러메시지는, 주로 리스트가 비어있는데 index에 접근하는 등, 빈 리스트에 특정 처리를 하면 발생.
모범 코드
1. 리스트.reverse 이후 pop() & deque 함수 사
from collections import deque
def solution(bridge_length, weight, truck_weights):
bridge = deque(0 for _ in range(bridge_length))
total_weight = 0
step = 0
truck_weights.reverse()
while truck_weights:
total_weight -= bridge.popleft()
if total_weight + truck_weights[-1] > weight:
bridge.append(0)
else:
truck = truck_weights.pop()
bridge.append(truck)
total_weight += truck
step += 1
step += bridge_length
return step
2. 간결함
def solution(bridge_length, weight, truck_weights):
q=[0]*bridge_length
sec=0
while q:
sec+=1
q.pop(0)
if truck_weights:
if sum(q)+truck_weights[0]<=weight:
q.append(truck_weights.pop(0))
else:
q.append(0)
return sec
*sum 함수 수정 필요
"while 변수: " 0이나 null값일 경우 False이기때문에, 빈리스트가 아니라면 True가되어 실행되는 함수 ex) while truck_weights: / while q:
1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다. 2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다. 3. 그렇지 않으면 J를 인쇄합니다.
내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 알고 싶습니다.
(숫자가 클 수록 더 중요한 문서)
input -priorities: 문서의 중요도가 순서대로 담긴 배열 -location: 내가 인쇄를 요청한 문서가 현재 대기목록의 어떤 위치에 있는지.
return 내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지.
나의 코드
def solution(priorities, location):
pri_tuple = list(enumerate(priorities))
target_tup = pri_tuple[location]
i=0
while target_tup in pri_tuple:
(max_idx,max_val) = sorted(pri_tuple, key=lambda x: x[1], reverse=True)[0]
max_value = (max_idx,max_val)
if pri_tuple[0][1] != max_val:
back_lst = pri_tuple[0:pri_tuple.index(max_value)]
del pri_tuple[0:pri_tuple.index(max_value)]
pri_tuple.extend(back_lst)
else:
pri_tuple.pop(0)
i+=1
answer = i
return answer
나의 아이디어: 현재 리스트에서 max값을 찾고 → 리스트의 첫번째 원소~max값 직전 원소까지 그대로 슬라이싱하여 → 리스트 맨 끝에 갖다 붙임: max값이 리스트의 맨 앞에 위치하게 됨 → 해당 max를 pop하여 제거 (i +1)
매개변수 location이 원본 priorities에 대한 index 값이므로, 원본 index 값을 저장하기 위해 enumerate 사용 → priorities 리스트의 각 원소가 (idx, value)의 튜플 형태로 저장됨
while문을 사용 (단, 무한루프의 위험 있으므로 while true는 지양하는 것이 좋음)
max값을 찾기 위해 튜플로 이루어진 pri_tuple 리스트를 sorted함 (정렬 기준이 value값이므로, key, lambda를 이용)
추가 테스트케이스에서 문제가 생겼던 부분 😂 1) while target_tup in pri_tuple에서, while문 내부의 pri_tuple이 새로 업데이트될 때 마다, 해당 while문의 pri_tuple도 함께 바뀜 2) 따라서 max_value, max_idx, max_val도 함께 업데이트됨 3) max_value자체가 튜플 형태이고, pri_tuple 리스트 애 max_value의 대상이 되는 원소 자체는 바뀌지만, 해당 원소 내부의 내용이 바뀌지는 않음 (초반에 enumerate로 정의되었기 때문에) → max_value의 max_idx와 pri_tuple.index(max_value)값은 엄연히 다름!!! 아예 다른 내용을 가리킴.
pop은 디폴트로 맨 마지막 값을 삭제하지만, 원하는 인덱스의 원소를 삭제할 수도 있음
리스트의 조작: del 리스트[삭제할 원소 슬라이싱] / 리스트.extend(연장할 리스트 내용)
def solution(priorities, location):
queue = [(i,p) for i,p in enumerate(priorities)]
answer = 0
while True:
cur = queue.pop(0)
if any(cur[1] < q[1] for q in queue):
queue.append(cur)
else:
answer += 1
if cur[0] == location:
return answer
원소 하나씩, 하나씩. any니까 괜찮음
[(i,p) for i,p in enumerate(priorities)] list comprehension에서 튜플을 다루는 법! 단순하지만 유용함
⭐⭐ 파이썬의 any, all 함수⭐⭐ any() : 하나라도 True인게 있으면 True all() : 모두 True여야 True 반환 → 아큐먼트로 iterable한 객체를 받음. (ex list) →이 객체를 돌면서 조건을 검사해 답을 True/False의 답을 반환 any(x, y for y in y_list) = True/False any()는 특히 대소비교를 할 때 사용하면 sort보다 실행시간을 많이 줄일 수 있다. 예를 들어 어떤 수와 어떤 리스트의 원소들을 비교하는데 해당 수가 리스트 안의 max값보다 큰지만 알고 싶다고 하자. 이 때, sort를 사용한 뒤 비교하면 리스트를 모두 정렬하기 때문에 시간이 걸린다. 하지만 any를 쓰면 리스트 내에 해당 수보다 큰 수가 있기만 하면 바로 True를 return하고 끝내기 때문에 시간이 덜 걸린다.
if 조건과 함께 다음과 같이 사용할 수도 있다.
cur = 3
temp = [1,3,6,2]
if any(cur<num for num in temp):
print("There exist number that is larger than 3")
2. deque의 활용 -> 효율성 향상
def solution(p, l):
ans = 0
m = max(p)
while True:
v = p.pop(0)
if m == v:
ans += 1
if l == 0:
break
else:
l -= 1
m = max(p)
else:
p.append(v)
if l == 0:
l = len(p)-1
else:
l -= 1
return ans
import math
def solution(progresses, speeds):
zipped = zip(progresses, speeds)
days = [math.ceil((100-x)/y) for x, y in zipped]
max_index = [0]
ptr = 0
answer = []
for _ in range(len(days)):
if days[max_index[-1]] >= days[ptr]:
ptr +=1
else:
max_index.append(ptr)
ptr +=1
last_element = len(days)-max_index[-1]
for x in range(len(max_index)-1):
answer.append(max_index[x+1]-max_index[x])
answer.append(last_element)
return answer
- zip하지 않은 상태로 여러 개의 리스트를 list comprehension에 동시에 쓸 수 없나봐
- pop은 index를 파라미터로 갖는구나! 원소 그자체가 아니구.
모범 코드
1. math의 ceil을 사용하지 않음
def solution(progresses, speeds):
Q=[]
for p, s in zip(progresses, speeds):
if len(Q)==0 or Q[-1][0]<-((p-100)//s):
Q.append([-((p-100)//s),1])
else:
Q[-1][1]+=1
return [q[1] for q in Q]
2. 군더더기 없이 담백하게 자료구조를 잘 녹여냄
def solution(progresses, speeds):
print(progresses)
print(speeds)
answer = []
time = 0
count = 0
while len(progresses)> 0:
if (progresses[0] + time*speeds[0]) >= 100:
progresses.pop(0)
speeds.pop(0)
count += 1
else:
if count > 0:
answer.append(count)
count = 0
time += 1
answer.append(count)
return answer
1. 장르 정렬: 곡수 2. 장르 내 곡 정렬: 재생량 / 같으면 고유번호 낮은 거 먼저.
입력 2개: 노래 장르 list, 노래별 재생횟수 list return: 베스트앨범 내 노래 고유번호 list
코드
def solution(genres, plays):
gen_type = set(genres)
gen_dict = {hash(a):0 for a in gen_type} #dictionary comprehension
genres = [hash(b) for b in genres] #list comprehension
zipped = list(enumerate(list(zip(genres, plays)))) #enumerate 통해 index 반환
for item in zipped:
gen_dict[item[1][0]] += item[1][1]
gen_dict = sorted(gen_dict.items(), key=lambda x : x[1], reverse=True) #how to sort dictionary #method 'sort' is not available
gen_sort = [x for x in list(map(lambda x: x[0], gen_dict))] #곡 재생수가 가장 큰 순으로 장르 나열
answer=[]
for gen in gen_sort:
a=[] #장르별 곡 리스트
for zips in zipped:
if zips[1][0]==gen:
a.append(zips)
else:
continue
a.sort(key=lambda x: x[1][1], reverse=True)
answer+=[x for x in list(map(lambda x: x[0], a[:2]))]
return answer
주요 도구
- 알고리즘: 해시(딕셔너리, 파이썬 hash 함수)
- dictionary comprehension: 딕셔너리 생성하여 각 장르를 key, 장르별 곡 재생수의 총합을 value로 정리함
- zip(리스트1, 리스트2)에 list를 한번 더 씌워야 함 => 각 튜플에도 다중 인덱스로 접근 가능
- index 정보를 반환해주는 enumerate에도 list를 한번 더 씌워야 함 => 마찬가지, 각 원소에 다중 인덱스로 접근 가능
- 기존에 value값이 0으로 저장된 딕셔너리에 [] 인덱스 통해 => 적절한 key값을 입력해줌
- 특정 기준으로 iterable 정렬하기: sorted & key & lambda의 조합! lambda 통해 iterable의 '각 원소'에 구체적으로 접근 가능.
-딕셔너리 정렬: 메서드 sort 대신 함수 sorted, 단.items()메소드 붙여야 함!
- map & lambda 조합 역시 중요: 주어진 이터러블 '각 원소'에 '동시에' 특정 함수를 적용하고 싶을 때.
map(함수, 이터러블) => map(lambda x: x~~, 이터러블)
마찬가지 map 이후 list 한번 더 씌워야 함.
- continue는 for문 처음으로 다시 돌아가는 것 vs return은 for문을 포함하여 함수 전체를 종료시키는 것
- indentation 아주 중요함. 엄밀한 논리 & 초반에 정확한 설계
다른 사람의 모범 풀이
def solution(genres, plays):
answer = []
d = {e:[] for e in set(genres)}
for e in zip(genres, plays, range(len(plays))):
d[e[0]].append([e[1] , e[2]])
genreSort =sorted(list(d.keys()), key= lambda x: sum( map(lambda y: y[0],d[x])), reverse = True)
for g in genreSort:
temp = [e[1] for e in sorted(d[g],key= lambda x: (x[0], -x[1]), reverse = True)]
answer += temp[:min(len(temp),2)]
return answer
: great for getting to grips with Sage Accounts before you move on to real data because any mistakes you make don't affect your live company
Structure of Policy Rules
Understanding how a policy rule is structured is helpful in understanding other Policy Management concepts. A policy rule is defined in an if-then structure, consisting of a set of conditions that the MPE device compares to information extracted from protocol messages or obtained from subscriber records, and a set of actions that are executed (or not executed) when the conditions match. Many conditions can be tested for existence or non-existence (by optionally selecting the logical operator NOT or using, where available, the policy condition operator is or is not).
Policy Parameters
When you define a policy rule, you select from a list of available conditions and actions. Most of the conditions and actions have parameters (that is, they contain placeholders that may be replaced with specific values to allow you to customize them as needed).
For example, consider the following policy rule, which has one condition and two actions:
where the device will be handling "greater than 100 upstream reserved flows"
apply profile Default Downstream Profile to request continue processing message
The condition, where the device will be handling..., allows the following parameters to be specified: - An operator (greater than) - A value (100) - The flow direction (upstream) - The bandwidth reservation type (reserved)
The first action, apply profile..., specifies a single parameter that is the name of a traffic profile to be applied to the request.
The second action, continue processing message, instructs the MPE device to evaluate the remaining rules within the policy rules list (as opposed to immediately accepting or rejecting the request). The conditions and actions that are available for writing policies are discussed later in this section.
- 단순히 기존 현실에 근거해서 생성되는 것이 다가 아니다! =>'새로운' 아이디어를 생성해내는 능력
- report나 essay를 작성하는 과정에서 실질적인 도움을 제공받을 수 있음
Broad CONCEPT
1) 기존의 GPT를 업그레이드 시킨 것, 즉 기본 model structure는 Transformer
2) GANs의 개념에 착안하여 text-based conversation에 적용함: input text에 대한 '현실적인' response를 출력
=> GANs concept의 엄청난 새로운 응용!
=> Transformer 구조 자체는 GANs의 구조와 무관함 (오해하지 말자~)
GANs(Generative Adversarial Networks)란? : 두 개의 competing networks(generator & discriminator)를 이용하여 현실과 가까운 output을 만들어내는 신경망 - generator가 fake output을 만들면 => discriminator는 fake와 real-world data 간의 차이를 식별하는 역할 - 양 간을 왔다갔다 하며 점차 real data와 구별하기 어려울 정도로 현실적인 output을 만들어낼 수 있게 됨
단순히 현실 정보를 추출하여 조합하는 방식이 아니라, 모델이 스스로 fictional creations을 생산해내는 것!
- 한편으로는 reality에 벗어나는 output이라고 평가할 수 있지만
- 달리 생각하면, 기존에 있던 것들 & 현실적인 상황에 갇히지 않고, 완전히 새로운 imaginary, creative, out-of-the-box 텍스트를 생산할 수 있다는 점에서 매우 유용하다
ChatGPT’s output only touches reality at a tangent But BEYOND the CONSTRAINTS of Our Everyday REALITY
METHODS
- 강화학습을 위한 Reward model
- Comparison data 이용: 여러 responses에 대한 rank를 매기고 이를 기반으로 reward models
- 최적화 및 파인튜닝: PPO(Proximal Policy Optimization)
https://openai.com/blog/chatgpt/
LIMITATION
- 잘못된 정보 생산 가능 (incorrect / nonsensical / biased)
- input 구절을 바꾸거나 꼬아서 작성할 때 / 같은 input을 여러 번 입력할 때 => 민감하게 반응
- 특정 phrase를 남용하거나 지나치게 장황한 text를 생산하는 경향
- 현재로서는 입력된 input(question)이 모호할 때 모델 스스로 질문의 의도를 추측하려는 경향이 있음
