밤이 블로그

BOJ#2666 벽장문의 이동 * 문제https://www.acmicpc.net/problem/2666 * 풀이1. 문제 이해벽장문을 이동을 열려있는 문이 이동한다는 것으로 바꿔서 생각해봅시다. 훨씬 편하게 문제를 이해할 수 있습니다.열려있는 문은 항상 2개 뿐이므로 하나를 F, 나머지를 S라고 해봅시다. 열려있는 문이 이동하므로 2가지 경우가 발생합니다. 1) F가 이동하는 경우2) S가 이동하는 경우 2. 풀이 설계이 문제는 벽장문의 사용 순서에 따라 탐색이 진행되고, 완전 탐색이 되어야 합니다.이 과정에서 필요한 것, 저장시켜야 하는 것, 변화하는 것들을 이용하여 dp를 정의하고 점화식을 세워보면 (정의)dp[pos1][pos2][idx] : 열린문 F의 위치가 pos1이고 열린문 S의 위치가 po..

BOJ#5557 1학년 * 문제https://www.acmicpc.net/problem/5557 * 풀이- dp[i][sum] : i번째까지 진행했을 때, 합이 sum인 경우의 개수- 구하는 값은 dp[N-2][A[N-1]]- solve(idx, sum) : dp[idx][sum]을 구하는 함수 * 나의 코드https://github.com/stack07142/BOJ/blob/master/BOJ%235557_FirstGrader/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; /** * BOJ#5557 ..

순열 (PERMUTATION) - 사전순 이전 글 : 순열 (PERMUTATION) http://stack07142.tistory.com/24 순열을 사전순으로 만들려면 어떻게 해야 할까 [1, 2, 3, 4] 순열이 있을 때,---------------------------------------------------------[1, 2, 3, 4] [1, 2, 3, 4][2, 1, 3, 4][3, 1, 2, 4][4, 1, 2, 3]---------------------------------------------------------[1, 2, 3, 4][1, 2, 3, 4][1, 3, 2, 4][1, 4, 2, 3][2, 1, 3, 4][2, 1, 3, 4][2, 3, 1, 4][2, 4, 1, 3]..

BOJ#2098 외판원 순회 * 문제https://www.acmicpc.net/problem/2098 * 풀이dp 문제입니다. (주의점, 힌트)1. 사이클이므로 어느 점을 시작점으로 잡아도 상관없다.2. 마을 방문 여부를 매개변수로 넘겨주기 위해서는 ? 비트마스크를 사용하자.3. 시간 복잡도 : O(N^2 * 2^N) * 나의 코드https://github.com/stack07142/BOJ/blob/master/BOJ%232098_TSP/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.St..

BOJ#1182 부분집합의 합 * 문제https://www.acmicpc.net/problem/1182 * 풀이처음에는 조합을 이용해서 풀었습니다. (160ms)집합에서 1개를 고르는 경우, 2개를 고르는 경우, ...., N개를 고르는 경우 두번째 풀때는 집합의 각 원소의 2가지 경우에 대해(고르는 경우, 고르지 않는 경우)재귀 함수 호출로 답을 구하였습니다. (76ms) 주의할 점 : S가 0인 경우에는 공집합도 카운트 될 수 있음 * 나의 코드 https://github.com/stack07142/BOJ/blob/master/BOJ%231182_SumOfSubsets/src/Main.java import java.io.*; import java.util.StringTokenizer; /** * BO..

BOJ#9520 NP-Hard * 문제https://www.acmicpc.net/problem/9520 * 풀이- 규칙 : 번호가 K인 도시를 방문하려면, K보다 작은 번호를 가진 모든 도시를 K번을 방문하기 전에 모두 방문하거나, 방문한 후에 모두 방문해야 한다.즉, K보다 번호가 작은 도시 중 하나를 K번 이전에 방문하고, 다른 하나를 K번 이후에 방문하면 안된다. 위 규칙을 만족하는 방문 수열은 아래와 같이 만들 수 있습니다. 맨 처음 1번 도시를 방문 : {1}그 다음 2번 도시는 수열의 왼쪽 또는 오른쪽에 들어갈 수 있습니다 : {2, 1}, {1, 2}그 다음 3번 도시는 수열의 왼쪽 또는 오른쪽에 들어갈 수 있습니다 : {3, 2, 1}, {2, 1, 3}, {3, 1, 2}, {1, 2, ..

BOJ#12101 1, 2, 3 더하기 2 * 문제https://www.acmicpc.net/problem/12101 * 풀이dfs로 풀었습니다. dfs를 돌리면 자연스럽게 오름차순으로 결과가 나옵니다.풀이는 쉽기 때문에 생략합니다. dp로 다시 푼 후 업데이트 예정. * 나의 코드https://github.com/stack07142/BOJ/blob/master/BOJ%2312101_Sum123_2/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; /** * BOJ#12101 1, 2, 3 더하기 2 * ..

BOJ#1987 알파벳 (Letters) * 문제https://www.acmicpc.net/problem/1987 * 풀이알파벳이 중복되는지 판단하는 방법으로 2가지 방법을 사용해 보았습니다.(비트마스크, 길이가 26인 boolean visited 배열) * 나의 코드https://github.com/stack07142/BOJ/tree/master/BOJ%231987_Alphabet/src import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; /** * BOJ#1987 알파벳 * https://www.acmicpc.net/proble..

BOJ#11048 이동하기 * 문제https://www.acmicpc.net/problem/11048 * 풀이풀이는 생략합니다.dp 초기값만 주의할 것. * 나의 코드https://github.com/stack07142/BOJ/blob/master/BOJ%2311048_Move/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; /** * BOJ#11048 이동하기 * https://www.acmicpc.net/problem/11048 */ public class..

BOJ#11058 크리보드 * 문제https://www.acmicpc.net/problem/11058 * 풀이- dp[i] : 버튼을 i번 눌렀을 때, 화면에 출력할 수 있는 A의 최대 개수 dp를 위와 같이 정의하고, 문제를 분석하면서 몇가지 성질을 찾아보았습니다. 0. i가 클수록 dp[i]가 무조건 크다. 1. i가 커질수록 인접한 dp값들의 차이가 커진다. 2. dp[i]의 값은 무조건 dp[i-3] * 2보다 무조건 크거나 같다. 또한 dp[i-3]의 값은 dp[i-6] * 2 보다 무조건 크거나 같다.... 3. i가 일정 수준 이상이면(7이상), 이제는 A를 하나 추가하는 버튼은 필요가 없다. 복사-붙여넣기 동작만 하는 것이 A를 최대로 출력할 수 있다. 4. dp[i] 값은 i번째에 1) ..