본문 바로가기
728x90

알고리즘316

[python] 백준 1525 퍼즐 https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 문제 해결 표에 숫자를 넣고 빈 곳(0)을 이용해 이동하는 문제 이동 방법은 동서남북이므로 move =[(-1,0), (1,0), (0,-1), (0,1)] 4가지가 있다. 위의 조건과 최소 이동 번수를 구하는 것이므로 아무래도 bfs가 좋다. 그런데 어떻게 풀어야하지?? (ㅜㅜ) 답은 리스트가 아니라 문자열 이용! 1 2 3 4 5 6 7 8 9 위 표는 "123456789" 문자열로 변환 시킬 수 있다! 그리고 n 위치는 (n//3, n%3) 으로 좌표를 만들 수 있다... 2023. 2. 28.
[python] 백준 18352 특정 거리의 도시 찾기 https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 문제 해결 특정 지점까지 가는데 최소 거리가 k인 점을 찾는 문제 (DFS,BFS 다 되지만 거리가 정해져있으므로 BFS로 너비로 찾는 것이 좋다!) 양방향 도로가 아니라는 것에 주의하자! CODE import sys from collections import deque input = sys.stdin.readline n, .. 2023. 2. 26.
[python] 백준 1033 칵테일 https://www.acmicpc.net/problem/1033 1033번: 칵테일 august14는 세상에서 가장 맛있는 칵테일이다. 이 칵테일을 만드는 정확한 방법은 아직 세상에 공개되지 않았지만, 들어가는 재료 N개는 공개되어 있다. 경근이는 인터넷 검색을 통해서 재료 쌍 N www.acmicpc.net 문제 해결 최소공배수를 이용해서 상대가격 비교 두 수(p,q)의 최소 공배수는 p*q//gcd(p,q) 이다. 상대 가격을 구한다음(P(2) =$\frac{P(1)}{i[1]} \times i[2] $) (i[1], i[2]는 1과 2의 상대 가격 비율) 모든 수의 최대공약수로 나누어서 출력한다. CODE n = int(input()) A = [[] for _ in range(n)] visited.. 2023. 2. 24.
[python] 백준 1850 최대공약수 import sys input = sys.stdin.readline a, b= map(int, input().split()) def gcd(a,b): if b==0: return a return gcd(b, a%b) ans = gcd(a,b) while ans: print(1, end='') ans -= 1 2023. 2. 24.
728x90