문제 https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 어떻게 풀 것인가? 특정 최단경로의 거리를 묻는 문제이다. 다익스트라를 이용하여 문제를 풀 수도 있지만, 나는 간단하게 BFS로 문제를 해결하였다. 최단경로를 묻는 것이 아닌 특정 최단경로의 거리를 묻는 것이기 때문에 그래프적 접근이 훨씬 좋다고 생각하였다. 풀면서 놓쳤던점 X 이 문제를 통해 얻어갈 것 BFS의 사용법..
문제 https://www.acmicpc.net/problem/15664 15664번: N과 M (10) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 어떻게 풀 것인가? 처음에는 단순 백트래킹을 이용한 조합 문제라고 생각했다. 하지만 다시보니 중복성을 제거 해야한다고 한다. 여기서 문제에 대해서 많이 생각을 했다. 결국 중복성에 대한 문제는 자료구조를 통해서 해결할 수 있었다. Set을 이용하기로 하였다. 조합을 이용한 백트레킹을 이용하였지만, 다른 사람의 풀이를 통해서 DFS 백트레킹을 이용하기로 하였다. 사실 큰 차이는 없는 것 같..
문제 https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 어떻게 풀 것인가? 구현, 시뮬레이션 문제이다. 하지만 생각할 것이 많아서 어려운 문제였다. 시간을 재고, 뱀 이동하기 범위를 벗어나거나, 뱀 몸통 만날 때 종료 사과가 있을 때 없을 때 처리 방향을 바꿔주는 시간을 만날 때 방향 변경 현재값 업데이트 위와 같은 로직을 While문을 통해서 반복해야한다. 답안 코드를 본다면 너무나도 쉽지만, 생각을 코드로 옮긴다는 것은 어려운 일인 것 같다. 풀면서..
문제 https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 어떻게 풀 것인가? DFS를 이용한 간단한 문제 풀이였다. 그래서는 이중연결리스트를 이용하여 연결된 친구사이를 표현한 뒤에 재귀를 이용한 DFS로 문제를 풀었으며 DFS를 통해서 노드를 쭉쭉 연결해 나아갔을때 status변수를 이용하여 만약 깊이가 5라면 true 그것이 아니라면 false를 반환하는 식으로 문제를 해결했다. 풀면서 놓쳤던점 그래프 탐색이라고 하면 항상 BFS만 이용하였기에 DFS는 익숙하지 않아서 애를 많이 먹었다. 이 문제를 통해 얻어갈 것 재귀를 이용한 DFS 문제 풀이 내 ..
문제 https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 어떻게 풀 것인가? 문제는 간단한 BFS 문제이다. 다만 매번 Visit 2차원 배열을 초기화하여 가장 긴 거리를 찾아야한다. 그렇기에 이 부분만 주의하여 푼다면 어렵지않다. 풀면서 놓쳤던점 X 이 문제를 통해 얻어갈 것 기본적인 BFS 풀이 내 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputSt..
문제 https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 어떻게 풀 것인가? 처음에는 아이디어가 떠오르지 않아서 많이 어려웠던 문제였다. 그래서 문제에 대한 힌트를 얻기위해서 아래에 알고리즘 분류를 확인하였으나, 이게 무슨... DP문제였다. 문제가 너무 어려웠다... 3시간의 고민 끝에 다른 분의 풀이를 참고하여 문제를 풀 수 있었다. 참고 사항에 그분의 풀이를 업로드하였다. 교차 여부를 구현으로 한다면 너무나 어렵다. 그렇다면 여기서 역으로 생각해야했..
문제 https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 어떻게 풀 것인가? 이 문제를 보자마자 떠올랐던 것은 바로 "투포인터를 이용한 이분탐색 알고리즘" 이었다. 이분 탐색과 result 배열을 이용하여 계속해서 0과 가까운 것을 비교하면서 찾아간다. 이것은 아마 코드를 보는 것이 이해가 더 빠를 것이다. 풀면서 놓쳤던점 X 이 문제를 통해 얻어갈 것 이분탐색에 대한 응용 내 코드 import java.io.Bu..
문제 https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 어떻게 풀 것인가? 문제는 상당히 짧다. 하지만 고민은 많이해야하는 문제였다. 우선적으로 문제에 대해서 고민을 하면 다이나믹 프로그래밍이라는 것을 알 수 있다. 하지만 다이나믹 프로그래밍에서 중요한 점화식에 대해서 고민이 상당히 오래걸렸다. (내가 오랜만에 풀어서 그런걸 수도 있다....) 나는 문제를 2시간 가량 고민하다가 결국엔 다른 분의 풀이를 참조했다. 아래를 잘 보자. 1. N=1일때 K=1인경우 : 1가지 (1) K=2인경우 : 2가지 (1+0, 0+1) K=3인경우 : 3가지 (0+1+1, 1+0+1, 1..
