프로그래민👨‍💻

위상정렬 혹은 DFS를 사용할 수 있는 문제였다. 이 문제는 트리 문제로써 각 위치마다 양 또는 늑대가 존재하고, 루트까지의 양의 총합을 구하는 문제였다. 트리를 형성하고, 전체를 순회하는 구조이기에 맨처음 DFS로 접근해보았다. 1번(루트)에서 DFS를 한번도는 방식을 구상하였는데, 양의 수를 구하기 위해 DFS를 돌때 리턴값(양의 수)을 가지게 되고 최종적으로 자식노드 부터 리턴값을 보내어 1번(루트)에서 받아보는 방식을 생각해보았다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 ..

위상정렬을 이용한 문제였다. 이 문제는 그림에 주어졌듯이 건물사이의 우선순위가 존재하고 사이클이 생기지 않기때문에 위상정렬을 사용하여 접근하였다. 다만 주의할점은 건설함에 있어 이전것이 다 지어져야하는 시간을 가져가야하기 때문에 시간을 갱신함에 있어 max 값을 처리해주는 것을 생각해야한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 ..

위상정렬을 이용한 그래프 문제였다. 이 문제는 부품사이의 순위가 존재하고 서로 이어보면 DAG를 형성할 수 있기에 위상정렬을 사용해보았다. 큰부품 -> 작음부품이렇게 바라보도록 그래프를 그리고, 갯수만큼 곱해주면서 위상정렬을 돌면 최소부품이 몇개 필요한지 찾을 수 있는 간단한 문제였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 ..

위상정렬을 이용하여 풀었던 그래프문제이다. 이 문제를 맨처음 접했을 때 각 노드끼리의 순위가 존재하고 싸이클이 없기에 위상정렬을 사용해보았다. 맨처음 문제를 접근을 다음과 같이해보았다. 만일 1등, 2등, 3등, 4등이 존재한다면 4등->3등, 3등->2등, 2등->1등 이런식으로 그래프를 그려보았다. 하지만 이 문제는 순위가 뒤바뀌는 경우가 있는데 맨처음 내가 적용한 방식은 순위가 뒤바뀌는 것을 처리해주지 못하기에 그래프를 새롭게 그려보았다. 즉, 4등->3등, 4등->2등, 4등->1등, 3등->2등, 3등->2등, 2등->1등과 같이 순위가 낮은것이 자기보다 높은 순위를 모두 볼수 있도록 그래프를 그리는 방식을 수정하였다. 이런 방식을 통해 순위가 바뀌는 경우도 처리해주었고, 그래프를 새로그린다음에..

위상정렬을 이용하여 풀은 문제였다. 문제를 맨처음 파악했을때, 일의 우선순위가 있고, 일끼리 싸이클을 만들지 않는 DAG임을 보장받을 수 있는 조건이라 위상정렬을 사용하여 문제를 풀었다. 이 문제에선 우선순위가 높은것 -> 우선순위가 낮은것 으로 간선을 연결해 주었고, indegree배열과 queue를 이용하여 위상정렬을 구현하였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 ..

이 문제는 위상정렬(Topoologicl Sort)를 이용하는 문제이다. 위상정렬을 이용하기 위해선 DAG(Directed Acyclic Graph, 유향 싸이클없는 그래프)를 만족해야지 사용할 수 있다. 위상정렬이란 DAG의 정점들을 쭉 나열하였을 때 왼쪽에서 오른쪽(한바향)으로만 모든 간선이 이동하는 모양을 가지도록 정렬되게 하는 알고리즘이다. 즉 다음과 같은 모양으로 모든 정점이 정렬되는 것이다. 이러한 위상정렬을 하기위해선 우선적으로 싸이클이 없는 DAG임을 확인하고, 그다음 indegree배열을 사용하여 자신으로 들어오게 되는 간선의 수를 저장한다. 그 후 queue를 이용하여 indegree[index]=0이 되면 queue에 offer해주고 인접리스트를 돌면서 indegree들을 하나씩 줄여..