Algorithm/Java28 [Java]백준 4963번 :: 섬의 개수 백준 온라인 저지 4963번 - 섬의 개수 Java 알고리즘 문제풀이 코딩테스트 DFS, BFS : https://developer-mac.tistory.com/64 풀이 그래프를 이용한 경로탐색 알고리즘에 대표적으로 2가지가 존재한다. DFS (깊이 우선 탐색) BFS (너비 우선 탐색) 코딩테스트에서 대표적으로 출제되는 문제라 알아두는 것이 좋은 알고리즘인데, 이 문제는 이 두가지 알고리즘을 연습하기에 좋은 문제이다. 실제 코딩테스트에서는 경로를 찾는 문제에서 많이 쓰인다. DFS 알고리즘에 경우 두 가지 방법으로 풀 수 있는데, 첫 번째로 스택을 이용하는 것 두 번째로 재귀함수를 이용하는 것인데, 재귀함수를 이용하는 것이 가장 보편적이고 짧은 코드를 작성할 수 있다. BFS 알고리즘은 Queue를 .. 2019. 3. 11. [Java]백준 1463번 :: 1로 만들기 백준 온라인 저지 1463번 - 1로 만들기 Java 알고리즘 문제풀이 풀이 다이나믹 프로그래밍(DP) 문제이다. 간략하게 DP를 소개하자면 큰 문제를 작은 단위로 쪼갠 작은 문제로 큰 문제의 답을 구하는 것을 뜻한다. 푸는 방식에는 2가지가 존재한다. 이 문제도 2가지 방법으로 풀어볼 것이다. 1. Top-Down 2. Bottom-Up 먼저, Top-down은 용어 그대로 위에서부터 아래로 이어지는 것이다. 이 방법에 특징은 재귀함수를 사용하는 것이다. 작은 부분의 답을 저장해 이미 계산을 진행한 작은문제는 저장된 값을 이용하는 방법이다. /* Top down */ import java.util.Scanner; public class Beak1463 { static int[] d; public sta.. 2019. 3. 10. [Java]백준 1260번 :: DFS와 BFS 백준 온라인 저지 1260번 - DFS와 BFS Java 알고리즘 문제풀이 풀이 그래프를 이용한 경로탐색 알고리즘에 대표적으로 2가지가 존재한다. DFS (깊이 우선 탐색) BFS (너비 우선 탐색) 코딩테스트에서 대표적으로 출제되는 문제라 알아두는 것이 좋은 알고리즘인데, 이 문제는 이 두가지 알고리즘을 연습하기에 좋은 문제이다. 실제 코딩테스트에서는 경로를 찾는 문제에서 많이 쓰인다. DFS 알고리즘에 경우 두 가지 방법으로 풀 수 있는데, 첫 번째로 스택을 이용하는 것 두 번째로 재귀함수를 이용하는 것인데, 재귀함수를 이용하는 것이 가장 보편적이고 짧은 코드를 작성할 수 있다. BFS 알고리즘은 Queue를 사용해서 문제를 해결하면 된다. import java.util.*; public class .. 2019. 3. 7. [Java]백준 10973번 :: 이전 순열 백준 온라인 저지 10973번 - 이전 순열 Java 알고리즘 문제풀이 풀이 완전탐색(BP)에 속하는 순열문제이다. 다음 순열 문제와 유사한 문제이다. 다음 순열 문제보기 다음 순열에서 부등호만 바꿔주면 되는 문제다. 1. A[i-1] > A[i]를 만족하는 가장 큰 i를 찾는다. 2. j >= i이면서 A[j] 1, i = 6 2. 다시 오른쪽부터 확인해서 4보다 첫 번째로 작은 수를 찾는다. -> 1 3. 4와 1의 자리를 바꾼다. -> 7 2 3 6 5 1 4 4. 바꾼 숫자의 오른쪽 .. 2019. 3. 1. [Java]백준 10972번 :: 다음 순열 백준 온라인 저지 10972번 - 다음 순열 Java 알고리즘 문제풀이 풀이 완전탐색(BP)에 속하는 순열문제이다. 푸는 방법은 아래와 같다. 1. A[i-1] = i 이면서 A[j] > A[i-1]를 만족하는 가장 큰 j를 찾는다. 3. A[i-1]과 A[j]를 swap한다. 4. A[i]부터 순열을 뒤집는다. ex) 7 2 3 6 5 4 1 1. 오른쪽부터 왼쪽이 작은 수를 찾는다. 3 4 3. 3과 4를 자리를 바꾼다 -> 7 2 4 6 5 3 1 4. 바꾼 숫자의 오른쪽 전부를 뒤집는다. -> 7 2 4 1 3 5 6 import java.ut.. 2019. 3. 1. [Java]백준 1978번 :: 소수 찾기 백준 온라인 저지 1978번 '소수 찾기' Java 알고리즘 문제풀이 풀이 소수찾기 문제이다. 이 문제는 입력한 숫자가 소수인지를 판단하는데 각각의 수가 소수인지 판단을 하고 소수이면 count값을 증가시키면 된다. 소수의 특징은 1과 자신만을 약수로 가진다는 점이다. 간단하게 풀 수 있는데 입력받은 숫자가 만약에 자신의 수 이외에 나머지 값을 0으로 가진다면 소수가 아니다. 이 점을 이용하면 된다. 이런 부류의 문제의 심화버전은 에라토스테네스의 체 알고리즘을 이용해야한다. import java.io.*; import java.util.*; public class Beak1978 { public static void main(String[] args) throws IOException { Buffered.. 2018. 12. 27. 이전 1 2 3 4 5 다음