밤이 블로그

BOJ#5214 환승 * 문제https://www.acmicpc.net/problem/5214 * 풀이 하이퍼튜브는 M개만큼 있고, 각각의 하이퍼튜브는 K개의 노드를 연결하고 있다. -> 간선 정보가 여태까지 풀어본 문제와는 다르게 주어짐-> 간선 정보를 어떤 자료구조에 어떻게 담을지 고민-> 인접 행렬은 메모리 초과 (N 각 하이퍼튜브는 최대 1000개의 노드 정보를 담고 있으므로, 이것을 일일이 짝을 맞추어가며 간선 정보를 저장하기 쉽지 않다. 생각한 아이디어는 다음과 같다.각 하이퍼튜브에 연결된 노드 정보는 아래와 같고1 2 3 1 4 5 3 6 7 5 6 7 6 8 9 각 하이퍼튜브에 속하는 노드에 임의의 더미 노드를 생성하여 연결시킨다.10 ↔ 1, 10 ↔ 2, 10 ↔ 311 ↔ 1, 11 ..

BOJ#1520 내리막 길 * 문제https://www.acmicpc.net/problem/1520 * 풀이무심코 풀었다가 틀린 원인을 찾지 못해서 고생한 문제입니다. 주의해야 할 점으로는내리막길로 이동하다가 중간에 멈추는 경우가 생길 수 있는데이 때 dp값은 0이 되어야 할 것입니다. 그런데 dp 초기값을 0으로 설정한 경우 위 경우를 처리할 수 없어 memoization을 하지 못하고 다시 연산을 해야하므로 시간초과가 발생하게 됩니다. 따라서 dp 초기값을 위 경우(0)를 처리할 수 있는 값으로 설정해야 합니다. (예: -1) ∴ dp 초기값 설정 시 주의할 것 * 나의 코드 https://github.com/stack07142/BOJ/blob/master/BOJ%231520_Downhill/src/..

BOJ#13460 째로탈출 2 * 문제https://www.acmicpc.net/problem/13460 * 풀이 dp + 탐색문제.별로 설명할 것이 없습니다. 코드 이해 안가시면 댓글 주세요. * 나의 코드 https://github.com/stack07142/BOJ/blob/master/BOJ%2313460_XHEscape/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; /** * BOJ#13460 째로탈출 * https://www.acmicpc.net/problem/13460 */ public cl..

BOJ#1254 팰린드롬 만들기 * 문제https://www.acmicpc.net/problem/1254 * 풀이 1. 입력받은 문자열 S를 뒤집은 문자열 R을 생성합니다.2. S의 접미사이면서 R의 접두사인 문자열을 찾습니다.3. 문자열을 찾고 나면, 이 때 R의 남은 부분을 S뒤에 붙이면 팰린드롬이 됩니다.4. 이런 경우가 여러개가 있다면, 그 중 팰린드롬의 길이가 최소가 되는 경우를 찾으면 됩니다. * 나의 코드 https://github.com/stack07142/BOJ/blob/master/BOJ%231254_Palindrome/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputS..