밤이 블로그

BOJ#2293 동전1 * 문제https://www.acmicpc.net/problem/2293 * 풀이정말 이해하기 쉽지 않은 문제였습니다.조금 더 완벽하게 이해한 후에 저의 풀이를 포스팅하도록 하겠습니다. 참고한 풀이 : http://blog.naver.com/occidere/220784778900import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; /** * BOJ#2293 동전1 * https://www.acmicpc.net/problem/2293 */ public class Main { // dp[i] : n가지 종류의 동전..

BOJ#1865 웜홀 * 문제https://www.acmicpc.net/problem/1865 * 풀이 벨만-포드 알고리즘을 활용하는 기본 문제입니다. 일단 기본적인 풀이 방법은 "BOJ#11657 타임머신" 문제와 같고,음수 간선 사이클이 존재하는지 확인만 하면 되는 문제입니다. 주의할 점 #1)도로에 방향이 없으므로,도로 정보를 입력 받을 때 양방향으로 생각해야 한다는 점입니다. -> 결국 Edge의 개수는 2 * M + W -> 코드 상 여러번 쓰이게 되므로, 실수하지 않게 따로 변수로 저장해둡시다. 주의할 점 #2)시작점이 주어지지 않았으므로, 시작점을 어느 곳으로 해야 할 지 결정해야 합니다. 음수 사이클은 웜홀이 연결된 지점에서만 존재 할 수 있으므로웜홀의 목적지들을 배열에 따로 저장하여, 이..

BOJ#11657 타임머신 * 문제https://www.acmicpc.net/problem/11657 * 풀이벨만-포드 알고리즘 문제입니다. → http://stack07142.tistory.com/79 알고리즘 설명은 위 링크를 참고하시면 됩니다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; /** * BOJ#11657 타임머신 * https://www.acmicpc.net/problem/11657 */ public class Main { static final int NONE = -1; static final int IN..

벨만-포드 알고리즘(Bellman-Ford algorithm) 최단 경로 알고리즘에서 대표적인 것으로는 1) 다익스트라 : 유향그래프, 한점 - 다수의 점, 음수 가중치 X2) 벨만-포드 : 유향그래프, 한점 - 다수의 점, 음수 가중치 O, 음수 사이클 X3) 플로이드-와샬 : 모든 점- 모든 점 여기서는 벨만-포드 알고리즘에 대해 알아보겠습니다. * 벨만-포드 알고리즘(Bellman-Ford algorithm) 벨만-포드 알고리즘은 가중 유향 그래프에서 최단 경로 문제를 푸는 알고리즘이다. 이때 변의 가중치는 음수일 수도 있다. 다익스트라 알고리즘은 벨먼-포드 알고리즘과 동일한 작업을 수행하고 실행 속도도 더 빠르다. 하지만 다익스트라 알고리즘은 가중치가 음수인 경우에는 처리할 수 없으므로, 이런 경..

BOJ#3109 빵집 (PLINOVOD) * 문제https://www.acmicpc.net/problem/3109 * 풀이 1) 가스관과 빵집을 연결하는 가스 파이프 라인은 첫번째 열에서 시작하고, 마지막 열에서 끝나게 됩니다. 2) 첫번째 열과 마지막 열은 항상 비어있습니다.3) 각 칸은 3가지 방향으로 (↗️, ➡️, ↘️) 연결할 수 있습니다.4) 건물이 있을 경우 파이프를 설치할 수 없고, 파이프끼리 겹칠 수도 없습니다. 1번 조건 : 첫번째 열에서 시작하여 마지막 열까지 진행 후 return 되는 Backtracking 함수 구현 : 마지막 열 도달 시 1을 return하여 파이프라인 개수를 증가시킨다. 2번, 3번 조건 : 첫번째 열은 모든 행을 검사해야 하고, 그 다음부터는 최대 3개의 행만..

BOJ#11066 파일 합치기 (Merging Files) * 문제https://www.acmicpc.net/problem/11066 * 풀이 수열이 주어지고, 인접한 숫자는 합칠 수 있습니다. 합치는 비용은 두 수의 합이고, 전체 수를 합치는데 필요한 최소 비용을 구하는 문제입니다. ,동적계획법 (Dynamic Programming)을 이용합니다. 먼저 dp의 정의를 세워보면dp[i][j] : 수열에서 i번째~j번째 수까지 합치는데 필요한 최소 비용 ,따라서 아래와 같은 수열이 존재할 때null 40 30 30 50 위 정의에 따르면 자기 자신인 경우에는 합칠 수 없으므로dp[1][1] = 0, dp[2][2] = 0 ... 이 될 것입니다. 또한 인접한 수에 대해서는dp[1][2] = 70, dp[2..

BOJ#2089 -2진수 * 문제 https://www.acmicpc.net/problem/2089 * 풀이 기존에 10진수를 2진수로 변환하는 알고리즘과 같이주어진 수를 (-2)로 나누어 가면서, 나머지들을 저장하는 방법을 쓴다. 단, 주의할 점으로는 나머지를 올림 해야 한다는 것이다. * 참고http://kin.naver.com/qna/detail.nhn?d1id=11&dirId=1113&docId=57428826&qb=7Iut7KeE7IiYIOydtOynhOyImCDrs4DtmZgg7JuQ66as&enc=utf8§ion=kin&rank=9&search_sort=0&spq=0 * 나의 코드https://github.com/stack07142/BOJ/tree/master/BOJ%232089_MinusB..

BOJ#1373 2진수 8진수 * 문제https://www.acmicpc.net/problem/1373 * 풀이2진수, 8진수, 16진수 간 변환은 2진수를 중심으로 하면 편합니다.즉, 8진수와 16진수 간의 변환도 일단 2진수로 변환을 한 후 다시 변환을 해주시는 것이 좋습니다. 2진수 11001100이 있을 때,2자리씩 묶으면 4진수11 00 11 00 → 30303자리씩 묶으면 8진수011 001 100 → 3144자리씩 묶으면 16진수1100 1100 → CC 1. String으로 입력 받은 2진수 입력값의 길이를 조사한다.2. 길이가 3으로 나누어 떨어지지 않는 경우, "0" 또는 "00"을 추가시켜준다.3. 3자리씩 끊어 가면서 int 변환한 후 8진수 값으로 변환한다. * 나의 코드https..

BOJ#2011 암호코드 * 문제https://www.acmicpc.net/problem/2011 * 풀이동적계획법(Dynamic Programming)을 이용합니다. 숫자의 범위가 1~26이므로어떤 해석할 수 있는 암호가 주어졌을 때, 마지막 숫자는 아래와 같이 3가지 경우로 나눌 수 있습니다. 그리고 아예 해석할 수 없는 경우도 있습니다. (dp[i] : i번째 숫자까지 해석했을 때, 해석의 가짓수)1) 한 자리수로만 해석할 수 있는 경우예 : "251" → 마지막 숫자 "1"은 "1"로 해석 가능하나, "51"로는 해석할 수 없다. 즉, "25"에서 "1"을 추가한 경우 dp[i] = dp[i-1]; 2) 두 자리수로만 해석할 수 있는 경우 예 : "2510" → 마지막 숫자 "0"은 "10"로 해..

BOJ#2225 합분해 * 문제https://www.acmicpc.net/problem/2225 * 풀이dynamic Programming 문제입니다. 예를 들어 2 2가 입력된 경우 아래와 같이 3가지 경우가 있을 수 있습니다.0 + 21 + 12 + 0 3 2가 입력된 경우에는0 + 31 + 22 + 13 + 0 4 2가 입력된 경우에는0 + 41 + 32 + 23 + 14 + 0 감이 오시나요?어떻게 풀어야 할지 모를때는 예제의 숫자를 낮춰서 생각하면 좋습니다. " N K가 입력된 경우에서첫번째 숫자가 m으로 정해지면나머지는 N-m K-1의 경우가 됩니다. " dp를 아래와 같이 정의하고 위 내용을 구현하시면 되겠습니다. - dp[N][K] : 0~N까지의 정수 K개를 더해서 그 합이 N이 되는 경..