알고 목록1

1. BruteForce (5문)
2. Greedy (3문)
3. Heap (8문)
4. Topology (3문)

• 17.5H

알고 목록2

1. BFS (8문)/DFS(1문)
2. Back Tracking
3. Hash
4. Sort,
5. String-sort

시간

2H : 알고리즘 (heap, 이중 우선순위q)
2.5H : 알고리즘 (Topology)
1.5H : 알고리즘 (Topology)
0.5H : 기록 정리
1H : BFS S1
1H : BFS G4
8.5H

1.5H : BFS G3 아기상어
0.5H : BFS S2 촌수계산
0.5H : BFS S1 1389 케빈베이커의 단계
1.5H : BFS G4 3055 탈출 FS2번 시간지도
0.5H : BFS G4 3055 water spread 적용
1.0H : BFS S1 1325 효율적인 해킹 (시간초과와 에지케이스 애먹음)
1.5H : 기록
7H

1:35m

위상정렬1

노트

1. ans, dp리스트 (누적 시간 update)
2. indg 리스트 필요 (우선 순위 확인)
3. time 리스트 필요 (독립 시간 확인)
4. 최소 시간 = 최소 heap 자료형 필요

case

1. 어떤일을 수행하는데 우선 작업 존재
2. 우선 작업에 시간 task 필요
3. 시간 task가 병렬적, 직렬적 2가지 존재
   - 병렬적 :
   a task는 b,c task 먼저 수행되야 진행 가능하다 하면 a task 수행 시간은 b,c 중 가장 늦게 수행된 시간을 합친 누적 시간
   - 직렬적 :
   a task 선행 작업인 b,c 중 b는 또다시 d라는 작업이 선행 되어야한다 가정하면, b 테크스 완료 시간은 b + d를 합친 시간으로 직렬화 되있다할 수 있음
   • a task 수행 시간은 결국 max(b+d, c) 시간임
4. task 마다 독립적인 수행 시간을 알고 있는 메모리 와 직렬적으로 누적 시간을 계산하고 있는 시간을 알고 있는 메모리 두개가 존재해야함
5. 두 메모리 중 큰 값을 선택해야 최종 a 수행 시간이 답이 된다.

위상정렬2

노트

1. grapg 연결노드 관계
2. board(dp)리스트 2차원 (해당노드끼리의 독립적인 갯수)
3. indg 리스트 필요 (우선 순위 확인)
4. ans 리스트 필요 (누적 갯수 기록)
5. 최소 시간 = 최소 heap 자료형 필요

case

1. graph[row][col] 역전
   • row : node
   • col : 선행 되어야할 node list
2. indg[row] : 어떤 노드를 위해 먼저 선행 되어야할 횟수 (완제품=0)
3. board[row][col] : row 노드를 만들기 위한 col 노드 갯수
4. pq[] : indg[] = 0 인 노드 push (완제품)

key 는 graph, board를 기존의 위상정렬 개념에서 반대로 구현
indg[0]으로 선행 관계를 확인하는 것은 동일
이 경우 선행 작업이 반드시 필요한 node 가 indg값 0 을 가진다.
즉 완제품, 선행해서 작업해줄 필요가 없는 독립적인 node를 반대로 먼저 탐색하게 함.

중요한 것은 indg 0으로 출발해서 참조할 연결 graph에 선행해야할 노드가 있으면 된다. 이관계만 잘파악하면 되는 것 같다.

BFS 2486 안전영역

1. q 엔트리 포인트에 대한 고민
2. 100개 정도는 고민 없이 모두 탐색하자
3. 엣지 케이스일때 ans 만 잡아주는 형태로 답안 구출 - 조금더 정교하게 다듬을 필요 잇다

BFS 2206 벽 부수고 이동하기 G4

1. 엔트리 포함 해서 모두 체크 하면 시간 초과

   • 벽을 하나씩 부수는 케이스 마다 BFS = 시간초과
   • 한번에 해결 해줘야 하며
   • VIS에 벽을 부수는 케이스와 그렇지 않는 케이스를 나누어서 탐색하게 설정
   • q에 이미 벽을 한번 부수었으면 표시를 해준다

2. BFS 벽을 부수지 않는 케이스 탐색:

   • 방문 가능 영역:
     vis 가능, 벽이 없는 케이스
     그리고, vis 가능, 벽이 있는 케이스
   • 벽을 한번 뚫어다는 표시를 해주고 Q push
   • 방문 여부는 벽을 부수는 케이스에 방문 표시

3. BFS 벽을 부수는 케이스 탐색 :

   • 방문 가능 영역:
     vis 가능, 벽이 없는 케이스만 가능
     노말하게 vis 체크 Q push

4. 이렇게 특이 조건을 부치는 케이스는 q에 담아 가는 케이스로 분기 할 수도 있지만, Q stack size over flow 가 날 수도 있다(고 하며, 경험이 ㅠ 주르륵)

5. 메모리를 전역으로 빼서 효율을 올리는 전형적인 케이스!

   16236 아기상어 G3

   BFS 구현 + 시물레이션 !
   최단거리용 deque 사용
   [최소거리, 위=최소값2, 왼쪽=최소값3]
   세개 원소를 heap그냥 넣고 pop해서 사용 ! 깔끔!

   파이썬

   2중 for 문, 3중 for문 3차원 리스트 한라인 쓰기

   a = [ [[False, False] for _  in range(M)] for a in range(N) ]
   

   BFS 2644 촌수 계산 s2

   아주간단한 BFS
   양갈래로 부모자식 연결 노드
   양방향
   undirected 를 사용하는 것 잊지말고
   최소힙, 우선순위 Q로 최단거리를 보장함을 잊지말자! ㅍ

   BFS 1389 케빈베이컨의 6단계 s1

   아주 간단한 BFS
   역시 양갈래로 연결 board
   deque로 Q BFS
   최소힙 heaqp로 정답 구현 (최소거리이자, 최소 인덱스), 정답 후보군 전부 힙에 밀어넣고 마지막에 힙 root만 pop 끝

   BFS 3055 시간지도 water spread

   BFS 를 2번할 경우
   동시성으로 인해 맵을 spread마다 바뀌게 참조해야 하는데
   퍼지는 시간을 참조할 수 있는 지도를 만들어서
   board(장애물 참조), vis(방문 체크 참조), water spread(바이러스등 동시로 퍼지는 장애물 참조)로 세가지 참조 그래프를 만들어서 BFS를 동시에 진행하지않고 단계별로 !! 진행해 볼 수 있다 !!