728x90 파이썬170 [BOJ/Python] 2688. 줄어들지 않아 📌 문제 https://www.acmicpc.net/problem/2688 2688번: 줄어들지 않아 첫째 줄에 테스트 케이스의 개수 T(1 2021. 10. 28. [BOJ/Python] 20057. 마법사 상어와 토네이도 📌 문제 https://www.acmicpc.net/problem/20057 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net 📌 문제 접근 방법 우선 토네이도가 이동하는 부분 먼저 구현해줬다. 출발은 (N//2, N//2)에서 한다. 왼쪽 -> 아래 -> 오른쪽 -> 위 의 방향 순서대로 움직이기 때문에 이에 맞춰 델타 행렬을 만들어준다. 1칸씩 2번, 2칸씩 2번, 3칸씩 2번 ... 이런식으로 이동하길래 cnt를 2로 초기화 한 후 2번 이동이 끝나면 값이 변경되도록 cnt를.. 2021. 10. 28. [BOJ/Python] 4948. 베르트랑 공준 📌 문제 https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 📌 문제 접근 방법 is_prime이라는 배열을 만들고, 2부터 n의 제곱근까지를 탐색하며 소수의 배수를 모두 False로 바꿔준다. n부터 2n까지 반복하여 해당 숫자가 소수라면 cnt를 1 더해준다. n에 0이 입력되면 반복문을 종료한다. 📌 코드 # 백준 4948 베르트랑 공준 import sys input = sys.stdin.readline def is_prime_numb.. 2021. 10. 21. [Algorithm] 다익스트라(dijkstra) 알고리즘 최단 경로 알고리즘 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로 하나의 시작 정점에서 끝 정점까지 최단 경로 다익스트라 알고리즘 : 음의 가중치 허용x 벨만-포드 알고리즘 : 음의 가중치 허용 모든 정점들에 대한 최단 경로 플로이드 워샬 알고리즘 다익스트라(dijkstra) 알고리즘 시작 정점에서 거리가 최소인 정점을 선택해나가면서 최단 경로 구함 탐욕 기법 사용, MST의 프림 알고리즘과 유사 def dijkstra(start): distance[start] = 0 # 노드의 개수만큼 반복 for _ in range(N+1): min_idx = -1 min_value = float('inf') for i in range(N+1): if not visit.. 2021. 10. 21. 이전 1 ··· 13 14 15 16 17 18 19 ··· 43 다음 728x90