Algorithm7 [Java]백준 4963번 :: 섬의 개수 백준 온라인 저지 4963번 - 섬의 개수 Java 알고리즘 문제풀이 코딩테스트 DFS, BFS : https://developer-mac.tistory.com/64 풀이 그래프를 이용한 경로탐색 알고리즘에 대표적으로 2가지가 존재한다. DFS (깊이 우선 탐색) BFS (너비 우선 탐색) 코딩테스트에서 대표적으로 출제되는 문제라 알아두는 것이 좋은 알고리즘인데, 이 문제는 이 두가지 알고리즘을 연습하기에 좋은 문제이다. 실제 코딩테스트에서는 경로를 찾는 문제에서 많이 쓰인다. DFS 알고리즘에 경우 두 가지 방법으로 풀 수 있는데, 첫 번째로 스택을 이용하는 것 두 번째로 재귀함수를 이용하는 것인데, 재귀함수를 이용하는 것이 가장 보편적이고 짧은 코드를 작성할 수 있다. BFS 알고리즘은 Queue를 .. 2019. 3. 11. [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]백준 2775번 :: 부녀회장이 될테야 백준 온라인 저지 2775번 '부녀회장이 될테야' Java 알고리즘 문제풀이 풀이 문제를 보고 연습장에 써보면 피보나치 수열문제와 유사하다는 것을 눈치챌 수 있다. 바로 재귀함수를 이용하면 쉽게풀리는 문제다. 만약 2층 2호를 구한다면 2층 2호의 값은 2층 1호의 값과 1층 2호 값을 더한 것이라는 것을 알 수 있다. import java.util.Scanner; public class java_2775 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int num = sc.nextInt(); for (int i = 0; i < num; i++) { int k = sc.nextInt(); int n = sc... 2018. 12. 27. [Java]백준 1780번 :: 종이의 개수 백준 온라인 저지 1780번 '종이의 개수' Java 알고리즘 문제풀이 풀이 이 문제는 분할정복(Divide and Conquer)로 풀면된다. 분할정복은 정말 쉬운 개념이다. (유사한 분할정복 문제 풀기 -> 백준 1992번 쿼드트리 https://developer-mac.tistory.com/37) 단순하게 복잡한 문제를 해결할 수 있는 작은단위로 나누어서 처리한 후 이것을 합치면 된다. 이 문제에서 3등분을 한다고 생각하면 된다. 먼저 입력을 받고 divide 함수에서 재귀적으로 동작한 후 if 문을 두어 모든 원소가 0이거나 1일때 빠져나오게 하면 된다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputS.. 2018. 10. 28. [Java]백준 15552 :: 빠른 A+B 문제 테스트 케이스 갯수 n만큼 사용자에게 입력받은 두 정수 A, B의 합을 순서대로 출력한다. 입력 첫 줄에 테스트케이스의 개수 T가 주어진다. T는 최대 1,000,000이다. 다음 T줄에는 각각 두 정수 A와 B가 주어진다. A와 B는 1 이상, 1,000 이하이다. 문제풀이 * Java 언어로 구현했습니다. 이 문제는 Scanner로 풀었으면 정말 간단하게 풀었을 문제다. 그러나 테스트 케이스가 만약에 작다면 Scanner을 사용했을 때 시간상 문제가 없겠지만 1,000개 10,000개가 넘어간다면 Scanner을 10,000번 부르는 것이므로 성능상 문제가 생긴다. 이때 Buffer을 이용해서 문제를 푼다. Buffere에 n값을 입력받는데 trim()을 이용해서 Buffer에서 잘라낸다. (n.. 2018. 7. 5. 이전 1 2 다음
