문제 설명 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 풀이 DP 개념 이해하고 연습문제 풀어보기! 1. 테이블 정의하기 D[i] = i를 1로 만들기 위해 필요한 연산 사용 횟수의 최솟값 2. 점화식 찾기 D[12] = ? 3으로 나누거나 (D[12] = D[4] + 1) 2로 나누거나 (D[12] = D[6] + 1) 1을 빼거나 (D[12] = D[11] + 1) => D[12] = min(D[4] + 1, D[6] + 1, D[11] + 1) D[k] = ? 3으로 나누어지면 3으로 나누거나 (D[k] = D[k/3] + 1) 2로 나누어지면..
알고리즘/백준
문제 설명 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 문제 풀이 구역의 개수를 구하는 문제이기 때문에 DFS로 풀었다! 파이썬은 재귀 limit이 있어서 setrecursionlimit으로 최대 재귀 횟수를 설정해주어야 한다. RGB배열을 만들어 하나씩 꺼내가며 R, G, B구역의 개수 더해가면서 적록색약이 아닌 사람이 봤을 때 구역을 구하였고, G를 R로 바꾸어 적록색약인 사람이 보는 구역의 수를 구했다. import sys sy..
문제 설명 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제 풀이 지금까지 풀었던 BFS 문제들은 2차원 리스트에서 상하좌우로 탐색하는 문제였다면 이 문제는 1차원 리스트에서 탐색하는 문제다 기존 문제들과 푸는 방법이 살짝 달라서 고민을 좀 하고 풀었다 제한사항을 읽어보고 아무 생각 없이 리스트의 크기를 100,000으로 지정했는데, 문제를 풀고 나서 코드를 다시 보니 탐색하다보면 범위를 넘을 수도 있다 수빈이와 ..
문제 설명 https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자 www.acmicpc.net 문제 풀이 bfs를 두 번을 해야 하는 문제는 처음이라 풀이 방향을 잡는데 어려웠다 일단 불이 확산되는 시간을 구하고, 그 다음에 지훈이가 탈출할 수 있는지 확인해야 하기 때문에 BFS를 두 번 수행해야 한다 지훈이가 미로 공간을 벗어나면 미로를 탈출하는 것이기 때문에 바로 return을 해줬다 BFS는 거리 순서대로 탐색해서 무조건 최소 시간이 맨 처음에 들어오기 때문..
문제 설명 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 문제 풀이 전형적인 BFS 문제 시작점이 여러 개인 BFS 문제를 처음 풀어봐서 풀다가 당황 ,,,, BFS 자체가 너비 우선으로 탐색하기 때문에 1일차, 2일차 이렇게 순서대로 큐에 들어간다 처음 시작점을 찾은 후 큐에 넣은 다음 BFS를 수행하면 된다 ! 다 풀고 나서 코드 리뷰를 해본 결과 bfs 함수 안에서 큐를 다 돌고 나서 안 익은 토마토가 있을 때(값이 0일..
문제 설명 https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 문제 풀이 visited로 방문 여부를 기록하였고, 이중 포문으로 값이 1이면서 아직 방문하지 않은 지점일 때 bfs를 시작하여 bfs의 시작점을 구했다. 가장 넓은 그림의 넓이를 출력하기 위해 max를 사용하여 비교했다! from collections import deque n, m = map(int, input().split()) visited = [[False] * m for _ in ..
문제 설명 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 문제 풀이 가장 기본적인 BFS 문제 경로의 최단 거리를 구하는 문제이기 때문에 BFS로 풀었다 만약 경로가 몇 가지인지를 묻는다면 DFS로..! 미로 범위에서 벗어난 경우이거나, 이동할 수 없는 칸을 무시하고 해당 칸을 처음 방문했을 때 이전 지점까지의 최단거리 + 1 해주었다 from collections import deque def bfs(x, y): queue = deque() queue.append((x, ..
