-

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 백준 DP 연습 문제다. DP는 크게 상향식, 하향식으로 나뉠 수 있는데, 이 문제는 상향식으로 풀었다. 즉, 초기값을 낮은곳에 잡고 이를 활용해 목적숫자로 커지며 답을 갱신하는 구조다. 작은 답이 큰 답의 도출에 이용되는 DP. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 #include #include #define maxlen 1000000+1 #define INF 987654321 usin..

https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 문제 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까? 입력 입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ... www.acmicpc.net BFS 알고리즘 연습 문제이다. 나이트가 갈 수 있는 방향 8개가 주어지고, 현재 위치와 목표로 하는 위치가 주어졌을 때, 몇 번만..

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 www.acmicpc.net 백준 BFS 연습문제이다. 계속해서 DFS와 BFS 연습문제들을 풀면서 좀더 느끼는 것은 어떨 때 BFS를, 어떨 때 DFS(혹은 백트래킹..

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수 www.acmicpc.net 백준 DFS 연습 문제다. 바로 전에 풀었던 1012번(유기농 배추, https://cpp-dev.tistory.com/22)과 유사한 문제다. 전체 map을 돌면..

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. ( www.acmicpc.net 백준 DFS 연습 문제이다. 주어진 밭의 정보에서 배추들의 '군' 개수를 dfs 탐색으로 찾는 문제였다. 각 테스트 케이스마다 밭에 ..

https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 백준 DFS 연습 문제이다. 최근 문제풀면서 DFS에 대한 응용력이 부족한것같아 풀어보았다. 원리와 성격을 알지만 응용을 잘 할 수 있게 지속적으로 연습하자. 이 문제는 각 정점에서 다른 정점으로 갈 수 있는 경로가 있다면 1, 아니면 0을 N x N 행렬에 저장해 출력하라는 문제다. 모든 정점 쌍에 대해 dfs 탐색을 하면 시간 초과가 뜨지만, 한 정점에서 갈 수 있는 모든 점들을 찾으면 그 점들에 갈 수 있는 경로가 있다는 뜻이므로 실..

2018년 상반기 삼성SW테스트 기출 문제다. https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선이 같은 위치를 갖는다. 아래 그림은 N = 5, H = 6 인 경우의 그림이고, 가로선은 없다. 초록선은 세로선을 나타내고, 초록선과 점선이 교차하는 점은 가로선을 놓을 수 있는 점이다. 가로선은 인접한 두 세로선을 연결해야 한다. 단, 두 가로선이 연속하거나 서로 www.acmicpc.net 기존에 4방위 또는 8방위에 대해 이리저리 이동하는 문제 (로봇)를 BFS 또는 DF..