최대힙

2023년 9월 1일 알고리즘 문제풀이 문제 1 백준 2252 문제 링크 1차 시도 위상정렬에 대한 개념을 다 까먹어서 어떻게 풀지 감이 안왔다.. 해서 위상정렬을 공부해보고 풀었다. 위상 정렬(topological sorting)은 유향 그래프의 꼭짓점들을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 쉽게 말하면 순서가 정해져있는 작업을 차례대로 수행할 때 순서를 결정하는 방법이다. 이번 문제도 어떤 학생들은 순서에 맞게 배열해야 하니 위상 정렬 문제로 풀 수있다. 위상 정렬의 과정은 다음과 같다. 방향이 있는 간선들의 정보가 주어지면 인접그래프를 만든다. 정점의 번호를 index로 하는 배열을 만든 후 해당 정점이 도착지가 되는 간선이 있을 떄마다 정점의 값을 1 올린다. 이 정점의 값이 진입차수를 의미한다. 해당 정점으로 진입하는 간선이 몇개인지를 나타내는 것이다. 위 과정이 완료되면 값이 0인 정점은 큐에 삽입한다. 큐에서 한 정점씩 꺼내어 해당 정점과 연결된 간선을 모두 제거한다. 이 과정에서 값이 0이 된 정점은 큐에 삽입하고 과정을 반복한다. 큐에서 꺼내지는 순서가 작업의 순서이다. 이 문제에 대입해보면, 문제의 입력값에서 순서가 있는 학생이 주어진다. 학생을 정점이라 생각하고 배열의 선후관계를 간선의 방향이라고 생각하면 된다. 코드는 다음과 같다. ...

2023년 8월 15일 알고리즘 문제풀이 문제 1 백준 1697 문제 링크 1차 시도 나의 생각 처음엔 재귀나 피보나치 등 여러 방법을 고민했다. 결국 다이나믹 프로그래밍으로 푸는게 적절하다고 생각했다. 맨처음 n에서 1초후 갈 수 있는 곳은 2n, n+1, n-1 이다. 이들을 큐에 저장하고 이들까지 도달하는데 걸린 시간도 같이 저장한다. 이 큐에서 하나씩 순회하며 2배한 좌표, +1, -1 한 좌표에 시간을 업데이트하고 큐에 다시 저장하는 것을 반복했다. 하지만 예시를 입력하면 올바른 정답이 나오지 않았다. 디버깅해봐야겠다. ...