알고리즘16 백준 사다리 조작(Python) 문제 링크: www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 삼성 기출문제로 상당히 까다로운 문제입니다. 우선 사다리는 2차원 배열을 통해 만들 수 있습니다. input으로 n, m, h가 주어지는데 이때 사다리는 n과 h로 만들어야 하는 것에 주의해야 합니다. 이후 주어지는 가로선들은 2차원 배열에 1로 표시합니다. (예를 들어 1번째 줄 3과 4를 잇는 가로선은 graph[1][3]에만 1로 체크해두고 나중에 사다리를 내려오면서 왼쪽에도 가로선이 있는지.. 2021. 4. 6. 백준 차이를 최대로 (Python/Go) 문제 링크: www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net N의 범위가 8이하로 작기 때문에 모든 순열을 구해서 풀면 되는 문제입니다. 아래는 파이썬 코드입니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 import sys from itertools import permutations def get_num(nums): tot = 0 for i in range(1, len(nums)): tot += abs(nums[i-1] - .. 2021. 4. 5. 백준 게임개발 (Python/Go) 문제 링크: www.acmicpc.net/problem/1516 위상 정렬 문제입니다. 그런데 최소 시간을 알아내야 하기 때문에 위상정렬 + heap을 사용하여 풀어야 합니다. 아래는 파이썬 코드입니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 import heapq from collections import defaultdict n = int(input()) degree = [0] * (n+1) # degree[1] = 2 이라면 1번 건물을 짓기 위해 먼저 지어져야 하는 건물이 2개라는 뜻 time = [0] * (n+1) # 각 건물 짓는데 걸.. 2021. 4. 4. 백준 최단경로 (Python/Go) 문제 링크: www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 기본 다익스트라 문제입니다. 아래는 파이썬 코드입니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 from collections import defaultdict import heapq def dijkstra(start): dist = defaultdict(in.. 2021. 4. 3. 이전 1 2 3 4 다음