도비LOG(跳飛錄)

https://www.acmicpc.net/problem/15686 문제 요약 치킨 거리 = 집과 가장 가까운 치킨 거리 = |x1-x2| + |y1-y2| 도시의 치킨 거리 = 모든 집의 치킨 거리의 합 도시의 치킨거리가 가장 작게 되도록 치킨집 M개만 남겼을 때의 도시의 치킨거리를 구하라. 풀이 m개의 치킨 집을 남기는 조합에 대해서, 도시의 치킨 거리가 최소가 되는 조합에서의 도시의 치킨 거리를 리턴한다. # 백준 15686 치킨 배달 골드5 https://www.acmicpc.net/problem/15686 # 치킨거리: 집과 가장 가까운 치킨집까지의 거리 = |x1-x2| + |y1-y2| # 도시의 치킨거리 = 모든 집의 치킨 거리의 합 # 도시의 치킨거리가 가장 작게 되도록 치킨집 M개만 남..

https://www.acmicpc.net/problem/2096 문제 요약 바로 아래 칸 혹은 바로 아래 칸과 인접한 칸으로만 이동이 가능할 때, 얻을 수 있는 최대 점수와 최소 점수를 리턴. 풀이 DP로 풀 수 있는데 메모리 제한이 4MB로 매우 작다. 입력값을 배열에 직접 담고, DP 방식으로 다음행에다가 이전 행의 정보를 계속 누적하는 방식으로 풀면 메모리 초과가 뜬다. DP 방식으로 풀되 매 행을 받을 때마다 결과를 처리함으로써 메모리를 절약해야 한다. # 백준 2096 내려가기 골드5 https://www.acmicpc.net/problem/2096 # 바로 아래 혹은 바로 아래와 인접한 칸으로만 이동 가능 # 최대 점수, 최소 점수를 구하라. n = int(input()) a,b,c = ma..

https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 문제 요약 출발 지점에서 끝 지점으로 가는 최소 비용 리턴 풀이 기름값이 가장 저렴한 도시에서 기름을 최대한 많이 채우면 된다. 출발 지점부터 끝 지점까지의 가격을 훑어보면서, 최저가 도시를 찾는다면 현재 필요한 비용을 해당 도시의 가격을 기준으로 갱신해준다. # 백준 13305 주유소 https://www.acmicpc.net/problem/13305 # 도시마다 주유소가 있음. ..

https://www.acmicpc.net/problem/1806 문제 요약 연속된 수들의 부분합 중에서 합이 S 이상 되는 것 중 길이가 가장 짧은 것의 길이를 리턴 풀이 투 포인터 방식으로 풀 수 있다. 부분합이 s이상일 경우 최소 길이를 업데이트해주고, 왼쪽 포인터를 오른쪽으로 이동한다. 그리고 부분합이 s 미만일 경우 오른쪽 포인터를 오른쪽으로 이동한다. 즉, 윈도우를 늘여서 부분합을 증가시켜준다. # 투 포인터 # 백준 1806 부분합 n, s = map(int, input().split()) nums = list(map(int, input().split())) left = 0 # 왼쪽포인터 right = 0 # 오른쪽포인터 summation = 0 # 부분합 min_len = 100000001..

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제 요약 바이러스는 상하좌우 인접 빈칸으로 퍼져나갈 수 있다. 벽 3개를 세워 확산을 최대한 막아야 한다. 0=빈칸, 1=벽, 2=바이러스 벽을 세운 뒤 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 함. 이 안전영역의 최댓값을 구하라. 풀이 먼저 벽을 3개 세우고 나서 바이러스의 위치부터 시작하는 bfs를 수행한다. 이렇게 함으로써 바이러스가 퍼지는 영역을 구해볼 수 있고, 바이러스가 다 퍼지고 난 후의 ..

https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 문제 요약 트리를 입력 받아서 전위 순회, 중위 순회, 후위 순회 결과를 출력하여라. 풀이 전위 순회, 중위 순회, 후위 순회를 하는 함수를 각각 구현한다. 전위 순회는 root -> left -> right 순서로, 중위 순회는 left -> root -> right 순서로, 후위 순회는 left -> right -> root 순서로 탐색해야 한다. 이를 위해 각 함수를 재귀함수로 구..

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 요약 주어지는 트리의 각 노드의 부모를 출력하여라. 풀이 BFS 방식으로 root인 1부터 시작해서 아래로 탐색해 나가면 부모들을 순서대로 만날 수 있다. 이렇게 마주치는 노드들을 parent라는 배열에 저장한다. 그러고 난 뒤 root를 제외한 부모들을 차례대로 출력해준다. # 백준 11725 트리의 부모 찾기 실버2 https://www.acmicpc.net/problem/11725 from collections import defaultdict, d..

https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 문제 요약 트리를 입력 받아서 해당 트리의 지름을 구하여라. 풀이 트리의 지름은 임의의 정점에서 출발하여 최단거리로 갈 수 있는 노드를 구하고, 그 노드에서 다시 최단 거리로 갈 수 있는 노드까지의 거리가 된다. 양의 가중치가 있는 트리가 입력으로 주어지므로, 양의 가중치 그래프에서 최단거리를 탐색할 때 활용할 수 있는 다익스트라 알고리즘을 활용한다. 처음 출발하는 임의의 노드..

https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 문제 $_nC_r$을 출력하라. 풀이 $$_nC_r = n! / r!(n-r)!$$ 조합의 수를 구하는 공식을 이용한다. factorial은 함수로 직접 구현해도 되고, 혹은 내장함수 math.factorial()를 사용해도 된다. # 백준 2407 조합 실버3 https://www.acmicpc.net/problem/2407 a, b = map(int, input().split()) def factorial(x): if x == 1: return 1 else: return x * factorial(x-1) de..

https://www.acmicpc.net/problem/1629 문제 요약 a ** b % c를 리턴해야 한다. 단, 이때 위 식 그대로 출력하게 되면 시간초과가 발생한다. 분할 정복으로 풀거나, 혹은 파이썬의 pow 함수를 이용한다. 아래 두 개의 풀이 모두 정답이 된다. 풀이 1 # 백준 1629 곱셈 실버1 https://www.acmicpc.net/problem/1629 a, b, c = map(int, input().split()) # 2**10 = 2**5 * 2**5 def div(a, b): if b == 1: return a % c temp = div(a, b // 2) # 분할 # b가 짝수일 때 if b % 2 == 0: return temp * temp % c # a가 홀수일 때 ..