밤이 블로그

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..

BOJ#1261 알고스팟 * 문제https://www.acmicpc.net/problem/1261 * 풀이 다익스트라 알고리즘 * 나의 코드 https://github.com/stack07142/BOJ/blob/master/BOJ%231261_Algospot/src/Main.java import java.io.IOException; import java.io.InputStreamReader; import java.util.*; import java.io.BufferedReader; /** * BOJ#1261 알고스팟 * https://www.acmicpc.net/problem/1261 */ public class Main { static int[][] map = new int[101][101]; stat..

BOJ#10942 팰린드롬? * 문제https://www.acmicpc.net/problem/10942 * 풀이 문자열 중에서 팰린드롬에 대하여 지금 공부할지 아니면 나중에 공부할지 고민했습니다만..(알고리즘 대회가 아니면 별로 쓸 일이 없기 때문에) 간단히 O(N^2) 풀이와 O(N)풀이에 대해 공부해 보았습니다. 완벽히 이해한 상태가 아니기 때문에 설명은 나중에 추가하도록 하겠습니다.팰린드롬은 너무 어렵습니다.. 팰린드롬 공부 링크 : http://stack07142.tistory.com/128 * 나의 코드 O(N), Manacher's Algorithm - 어느 한 원소를 기준으로 좌/우로 넓혀가면서 검사 -> N이 홀수인 경우에는 문제없지만, N이 짝수인 경우에는 문제가 생김 -> 일괄적으로 2..

n명을 k개의 그룹으로 분할하는 경우의 수 (제 2종 스털링 수) 출처 : http://terms.naver.com/entry.nhn?docId=3405190&cid=47324&categoryId=47324

Manacher's Algorithm #1 : https://algospot.com/wiki/read/Manacher's_algorithm#2 : http://www.ideserve.co.in/learn/longest-palindromic-substring-manachers-algorithm 알고리즘 설명은 위 출처에 잘 되어 있습니다.- Time Complexity : O(n)- Space Complexity : O(n) * 관련 문제BOJ#10942 팰린드롬? https://www.acmicpc.net/problem/10942 * 코드 public class Manacher { public Manacher(String s) { char[] T = new char[s.length()*2 + 3]; T[..

BOJ#12851 숨바꼭질 2 * 문제https://www.acmicpc.net/problem/12851 * 풀이 쉬운 문제인데 푸는데 고생을 좀 했습니다. 일단은 1697 숨바꼭질 문제와 동일한데..동생을 찾는 가장 빠른 시간을 출력하는 것과가장 빠른 시간으로 찾는 방법의 개수까지 출력해야 합니다. 헷갈리지 말아야 할 것은 가장 빠른 시간으로 찾는 '경로'가 아니라 '방법'의 개수 입니다. 즉, 입력 데이터가 1 10일 때가장 빠른 경로는 1 -> 2 -> 4 -> 5 -> 10 이지만방법으로 따지면 아래와 같이 2가지가 있습니다.1 -> 2(+1) -> 4(*2) -> 5(+1) -> 10(*2)1 -> 2(*2) -> 4(*2) -> 5(+1) -> 10(*2) 따라서 방법의 개수를 구하려면 큐에 ..

BOJ#1670 정상 회담2 * 문제https://www.acmicpc.net/problem/1670 * 풀이 Dynamic Programming 문제입니다. 동적계획법은 복잡한 문제를 하위 문제로 나누어 푸는 것을 말합니다. 이 문제에서는 그림을 그려보면 이해하기 쉽습니다. 예를 들어 N = 6일 때, 아래 3가지 경우의 합을 구하면 되겠습니다. 1) 0번째 사람과 1번째 사람이 악수하는 경우dp[6] += dp[0] + dp[4](한쪽 구역은 0명, 다른 구역은 4명) 2) 0번째 사람과 3번째 사람이 악수하는 경우dp[6] += dp[2] + dp[2](한쪽 구역은 2명, 다른 구역은 2명) 3) 0번째 사람과 5번째 사람이 악수하는 경우dp[6] += dp[4] + dp[0](한쪽 구역은 4명, ..