달리기 경주 for문 안에서 in answer랑 callings 둘 다 배열인데 이렇게 하면 시간초과 날 확률이 높다 in때문에 결국 answer배열도 다 돌면서 사실상 2중 for문이 됨 -> 딕셔너리 2개 써서 하자 (프로그래머스/달리기경주) enumerate 리스트를 딕셔너리로 바꿔줌 -> 인덱스,값 으로 결과 파이썬 swap 파이썬에서 swap 하고 싶으면 이런식으로 하면 됨 딕셔너리에서 value값만 배열로 반환하고 싶다 자릿수 더하기 "hello"라는 문자열을 하나하나 자르고 싶다? str_list = list("hello") 하면 str_list에 하나하나 잘려서 들어가있음 [1차] 비밀지도 bin 10진수를 2진수로 변환하는 함수 tmp[2:].zfill(n) tmp[2:]는 앞에 2개를 지우는거임 (tmp는 배열아님 그냥 string) zfill(n)은 n자릿수 만큼 앞에다 0으로 채워

문제를 쪼개서 작은문제의 답을 구하고 그것을 이용해 더 큰 문제의 답을 구하는 방식 분할정복과 비슷 DP를 구현하는 2가지 방법 Top-Down 구현 : 재귀 저장 방식 : 메모이제이션 (memoization) Bottom-Up 구현 : 반복문 저장 방식 : 타뷸레이션 (tabulation) 메모이제이션 (memoization) 한 번 구한 답들은 다시 새로 구하지 않도록 저장해두자 cache에 저장해두고 바로 갖다 쓰자 필요한 부분의 문제들의 답만 구해놓는다 ( Lazy-Evalutaion) 빈 dp 테이블에 필요한 곳에만 답을 채워놓는 식 타뷸레이션 (tabulation) 부분문제들의 답을 미리 다 구해놓는다 (Eager - Evalutation) dp 테이블에 모두 값을 채워놓는다고 해서 타뷸레이션이라고 함

이진(이분) 탐색이란? > 살펴보는 범위를 절반 씩 줄여가며 답을 찾는 탐색임 따라서 정렬이 되어있어야 함 ex) A부터 Z까지 책이 정렬이 되어있을 때 Cook이라는 책을 찾고싶음 내가 임의로 책 하나를 골랐는데 그게 Y로 시작하는 책이면 내가 고른 그 책 포함 그뒤로는 다 제끼고 남은책들 중에서 고르면됨 이런식으로 반복해 나가는게 이진탐색 파라메트릭 서치 >최적화 문제를 결정 문제로 바꿔서 이진탐색으로 푸는 방법 최적화 문제 : 문제상황을 만족하는 변수의 최대,최소값을 구하는 문제 결정 문제 : Yes or No 문제 예를 들어 사람들이 나이순대로 쭉 있고 대통령 선거투표를 할 수 없는 사람 중 가장 나이많은사람을 찾고싶다(최적화 문제) -> 모든 사람들을 투표 가능하면 Yes, 못하면 No 로 바꾸어 푼다(결정 문제) 보통 문제가 주어지면 이것이 True인지 False인지 구분하는 함수를 만들어서 진행함 그래서 Parameter가 주어지면 True or

그래프 노드 무방향(=양뱡향) vs 방향 순환그래프 vs 비순환그래프 방향성 비순환 그래프 DAG (Diredcted Acyclic Graph) -> ex) VCS(버전관리 시스템) like git/github 코드로 그래프를 나타내는 방법 인접행렬 행렬에 갈수있으면 1 갈수없으면 0 시간 복잡도 O(V2) -> 정점 갯수의 제곱 인접리스트 한 노드로부터 갈 수 있는 노드들을 연결리스트로 시간 복잡도 O(V+E) -> 정점 갯수+간선 갯수 비교 공간과 시간은 trade off 관계임 인접행렬

배열 파이썬은 리스트를 사용해서 구현함 벡터 벡터는 잘 안씀 연결리스트 삽입/삭제 : O(1) 기본적으로 파이썬에는 연결리스트가 없어서 필요하면 직접 구현해야함 특징에는 특정 노드로 가기위해서는 바로 직전에 연결된 노드로 먼저 가야한다 그 특정 노드가 어디에 있는지는 연결된 노드들만 알고있기 떄문이다 스택 (Stack) 파이썬은 리스트로 구현함 삽입/삭제 : O(1) 큐 (Queue) 삽입/삭제 : O(1) 원래 파이썬에 from queue import Queue가 있긴한데 thread-safe (멀티쓰레딩 프로그래밍 시 필요)기능이 있어서 속도가 좀 느림 따라서 알고리즘 문제를 풀때는 멀티쓰레드를 고려하지 않아도 되기때문에 collections에 있는 deque을 사용함 deque은 double-ended-queue 임 그냥 queue랑 같은건데 앞뒤로 다 넣을 수 있는 queue라고 보면 됨 appendleft하면 왼쪽에서 넣고 그냥 append

input()은 한 줄의 입력을 모두 저장한다 따라서 공백이 포함된 문자열도 한 줄에 넣어 입력할 수 있다 > n = input.split() -> 123 456 ['123','456'] a,b = input().split() print(a) print(b) -> 2 8 2 8 a,b = map(int,input().split()) print(a + 2) print(b + 4) -> -1 1 1 5 배열 arr + 4byte x n 으로 메모리주소를 한 번에 계산을 해서 바로 접근하므로 탐색시간은 O(1)이다. 이렇게 바로 계산해서 접근하는 것을 임의접근(random access) 이라고 함 리스트 foods=["된장찌개","피자","파스타"] random.choice( ["된장찌개","피자"]) foods.append("김밥") -> 리스트의 추가방법 (append 이용) del foods[1] -> 1번 인덱스의 내용 삭제 반복문 ![]