Goyummy

문제 링크 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..

문제 링크 https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net __init__ : 생성자라고 불리는 초기화를 위한 함수. 인스턴스화를 할 때 반드시 처음 호출되는 함수. 오브젝트 생성(인스턴스 생성)과 관련하여 데어터의 초기화를 실시하는 함수. __init__은 반드시 첫번째 인수로 self를 지정해야함. 클래스 생성할 때에 지정된인수는 초기화 메소드의 2번째 부터 작성. 전위 순회, 중위 순회, 후위 순회를 하는 코드를 작성할 때, 각..

문제링크 https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net bfs를 두번 쓰는 문제는 처음이라 어려웠다. 한 섬에서 다른 섬으로 가는 최단 거리를 찾는 문제다. 그래서 이 문제에서 해야 할 일은 섬 구분하기, 최단 거리 찾기가 있다. 이를 위해 bfs를 두번 사용해야한다. 나중에 한번 더 풀어봐야 할 문제다. 정답 코드 import sys from collections import deque dx = [-1,1,0,0] dy = [0,0,-1,1] d..

문제 링크 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 7576번 토마토 문제와 유사하다. 앞에서 선언한 미로의 크기에서만 움직일 수 있도록 if 문을 사용하였다. 그리고 (0,0)에서 한 칸씩 나아갈 때마다 그 미로 칸의 값에 +1씩 해주어 최종적으로 마지막 칸에 도착했을 때의 값을 출력하면 얼마나 이동했는지 알 수 있다. 정답 코드 import sys from collections import deque def bfs(x,y): dx = [-1,1,0,0] dy = [..