구빙그르르르

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제 한줄 이해 - N*M 크기의 연구소에 바이러스(2), 벽(1), 빈칸(0)이 있을때 벽 3개를 새로 세워 바이러스가 퍼져나간뒤 안전한 칸이 제일 많은 경우를 구하기! 생각난 풀이 1번째 방법: 먼저 백트래킹이 떠올랐다. 현재 그래프 상태에서 벽을 새로 3개를 세우는 경우를 판단하기 위해서이다. 그런 다음 백트래킹의 종료 조건절에서 BFS 탐색을 통해 바이러스가 퍼지게 한 후 안전한 칸을 카운팅했다!!! ..

https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 문제 한줄 이해 - 전휘 순회로 출력된 결과를 가지고 후위 순회한 결과 뽑기 생각난 풀이 1번째 방법: 먼저 전회 순회를 통해 루트를 기준으로 루트보다 큰 값을 만나는 순간 왼쪽 오른쪽으로 나눠진다는 것은 알아냈지만 이를 어떻게 활용해야할까 고민을하다가 계속 파고드네????? 재귀를 써야하나??? 접근해봤다. 예제를 보면 50 30 24 5 28 45 98 52 60 이렇게 전회 순회..

https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 문제 한줄 이해 - N줄에 3개의 숫자가 쓰여져 있을 때 첫줄 부터 숫자를 선택해 더해나가면서 최소와 최대인 경우 구하기 생각난 풀이 1번째 방법: 며칠전에 RGB거리 문제랑 비슷한 느낌인데 라는 생각에 다이나믹프로그래밍을 떠올렸다. 이때 그때의 아이디어랑 똑같이 풀면 되겠는데? 라는 생각했다. 먼저 수를 고를때 이전에 더해진 값들이 저장된 dp 값중에서 최대와 최소를 구해가자라고 생각했다. 이때 각자리를 선택..

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 문제 한줄 이해 -N개의 도시가 주어지고 M개의 버스들이 출발 도시에서 도착 도시까지 가는 비용을 가지고 있을때 원하는 시작 도시에서 도착 도시까지의 최소 비용 구하기 생각난 풀이 1번째 방법: 오랜만에 다익스트라 문제를 만났다. 다익스트라가 무엇이냐 하면 간단히 얘기하면 특정 노드에서 다른 노드로 갈 수 있는 최소 가중치를 가지도록 하는것이다. 이때 다익스트라를..

https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 문제 한줄 이해 -N*N 의 그래프가 주어질때 (x1,y1) - (x2,y2)까지의 합 구하기 생각난 풀이 1번째 방법: 문제 이름이 대놓고 누적합이라 어떤식으로 디피에 저장을 해서 이용을 할까 생각을 했다. 이때 dp에 그래프를 순차적으로 돌면서 합을 저장 해놓고 이를 활용 하면 된다고 생각 했다. 이유는 그림에서 설명한거 처럼 구하고자 하는 범위까지 ..

https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 문제 한줄 이해 -2행 n열의 스티커가 있고 스티커의 점수가 있을때 주어진 조건에 맞춰서 높은 점수를 확보하도록 스티커를 떼기 생각난 풀이 1번째 방법: DP가 떠올라서 점화식을 어떻게 세울까 고민했다. 먼저 스티커를 골라갈때 2가지 경우가 있다. 지그재그로 갈건지 바로 다음칸은 뜯지 않고 다다음칸에 더 큰 점수를 갖는 스티커를 뜯을지이다. 그렇다면 DP에 어떤값을 저장하고 어떻게 활용..

https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 문제 한줄 이해 -A숫자를 B번 곱한뒤 C로 나눈 나머지 구하기 생각난 풀이 1번째 방법: A를 1~B번 곱해가면서 각각 C로 나눈 나머지가 규칙을 이룰 것이라 생각하고 다음과 같이 코드를 짰다. import sys a,b,c = map(int,sys.stdin.readline().split()) dp = [] cnt = 0 for i in range(b): cnt +=1 now = a**i % c if now in dp: cnt -= 1 break dp.app..

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제 한줄 이해 -N개의 집이 있을때 문제에 주어진 규칙에 따라 집에 색칠을 칠할때 최소비용 구하기! 생각난 풀이 1번째 방법: 처음에는 첫번째 집이 각각 R, G, B의 경우에 따라 모든 경우의 수를 재귀함수를 통해 구현했다. import sys n = int(sys.stdin.readline()) homes = [] for i in range(n): homes.append..

https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 문제 한줄 이해 -A숫자를 2배, A숫자 뒤에 1 붙이기를 해가면서 B가 되기위한 최소 횟수 구하기 생각난 풀이 1번째 방법: 숫자의 연산을 해주고 탐색을 진행하는 BFS 아이디어를 떠올려 적용해봤다. 이유는 A 2*A A1 이런식으로 계속 숫자들이 뻗어 나가기 때문이다. import sys from collections import deque #숫자에 1을 붙여주기위해 문자연산이 가능하게 str로 a, b = map(str,sys.stdin.readline().split()) que = deque() #큐에 횟수와 현재..

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 한줄 이해 -노드들의 부모트리 찾기 생각난 풀이 1번째 방법: 노드들의 연결 정보를 인접행렬로 나타내 bfs 탐색을 통해 확인 하려 했다. 이때 큐에 연결된노드와 현재 노드를 같이 넘겨주고 꺼낼때마다 visited에 방문을 표시할겸 부모노드의 번호로 바꿔줬다. import sys from collections import deque n = int(sys.stdin.readline()) visited = [0] * (n+1) graph = [[0 for i..