본문 바로가기

ALGORITHM78

[BOJ/PYTHON] gold5-7576. 토마토 백준 문제 링크: https://www.acmicpc.net/problem/7576 문제 요약 토마토가 모두 익는 데 걸리는 최소 일수 (익은 토마토와 인접하면 1일 후 익음) 토마토의 상태: 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸 핵심 아이디어 바이러스를 감염시키는 것과 같은 bfs 문제이다. 익은 토마토가 감염원이므로 값이 1(처음부터 익은 토마토)인 좌표를 큐에 넣고 시작한다. bfs를 돌면서 익지 않은 토마토를 발견하면 큐에 넣어주고 값을 1 더해준다. 이때, 새로 방문한 익지 않은 토마토 자리에 그 값을 그대로 1 더해주는 게 아니라 감염시키는 좌표의 값에서 1을 더해줘야 한다. (array[nx][ny] += 1이 아니라 array[nx].. 2023. 9. 10.
[BOJ/PYTHON] 1865. 웜홀 백준 문제 링크: https://www.acmicpc.net/problem/1865 문제 요약 한 지점에서 출발해 시간여행 후 다시 출발 위치로 돌아왔을 때 출발 때보다 시간이 되돌아간 경우가 가능한지 벨만포드 안 if문에서 distance[node] != INF 조건도 넣어줬었는데 그거땜에 틀림 핵심 아이디어 ‘시간 여행’ 특성 상 과거로 돌아올 수 있으니 시간이 음수가 될 수 있다는 것을 파악하고, 음수 가중치도 가능한 벨만포드 알고리즘을 사용하면 된다. 풀이 # gold3-1865. 웜홀 import sys input = sys.stdin.readline def bellmanford(start): distance[start] = 0 for i in range(n): for node, next_nod.. 2023. 9. 3.
[BOJ/PYTHON] silver2 특정 거리의 도시 찾기 백준 문제 링크: https://www.acmicpc.net/problem/18352 문제 요약 도시 방향 그래프 (가중치 없음) 특정 도시 X에서 출발해 도달할 수 있는 모든 도시 중 최단 거리가 정확히 K인 모든 도시의 번호 출력 핵심 아이디어 bfs 문제이다. 방문한 적 없는 노드이면 방문 처리를 해주고, 이전 거리에서 1을 더해주는 식으로 갱신해주면 된다. distance 갱신을 다 끝내고 거리가 k인 걸 발견하면 출력한 후 has_city라는 플래그 변수를 true로 만들어준다. 그리고 for문을 다 돌았는데도 플래그가 false이면 최단 거리가 정확히 K인 도시가 없는 거니 -1을 출력한다. 풀이 # silver2-18352. 특정 거리의 도시 찾기 import sys from collecti.. 2023. 8. 27.
[BOJ/PYTHON] 20412. 추첨상 사수 대작전! (Hard) 백준 문제 링크: https://www.acmicpc.net/problem/20412 문제 요약 난수생성기에서 준표가 비밀리에서 설정한 정수 a, c를 출력 핵심 아이디어 X1 = (a × Seed + c) % m X2 = (a × X1 + c) % m ... Xn + 1 = (a × Xn + c) % m a × (Seed - X1) 은 X1 - X2와 m으로 나눴을 경우의 나머지가 동일 a × (Seed - X1) ≡ X1 - X2 (mod m) a × (Seed - X1)(m - 1) ≡ (X1 - X2) × (Seed - X1)(m - 2) (mod m) a**(m-1) ≡ 1 (mod m) 인 페르마 소정리에 의해 a × 1 ≡ (X1 - X2) × (Seed - X1)**(m - 2) (mod .. 2023. 8. 17.
[BOJ/PYTHON] 14565. 역원(Inverse) 구하기 백준 문제 링크: https://www.acmicpc.net/problem/14565 문제 요약 정수 N, A가 주어졌을 때 Zn에서의 A의 덧셈역과 곱셈역을 구하기 덧셈역: (a+b) mod n = 0일 경우의 b는 a의 덧셈역 곱셈역: (a*c) mod n = 1이면 c는 a의 곱셈역 핵심 아이디어 덧셈역: b = -a % n 곱셈역: a * c = nx + 1 곱셈역: ac - nx = 1 => ax0 - ny0 = 1 확장 유클리드 호제법을 이용한 풀이이다. 풀이 # gold2-14565. 역원(Inverse) 구하기 import sys input = sys.stdin.readline n, a = map(int, input().split()) def solve(): x0, y0, value0 = .. 2023. 8. 17.
[BOJ/PYTHON] 11689. GCD(n, k) = 1 백준 문제 링크: https://www.acmicpc.net/problem/11689 문제 요약 자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하기 핵심 아이디어 오일러 피 함수를 쓰면 된다. 오일러 피 함수란 n이하의 서로소 개수를 구할 때 사용하는 함수이다. n을 구성하는 소인수인 p들에 대해, n에 (1 - 1/p)를 곱하면 된다. 60의 경우 소인수분해하면 2^235라서, 2, 3, 5가 p이다. 오일러피 함수를 이용해 60 이하의 이하의 서로소 개수를 구하면, 60 * 1/2 * 2/3 * 4/5 = 16이다. 풀이 # gold1-11689. GCD(n, k) = 1 import sys, math input = sys.stdin.readlin.. 2023. 8. 17.

티스토리툴바