본문 바로가기
728x90

TIL - 프로그래밍292

Python 최대공약수 / 최소공배수 import math import math a,b = map(int,input().split()) # 최대공약수 (Greatest Common Divisor) print(math.gcd(a,b)) # 최소공배수 (Lowest Common Multiple) print(math.lcm(a,b)) 유클리드 호제법 시간복잡도 O(logN) 2개의 자연수 a,b(a>b)에 대해서 a를 b로 나눈 나머지를 r0이라 하면 a와 b의 최대공약수 == b와 r0의 최대공약수 위 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 최대공약수 def gcd(a,b): while b>0: a,b = b, a%b return a def lcm(a,b): return (a*b)//gcd(a,b) 2022. 9. 22.
[백준] 16236. 아기 상어 - Python https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net from dis import dis from sys import stdin from collections import deque input = stdin.readline # 공간의 크기 N = int(input()) # 공간의 상태 space = [list(map(int,input().split())) for _ in range(N)] # 아기 상어 위치 찾기 def wherebaby(sp.. 2022. 8. 1.
[백준] 9934. 완전 이진 트리 https://www.acmicpc.net/problem/9934 9934번: 완전 이진 트리 상근이는 슬로베니아의 도시 Donji Andrijevci를 여행하고 있다. 이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다. 깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다. (아래 www.acmicpc.net from re import M from sys import stdin input = stdin.readline # 트리 깊이 K = int(input()) # 방문한 빌딩의 번호 building = list(map(int,input().split())) tree = [[] for _ in range(K)] def Maketree(arr,level): # 중위 순회니 arr.. 2022. 8. 1.
[백준] 1991. 트리 순회 - Python https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net from sys import stdin from collections import deque input = stdin.readline # 전위 순회, 중위 순회, 후위 순회 결과 출력 # 노드의 개수 N = int(input()) # 연결 노드 node = [[] for _ in range(N+1)] # 부모 노드 번호 parent = [0 for _ in range(N+1)] for .. 2022. 8. 1.
[백준] 11403. 경로 찾기 - Python https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net from sys import stdin input = stdin.readline # 정점의 개수 N = int(input()) # 인접 행렬 adj = [list(map(int,input().split())) for _ in range(N)] # a -> b and b -> c == a -> c for b in range(N): for a in range(N): for c in range(N): if adj[a][b] and adj[b][.. 2022. 7. 22.
[백준] 5014. 스타트링크 - Python https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 생각 최단 경로를 구하는 것이므로 bfs 코드 from sys import stdin from collections import deque input = stdin.readline F,S,G,U,D = map(int,input().split()) # 총 F층인 건물, S층에서 G층 가기 # 방문 표시 visited = [0]*(F+1) def bfs(now): global visited visited[now].. 2022. 7. 13.
반응형

티스토리툴바