Goyummy

문제 링크 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://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 = [..

문제링크 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 여러 개의 익은 토마토로부터 시작하기 위해, 큐를 함수 밖에서 선언하고 큐 삽입을 선언한다. 정답 코드 import sys from collections import deque def bfs(): while queue: x, y = queue.popleft() for i in range(4): pointX = x + dx[i] pointY = y + dy[i] if 0

문제 링크 https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 2667번과 아주 유사한 문제다. 2667번에서는 델타값을 dx = [0, 0, -1, 1] dy = [-1, 1, 0, 0] 으로 주었지만 이번 4963번 문제에서는 대각선 방향만 추가해주어야 한다. 그래서 델타 값을 dx = [0, 0, -1, 1, -1, -1, 1, 1] dy = [-1, 1, 0, 0, -1, 1, -1, 1] 로 주었다. 계속 list out of ran..

문제 링크 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 파이썬 델타 값 이용하기 dx = [0,0,-1,1] dy = [-1,1,0,0] for i in range(4): pointX = x + dx[i] pointY = y + dy[i] => i = 0 pointX = x , pointY = y - 1 : 왼쪽 노드 i = 1 pointX = x , pointY = y + 1 : 오른쪽 노드 i = 2 pointX = x - 1 , poin..