몽상실현개발주의

[BOJ] 1654 / 랜선 자르기 / Python 파이썬 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 풀이 이분 탐색의 기본 문제이다. 첫 시도는 완전 탐색으로 접근하였지만 당연히 시간초과가 발생 하였다. 가장 기본적인 이분 탐색의 구조로 해결 하였다. import sys input = sys.stdin.readline K, N = map(int, input().split()) lines = [] for _ i..

[BOJ] 1967 / 트리의 지름 / Python 파이썬 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 풀이 전날 풀었던 [BOJ] 1167 / 트리의 지름 / Python 파이썬 문제와 같이 Tree 의 지름을 구하는 문제이다. 다시 복습하자면, Tree 의 지름 : 가장 먼 두 정점 사이의 거리 혹은 가장 먼 두 정점을 연결하는 경로 선형 시간내에 Tree 의 지름을 구하는 Algorithm 트리에서 임의의 정점 xx..

[BOJ] 1167 / 트리의 지름 / Python 파이썬 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 풀이 Tree 의 지름을 구하는 문제이다. 문제를 선형시간안에 풀기위해서는 Tree 의 지름과 구하는 알고리즘에 대한 사전 지식이 필요하였다. Tree 의 지름 : 가장 먼 두 정점 사이의 거리 혹은 가장 먼 두 정점을 연결하는 경로 선형 시간내에 Tree 의 지름을 구하는 Algorithm 트리에서 임의의 정점 xx를 잡..

[BOJ] 11725 / 트리의 부모 찾기 / Python 파이썬 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 각 node의 root를 찾는 문제이다. 최상단의 root 노드가 항상 1로 시작하기 때문에, 모든 edge 를 기록한뒤 1부터 Tree 를 내려가며 root 를 기록하였다. from collections import deque N = int(input()) graph = [[] for _ in range(N+1)] for _ in range(N-1): f, t = map(int, inpu..

[BOJ] 1991 / 트리 순회 / Python 파이썬 https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 www.acmicpc.net 풀이 트리 순회의 기본 문제이다. 전위 순회(pre-order): Root -> Left -> Right 중위 순회(in-order): Left -> Root -> Right 후위 순회(post-order): Left -> Right -> Root N = int(input()) tree = {} for _ in range(N): nod..

[BOJ] 2146 / 다리 만들기 / Python 파이썬 https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 풀이 주어진 이중배열에서 1로 이루어진 무리 사이의 최단 거리를 구하는 문제이다. 문제를 이해하였지만, 구현하는데에 많은 어려움이 있었다. BFS 를 이용하여 최단거리를 구하는 것과 문제를 풀기위한 환경 구성을 함께 고려해 주어야 한다. from collections import deque def setIsland(y, x, setN): glo..

[BOJ] 2178 / 미로 탐색 / Python 파이썬 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 풀이 경로탐색의 기본 문제이다. bfs 로 경로상의 이동 거리를 저장하며 경로를 진행하도록 하였다. from collections import deque N, M = map(int, input().split()) maps = [] for _ in range(N): maps.append(list(map(int, list(input())))) dq = deque() dq.ap..

[BOJ] 7576 / 토마토 / Python 파이썬 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 풀이 이차원 배열에서 주어진 시작점으로 부터 주어진 규칙을 시행하는 문제였다. 처음에는 각각의 시작점에서 시행하는 경우가 동시에 발생 하는 것을 고려하지 못하고, 독립적으로 시행하게 구현하였더니 시간초과가 발생하였다. BFS 로 각각의 시작점을 같은 단계에서 동시에 수행되도록 구현하였더니 통과하였다. from collection..