🧚🏻‍♀️알고리즘 tip! 모으기🧚🏻‍♀️

🧚🏻‍♀️알고리즘 tip!🧚🏻‍♀️

 

- 반복해서 쓰이는 것이 있을 시

한번만 구해 리스트에 넣어놓고 사용한다.

+ 구간합!

---

- 자료구조 여러 개 쓸 때 '인덱스 번호' 활용하여 쓰기 ( 인덱스 번호와 실제 값 유리시키기)

라고 써놨는데 무슨말이냐

과거의 은체야 이해가 안 돼

---

- 펠린드롬 수를 구할 때

- "연속된" 뭔가에 대한 값을 구할 때

- 두 개를 골라야 할 때

등

 투 포인터를 이용하자

---

- 리스트에서 범위를 유지시키며 탐색할 때 (IOIOI문제같이)

슬라이딩 윈도우를 이용하자

---

- 2차원 리스트에서 깊이 등 찾기

리스트에 표시하며 활용하기 

---

- 백트래킹(역순 문자열 만들기, 등)

- 깊이 우선 탐색할 떼

- 두개 짝지어서 연결할 때 

등 선입후출 필요시

스택 쓰기

 

 

- 원형 형태의 데이터 필요 시

- 너비 우선 탐색할 때

등 선입 선출 필요할 때

큐 쓰기

 

덱도  적당히 기억하고 쓰기

---

스택 쓸 때 ( 자료 탐색 많이 할 때)

리스트 쓰기

 

 

큐 덱 쓸 때 (맨 뒤 아닌 곳에서 데이터 삽입/삭제 많이 할 때)

컬렉션 모듈 덱 / 큐 모듈의 큐 클래스 사용하기

---

- 쪼개는 거 느낌이 재귀면 재귀를 쓰면 됨 (?)

---

- 최대공약수 구할 때

유클리드 호제법을 사용

1 ) 큰 수를 작은 수로 나누는 MOD 연산 수행
2 ) 앞 단계에서의 작은 수와 MOD 연산 결과값(나머지)로 MOD 연산 수행
3 ) 단계 2를 반복하다가 MOD 값이 0이 되는 순간의 작은 수가 최대공약수

---

- 소수 구할 때

에라토스테네스의 체를 사용

 

해당 수보다 작은 수 나누어지는지 전부 확인하기 X

아 물론 하나만 확인하면 되면 이게 더 나을듯

 

math.sqrt() 이용 권장

---

- 문제가 그리디 삘인지 잘 확인해보기

---

대체로 sort() 좋지만

상황이랑 시간제한 눈치 보고

기수계수 정렬 등 사용하기

 

 

버블? 선택? 삽입? 퀵? 병합? 정렬 기억

---

- 단절점/선 찾기

- 사이클 찾기

- 위상정렬

- 깊이(연결고리)

DFS 쓰기

 

 

-  최단 깊이(거리) 찾기

근처 먼저 보기

BFS 쓰기

---

 

비둘기집 원리!

n개 보다 많은 물건을 n개의 집합에 나누어 넣는다면 적어도 어느 한 집합에는 2개 이상의 물건이 속하게 된다는 내용

적용되는지 확인 후 시간복잡도 줄이기 ( 엠비티아이문제처럼 )

---

 

---

---

---

🧚🏻‍♀️문법?등 이외 tip!🧚🏻‍♀️

-  문자열 줄넘김문자 정리 rsplit() 활용

a, b = map(str,stdin.readline().rsplit())

---

-  상하좌우 다 탐색할 때 활용하면 굿

dx = [1,-1,0,0]

dy = [0,0,1,-1]

범위 안빠져나가게 조건 잊지말

---

-  딕셔너리 잘 활용해봐

---

- (A +B ) mod C == ((A mod C) + (B mod C)) mod C

- (A * B ) mod C == ((A mod C) * (B mod C)) mod C

---

-  시간복잡도 줄이기(DP, 브루트포스)

N을 구하기 위해 이전 값을 다 구하는 방식을 사용했다면,

바로 N을 구할 수 있진 않았는지 확인

---

 

글 읽기 - 왜 같은 수가 들어가나요???

첫번째 row에만 넣어도 다 들어감

append하면 값을 깊은복사해서 넣는 게 아니라 주소만 넣나 봄..!

주의주의

---

값 변경 할 일 없을 때는 튜플()

빠름

---

최대로 줄여보기!

(전체 값이 일정해서 하나의 값은 나머지로 도출할 수 있을 때 그 하나의 값에 대한 자료구조 없애기 등)(2251물통)

---