알고 목록1
- BruteForce (5문)
- Greedy (3문)
- Heap (8문)
- Topology (3문)
- 17.5H
알고 목록2
- BFS (8문)
- DFS (14문)
- DFS-DP (5문)
- Tree-DP (2문)
- BackTrack(7문)
- 정렬
- Hash
- 분할 정복
- 이분 탐색
알고 목록3
- 문자열 알고리즘
- 수학
- 자료구조
- 그래프, 트리
시간
1.5H: Test Case Check
1H: DFS with DP
1H: DFS with DP (py3, python3 메모리, recursion 이슈)
1H: DFS with DP (back-tracking checker )
2H : DFS with DP - Tree DP
0.5H : DFS with DP - Tree DP (우수마을)
1H : DFS with DP - Tree DP (트리의 독립집합-경로 복원까지- failed)
part1-tot : 8H
1.5H test case check
6.5H 6문 DFS-DP, tree-DP
1.0H : BackTracking (연산자 끼워넣기, 재귀 탈출조건 선행)
0.5H : BaackTracking (인원을 두팀으로 나눌때 가장 편차 작게, pos 인자로 안념겨 주면 시간초과 )
1.5H : 기록
0.5H : BackTracking (조합! 내장 모듈)
2.5H : BackTracking(1987,알파벳, 시간!,88% failed, SET!! 자료형 BFS)
1.0H : BackTracking (2580 수도쿠 ! BackTracking! )
1.0H : BackTracking (9663 N-Queen, 대각선, DFS(인자를 증가시키며), 대각선 선형체크!, xy중 하나만 걸려도 둘다 걸림 )
1.5H : BackTrack + BitMask + DFS-DP (외판원, Bitmask, 미완 )
part2-tot : 9.5H
8H : 7문 BackTracking
1.5H : 기록, and 공부
Tot : 17.5H
문항 : 13 + 1
1520 DFS + DP
- 도착 return 1
- 첫방문 아니면 return 기록값
- 첫방문이면 : dp 기록 = 0 초기화 해주고
- 4방향 DFS 호출
- dp += DFS 결과값 저장
- for 4방향 탐색 완료 후 return 기록값
1937 욕심쟁이 판다 G3 DFS + DP
재귀 DP 초기화 방식 차이
-
방문한적 있으면 return dp 값
-
첫방문 : dp 초기값 = 0
- 4방향 호출- 그 중 max 값만 선택
- for 끝난 후 max값+1 (현재 칸수=1)로 dp 저장
- 최종 dp 값 return
첫 방문 or not 최종 적으로 return dp 해당지점 으로 동일
굳이 return을 나눌 필요 없다.
key 연산 or 재귀가 필요하면 재귀호출하고,
해당 지점 모든 연산 or 재귀 호출이 완료되면 값 update하고 dp저장후 return 형태
Python3 재귀 늘리기 sys
from sys import setrecursionlimit
setrecursionlimit(10**9)- py3 적용이 안된다.
1103 게임 G2 DFS + DP + BackTrack for vis
Python
quit() 답출력후 프로그램 종료
2533 사회망 서비스 G3
- tree dp 특징 : 리프까지 보낸다
- dfs 양방향 간선정보를 vis로 체크(복구x) 하면 트리 탐색이 가능
- dfs 쭈우욱 보낸다 leaf 까지 먼저
- leaf로 부터 역으로 올라갈때 자식 탐색 위에 dfs내 dp초기화값으로 update !
1943 우수마을 G2
- vis, DFS로 트리 순환
- 자식 leaf 까지 먼저 보낸다 ! DFS first in loop
- DFS내 지역 local 환경에서 vis 처리, dp값 초기화 (2케이스)
- loop DFS이후 자식값 참조후 update
- no return
1987 알파벳 G3 fail 시간초과 (88%)
- 4방향 경로 탐색의 조건이 2개
- 방문한곳 재방문 x + 중복된 알파벳을 가지지 않도록 방문 (여태 지나온 경로를 모두 알고 있어야 가능)
- 경로 마다 최대 case가 모두 다르기 때문에, dp로 메모할 수 없다
- 경로를 backTracking 하는 DFS => 4경로 모두 탐색 후에 표시 flag를 통해 탈출 조건으로 재귀의 반복성을 조금 줄일 수 있따.
1987 알파벳 G3 BFS set으로 통과
- vis, alph모두 조건을 걸면 back tracking 안됨
- 왔던길을 다시 갈 수 있게 해주려면, 알파벳 조건만으로만 방문확인을 걸어주면 된다.
- 그리고 set으로 q를 구현하고 pop add하면 되는데
- set으로 [누적거리, 좌표, 현재경로]를 저장하고, 동일한게 다시 Q로 담겨도, 동일한 경로로 중복 검색을 하지 않는다
- vis 처리하지 않아 재탐색 재방문 overhead 걱정 안해도 되며,
- 좌표만 인식해서 재방문처리하지 않으면, 동일 좌표를 여러번 방문할 수있다. 정확히 backTracking 처럼 동작!
( DFS-DP-Bitmask로 푸는게 효율적일수있다 (--외판원문제) )
BackTracking 을 BFS Q로 = SET!!
2580 스도쿠 G4
- BackTrack 처리, vis처리 : board의 값
- vis-valid checker : 가로,세로, 3x3
9663 N-Queen G3
- BackTrack 처리, visList 3개로 처리 (메모리로 효율!)
- 대각선, 라인(x,y= 가로세로 하나만 파악해도됨 ), 대각선 선형 리스트화
- BackTrack 인자 , increasing way
10971 외판원, BackTrack, DFS-DP, Bitmask
