코테 스터디 38일차 TIL + 오늘의 학습 키워드 위상정렬

- 오늘의 학습 키워드 위상 정렬(백준1516)

 

- 공부한 내용 본인의 언어로 정리하기

위상정렬 사이클이 없는 방향그래프에서 노드 순서를 찾는 알고리즘

진입 차수: 자기 자신을 가리키는 에지의 개수

인접리스트: 각 건물이 완성되면 건설 가능한 다음 건물들

진입차수 배열: 각 건물을 짓기위해 필요한 선행 건물 개수

정답배열: 각 건물의 최소 완성시간

 

수도 코드

1. 입력받기
 -N 개 건물의 건설 시간
 - 각 건물의 선행 관계
 2. 자료 구조 초기화
   - 인접리스트 adj[N+1]
    -진입 차수 배열 indegree[N+1] ={0}
    -정답 배열 result[N+1] ={0}
    -건물 시간 배열 time[N+1]
    
 3. 그래프 구성
   for 각 선행 관계(a,b)
     adj[a].push(b) //a완성후 b 건설 가능
     indegree[b]++ //b의 진입차수 증가
     
 4. 위상 정렬 + dp
 
 queue에 진입 차수가 0인 건물들 추가
 result [i] = time[i] for 진입차수가 0인 건물들
 
 while queue가 비어있지 않음
   current = queue.pop
   for next in adj[current]:
     result[next] = max(result[next], result[current] + time[next])
     indegree[next] --
     if indegree[next] ==0;
       queue.push(next)
       
5. 출력
  for i=1 to N:
     print result[i]

 

- 오늘의 회고
  - 어떤 문제가 있었고, 나는 어떤 시도를 했는지

 

진입차수를 1씩 빼기 - "선행 조건 하나가 완료되었다." 

진입 차수 0이 되면 - 모든 조건 만족한거고 작업 시작이 가능하다.

큐: 지금 당장 실행 가능한 작업의 대기열

 

 

- 오늘의 학습 키워드 위상 정렬

 

 

- 공부한 내용 본인의 언어로 정리하기

 

위상정렬 사이클이 없는 방향그래프에서 노드 순서를 찾는 알고리즘

 

진입 차수: 자기 자신을 가리키는 에지의 개수

- 오늘의 회고

  - 어떤 문제가 있었고, 나는 어떤 시도를 했는지

 

진입 차수가 0인 노드를 선택하고 선택된 노드를 정렬 배열에 저장하는거 까지는 이해했음

 

인접 리스트에서 선택된 노드가 가리키는 노드들의 진입차수를 1씩 빼라는게 무슨 말인지 이해가 안감
  - 어떻게 해결했는지

Q1: 진입차수 배열 [0,1,1,2,1]은 어디서 나오는가?

A: 이는 입력에서 각 건물의 선행관계를 분석해서 직접 계산해야 하는 값입니다. 문제에서 직접 주어지지 않고, 선행관계 입력을 바탕으로 우리가 구해야 합니다.

Q2: 정답 배열을 모두 0으로 초기화한다는 것은?

A: 이는 알고리즘 구현상의 초기화 과정입니다. 각 건물의 최소 완성시간을 저장할 배열을 0으로 시작해서, 위상정렬 과정에서 점진적으로 업데이트합니다.

Q3: 위상정렬 실행하면서 최대 시간을 업데이트한다는 것은?

A: 이는 알고리즘의 핵심 로직입니다. 문제 설명에서 "선행 건물이 완성되어야 다음 건물을 지을 수 있다"는 조건이 이를 의미합니다.

Q4: 정답 배열에 자기 건물 시간을 더한다는 것은?

A: 각 건물은 선행 건물들의 완성시간 + 자기 자신의 건설시간이 총 완성시간이 되므로, 이를 계산하는 과정입니다.

이 문제의 핵심은 의존관계가 있는 작업 스케줄링을 위상정렬로 해결하는 것

  - 무엇을 새롭게 알았는지
  - 내일 학습할 것은 무엇인지