본문 바로가기

Algorithm/BOJ172

[BOJ]2458번: 키 순서 문제: https://www.acmicpc.net/problem/2458 모든 학생들 간의 관계 (모든 노드간의 순서쌍)을 구하는 문제이므로 플로이드로 해결할 수 있는 문제입니다. N 제한이 작아 N^3을 돌려도 해결할 수 있다는 점을 단서로 삼을 수 있습니다. 학생들간의 키 관계를 담은 3차원 배열 int[][][] dist를 선언하였고 정보를 담아줍니다. dist[0][a][b] = 1이 의미하는 바는 a가 b보다 작은 경우입니다. dist[1][a][b] = 1이 의미하는 바는 a가 b보다 큰 경우입니다. 그래서 플로이드쌍을 전부 갱신해준 뒤 dist[0][][], dist[1][][]를 순회해서 비교 횟수가 N-1인 학생인 자신의 키 순서를 알 수 있습니다. 코드: https://github.co.. 2022. 3. 23.
[BOJ]10282번: 해킹 문제: https://www.acmicpc.net/problem/10282 최단 경로문제입니다. 각 컴퓨터의 의존관계와 감염되는데 걸리는 시간을 저장한 뒤 다익스트라를 통해 순회한 후 다익스트라로 인해 dist[] 배열 값이 바뀌어 있는 노드의 갯수가 감염된 노드의 총 갯수이고 초기화값을 제외한 dist[] 배열 내 최댓값이 가장 늦게 감염되는 컴퓨터 시간입니다. 코드: https://github.com/cotchan/algorithm/blob/main/BOJ/BOJ10282.java 2022. 3. 22.
[BOJ]14567번: 선수과목 (Prerequisite) 문제: https://www.acmicpc.net/problem/14567 위상정렬 문제입니다. 과목들 간의 우선순위를 저장을 한 후, 한 과목 당 자신의 선수 과목이 몇 개나 있는지 parentCnt[] 배열에 저장합니다. 선수과목이 0개인 (parentCnt[k] == 0) 과목들부터 큐에서 꺼내오면서 해당 과목을 선수 과목으로 가지고 있는 후수 과목들의 parentCnt[k] 값을 1씩 빼줍니다. 특정 과목을 들을 수 있는 시점은 parentCnt[k] == 0 일 때 해당 과목을 수강할 수 있습니다. 현재 큐에 들어있는 사이즈만큼 루프를 돌면서 (한 학기에 해당) 위 과정을 반복하면 됩니다. 코드: https://github.com/cotchan/algorithm/blob/main/BOJ/BOJ1.. 2022. 3. 22.
[BOJ]2665번: 미로만들기 문제: https://www.acmicpc.net/problem/2665 parametric search + BFS 문제입니다. 몇 개의 검은 블럭을 바꿔야 이동 가능한지는 직접 시뮬레이션해보기전까지는 알 수 없습니다. 그러므로 최소 0개부터 최대 N^2 개의 블럭을 모두 바꾸는 경우까지 시도해봐야 합니다. N제한이 작으므로 O(N^4)으로 BFS를 돌려도 시간초과는 나지 않습니다. 그러나 0개에서부터 ~ N^2를 탐색하는 과정을 이분 탐색을 통해 O(log(N^2)^N2)으로 줄일 수 있습니다. Q. X개의 블럭을 바꿀 수 있을 때 board[N][N]에 도달가능한가? 를 결정하는 결정문제로 바꿀 수 있습니다. X가 주어진 조건을 만족한다면 상한을 줄여서 다시 탐색해보고, X가 조건을 만족하지 않으면 .. 2022. 3. 22.

티스토리툴바