밤이 블로그

Nim 게임 * Nim 게임이란?님(Nim)은 수학적 전략 보드 게임이다. 몇개의 줄에 숫자나 자연수개의 돌을 두고 순서대로 돌아가면서 한 줄에서 정해진 수의 숫자를 제거한다. 가져오는 숫자에는 상한이 있으며 무조건 1개는 가져와야 한다. 마지막 돌을 가져오는 사람이 이긴다. (마지막 돌을 가져오는 사람이 지는 것으로 하기도 한다.) * 필승 규칙"불균형 상태를 균형 상태로 바꾼다." - 2줄인 경우 -> 균형 상태 : 두 줄의 돌의 개수가 같은 경우 -> 불균형 상태 : 두 줄의 돌의 개수가 다른 경우 - 3줄인 경우 : -> 균형 상태 : Nim Sum이 000인 경우 -> 불균형 상태 : 균형 상태가 아닌 경우 * Nim 게임 해보기http://www.transience.com.au/pearl3.h..

BOJ#5014 스타트링크 * 문제https://www.acmicpc.net/problem/5014 * 풀이 생략 * 나의 코드 https://github.com/stack07142/BOJ/blob/master/BOJ%235014_Startlink/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.PriorityQueue; import java.util.StringTokenizer; /** * BOJ#5014 스타트링크 * https://www.acmicpc.net/problem/5014 *..

BOJ#2468 안전 영역 * 문제https://www.acmicpc.net/problem/2468 * 풀이 비가 내리는 양을 증가시키면서 BFS 또는 DFS를 수행하면 됩니다. * 나의 코드 https://github.com/stack07142/BOJ/blob/master/BOJ%232468_SafetyZone/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; /** * BOJ#2468 안전영역 * https:..

BOJ#2206 벽 부수고 이동하기 * 문제https://www.acmicpc.net/problem/2206 * 풀이 BFS 또는 다익스트라로 풀 수 있습니다.벽을 부수는 경우와 벽을 부수지 않는 경우를 나누어서 진행하면 됩니다. 비슷한 문제 : 도로포장, 알고스팟 * 나의 코드 https://github.com/stack07142/BOJ/tree/master/BOJ%232206_WallDestroy/src import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.Strin..

BOJ#3055 탈출 * 문제https://www.acmicpc.net/problem/3055 * 풀이BFS로 풀었습니다.map을 3차원 배열로 만들었고(행, 열, 시간)물의 위치에서 bfs 탐색, 그 이후 고슴도치 위치에서 bfs탐색하여 탈출이 가능한지 판단하였습니다. 비슷한 문제 : 5427 불 https://www.acmicpc.net/problem/5427 * 나의 코드 https://github.com/stack07142/BOJ/blob/master/BOJ%233055_Escape/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.ut..

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