python algorithm class
문자열 조작
문자열 immutable 한 문자 배열
str-obj 이므로 str-method 만 사용 가능함
자주 쓰는 것들
isalpha isdigit isalnum find/rfind
*split *join upper lower replace
valid palindrome
- 내가 생각한 풀이
upper 로 다 바꾸고
정규 표현식으로 영어만 가져오도록 한다
replace 를 통해 " " 공백을 다 없애도록 처리한다
len 을 통해 문자열 전체의 길이를 얻고
그 반만큼 range 를 통해 접근한다
arr[i] arr[i-1] 만큼을 비교한
str[::-1] 이 reverse 속도 제일 빠르다
- filter
filter(함수명이 들어옴 ex. str.isalnum, s)
filter 첫번째 인자로 오는것의 두번째에 s 를 넣어 true 로 나오는 것만 남기게 됨
join 은 문자열을 list 로 바꾸어주는 것 list 를 합쳐서 string 배열로 만듬
join 문자열 배열중에 isalpha num 에서 true 가 나오게 하는 것의 모음만을 남김
- re
re.sub('[^a-z0-9]', '', s)
배열에서 첫번째 조건에 맞는것을 다 '' 로 바꾸겠다
^ : 아래것들을 제외하고 라는 뜻
* revers string
- s.reverse
- s[i], s[len - i] = s[len -i], s[i]
- arr[::-1]
- while : while 다음 조건이 충족할때 까지 이므로 조건은 알지만 언제 끝날지 바로 알 수 없을 때
for : 언제 끝날지 완벽하게 알 때 (정수형으로 표현 가능할 때)
* two pointer 를 정확히 이해할 필요
왼쪽 끝 오른쪽 끝을 바꿈
left 와 right 가 같아지면 끝남
문제 ) 보석상
! 투포인터 간단한 문제
23415679
합이 16이 되는 구간 찾기
윈도우 크기를 키우면 val 커지고
윈도우 크기가 작아지면 val 작아짐
1. 오른쪽 가는것을 유지하되
2. 왼쪽으로 이동하는 경우 값이 최대를 넘어섰을때에
투포인터에 대한 과제를 좀 더 보고 보석상이라는 문제를 보자
조건을 충족하는 것을 빠르게 찾아내는 방법
엄청난 기교가 필요하진 않지만 technical 적인 구현이 가능한가를 봄
문제 )
다중 조건 정렬
문자와 숫자 나누어 담음
log 를 하나씩 넘김
split 하고 return 값이 배열 첫번째 요소가 숫자로만 이루어졌는가
isdigit 으로 보고 숫자만 넘기는 배열
문자만 담긴 배열 따로 넘김
split 을 하고 첫번째가 숫자인지 아닌지를 보자
letters + digits
비교를 할 수 있기 때문에 정렬이 가능함
정렬은 기준에 따라서 정렬을 하는것이지 기준 자체를 가질순 없음
숫자의 값이 대소 비교를 하였을 때에 큰/작은 값이 뒤로 감
lambda 익명 함수
key 에다가 lambda 왜 쓰나요
정렬 조건이 두개
key 는 값을 하나만 받을 수 있음
길이 수는 정렬이 가능
문자, 숫자, 입력순
x 를 입력을 받았을 때에 digit 은 정렬하지 않고 letters 만 정렬을 함
문자가 크기가 큰 순으로 온다는 뜻
다중 조건 정렬을 할 때에는 key 와 lambda 를 주고 우선 순위대로 다중조건 정렬이 된다는 것
0, 1, -1
compare 될 때 1 이랑 3
문자열이 오름차순인가, 입력 순서
order 라는 녀석은 isNum digit 1/0
첫번째는 숫자인 것이 더 크다는 것
다음은 content 가 오름차순인가를 보겠음
그다음은 id_num
compare to key 를 참고해라
첫번째 정렬 조건은 숫자
두번째 정렬 조건은 인식표의 길이에 1을 더해서 잘라낸 것
세번째 정렬 조건은 들어온 숫자대로 인식표 조건대로 정렬
문제) most common word
정규 표현식을 사용하여 영어만 가지도록 함
replace hit
공백 기준으로 split 을 하고 list 에 넣음
1. counter
2. dictionary 통해서 단어 넣기
list:0 for i list 하고 등장할 때 마다 더하기
dict 자료형
list 자료형은 문자 -> index 로 바꾼 다음에 접근이 가능해짐
dict 는 바로 접근이 가능해짐
ban 이라는 것을 사용가능해짐
list 는 숫자로만 값을 뽑아낼 수 있음
dict 는 char 숫자로도 다 값을 가질 수 있음,
tuple 이 있어서 dictionary 에 key 값으로 들어갈 수 있음
Counter 도 dictionary 로 구현하는 것이므로 dict 로 구현하는 것이 제일 정석
Anagrams
같은 anagrams 들끼리 묶어서 반환
split("")
set() 을 때린다음 같은거 끼리 묶기 key 로
dict 나 set 으로
dict 로 key 값 할당한 다음에
''.join(sorted(word))
anagrams[key].append(word)
** dict 에 있는 메소드
keys()
values()
items() 외우고이쑤
longest palidromic substring
재귀
1. 탈출 조건
2. 자기 자신을 다시 호출
-> 가변적인 반복을 처리하기 위함
while 문으로 치환되는 경우가 많음
for
횟수 불변
while
횟수 가변
부분 문제 : a 안에 a 가 있는 구조
문제 안에 문제가 반복되는 구조 가장 큰 정사각형은 전체가 됨
그다음 정사각형 4등분
탈출조건 명확함
같은 문제를 쪼개서 풀어나가는 것을 분할정복
동적 계획법 : 이전에 계산했던 값을 사용한다는
똑같은 값이 나올수도 있응께 기억해놨다가 갖다가 쓰자 라는 뜻
동적 계획법이다
DP
최대길이가 aba pelindrom 이면 abba 이면 중간도 pelindrom 바깥도 pelindrom 가장 긴 팰린드롬은
작은 팰린드롬의 합으로 이루어짐
subproblem 이다를 인지
중첩 연산이 발생할 수 밖에 없다
길이가 명확하니까 고민할 필요가 없음
2차원 dp : 골드 플레급 dp
중복확인할 필요없이 2차원 배열로 기억하면 효율이 좋음
다이나믹 프로그래밍
상태를 기준으로 코드를 뻗어나가며 의미가 있는 것과 아닌것을 찾기
포인터 두개 pelindrom 짝수 , 홀수가 생김
길이가 2인 pointer 3인 pointer 을 두고 밀기
첫번째는 2 두번째는 3 짝수 팰린드롬이랑 홀수 팰린드롬을 같이 판단하기 위해
제일 긴걸 찾는 것이니까 뒤로 쭉 밀어서 사용
left 와 right 범위를 받고 left 가 0보다 크고 right 가 0보다 작은지 판단
유효한 범위에 잇는동안 늘린다
맨 겉에 for 문 window swip
부분적으로 사용하는 재귀
만약 팰린드롬이라면 크기를 키움
expand 1 홀수
expand 2 짝수 판단
조건이 맞는 동안 계속 확장됨
선형적 확인이 필요
loop 를 길이 -1 만큼 돌게 됨
result 초기화는 공백으로 되어있음
max 에 key 를 줄 수 있음
재귀의 expand 가능
pelindrom 1, 2 가능
자기 자신 확인 가능
maximum 늘리고 return 가능
문자열 조작
문자열 method 암기
filter 함수
정규표현식
투포인터
다중 조건 정렬
stable sort : 안정 정렬 정렬 했을 때 나머지 값들이 바뀌지 않느뇽
12345 교체를 했을 때 나머지 다른 숫자의 흐름을 바뀌지 않는가 이런거
-> 앞선 문제에서 log 다중정렬 조건 digit 정렬 가능했던 이유가 stable sort 때문
split('') 는 에러 발생
split() 공백 전체 분리
split(" ") 공백 하나 분리
dict vs defaultdict(type)
연결 리스트
array : 배열 메모리 따닥 붙어놓음 (미리 할당) 공간 비효율적
linked list : linked list 위치가 같아도 되고 안같아도 됨 쓰는만큼만 효율적이게
list : list 도 똑같이 붙어있음, but... 파이썬의 타입을 결정가능 아무거나 설정 가능
배열의 크기가 다 똑같지 않음 그래서 찾아가는게 느릴수도 있음
파이썬 배열과 똑같지만 타입이 가변적이므로 메모리 주소를 c 언어처럼 빠르게 indexing 하기는 어렵음
파이썬에서 연결리스트는 예시를 하나 줌 value next linked list 가 팰린드롬이느뇽?...
linked list 가 어떻게 팰린드롬인가를 살펴보는 에시하나
그냥 list 를 stack 처럼 쓰는건 되지만 que 처럼 쓰는건 안됨
collections 의 deque 를 사용
linked list merge
while 문 두개 써서 안에 node 를 넣음
재귀로 짜면 6줄로 가능
reverse linked list
뒤집기 재귀적으로 뒤집으며 가기
하나 꺼내서 뽑아놓고 다음껄 뒤에 이어붙이고
또 다음껄 뒤에 이어붙임
pop 하여 이어붙이기
java runner 두명 뛰게 시킴
fast runner
slow runner
속도가 두배 차이가 나게 됨
중간을 아는게 중요함 -> merge sort
길이를 모르는 sort 에서 중간점을 어떻게 알아내느냐
linked list 뭔지 판서로 설명 가능
재귀 두가지 조건
deque
runner 기법
재귀 반복문의 비교
pop left 차이 왜 나는지 메모리 관점에서 설명 가능해야함
runner 기법 설명 가능해야함
while for 왜 치환이 안되는가
배열과 스택
graph : 비선형
선형 자료형 index
index 중요!
근거가 될 수 있음
index 가 고유하기 때문에 순서가 존재
순서가 있기 때문에 비교가 가능하고 정렬이 가능해짐
비교를 통해 정렬을 하니까
key 함수가 존재하게 됨
nums_map 할당 가능
expect num 에 target num 할당 가능
왈루프 연산자
target - num 을 dictionary 에 다 저장
technical 적인것을 사용
n^2 브루트 포스같은거
3 수의 합
아까 문제랑 다름
조건이 맞는 동안 범위를 조절할 수 있는 투 포인터
정렬 이분 탐색 빠르게
정렬이 되어있으면 탐색이 빠름
투 포인터를 빠르게 쓸거니까
세수의 합으로 0이 나오면 되니까 순서의 의미가 없음
투 포인터해서 0이 되는 지점을 찾음
n ^ 2 으로 풀림
반복문 n 을 도는 이유 고정점 하나 찍고 0이 충족될 때 까지 더함
결과가 충족되면 더해서 반영
효율 때문에 중요 -> -1,0,-1
조합이 중요해서 정렬을 했다면 똑같은건 붙어있음
사소한 디테일을 잡아서 최적화가 가능
Array Partition
합을 최대로 하는 값을 알아내라
값이 비슷한걸로 알아야한다
정렬을 하면 오름차순으로 간당
정렬 해버리고 짝수번째인걸 고르겠다
왼쪽걸 뽑아서 고르면 된당
파이썬스럽게 짜라 [::2] 정렬하고 두칸씩 띄워서 하겠다
이게 더 빠르다 pythonic
생각없이 흘러가는대로 포문 짜면 안됨
정직하게 푸는건 사치 -> 무조건 시간에 집중
순서도 정보이다 ( indexing )
투 포인터 ( two pointer )
slicing ( -1 로 뒤집기 등등이 가능 원하는대로 잘라내는게 자유자재로 가능함 )
1. 조건부 pop()
2. 재귀 반복
3. 우선순위 큐 -> 선입 선출 구조 급한 애부터 빠져나가는 것 최소값 최대값을 찾을 때에 사용
4. heapq -> 힙큐 사용할 때 가능
해시 테이블
list indexing 은 그저 숫자
dict 는 immutable 자료형
카카오 문제 신고 횟수세기
a user b user 이런거
anagram 문제 였던거 -> Counter
겹치는 문자 없이 제일 긴 pelindrom
top k frequent
1,1,1,2,2,3 제일 많이 나온거 출력
1 key 값 value 값 세기
2 key 값 value 값 세기
heap 최솟값 뽑아내기
크기 따지는 것 부호를 뒤집기
heap 을 만들어서 counter 된 것의 heappush 를 일일이 다 하기
heappop 을 할 때 마다 가장 큰게 뽑힘
hash table key immutable
default dict
comprehension
* 에스터리스크
zip수