🧚🏻♀️알고리즘 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을 구할 수 있진 않았는지 확인
글 읽기 - 왜 같은 수가 들어가나요???
댓글을 작성하려면 로그인해야 합니다.
www.acmicpc.net
append하면 값을 깊은복사해서 넣는 게 아니라 주소만 넣나 봄..!
주의주의
값 변경 할 일 없을 때는 튜플()
빠름
최대로 줄여보기!
(전체 값이 일정해서 하나의 값은 나머지로 도출할 수 있을 때 그 하나의 값에 대한 자료구조 없애기 등)(2251물통)