메인17 다익스트라(Dijkstra) 알고리즘 with Java 다익스트라 알고리즘 다익스트라 알고리즘은 음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단거리를 구하는 알고리즘입니다. 단 한개의 음의 가중치라도 허용되지 않으며, 만약 음의 가중치가 있는 그래프라면 다익스트라 알고리즘 대신 벨맨 포드 알고리즘을 사용하는 방법이 있습니다. 구현방법 다익스트라 알고리즘을 구현하는 방법에는 반복 문을 사용하는 방법과 우선순위 큐를 사용하는 방법이 존재합니다. 현재 포스팅에서는 이해가 쉬운 반복문을 사용하는 방법을 배운 뒤 이를 응용하여 우선순위 큐로 구현하는 법으로 넘어가겠습니다 :) 구현 길이를 저장할 배열과, 해당 노드에 방문했는지 확인할 배열이 필요합니다. 이 예제에서는 dist, ch 라고 이름을 붙히겠습니다. dist와 ch 배열의 크기는 노드의 개수로.. 2022. 9. 14. [백준/BAEKJOON] 11723 : 집합 with Java 문제 비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오. add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다. remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다. check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20) toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20) all: S를 {1, 2, ..., 20} 으로 바꾼다. empty: S를 공집합으로 바꾼다. 입력 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 .. 2022. 9. 12. [백준/BAEKJOON] 1620 : 나는야 포켓몬 마스터 이다솜 with Java 문제 https://www.acmicpc.net/problem/1620 입력 첫째 줄에는 포켓몬의 개수 N이랑 맞춰야 하는 문제의 개수 M이 주어진다. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 포켓몬의 번호가 1번인 포켓몬부터 N번에 해당하는 포켓몬까지 한 줄에 하나씩 입력으로 들어온다. 포켓몬 이름의 최대 길이는 20, 최소 길이는 2야. 그 다음 줄부터 총 M개의 줄에 내가 맞춰야하는 문제가 입력으로 들어와. 문제가 알파벳으로만 들어오면 포켓몬 번호를 말해야 하고, 숫자로만 들어오면, 포켓몬 번호에 해당하는 문자를 출력해야한다. 출력 첫째 줄부터 차례대로 M개의 줄에 각각의 문제에 대한 답을 말한다. 숫자가 들어왔다면 숫자에 해당하는 포켓몬,.. 2022. 9. 12. [백준/BAEKJOON] 1676 : 팩토리얼 0의 개수 with Java 문제 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500) 출력 첫째 줄에 구한 0의 개수를 출력한다. 입력 예시 1 10 출력 예시 1 3 아이디어 팩토리얼은 1부터 N까지의 자연수 곱을 일컫습니다. 일례로 5! = 1 x 2 x 3 x 4 x 5, 7! = 1 x 2 x 3 x 4 x 5 x 6 x 7 등이 있습니다. 팩토리얼은 25만 넘어가도 그 수가 10의 25승이 넘게 됩니다. 하지만 문제에서는 0부터 500까지의 수가 입력될 수 있으며, 자바는 매우 큰 수를 효과적으로 처리하지 못하므로 우리는 다른 방식으로 팩토리얼에 접근할 필요가 있습니다. 뒤에서부터 0이 나오려면 어떻게 해야 할까요? 바로.. 2022. 9. 12. 이전 1 2 3 4 5 다음
