사이트: 백준 / 프로그래머스 / 리트코드
접근 기준
최악의 경우 고려?
구현 위주?
가능한 이용 요소?
예외의 경우? 최저 최고
주의(막히면 생각 할 부분)
indent가 올바른가?
반복 시, loop 범위가 올바른가(과다, 부족, 오류 등)
예외의 경우? 0개 일 때 / 1개 일 때 / max 일 때 등
자료구조(DATA STRUCTURE)
Array
- add / delete 시 효율성 저하
add → 총 길이에 맞는 list를 재생산 / 기존 list 복붙 / 그 뒤에 add 요소
delete → delete원하는 요소 찾음(indexing 혹은 value로, 처음부터) / 지워 진 후 요소들 재정렬 필요
stack : First in Last out / 한 쪽 끝이 막힌 원통에 데이터가 들어갔다 나오려면? 이력관리,함수실행 콜스택 등
queue: First in First out/ 양 쪽이 뚫린 원통에 데이터가 들어가서 나오려면? 계산대, 프린트 순서 등 시계열대로
4.set
set는 밑에 쭉 정리해놈
알고리즘
(1) 해쉬
Key - value 를 이용한 접근
1.완주하지 못한 선수
내 풀이
1. 정확성 50 / 효율성 0
def solution(participant, completion):
for i in participant:
if i not in completion:
answer = i
break
completion.remove(i)
return answer
답
#collections.Counter()의 사칙연산 가능 특징 활용하여 key 호출
import collections
def solution(participant, completion):
answer = collections.Counter(participant) - collections.Counter(completion)
return list(answer.keys())[0]
2.의상
import collections
from functools import reduce
def solution(clothes):
#의상종류 갯수 list
type = [i[1] for i in clothes]
count_list = collections.Counter(type).values()
count_list = list(count_list)
#의상종류 1개인 경우
answer=1
if len(count_list)==1:
answer *= count_list[0]
return answer
#의상종류 2개 이상인 경우
for i in count_list:
answer *= (i+1)
answer = answer-1
return answer
답1
#lambda 이쁘게 변형, initializer 활용
def solution(clothes):
from collections import Counter
from functools import reduce
cnt = Counter([kind for name, kind in clothes])
answer = reduce(lambda x, y: x*(y+1), cnt.values(), 1) - 1
return answer
답2
#list 만들 때 부터 for 구문으로 이쁘게 만들기
import collections
from functools import reduce
def solution(c):
return reduce(lambda x,y:x*y,[a+1 for a in collections.Counter([x[1] for x in c]).values()])-1
답3
def solution(clothes):
clothes_type = {}
#Counter 대신 dict에 갯수 담기
for c, t in clothes:
if t not in clothes_type:
clothes_type[t] = 2
else:
clothes_type[t] += 1
#갯수 list 받아서 요소곱
cnt = 1
for num in clothes_type.values():
cnt *= num
return cnt - 1- 베스트 앨범
def solution(genres, plays):
#장르 별 총 재생횟수로 배열
data = list(zip(genres,plays))
data_dict = {}
for key, value in data:
if key not in data_dict:
data_dict[key] = value
else :
data_dict[key] += value
sorted_genres = sorted(data_dict.items(), key = lambda x : -x[1])
#장르 내 에서 노래 별 재생횟수에 따른 배열
answer2 = []
for k,v in sorted_genres:
answer=[]
sorted_play = [(n,i[1]) for n,i in enumerate(data) if i[0]==k]
answer.extend(sorted_play)
answer = sorted(answer,key = lambda x: (-x[1],x[0]))
answer = [i[0] for n,i in enumerate(answer) if n <2]
answer2.extend(answer)
return answer2- 전화번호
import collections
def solution(phone_book):
phone_dict = collections.defaultdict(str)
for phone_number in phone_book:
phone_dict[phone_number]
for phone_number in phone_book:
temp=''
for number in phone_number:
temp += number
if temp in phone_dict and temp != phone_number:
return False
return True
temp in list 보다 temp in dict로 hash 형태 사용 시, 시간효율성 훨씬 양호해진다
indexing아닌 temp in list는 O(N), indexing / key hashing으로 찾는게 훨씬 양호hash()
: string을 int로 보고 싶을 때 , 단방향만 가능
if 로 경우의 수를 나누기보다, 케이스마다 키-밸류로 표현해서 응용할 생각해보자
(2) queue
import math
def solution(progresses, speeds):
remains = [int(math.ceil((100-a)/b)) for (a,b) in zip(progresses, speeds)]
temp = 0
upper = remains[0] #기준
result = []
for remain in remains:
if remain > upper:
result.append(temp)
temp = 0 # 초기화
upper = remain #기준 바꿈
temp += 1
result.append(temp)
return result
1. remains 구하지 않고, 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. while 조건문 형식 : True / ~까지 / ~부터
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
3. 기준점 밀어주기 + except로 error 예외처리
from math import ceil
def solution(progresses, speeds):
daysLeft = list(map(lambda x: (ceil((100 - progresses[x]) / speeds[x])), range(len(progresses))))
count = 1
retList = []
for i in range(len(daysLeft)):
try:
if daysLeft[i] < daysLeft[i + 1]:
retList.append(count)
count = 1
else:
daysLeft[i + 1] = daysLeft[i] # 기준 점 밀어주기
count += 1
except IndexError: #예외처리로 마지막 방점
retList.append(count)
return retList(4) 정렬
- k 번째 수 찾기
1. map과 lambda의 조화 , sorted(list) 하면 바로 정렬
def solution(array, commands):
return list(map(lambda x:sorted(array[x[0]-1:x[1]])[x[2]-1], commands))(5) 완전탐색
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
def solution(answers):
p = [[1, 2, 3, 4, 5],
[2, 1, 2, 3, 2, 4, 2, 5],
[3, 3, 1, 1, 2, 2, 4, 4, 5, 5]]
s = [0] * len(p)
for q, a in enumerate(answers):
for i, v in enumerate(p):
if a == v[q % len(v)]:
s[i] += 1
return [i + 1 for i, v in enumerate(s) if v == max(s)]
#cycle의 사용
from itertools import cycle
def solution(answers):
giveups = [
cycle([1,2,3,4,5]),
cycle([2,1,2,3,2,4,2,5]),
cycle([3,3,1,1,2,2,4,4,5,5]),
]
scores = [0, 0, 0]
for num in answers:
for i in range(3):
if next(giveups[i]) == num:
scores[i] += 1
highest = max(scores)
return [i + 1 for i, v in enumerate(scores) if v == highest]2.약수 /몫/나머지 넓이 / 둘레 이용한 도형 문제
def solution(brown, red):
for i in range(1, int(red**(1/2))+1): #가로가 같거나 더 길어서
if red % i == 0: #조건 만족하면 약수이다
if 2*(i + red//i) == brown-4:
return [red//i+2, i+2]
def solution(brown, red):
nm = brown + red
for n in range(1, nm+1):
if nm%n != 0:
continue #반복loop로 강제 회귀
m = nm//n
if (n-2)*(m-2) == red:
return sorted([n, m], reverse = True) # 가로가 같거나 더 길어서(6) DFS
1.조합
-가 붙을 모든 조합구하기
import itertools #모든 조합을 위해!
def solution(numbers, target):
answer = 0
asum=0
alist=[]
goal = sum(numbers)-target
for i in range(len(numbers)):
alist.append(i)
for j in range(len(numbers)):
mypermutation = itertools.combinations(alist,j+1)
for s in mypermutation: #각 조합에서의 모든 경우에서
for k in s:
asum = asum + numbers[k]*2
if asum == goal:
answer = answer + 1
asum=0
return answer
-------------
POP 과 범위 이용
def solution(numbers, target):
q = [0]
for n in numbers:
s = []
for _ in range(len(q)):
x = q.pop()
s.append(x + n)
s.append(x + n*(-1))
q = s.copy()
return q.count(target)
------------
dfs 따로 정의 / 재귀함수
def dfs(nums, i, n, t):
ret = 0
if i==len(nums):
if n==t: return 1
else: return 0
ret += dfs(nums, i+1, n+nums[i], t)
ret += dfs(nums, i+1, n-nums[i], t)
return ret
def solution(numbers, target):
answer = dfs(numbers, 0, 0, target)
return answer
answer = 0
def DFS(idx, numbers, target, value):
global answer
N = len(numbers)
if(idx== N and target == value):
answer += 1
return #재귀 종료할 때 사용
if(idx == N):
return
DFS(idx+1,numbers,target,value+numbers[idx])
DFS(idx+1,numbers,target,value-numbers[idx])
def solution(numbers, target):
global answer
DFS(0,numbers,target,0)
return answer
----------
모든 조합 / 언팩킹 / product / sum / map
from itertools import product
def solution(numbers, target):
l = [(x, -x) for x in numbers]
s = list(map(sum, product(*l)))
return s.count(target)
------
재귀함수
def solution(numbers, target):
if not numbers and target == 0 :
return 1
elif not numbers:
return 0
else:
return solution(numbers[1:], target-numbers[0]) + solution(numbers[1:], target+numbers[0])2.단어변환
list 대신 deque 이용 / 문자열 간 zip/dict.get(key,default) / generator(yeild)
from collections import deque
def get_adjacent(current, words):
for word in words:
if len(current) != len(word):
continue
count = 0
for c, w in zip(current, word):
if c != w:
count += 1
if count == 1:
yield word
def solution(begin, target, words):
dist = {begin: 0}
queue = deque([begin])
while queue:
current = queue.popleft()
for next_word in get_adjacent(current, words):
if next_word not in dist:
dist[next_word] = dist[current] + 1
queue.append(next_word)
return dist.get(target, 0)
----
range / list 내 true,false 들의 sum / DFS의 이중배열을 하나 씩 표현하면서 진행
def solution(begin, target, words):
answer = 0
Q = [begin]
while True:
temp_Q = []
for word_1 in Q:
if word_1 == target:
return answer
for i in range(len(words)-1, -1, -1):
word_2 = words[i]
if sum([x!=y for x, y in zip(word_1, word_2)]) == 1:
temp_Q.append(words.pop(i))
if not temp_Q:
return 0
Q = temp_Q
answer += 1
---------
lambda 를 변수로 정의
transistable = lambda a,b: sum((1 if x!=y else 0) for x,y in zip(a,b)) == 1
visited = defaultdict(lambda: False)
함수 추가 사용 2개,3개 ...
----------
재귀함수
def DFS(begin,target,words,cnt):
result=[]
for word in words:
temp=0
for i in range(len(begin)):
if begin[i]==word[i]:
temp+=1
if temp == len(begin)-1 and word==target:
return cnt
if temp == len(begin)-1 and word!=target:
result.append(word)
if not result: return 0
cnt +=1
answer_list=[]
for i in result:
w=words.copy()
w.remove(i)
answer_list.append(DFS(i,target,w,cnt))
return min(answer_list)
def solution(begin, target, words):
if target not in words:
return 0
cnt=1
answer=DFS(begin,target,words,cnt)
return answer
(7) BFS
거리두기 문제: BFS 정리
def bfs 로 start node(index)기준으로 완전히 훑고
/ visited에 0이 남아있으면, start node 변경해가면서 완전히 훑고, visited에 0 없을때까지
def bfs(computers, visited, start):
stack = [start]
while stack:
j = stack.pop()
if visited[j]:
continue #수행속도 증가
for i in range(0, len(computers)):
if computers[j][i] ==1 and visited[i] == 0:
visited[j] = 1
stack.append(i)
def solution(n, computers):
answer = 0
visited = [0 for i in range(n)]
i=0
while 0 in visited:
if visited[i] ==0:
dfs(computers, visited, i)
answer +=1
i+=1
return answer
-----
def BFS를 정의하고(전체 2차배열, visit array, 시작 node(2차배열index)) / 전체 훑으면서 방문 표시 / visited=0인 첫 번째 index로 옮겨가면서 BFS 반복
def BFS(computers,visit,node):
que = [node]
visit[node] = 1
while que:
v = que.pop(0)
for i in range(n):
if computers[v][i] == 1 and visit[i] == 0:
visit[i] = 1
que.append(i)
return visit
def solution(n, computers):
visit = [0 for i in range(n)]
answer = 0
for i in range(n):
try:
visit = BFS(computers, visit,visit.index(0))
answer += 1
except:
break
return answer
(8)트리 순회
(9) heap 정렬
우선순위queue
heapq
(10) 특정 합 가지는 부분 연속 수열 - 투포인트
#start/end point 제일 왼쪽부터 시작, 합보다 작으면 end 이동, 합보다 크면 start 이동
#데이터 갯수 n과 부분 연속 수열의 합 m 받기
n,m = 5,5
data=[1,2,3,4,5]
result=0
summary=0
end=0
for start in range(n):
#end를 가능한만큼 이동시키기
while summary<m and end<n:
summary += data[end]
end +=1
#부분 합이 m일 때 카운트 증가
if summary == m:
result +=1
summary -= data[start]
print(result)#구간 합 계산
#데이터의 개수 M과 데이터 입력 받기
n=5
data=[10,20,30,40,50]
#prefix sum 배열 계산
summary=0
prefix_sum=[0]
for i in data:
summary +=i
prefix_sum.append(summary)
right, left 주어졌을 때
answer = prefix_sum[right]-prefix_sum[left-1](11) 최단경로: 다익스트라 알고리즘
#특정 node에서 모든 node에 대한 최단경로 구하기
#특정 node 기준으로 각 node에 대한 경로 구하고(미연결은 무한), node(index)에 대한 경로값(value)로!
#최소경로인 node(index)부터 방문하여 해당 node를 거쳐 다른 node로 갔을 때 경로값을, 기존 특정된 node에서 갔을 때 값과 비교하여 더 작을 시 값 변경해준다
파이썬 함수 정리
풀이 tip
자유롭게 마음껏 생각하자
dict의 keyvalue 시 value에 list도 가능
-> iterator 간 서로의 요소가 될 수 있다
형식 상 정의하는 변수는 _ 처리하자
-> for _,v in list
반복 활용 위해서는?
while(조건문 잘 만들기)
for (하나 발라내서 잘 정의하고, 끝까지~~)
temp in list 보다 temp in dict로 hash 형태 사용 시, 시간효율성 훨씬 양호해진다
indexing아닌 temp in list는 O(N), indexing / key hashing으로 찾는게 훨씬 양호**List에서 특정요소 지우기**
1) del list[index] : 특정 인덱스 삭제 / slicing 범위로 지우기 가능
2) list.remove(value) : 특정 value 삭제, 첫 번째 1개 지운다
3) list.pop(index) :특정 인덱스 삭제, ()이면 가장 마지막 요소 지운다
4) list comprehension + 조건문 으로 삭제
lst = [4, 3, 2, 3, 1]
lst = [item for item in lst if item != 3 and item != 1]
**파이썬 기타 함수 간략 정리**
- import collections / Counter(list)
****collections.Counter(list) : list 요소를 key로, 각 요소의 갯수를 value로 dict 형태 만듬
li = [1,2,3,1,2], collections.Counter(li) -> {1:2, 2:2, 3:1}
collection.Counter 객체 간
더하기 : Counter의 객체인 dict 끼리 합
빼기 : Counter의 객체인 dict 끼리 합
교집합
합집합
update : Counter의 객체인 dict 끼리 합
most_common(n=~) : n번째까지 가장 갯수 많은 요소를 [(요소,갯수),(요소,갯수)..] 형태로 반환
가능하다
- reduce(함수 , list , (초기값, 안쓰면 None))
- (lambda 인수 : 함수로직) 이름없는 함수를 정의, 결과 값을 return
- map(lambda 등 함수 , list) : list를 return
- zip(list1, list2) : 동일
list 간 같은 index 값끼리 묶어서 tuple 나열식으로 반환
더 긴 list 쪽의 남은 data는 버림
- operator
:연산처리속도 증가 가능
예시)
import operator
reduce(operator.mul, iterator)
a=[1,2,3,4,5]
b=reduce(lambda x,y:x+y, a)
c=reduce(operator.add,a)
https://noodle-dev.tistory.com/83
연사자 오버로딩/언더스코어/매직매소드
https://planbs.tistory.com/entry/Python-%EC%97%B0%EC%82%B0%EC%9E%90-%EC%98%A4%EB%B2%84%EB%A1%9C%EB%94%A9
- list_comprehension
for ~ in ~ if 조건문
if ~ else ~
- slicing: list[시작(이상):끝(미만):간격] 잘라진 범위 list로 return
a = ['a', 'b', 'c', 'd', 'e']
# 인덱스 1 ~ 3까지의 값을 거꾸로 가져오기
>>> a[ 3 : 0 : -1] #-1은 거꾸로 가져오기, slicing 방향
['d', 'c', 'b']
- range(시작:끝:간격) : 범위 내 int로 표현 된 list return
range(4) : 4미만
range(5,8) : 5이상 8미만
&주의
slicing과 range모두 -로 간격 시 시작이 끝보다 크게 범위 지정
- filter(lambda 등 함수로 조건, list나 range로 범위) : list 를 return
예시: test_list라는 list에서 요소가 3인 index의 배열
list(filter(lambda x: test_list[x] == 3, range(len(test_list))))
- enumerate(list) : index, value 쌍으로 반환
- attrgetter , itemgetter
- 정규표현식
# import re
# #전방주의
# a = "abc12?님이 나갔습니다."
# b= re.sub('[가-힣a-zA-Z0-9+-_.?!]+(?=님이)','사과',a)
- heapq
a = sorted(a, reverse=True) > a.sort(reverse=True)
a,b = b,a
heap 구조: [0]이 최소값, [K]가 항상 [2K+1],[2K+2]보다 작은 구조
import heapq :
hq.heapify(list) : hq에 list를 heap구조로 정렬 hq.heappop(list): 최소node[0]을 호출하고, hq는 [0] 제외된 list의 heap 구조됨
hq.heappush(list, a) : list에 node 'a'를 넣고 heap 구조
heap의 의미와 시간복잡도 상의 이득 알기
import heapq as hq
def solution(scoville, K):
hq.heapify(scoville)
answer = 0
while True:
first = hq.heappop(scoville)
if first >= K:
break
if len(scoville) == 0:
return -1
second = hq.heappop(scoville)
hq.heappush(scoville, first + second*2)
answer += 1
return answer
- deque() : 자료구조
https://chaewonkong.github.io/posts/python-deque.html
보통 큐(queue)는 선입선출(FIFO) 방식으로 작동한다. 반면, 양방향 큐가 있는데 그것이 바로 데크(deque)다.
즉, 앞, 뒤 양쪽 방향에서 엘리먼트(element)를 추가하거나 제거할 수 있다.
데크는 양 끝 엘리먼트의 append와 pop이 압도적으로 빠르다.
컨테이너(container)의 양끝 엘리먼트(element)에 접근하여 삽입 또는 제거를 할 경우, 일반적인 리스트(list)가 이러한 연산에 O(n)이 소요되는 데 반해, 데크(deque)는 O(1)로 접근 가능하다.
예시)
from collections import deque
deq = deque()
#Add element to the start
deq.appendleft(10)
#Add element to the end
deq.append(0)
#Pop element from the start
deq.popleft()
#Pop element from the end
deq.pop()
deque.append(item): item을 데크의 오른쪽 끝에 삽입한다.
deque.appendleft(item): item을 데크의 왼쪽 끝에 삽입한다.
deque.pop(): 데크의 오른쪽 끝 엘리먼트를 가져오는 동시에 데크에서 삭제한다.
deque.popleft(): 데크의 왼쪽 끝 엘리먼트를 가져오는 동시에 데크에서 삭제한다.
deque.extend(array): 주어진 배열(array)을 순환하면서 데크의 오른쪽에 추가한다.
deque.extendleft(array): 주어진 배열(array)을 순환하면서 데크의 왼쪽에 추가한다.
deque.remove(item): item을 데크에서 찾아 삭제한다.
deque.rotate(num): 데크를 num만큼 회전한다(양수면 오른쪽, 음수면 왼쪽).-
순열 / 조합 / product
from iteratools import
permutations(list, 갯수)
combinations(list, 갯수)
list=product(list1,list2) -
sum의 이해
sum(iterable)
sum(iterable, 시작값)
map(sum,iterable)과 reduce(lambda x,y: x+y, iterable,시작값default0) 차이 알기 -
비트연산자
파이썬 set 함수 정리
{[list]} : set는 주로 list형태에 set을 씌워 만든다
set(list)
set(tuple)
list(set)
list(tuple)
가능하다
- 중복확인 가능
def isDuplicated(arr):
in_set = set(arr)
return len(in_set)<len(arr) # bool값으로 return받아 duplicate여부 확인
-집합관계
교집합 : s1&s2 혹은 s1.intersection(s2)
합집합 : s1 | s2 혹은 s1.union(s2)
차집합 : s2 - s1 혹은 s2.difference(s1)
- add / update / remove
add: 1개 추가s1 = set([1, 2, 3])
s1.add(4)
update: 여러개 추가
s1 = set([1, 2, 3])
s1.update([4, 5, 6])
remove: 특정값 추가
s1 = set([1, 2, 3])
s1.remove(2)
파이썬 list 함수 간략 정리
[ ]
sorted(list, key= len 등 정렬가능한 함수, reverse=bool)
https://blockdmask.tistory.com/466
예시: key=lambda x:(x[1], -x[0]) , x[1] 기준으로 정렬 후 동일한 요소끼리 x[0]역순으로 추가 정렬
list.count(value) : 해당 value의 갯수 return
list 요소 곱 구하기:
result = reduce(lambda x,y:x*y, lit)
%주의 :
reduce를 이용하므로 이 상태 그대로 써야 요소 곱 된다
lambda를 이용한 식 변경은 reduce고려해야함, 주의하자
list.append(요소로 더해짐)
list.extend(list간 + 와 동일하게 더해짐)
: 따로 정의하지 않고 list 자체 업데이트
for i in range(): index 적용으로 list간 요소 사칙연산 가능
파이썬 2차원 list 정리
for x,y in list 로 풀어내기 가능
list = [[0]*m for _ in range(n)] : nxm 2차원 리스트 표현
2차원 list.sort() : 각 요소의 첫번째 요소 기준으로 정렬
이중for문 list comprehension
new_words =
for word_list in words:
for word in word_list:
if len(word) > 4:
new_words.append(word)
(comprehension)
new_words = [ word for word_list in words for word in word_list if len(word) > 4]
파이썬 tuple 함수 간략 정리
파이썬 dict 함수 간략 정리
{key : value}
list(dict) : dict key로 list 정렬
dict.keys() : key list 정렬, dict_key type이다, list()필요
dict.values() : value list 정렬, 이 때 정확히는 dict_value type이므로
연산하거나 요소 확인 필요 시, list(dict.values())로 type 변경 필요
dict.items() : (key,value)로 tuple 반환, key와 value로 for 구문 작성 시 사용
dict[key] = value : key에 해당하는 value 수정하거나 / key: value 추가
dict.get(key, default) : key에 관한 value 가져오거나 / key 없으면 default를 key로 하여 value가져온다
dict(list(tuple,tuple..)) : list 요소인 tuple들을 dict 형태로 전환
예)
persons = [('김기수', 30), ('홍대길', 35), ('강찬수', 25)]
mydict = dict(persons)
age = mydict["홍대길"]
print(age) # 35
import collections
defaultdict(int) : (key는 항상 str이다)
value를 int로 가지는 defaultdict 인 {}를 만든다, 아무 입력 없으면 default=0
value를 str로 가지는 defaultdict 인 {}를 만든다, 아무 입력 없으면 default=''
<defaultdict 없이 dict 만들기>
data_dict = {} #빈 dict 만들고, key 있는 경우와 없는 경우 나누어 dict 완성
if key not in data_dict:
data_dict[key] = value
else :
data_dict[key] += value
<defaultdict로 dict 만들기>
#data_dict={} 와 data_dict[key]=value 과정 생략하고 error없이 바로 만들 수 있다
data_dict = collections.defaultdict(int)
for key, value in data:
data_dict[key] += value
phone_dict = collections.defaultdict(int)
for phone_number in a:
phone_dict[phone_number]
<dict max value값의 key 구하기>
max(di,key=di.get) # di.get 이용, 1개만나옴
[k for k,v in di.items() if max(di.values()) == v] # 리스트 컴프리헨션 이용, 중복 max 전부 나옴
```python
알고리즘 이론 정리
-최빈출
그리디
구현
DFS / BFS
정렬
- 시간 복잡도
(공간 복잡도, 메모리 효율 늘리기는 메모리 발전으로 덜 중요)
10초 안에 모두 실행될 수 있도록
1초 기준 / python은 2000만번정도 생각하고 풀면 합리적
N 범위 500 : 시간 복잡도 O(N3)
N 범위 2,000 : 시간 복잡도 O(N2)
N 범위 100,000 : 시간 복잡도 O(NlogN)
N 범위 10,000,000 : 시간 복잡도 O(N)
- 자료구조
~숫자형
정수형
실수형
round(value, 소수점아래자리)
-----------
~list
-----------
~문자열
print( 값 , end='') #한 줄 뛰기 안 할 때
strip: 양쪽 제일 끝에 있는 것 중 일치하는 것만 strip
lstrip
strip
.find
.findall
replace(올드,뉴,몇개?)(디폴트: 모두대체)
빈 칸 넣으려면:’(스페이스바)’
https://dojang.io/mod/page/view.php?id=2299
~tuple
메모리 작고 / 요소 변경할 수 없으며, 참조만 할 수 있다
-----------
~dict
~set
------------
~ 조건문
bool
break / pass 뒤 순서 진행 / continue 강제로 loop로 돌아가 반복
~ 반복문
--------------
~함수
a
def fun(*arg,**kwarg)
global a
return ~~
~lambda x,y : ~~
----------------
유용한 라이브러리
~내장함수
// 몫
% 나머지
a += b
a -= b
a *= b
a //= b # a에 b를 나눈 몫을 a로 한다, a = a//b
~itertools:
순열 permutations(list, 몇 개)
product(list, 몇 개) : 동일 원소를 중복으로 뽑는 것 허용
조합 combinations(list, 몇 개)
combinations_with_replacement(list,몇 개): 동일 원소를 중복으로 뽑는 것 허용
~heapq
~bisect
~collections:
deque
Counter(list) : key와 등장횟수 value 지니며 dict 반환
~math : 최대공약수 / 최소공배수 /팩토리얼 / 원주율
import math
최대공약수
math.gcd(a,b)
최소공배수
lcm = a*b//math.gcd(a,b)
-----------------
~그리디 알고리즘(탐욕법)
현재 개별 상황에서 지금 당장 좋은 것만 고르는 방법
최소한의 아이디어가 필요
정당성 분석이 중요하다: 각 상황에서 최적의 선택만 한다면 최종적으로 최적의 해 일까?
그렇지 않은 경우도 많지만, 그리디 문제는 최적의 선택이 중첩 시 최적의 해가 나오도록 출제
1.최소한의 아이디어를 내서
2.그리디하게 풀이 후(최적의 선택만하며)
3.정당성(최적의 선택만 한다면 최종적으로 가장 올바른 해 일까?)분석한다
예시: 모험자 길드
최대 그룹이므로, 배열 후 작은 수부터 하나씩 그룹에 넣고, 그룹 내 요소갯수가 조건 만족 시에만 result에 +1, 만족 못하면 자동으로 count 안 됨
def adventure(traveler):
traveler.sort()
count = 0
result = 0
for i in traveler:
count +=1
if count>=i:
result +=1
count = 0
return result
~구현문제 : 시뮬레이션과 완전 탐색 (시뮬, 구현, 완전탐색은 비슷하다, 충실하게 구현하자)
구현이란, 머리속에 있는 알고리즘을 소스코드로 바꾸는 과정
구현유형: 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려우 문제를 지칭
1. 2차원 공간 행렬(세로 x 가로)
중요: (세로, 가로)이므로 xy 축을 세로x, 가로y 눕혀서 본다
시뮬레이션 및 완전탐색 문제에서는 2차원 공간에서 방향벡터 활용
방향 벡터
dx = [0,-1,0,1]
dy = [1,0,-1,0]
현재 위치 : (x,y)
이동 후 위치 : x = x+dx[i] / y = y+dy[i]
예시: 여행자 상하좌우, (1,1) 좌상단에서 출발, 범위 벗어나면 명령 무시
plan = [이동명령~~]
n=가로와 세로 크기, 즉 총 n2의 면적
x,y = 1,1
#dx,dy 방향벡터와 move 명령어 index 맞춤
dx = [0,0,-1,1]
dy = [-1,1,0,0]
move = ['L','R','U','D']
#혹은 move_list 로 통일해도 될 듯..빠른걸로 사용하자
move_list= [['L',0,-1],['R',0,1],['U',-1,0],['D',1,0]]
for plan in plans :
for i in range(len(move)):
if plan == move[i]:
nx = x +dx[i]
ny = y +dy[i]
if nx<1 or ny<1 or nx>n or ny>n: #가로세로 최소범위1 최대범위n 외부에 있으면
continue # 범위나갔으니, 명령무시하고, 다음 for 구문 돌려라
x,y = nx, ny # 범위 나간게 아니면, 명령 수행해라
print(x,y)
2. 시간 문제
그냥 쭉 나열, 최대 86400이므로 그냥 구현 할 만하다(brute forcing, 가능한 모든 경우 구해도 될 때)
count=0
for i in range(h+1):
for j in range(60):
for k in range(60):
if '3' in str(i)+str(j)+str(k):
count+=1
print(count)
3. 문자열재정렬
#서로 다른 그릇에 담아 정렬 후, 다시 합치자
data = 'asdr1vfsb4v7'
result = [] #alphbet은 list에 담자
value = 0 #num는 변수에 더하면서 담자
for x in data:
if x.isalpha():
result.append(x)
else:
value += int(x)
result.sort()
if value !=0:
result.append(str(value))
result = ''.join(result)
4. 문자열 판단
#isupper(),upper(),islower(),lower()
#isalpha(),isdigit(),isalnum()
5. binary한 표현(이진법)
이진법과 문자열 보기 : 비밀지도 문제와 해답 반드시 확인
https://comgong-man.tistory.com/59
---------------------------
- 그래프 탐색 알고리즘: DFS/ BFS
많은 데이터 중 원하는 데이터를 탐색하여 찾는 과정,(노드 위를 이동)
- stack자료구조: 선입 후출, 입구와 출구가 동일한 형태, 세워져있는 블록 생각
list.append(a)
list.append(b)
list.append(3)
list.append(d)
list.pop() #마지막 in이 첫번째 out : 원래 알던 list 상 구조
ab3d -> ab3
- queue자료구조: 선입 선출, 차례대로 들어가서 차례대로 나옴, 눕혀져는 블록 생각
시간효율성을 위해! list 사용하지않고 deque() 사용한다
from collecions import deque
queue = deque()
queue.append(a)
queue.append(b)
queue.append(c)
queue.append(d)
queue.popleft() #선 in, 선 out
abcd -> bcd
-재귀함수
함수가 자기 스스로를 호출, 반복문을 쓰지 않고 반복을 재귀적으로 표현 할 수 있다.
모든 반복문과 재귀함수는 서로 표현 할 수 있다, 특히 스택 표현 시 사용 가능
제일 먼저 종료조건을 반드시 생각하고 명시해야한다
예시
def recursive_function():
if i ==100:
return #종료 조건
print('a')
recursive_function(i+1)
print('b')
#함수 호출
def recursive_function()
#호출
a
a
..100번
b
b
..100번
~~DFS(Depth-First Search): 깊이 우선 탐색
탐색 시작 노드로부터 / 깊은 부분을 우선적으로 방문하면서 / 탐색하는 알고리즘
자료구조:스택과 재귀함수를 이용한다
예제
graph = [] node를 2차원 list로 표현
(index를 node로 보고 해당 node에 인접하는 node를 list에 넣는다)
(보통 1부터 시작하므로 index 0에[]넣어주고 시작한다)
visited = [ ] 여부 표현 list
~~BFS(Breadth-First Search)
BFS는 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘
큐 자료구조 활용(queue = deque())
탐색시작 노드를 큐에 삽입하고 방문 처리
큐에서 노드를 꺼낸 뒤 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리합니다
반복
재귀함수를 통한 깊이 탐색 방법, 특정 기준에 따라 노드의 깊이 방향으로 탐색 지속
개발아 사이좋게 지내자