문제 설명 https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 문제 풀이 1로 만들기와 똑같은 문제인데 여기서는 과정을 출력해야 한다 (경로 추적) 처음에는 i마다 i를 1로 만드는 과정들을 2차원 배열로 저장하고, 이전 단계의 배열을 복사해와서 거기에 append를 통해 모든 i의 과정을 저장하는 방법을 사용하였다 n까지 다 구해지면 n을 1로 만드는 과정이 담긴 배열을 reverse 한 후 len과 함께 출력했는데 시간초과... 아마 배열을 복사하는 과정에서 시간초과가 났던 것 같다 시간 초과가 나와서 다른 방법을 생각했다 어디서 왔는지 경로를 추적..
알고리즘
문제 설명 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제 풀이 처음에 테이블을 생각할 때 최소비용을 저장하는 1차원 배열로 정의해서 점화식을 생각해봤는데 아무리 생각해도 점화식 구하기 너무 힘들 것 같아서 2차원 배열로 정의했다 점화식 d[i][0] = min(d[i - 1][1], d[i - 1][2]) + cost[i][0] d[i][1] = min(d[i - 1][0], d[i - 1][2]) + cost[i]..
문제 설명 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제 풀이 점화식 구하기 2번째 전 계단을 밟는 경우 => D[i - 2] + floor[i] 1번째 전 계단을 밟는 경우 (연속된 세 계단을 밟으면 안 되기 때문에 3번째 계단을 밟고 1번째 전 계단으로 올라와야 한다) => D[i - 3] + floor[i - 1] + floor[i] 이 두 경우 중 최댓값이 D[i]이 된다! 점화식 : D[i] = max(D[i - 2] + floor[i], ..
문제 설명 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제 풀이 점화식 구하는 것에 익숙해지려고 쉬운 DP 문제부터 푸는 중 .. 예시에 나온 D[4]를 봤을 때 1 + 1 + 1 + 1, 1 + 2 + 1, 2 + 1 + 1, 3 + 1 => 3을 1, 2, 3의 합으로 나타내는 법 + 1 1 + 1 + 2, 2 + 2 => 2를 1, 2, 3의 합으로 나타내는 법 + 2 1 + 3 => 1을 1, 2, 3의 합으로 나타내는 법 + 3 점화식 : D[i] = D[i - 1] + D[i - 2] + D[i - 3] 초기값 : D[1] =..
문제 설명 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 문제 풀이 이 문제는 BFS, DFS 두 방법 다 사용 가능하다 그래서 두 가지 방법으로 풀어보았다! 1. DFS 배추가 심어진 땅의 개수를 구하는 것이기 때문에 가장 먼저 DFS로 푸는 방법을 떠올렸다 재귀를 돌면서 아직 방문하지 않았으면서 값이 1인 부분을 찾고, 재귀가 끝나면 return True를 해준다 반복문으로 dfs 함수를 호출해 true면 result를 증가해준다 import sys ..
문제 설명 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로 나누어지면..
동적 프로그래밍 (Dynamic Programming) : 여러 개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘 목적 수행 시간을 단축하고자 만든 알고리즘 여러 개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘 메모리를 사용해서 중복 연산을 줄이고, 중복 연산을 줄여서 수행 속도 개선 메모리 사용: 배열 또는 자료구조 생성 중복 연산 줄임 : 한 번 연산한 결과를 배열에 저장 푸는 과정 테이블 정의하기 점화식 찾기 초기값 정하기 구현 방법 1. Memoization 중복되는 계산은 한 번만 계산 후 메모 하향식 접근 (Top-down), 재귀 기반 코드 한 번 계산 후 저장해놓고, 저장해둔 결과를 꺼내서 사용하며 구현 2. Tabulati..
문제 설명 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는 거리 순서대로 탐색해서 무조건 최소 시간이 맨 처음에 들어오기 때문..
