본문 바로가기
반응형

알고리즘113

백준 15663번 : N과 M (9) java 이 문제는 dfs를 이용한 백트래킹 문제입니다. 이 문제를 풀 때 유의해야 하는 것은 중복되는 입력이 있을 수 있고 중복되는 수열을 여러 번 출력하면 안 된다는 것입니다. 코드를 보면서 설명 드리겠습니다. import java.io.*; import java.util.*; public class Main { static int[] numArr; static int[] out; static boolean[] visited; static int M; static int N; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in));.. 2022. 6. 3.
백준 13549번 : 숨바꼭질 3 java 이 문에는 *2 +1 -1로 이동하면서 bfs에 노드들을 삽입하면서 문제를 해결하면 됩니다. 이때 유의하셔야 하는 점은 *로 가는 연산을 먼저 해야 연산 횟수를 줄일 수 있기 때문에 이 연산을 먼저 해야 한다는 것입니다. 또한 같은 자리에 나중에 도착하게 되더라도 *2할 때 걸리는 시간이 0이기 때문에 더 적은 시간으로 올 수도 있습니다. 따라서 min 변수를 Math.min으로 초기화하면서 저장해야 합니다. 이를 그림으로 설명드리겠습니다. 위의 그림과 같이 1 2 3 4이라는 수가 있습니다. 이를 +1연산으로만 채워보겠습니다. 그럼 각 자리까지 가는 시간은 위의 그림과 같습니다. 이제 *2연산을 더해보도록 하겠습니다. 1에서 시간한다고 할 때 2까지는 순간이동이니 시간이 들지 않고 4도 마찬가지입니다... 2022. 6. 3.
백준 11404번 : 플로이드 java 이 문제는 플로이드-워셜 알고리즘을 푸는 문제입니다. 문제를 풀 때 주의해야하는 점은 시작 도시와 도착 도시를 연결하는 노선이 하나가 아닐 수 있다는 것입니다. 노선을 입력받아서 그 비용이 더 적은지를 비교한 후에 넣어야합니다. 플로이드 워셜 알고리즘은 각 정점으로부터 다른 정점까지 갈 때 거쳐가는 정점을 추가하면서 진행하는 알고리즘입니다. 코드를 보며 추가로 설명드리겠습니다. import java.io.*; import java.util.*; public class Main{ public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.i.. 2022. 6. 2.
백준 9251번 : LCS java 이 문제는 LCS(Longest Common Subsequence) 알고리즘입니다. 이 알고리즘을 위 문제의 예제 입력을 통해 설명드리겠습니다. 주어진 입력들을 받아서 다음과 같이 표로 나타냅니다. 각 셀은 이 구간까지 탐색했을 때 겹치는 subsequence가 얼마나 있느냐입니다. 예를 들어 (2, 3)에 들어가 있는 수는 CA와 ACA가 얼마나 겹치는가입니다. 이 규칙대로 위의 표를 채워보겠습니다. C 하나와 비교했을 때 2번 column의 C의 subsequence가 되니 그 이후는 전후 1입니다. CA와 비교할 때 A만 있을 때는 subsequence가 A이지만 ACA와 CA를 비교하면 CA가 겹치니 2가 됩니다. 마찬가지로 CAP가 겹치니 3까지 나옵니다. CAPC는 위의 문자열과 겹치지 않으므.. 2022. 6. 2.
백준 16953번 : A → B java 이 문제는 bfs를 이용하여 A가 조건에 맞게 바뀔 때 B로 가장 적은 연산으로 바뀌는 연산의 수를 구하는 문제입니다. 바로 코드를 보여드리겠습니다. import java.util.*; import java.io.*; public class Main{ static int B; static boolean get; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int A = Integer.parseInt(st.nextT.. 2022. 6. 1.
백준 12865번 : 평범한 배낭 java 이 문제는 knapsack problem이라는 최적화 조합을 찾는 다이나믹 프로그래밍 문제입니다. 이 문제에서는 들 수 있는 무게가 정해져 있을 때 가장 가치합이 큰 값을 찾아내는 문제입니다. 저는 이 문제를 풀 때 특정한 무게에 따라서 각각의 물건들을 들 수 있는지를 따져가며 풀었습니다. 예제 1번을 통해서 그림과 같이 제가 이 문제를 푼 방식에 대해서 설명드리겠습니다. 예제 1번에서는 무게를 7kg까지 들 수 있고 물건이 4개가 주어진다고 하였기 때문에 다음과 같이 표를 그렸습니다. 무게가 0일 때는 아무것도 들 수 없고 물품이 0일 때는 아무 물건도 챙길 수 없다는 의미입니다. 따라서 무게가 0일 때와 물품이 0일 때의 셀에는 가치합이 0이 됩니다. 이제 각각의 무게에서 그 번호의 물품을 들 수 있.. 2022. 6. 1.
백준 15654번 : N과 M(5) java 이 문제는 재귀를 이용하여 원하는 조건을 출력하는 백트래킹 문제입니다. 이 문제를 풀 때 Arrays.sort를 이용하여 입력받은 배열들을 오름차순으로 정렬한 후에 푸시면 됩니다. 바로 코드를 보여드리겠습니다. import java.io.*; import java.util.*; public class Main{ static int[] intArr; static int[] dfsArr; static boolean[] visited; static int N; static int M; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System... 2022. 5. 31.
백준 1753번 : 최단경로 java 이 문제는 다익스트라 알고리즘을 푸는 문제입니다. 이 문제를 풀 때 유의하셔야 하는 점은 메모리 제한이 256MB라는 점입니다. 저는 이 문제를 풀 때 처음에는 들어온 자료들을 2차원 배열에 입력하였습니다. 그러나 이 방식을 이용하면 정점의 개수가 최대인 20,000개일 때 20,000 * 20,000 * 4byte = 1,600,000,000byte 즉 이 2차원 배열을 int형으로 선언하는 데만도 1.6GB라는 어마어마한 메모리를 사용한다는 것을 알게 되었습니다. 따라서 이 문제를 다른 방식으로 풀 수 있나를 찾아보니 우선순위 큐를 이용하여 문제를 푸는 방법이 있어서 이 방법을 이용하여 다익스트라 알고리즘을 구현하였습니다. 문제를 푼 방법은 코드를 보면서 추가로 설명드리겠습니다. import java.. 2022. 5. 31.
반응형

티스토리툴바