자바알고리즘

오늘도 DFS+BackTracking문제중 하나를 풀어 보았다.! 바로 설명하겠다 문제 풀이 일반적인 스도쿠를 프로그래밍해서 푸는 문제이다! 스도쿠는 어려서 한번쯤은 해봤을 것이다. 그래서 문제 이해하기에는 어렵지 않을 것이다. 스도쿠 판의 크기는 9x9로 일정하고 가로, 세로 , 같은 9개의 네모 칸에서 같은 숫자가 존재하면 안된다는 조건이 있다. 풀이 순서는 다음과 같다. 1. 0인 값들을 Arraylist에 추가해 0인값들만 탐색하게 한다. 2. 0인 값을 탐색할때 가로,세로,같은 네모칸 조건에 맞게 탐색할 수 있는 함수를 만들어 줘야 할 것이다. 3. 0인 값들을 모두 조건에 맞게 탐색하면 바로 return 해 주면 될 것이다. (Arrayslist의 size만큼 DFS를 성공하면) import ..

오늘은 DFS와 비슷하면서도 조금은 다른 BackTracking에 대해서 알아보겠다. 백트래킹(Backtracking)은 문제의 해답을 찾는 도중에 가능성이 없다고 판단되는 경우에는 더 이상 해당 경로를 따라가지 않고, 되돌아가서 다른 경로를 탐색하는 알고리즘이다. 백트래킹은 트리 기반의 재귀적 탐색 방법 중 하나로, 재귀 함수의 호출과 되돌아감을 통해 구현된다. 예를 들어 순열을 구하는 문제를 생각해보자. [1, 2, 3]의 숫자로 만들 수 있는 모든 순열을 찾아야 한다고 가정한다. 이때 백트래킹은 가능한 모든 순열을 탐색하면서, 더 이상 순열을 완성할 수 없는 경우에는 되돌아가서 다른 선택지를 탐색한다. 반면 DFS는 가능한 모든 순열을 깊이 우선으로 탐색하면서 모든 경우를 다 시도하고 나서야 되돌아..

문제 풀이 이 문제는 격자형 그래프를 DFS 탐색을 하여 연결된 점들을 구하는 문제이다. 어떻게 보면 격자형 그래프의 UNION FIND 라고 할 수 있나 싶기도 하다. 풀이법은 방문 되지 않은 노드를 모두 방문하여 옆에 있는 노드로 이동 할 수 있으면 이동하여 체크를 하고 같은 집합에 포함시키는 것이다. 여기서는 집합의 갯수를 구하는 문제 이므로 집합의 갯수를 1더하는 것으로 하겠다. 집합의 갯수는 몇개가 나올지 모르므로 ArrrayList를 사용할 것이며 Map은 이중배열을 통해서 구현하고 move 즉 이동도 이중 배열을 통해 구현하겠다. * move에서 중요한점은 이동한 후 node가 bound를 넘지 않는지 check하는 것과 방문하였는지 안하였는지 0이 아닌지 체크 하는 것이다 * Map에서 방..

문제 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. 첫째 줄에 A와 B가 주어진다. (0 < A,B < 10^10000) 풀이 무턱대고 int, long으로 받아서 A+B를 하면 안된다 그 이유는 10^10000은 int와 long의 범위를 훨씬 넘기 때문이다. 그렇다면 일반적인 수의 '+' 연산을 사용할수 없다는 거고 우리가 직접 더하기 알고리즘을 구현해야 하는 것이다. i) A, B를 String으로 입력받는다 ii) A, B를 알고리즘에 넣고 String으로 반환한다. iii) String출력 Algorithm i) 더하기는 예전부터 배웠듯이 일의 자리 수부터 더해야 한다. ii) 두개를 더했는데 10을 넘어가면 앞에 1의 자리에 1을 올려준다. iii) 같은 자릿수만..

문제 N개의 바구니가 있고, 각각의 번호는 1~N 까지 순서대로 적혀있다. begin mid end를 선택한 후 begin mid end안의 바구니 순서를 mid, mid+1, ..., end-1, end, begin, begin+1, ..., mid-1로 바꾸게 된다. M번의 회전 후 가장 왼쪽의 바구니부터 번호를 출력한다. 풀이 i) N과 M을 입력받고 배스킷 배열을 생성 ii) 회전 알고리즘을 만든 후 M번 실행한다. iii) 왼쪽 바구니 부터 배스킷 번호를 출력한다. import java.io.*; import java.util.*; public class Main{ public static void main(String args[])throws IOException{ BufferedReader ..