자바 (73) 썸네일형 리스트형 [백준] 11729 하노이 탑 이동 순서 (JAVA) 풀이 이전에 학교를 다니면서 풀어보았던 문제이기에 덤벼 들었다. 위의 문제는 일반적인 점화식을 찾는것이 중요하면 규칙을 찾는것 또한 중요하다. 재귀함수의 규칙이라고 해서 어려운것이 아니다 그냥 가장 작은 문제로 줄여가면서 규칙을 찾아야 한다. 예전에 보았던 문제라도 다시 보고 또 봐야겠다. import java.io.*; import java.util.StringTokenizer; public class Main { static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { BufferedReader br = .. [백준] 11053 가장 긴 증가하는 부분수열 (JAVA) 풀이 위의 문제는 대표적인 LIS문제로 dp를 이용해 푸는 문제이다. 만약 LIS알고리즘을 돌렸을때 특정 인덱스에서 현재의 값(seq)이 이전 인덱스의 값(seq)보다 크다면 이전 인덱스에서 만족하는 부분수열은 자연스럽게 만족하므로 현재위치의 dp는 특정인덱스의 dp에 +1을 하면 된다. (이전 인덱스의 수 또한 포함하므로.) 유사한 문제로 포도주문제나 계단오르기 가 있다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int N; static Integer[] seq; stat.. [백준 ]11401 이항계수 3 (JAVA) 일반적인 이항계수 공식으로는 시간초과및 오버플로우가 나와버린다. 그도 그럴것이 문제에서는 최악의 경우 4000000!을 계산하고 그래야하는데 이것은 long타입의 저장범위를 아득히 넘어버린다. 그로 인해 우리는 다른 방법을 생각해 보아야 하는데 여기서 나오는것이 페르마의 소정리이다. 우리는 알고리즘 문제를 푸는것이지 수학문제를 푸는것이 아니기 때문에 간략하게 정리만 하고 넘어갈것이다.모듈러연산(페르마의 소정리)의 공식에는 덧셈,뺄셈,곱셈이 있으면 나눗셈은 통용되지 않는다. 우선 페르마의 정의는 이렇다. 여기서 조금만 더 나아간다면 이렇게 유도가 가능할 것이다. 그렇다면 우리가 구하고 싶은 나눗셈 꼴은 역원으로 구할수있으면 이를 정리하면 위와 같이 나오며 최종적으로 우리가 도출하고자 하는 계산식은 아래와 .. 이전 1 ··· 5 6 7 8 다음
