Goyummy

문제 링크 https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 분할 정복은 문제를 나눌 수 없을 때까지 나누어서 각각 풀고 합병하는 방식이다. 함수를 재귀적으로 호출하여 문제를 해결한다는 특징이 있다. 전체 종이를 ‘N//2’ 절반씩 나누어 함수에 넣고 더 이상 나누어지지 않을 때까지 함수를 계속해서 불러왔다. 정답 코드 import sys N = int(sys.stdin.readline()) whole = [list(m..

문제 링크 https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 10815번 문제와 유사해서 계속 이진 탐색 주변만 맴돌았다. 제대로 풀지 못했다. 정답 코드 1. Counter 이용 Counter를 이용해서 풀 수 있다. Counter는 각 원소가 몇번 나오는지 딕셔너리 형태로 반환해준다. ‘from collections import Counter’를 맨 위에 해주어야 한다. count = Counter(nums_..

문제 링크 https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net print(*result) : 리스트의 요소만 출력 정답 코드 import sys N = int(sys.stdin.readline()) nums_card = list(map(int,sys.stdin.readline().split())) M = int(sys.stdin.readline()) nums_int = list(map(int,sys.stdin.read..

문제 링크 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net mid의 값을 간격으로 공유기를 설치한다. 만약 공유기의 개수가 N보다 크면, start를 mid+1로 하여 간격을 넓힌다. 만약 공유기의 개수가 N보다 작으면, end를 mid-1로 하여 간격을 좁힌다. 가장 인접한 공유기의 거리를 최대로 하는 결과를 출력해야하기 때문에 end의 값을 출력해야한다. 5 3 / 1 6 7 8 9 의 테..

문제 링크 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 이 문제는 1654번 문제와 유사하다. 다른 점은 나무를 자르는 것이므로 나무의 높이가 자르는 높이보다 커야한다는 점이다. 그래서 ‘if t >= mid:’ 를 추가해주어야 한다. 정답 코드 import sys N, M = map(int,sys.stdin.readline().split()) trees = list(map(int,sys.stdin.r..

문제 링크 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net start를 1, end를 lan 배열에서 가장 긴 길이로 하였다. amount와 목표로 하는 개수 N이 같아지면, start와 end의 값이 같아지게 된다. 만약 52cm를 두개로 자르려 할 때, 25cm도 2개, 26cm도 2개이다. 이 문제는 최대 길이를 출력하는 것이므로, end를 결과로 출력해야 한다. 정답 코드 import sys K, N = ma..

https://youtu.be/94RC-DsGMLo 이 영상을 보며 작성하였습니다. 이진 탐색: 시작점, 끝점, 중간점의 위치를 나타내는 변수 3개를 이용함. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 방법. #이진 탐색 소스코드 구현 (재귀 함수) def binary_search(array,targrt,start,end): if start > end: return None mid = (start+end) // 2 #찾은 경우 중간점 인덱스 반환 if array[mid] == target: return mid #중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인 elif array[mid] > target: return binary_search(array,..

문제 링크 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net for node, d in tree[start]: 로 자식 노드를 방문하므로 visited 배열을 사용할 필요가 없다. 어떤 노드의 자식 노드가 여러개 일 때, 각각의 방향으로 나아간 거리가 가장 먼, 두개의 길이를 이용하였다. 정답 코드 import sys sys.setrecursionlimit(10 ** 6) n = int(sys.stdin.readline()) ..

문제 링크 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 잘못 푼 코드 import sys sys.setrecursionlimit(10 ** 9) def dfs(start,result): visited[start] = True for i in graph[start]: if not visited[i]: result += distance[start][i] print(result) dfs(i) V = int(sys.stdin.rea..

문제 링크 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 처음에 parent 배열을 모두 -1로 두고 시작했다. 그리고 for i in Tree[start]를 하면서 자식들을 만날 때마다, parent배열에 부모를 할당해주었다. 트리의 루트는 1이므로 dfs(1)을 해주었다. 정답 코드 import sys sys.setrecursionlimit(10 ** 6) N = int(sys.stdin.readline()) Tree = [] Tree = [[]* (N+1) for i in range(N+1)] for..