개인사

리뷰 max이 하나가 정답을 좌지우지 했다 ㅠㅜhttps://www.acmicpc.net/problem/2056 전역 변수n : 작업의 개수 함수없음  문제풀이n값을 입력 받고 작업 시간 정보 times와 인접 리스트를 초기화할 정수 벡터 path를 n + 1크기로 초기화 한다.1부터 n개의 각각의 작업에 걸리는 시간을 times 벡터에 저장해 준다.이후 선행이 필요한 작업을 인접 리스트로 추가해 준다, 역방향으로 삽입해 주어야 한다.선행 작업의 개수를 저장할 벡터 cnt를 n + 1크기, 기본값은 0인 상태로 초기화 해준다.각 작업을 순회하며 작업의 인접리스트에 저장된 작업을의 cnt를 증가시켜준다.정수형 큐 q를 초기화 한 후에 cnt가 0인 작업을 큐에 넣어준다.정답을 저장할 정수형 벡터 ans를 ..

리뷰 각 순위별 간선을 생성하고, 쿼리로 입력되는 노드간 간선을 반전시킨 후 위상 정렬을 수행하는 문제https://www.acmicpc.net/problem/3665 전역 변수tc, n, m : 테스트 케이스의 개수 tc, 팀의 개수 n, 순위 변경 쿼리의 개수 mlst : 작년 순위 정보를 저장할 정수형 벡터cnt : 선순위의 개수를 저장할 정수형 벡터result : 금년 순위 정보를 저장할 정수형 벡터path : 인접 리스트를 저장할 정수형 2차원 벡터 함수1. initvoid init() 각 테스트 케이스마다 lst, cnt, result, path 벡터를 clear해주는 함수 2. input()void input() n값을 입력 받고 각 테스트 케이스 마다 lst, cnt, path의 크기를 n..

리뷰 가수의 출연 순서를 구하는 위상 정렬 문제, 보조PD 라는 것에 의미를 부여하는 함정에 빠지면 안된다.https://www.acmicpc.net/problem/2623 문제 풀이가수의 개수n, 보조 PD의 개수m, 인접리스트용 벡터 path를 전역변수로 설정해 준다.n과 m값을 입력 받고, m크기만큼의 루프를 돌려준다, 이후 가수의 개수 a와 가수 b를 입력 받아준다.가수의 개수를 전위 감소 연산을 통해 while루프를 돌려주고 그 이후의 가수 c를 입력 받아준다.b의 path에 c를 push_back을 해준 뒤 b를 c로 교체시켜 준다. 이후 계속 반복해 준다.위 작업을 통해 가수의 순서대로 우선 순위가 적용되어 가수간의 출연 순서가 만들어 진다.cnt벡터를 n + 1크기로, 값은 모두 0으로 초..

리뷰 위상 정렬에 우선 순위 큐를 사용하여 최대한 난이도가 낮은 순서로 출력하는 문제https://www.acmicpc.net/problem/1766 문제 풀이문제의 수 n과 선수 문제의 개수 m, 인접 리스트 벡터path를 전역변수로 설정해 준다.n과 m값을 입력 받고, m개의 선수 문제 정보를 인접 리스트 path에 추가해 준다.선수 문제 개수를 저장할 cnt 벡터를 n + 1크기로, 내부 값을 모두 0으로 초기화 해준다.n개의 문제의 인접 리스트를 순회하며 인접 리스트에 담긴 문제의 개수를 증가시켜 준다.오름차순 정렬 형태의 우선순위 큐 pq를 초기화 해준다.다시 n개의 문제를 순회하며 cnt의 개수가 0개라면 pq에 추가해 준다.pq에 요소가 없을 때까지 순회하며 pq의 top요소를 뽑아 cn으로..

리뷰 게임 상에서 각 건물이 지어질 수 있는 최소 시간을 구하는 문제 위상 정렬을 통해 쉽게 해결할 수 있다.https://www.acmicpc.net/problem/1516 문제 풀이건물의 개수 n과 각 건물의 건설 시간 t배열, 인접 리스트용 벡터 path를 전역 변수로 초기화 해준다.input 함수를 통해 n값을 입력 받고 1~n번째 건물의 건설 시간과 인접 리스트를 입력 받아준다.solution함수를 통해 각 건물의 건설 완료 시간을 구해줄 수 있다.각 건물의 건설 완료 시간 벡터 sum과 건물을 짓기위한 우선순위의 개수 벡터 cnt를 n + 1, 0값으로 초기화 한다.각 건물의 인접리스트를 순회하며 인접 리스트에 저장된 건물의 cnt를 1개씩 늘려준다.정수형 큐 q를 주비하고 cnt가 0인 건물..

리뷰 처참한 전투흔적.. 위상 정렬의 응용 문제였는데 꽤나 애를 먹었다.최소 거리를 구하는 부분은 쉽게 나왔으나 1분도 쉬지 않고 달려야 하는 도로의 수를 구하는게 어려웠다.처음엔 거리 배열을 사용하여 max로 갱신될 경우 이전 경로로 교체를 해주고, 값이 같을땐 현재 저장된 거리에 새로 들어온 경로를 더해주는 방식으로 생각했었다.하지만 이전까지 같은 경로로 오다 갈라진 후 다시 합쳐지는 케이스에서는 해당 방법을 사용할 수 없었다.이후 set를 사용해 왔던 경로를 모두 저장해 준 뒤 set의 크기를 출력해 주었으나 메모리 초과가 났다.결국 왔던 길을 역추적 해서 검증이 가능한 길의 개수만 구해지는 방식으로 풀이하였다.해당 방식이 맞는 접근 방법이나, 중복이 가능한 케이스들을 놓쳐서 방문 처리를 하고 나니..

리뷰 위상 정렬을 통해 가중치가 있는 간선을 갖고 특정 노드의 최소값을 구하는 문제https://www.acmicpc.net/problem/1005 문제 풀이테스트 케이스의 개수 tc, 노드의 개수 n, 간선의 개수 m, 목표 노드 dest를 전역변수로 초기화 해준다.인접 리스트를 담을 정수형 벡터 path, 각 노드의 소요시간 정보 times의 크기를 n의 최대값으로 설정해 준다.init 함수를 통해 times 배열 초기화, path 백터를 초기화 해준다.input 함수를 통해 n, m값과 각 노드의 소요시간, 간선정보, 목표 노드를 입력 받는다.solution 함수를 통해 dest 노드가 건설이 완료 되기까지의 최소 시간을 출력해 준다.cnt, sum 벡터를 n + 1 크기로, 초기값은 0으로 초기화..