알고리즘261 [BOJ]1719번: 택배 문제: https://www.acmicpc.net/problem/1719 다익스트라로 해결한 문제입니다. 임의의 A->B 두 순서쌍 경로 사이에 가장 먼저 방문하게 되는 노드를 구해야하는 문제입니다. 다익스트라를 사용하면 임의의 노드 A에 대해 나머지 노드에 대한 최단 경로 + 방문 정보를 저장할 수 있습니다. 그래서 N 개의 노드에 대해 N번 다익스트라를 돌린 후 1회 다익스트라 수행 때 마다 i번째 노드에서 나머지 노드를 방문할 때 최초로 방문해야 하는 노드 정보를 저장합니다. N번을 모두 돌리게 되면 2차원 배열 정답을 완성할 수 있습니다. N제한이 작으므로 log(V*Elog(V)로도 해결할 수 있습니다. 코드: https://github.com/cotchan/algorithm/blob/main/.. 2022. 3. 23. [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. [PRGRMS]42839번: 소수 찾기 문제: https://programmers.co.kr/learn/courses/30/lessons/42839 완전 탐색문제입니다. 아래와 같은 순서로 해결하였습니다. 1. 에라토스테네스 체로 소수 미리 구해놓기 2. 2^N개만큼 만들 수 있는 숫자 전부 생성 3. 만든 숫자에 대해 순열 생성 4. 생성한 순열에 대해 소수 판별 코드: https://github.com/cotchan/algorithm/blob/main/PRGRMS/%EC%86%8C%EC%88%98%20%EC%B0%BE%EA%B8%B0.java 2022. 3. 23. [PRGRMS]92343번: 양과 늑대 문제: https://programmers.co.kr/learn/courses/30/lessons/92343 바킹독님 풀이를 참고하여 해결하였습니다. 풀이가 정말 자세히 나와있으니 참고하시면 좋을 것 같습니다. 비트마스킹 문제입니다. 가장 최초의 상태를 0000...000001 (0번째 노드만 방문)로 두고 현재 켜져있는 비트(사용하겠다는 의미)에서 이동가능한 다음 상태(자식 노드 존재)로 DFS를 탐색해서 2^17개의 상태를 전부 탐색해보는 방법으로 해결할 수 있습니다. 코드: https://github.com/cotchan/algorithm/blob/main/PRGRMS/%EC%96%91%EA%B3%BC%20%EB%8A%91%EB%8C%80.java 2022. 3. 23. 이전 1 ··· 4 5 6 7 8 9 10 ··· 66 다음
