728x90 분류 전체보기138 순환의 응용 : n queens problem - queen이 같은 행이나 열에 있으면 안됌 Backtracking - 진행하다가 막다른 길에 도달할 때 왔던 길을 되돌아가는 방법 *상태공간트리 - 상태공간트리란 찾는 해를 포함하는 트리 - 해가 존재한다면 그것은 반드시 이 트리의 어떤 한 노드에 해당함 -> 이 트리를 체계적으로 탐색하면 해를 구할 수 있음 * 상태공간 트리의 모든 노드를 탐색해야 하는 것은 아님 ex) 1번 말이 1,1에 있다면 2번말은 2,1과 2,2에는 갈 수가 없으므로 그 밑은 찾아볼 필요가 없다. => backtracking 기법 - 꽝인지 확인 -> 밑으로 내려갈 필요 x - 정답이라면 리턴 - 꽝이 아닌데 정답도 아니라면 -> queen함수를 다시 호출 - 성공인지 확인하는 방법 : 매개변수 값이 내가 놓고 싶은 말의 .. 2021. 5. 5. 순환의 응용 - 미로찾기 순환적 사고 - 현재 위치에서 출구까지 가는 경로가 있으려면 1. 현재 위치가 출구이거나 혹은 2. 이웃한 셀들 중 하나에서 현재 위치를 다시 오지 않고 출구까지 가는 경로가 있거나 미로찾기(Decision Problem) - 현재 위치가 출구이면 true 리턴 - 출구가 아니면 이웃한 셀들을 찾아보고 이훗한 셀들이 갈 수 있는 길이라면 셀들을 갖고 findPath 다시 호출 - 하지만 위의 코드로 구현하면 지금 방문한 셀이 왔던 곳인지 모르기 때문에 무한루프에 빠질 수 있음 따라서 방문했는지 안했는지를 알려줘야함 - 처음에 방문했다고 표시 - 이웃한 셀들 중 검사할 셀이 이미 방문했는지 확인한다. - 지금 셀이 벽인지와 방문했는지를 체크 - 지금 셀이 출구면 true리턴 - 출구가 아니면 방문한걸로 체.. 2021. 5. 5. [백준 1654] 랜선 자르기 [java] 이분 탐색 문제로 풀었다. 이 문제에서 두 가지 주의할 점이 있는데 하나는 범위가 커서 long형으로 선언해야하는 점과 문제에서 랜선의 길이는 자연수라는 점이다. 우선 랜선의 길이는 1부터 주어진 랜선들 중 가장 긴 랜선의 길이가 될 수 있다. 따라서 1과 가장 긴 랜선의 길이의 평균 값을 기준으로 위아래로 찾아보면 된다. 코드 package baekjoon; import java.util.Scanner; public class cut_lanwire { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int k = scan.nextInt(); long n = scan.nextLong(); long arr[] =.. 2021. 5. 4. [백준10816] 숫자 카드 2[java] 이 문제는 단순한 이분탐색으로는 풀 수 없는 문제였다. 여러가지로 시도해봤지만 결국 시간초과 오류.... 거기다가 println을 사용해도 시간초과가 떴다. 결국 모든 데이터를 배열에 넣고 찾고 싶은 값 num의 범위를 찾아냈다. lower와 upper메소드를 만들어 마지막에 upper의 값과 lower의 값을 빼는 것이다. 그리고 출력은 BufferedWriter를 이용하여 마무리 했다. 코드 package baekjoon; import java.io.*; import java.util.*; public class num_card2 { static int[] arr1; public static void main(String[] args) throws IOException { BufferedReader .. 2021. 5. 4. 순환의 개념과 기본예제 3 순환 알고리즘의 설계 - 적어도 하나의 base case, 즉 순환되지 않고 종료되는 case가 있어야 함 - 모든 case는 결국 base case로 수렴해야 함 * 가능하다면 암시적 매개변수를 명시적 매개변수로 바꾸어라. -> 순환 알고리즘을 만들때 중요 - data배열을 0~n-1까지 n개를 탐색함 -> n-1은 n을 통해 명시적으로 표현되어있다고 할 수 있지만, 0은 암시적으로 표현되어 있다고 할 수 있다. - 배열의 시작점과 끝을 begin과 end로 명시적으로 표현함 2021. 5. 1. 순환의 개념과 기본예제 2 순환 - 수학함수 뿐만 아니라 다른 문제들도 해결가능 *문자열의 길이 계산 - 첫글자를 제거한 나머지 문자열의 길이를 잰다 *문자열을 뒤집어 프린트 - 첫글자를 자르고 순환함수를 호출한다. - 돌아올때 출력하면 문자열의 끝부터 출력한다. *배열의 합 구하기 - 배열 data에서 하나씩 꺼내서 더해준다. *순환과 반복문 - 모든 순환함수는 반복문으로 변경 가능 - 반대도 가능함 -> 반복문은 순환으로 표현 가능 - 순환함수는 복잡한 알고리즘을 단순하고 알기쉽게 표현하는 것이 가능함 - 하지만 함수 호출에 따른 오버헤드가 있음 2021. 5. 1. 이전 1 ··· 11 12 13 14 15 16 17 ··· 23 다음 728x90
