분류 전체보기 (308) 썸네일형 리스트형 [백준] 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 = .. [백준] 1931 회의실 배정 (JAVA) 풀이 처음에는 bfs, dfs문제인줄 알고 덤볐으나 bfs,dfs로는 답이 도출되지 않아서 이리저리 고민하다가 시간별로 정렬하자는 생각이 들었다. 처음에는 사전식으로 정렬하듯이 시작시간먼저 정렬하고 시작시간이 같다면 끝나는 시간으로 정렬하였다. 하지만 이렇게 풀다보니 나중에 값을 도출하는데 시간도 오래 걸리고 복잡하였다. 무엇보다 BOJ에서 시간초과가 나와서 조금더 단순하게 생각기로 했다. 아래 코드는 시작하는 시간순으로 정렬하는것이 아닌 끝나는 시간을 기준으로 정렬하였다. 그리고 만약 끝나는 시간이 같다면 시작하는 시간순으로 정렬하였다. 코드의 중요 포인트는 "이전 회의 기준"으로 끝나는 시각과 다음에 올 적절한 회의를 찾는것이다. 회의시간은 이미 위에서 정렬했기에 차례대로 순회하면 되기때문에 코드는 .. [백준] 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.. [백준] 1012 유기농배추(JAVA) https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 문제 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어,.. [백준] 1260 DFS와BFS (JAVA) 이 문제는 DFS와 BFS를 구현만 하면 되는 간단한 문제이다. DFS는 재귀로 진행하였고 BFS는 큐로 풀었다 다음에는 DFS를 스택으로 풀어보아야겠다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Main { static int n; static int m; static int start; static boolean[] visited; static int[][] check; public static void main(String[] args) throws.. 페르마의 소정리 정수 a와 p가 있고 a가 p의 배수가 아니면서 p가 소수(Prime number)일 때 다음이 성립한다. 수식을 풀이하면 a^p를 p로 나눈 나머지는 a가 된다는 뜻이다. 또한 여기서 양변에 a를 나누는 것으로 다음 두 식을 유도할 수 있다. 모듈러 연산은 덧셈, 뺄셈, 곱셈이 가능하다. 나눗셈은 불가능하므로 [백준 ]11401 이항계수 3 (JAVA) 일반적인 이항계수 공식으로는 시간초과및 오버플로우가 나와버린다. 그도 그럴것이 문제에서는 최악의 경우 4000000!을 계산하고 그래야하는데 이것은 long타입의 저장범위를 아득히 넘어버린다. 그로 인해 우리는 다른 방법을 생각해 보아야 하는데 여기서 나오는것이 페르마의 소정리이다. 우리는 알고리즘 문제를 푸는것이지 수학문제를 푸는것이 아니기 때문에 간략하게 정리만 하고 넘어갈것이다.모듈러연산(페르마의 소정리)의 공식에는 덧셈,뺄셈,곱셈이 있으면 나눗셈은 통용되지 않는다. 우선 페르마의 정의는 이렇다. 여기서 조금만 더 나아간다면 이렇게 유도가 가능할 것이다. 그렇다면 우리가 구하고 싶은 나눗셈 꼴은 역원으로 구할수있으면 이를 정리하면 위와 같이 나오며 최종적으로 우리가 도출하고자 하는 계산식은 아래와 .. [백준] 11051 이항계수2 (JAVA) https://www.acmicpc.net/problem/11051 위의 문제는 BOJ에서 유저들이 만들어 놓은 문제집중 redbin0471님의 "단기간 성장"이라는 문제집에속해있는 문제중 하나이다. 이항계수문제의 시리즈는 1부터3까지있는데 2부터는 범위가 1000으로 늘어나서 일반적인 이항계수의 공식으로는 시간초과가 나온다. 위의 문제의 정답은 파스칼의 삼각형과 동적계획법을 이용해 풀면 쉽게 풀린다 import java.io.*; import java.util.StringTokenizer; public class Main { public static void main(String args[]) throws IOException { BufferedReader br = new BufferedReader(n.. 이전 1 ··· 28 29 30 31 다음
