Python_알고리즘
-
14284. [Python]간선 이어가기 2Python_알고리즘/Gold V 2024. 5. 8. 20:49
1. 문제 https://www.acmicpc.net/problem/14284 2. 접근 방법 시간 제한: 2초메모리 제한: 512MB다익스트라 알고리즘 3. 파이썬 코드 import sysimport heapqinput = sys.stdin.readline# 다익스트라 알고리즘def dijkstra(start): # q 초기화 q = [] # heapq 로 q 리스트 생성 heapq.heappush(q,(0,start)) # distance로 초기 시작점 0 으로 초기화 distance[start] = 0 # q 값이 존재할 경우 반복문 진행 while q: # 거리, 현재 값으로 값을 뽑아냄 dist, now = heapq.heapp..
-
7569. [Python]토마토Python_알고리즘/Gold V 2024. 4. 25. 01:47
1. 문제 https://www.acmicpc.net/problem/7569 7569번: 토마토첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100,www.acmicpc.net 2. 접근 방법 시간 제한: 1초메모리 제한: 256MB그래프 탐색 3. 파이썬 코드 import sysfrom collections import dequeinput = sys.stdin.readlineN, M, H = map(int,input().split())tomato = [ list(map(int,input().split())) for _ in range(M*..
-
1932. [Python]정수 삼각형Python_알고리즘/Silver I 2024. 4. 22. 19:47
1. 문제 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 2. 접근 방법 시간 제한: 2초 메모리 제한: 128MB DP(다이나믹 프로그래밍) 3. 파이썬 코드 import sys # 많은 인풋 처리 input = sys.stdin.readline N = int(input()) # 숫자 저장할 리스트 num_list = [] # 숫자 저장 for _ in range(N): num_list.append(list(map(int,input().split()))) # 1 ~ N 까지 반복 for i in range(1,N..
-
7682. [Python]틱택토Python_알고리즘/Gold V 2024. 4. 17. 21:08
1. 문제 https://www.acmicpc.net/problem/7682 7682번: 틱택토 틱택토 게임은 두 명의 사람이 번갈아가며 말을 놓는 게임이다. 게임판은 3×3 격자판이며, 처음에는 비어 있다. 두 사람은 각각 X 또는 O 말을 번갈아가며 놓는데, 반드시 첫 번째 사람이 X를 놓고 www.acmicpc.net 2. 접근 방법 시간 제한: 1초 메모리 제한: 128MB 구현 3. 파이썬 코드 while True: game = input() if game == "end": break game = list(map(str,game)) circle = game.count("O") cross = game.count("X") dot = game.count(".") if circle > cross: pr..
-
1456. [Python]거의 소수Python_알고리즘/Gold V 2024. 4. 14. 20:16
1. 문제 https://www.acmicpc.net/problem/1456 1456번: 거의 소수 어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다. 두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다. www.acmicpc.net 2. 접근 방법 시간 제한: 2초 메모리 제한: 256MB 에라토스테네스의 체 3. 파이썬 코드 # 에라토스 테네스의 체를 end 범위까지 시행 def prime_check(end): prime_list = [False, False] + [True]*end for i in range(2,int(end**.5)+1): if prime_list[i]: for j in range(i*2,end+1,i)..
-
1141. [Python] 접두사Python_알고리즘/Silver I 2024. 4. 9. 21:12
1. 문제 https://www.acmicpc.net/problem/1141 1141번: 접두사 접두사X 집합이란 집합의 어떤 한 단어가, 다른 단어의 접두어가 되지 않는 집합이다. 예를 들어, {hello}, {hello, goodbye, giant, hi}, 비어있는 집합은 모두 접두사X 집합이다. 하지만, {hello, hell}, {giant, www.acmicpc.net 2. 접근 방법 시간 제한: 2초 메모리 제한: 128MB 정렬 그리디 알고리즘 3. 파이썬 코드 N = int(input()) # 단어 저장 word_list = [] # 단어 길이와 문자로 저장 for _ in range(N): word = input() word_list.append([len(word),word]) # 길이..
-
1253. [Python] 좋다Python_알고리즘/Gold IV 2024. 3. 13. 01:20
1. 문제 https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 2. 접근 방법 시간 제한: 2초 메모리 제한: 256MB 투 포인터 이분탐색 3. 파이썬 코드 N = int(input()) # 이분 탐색 num_list = list(map(int,input().split())) # 정렬 num_list.sort() cnt = 0 for i in range(N): # 시작 start = 0 # 끝 end = N-1 # 이분 탐색 진행 while start < end: # 시작 ..
-
1261. [Python]알고스팟Python_알고리즘/Gold IV 2024. 3. 6. 20:25
1. 문제 https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 2. 접근 방법 시간 제한: 1초 메모리 제한: 128MB 다익스트라 우선순위 큐 3. 파이썬 코드 import heapq N,M = map(int,input().split()) matrix = [ list(map(int,input())) for _ in range(M) ] # 방향배열 탐색 direction = [(0,-1), (-1,0), (0,1), (1,0)..
-
1916. [Python]최소비용 구하기Python_알고리즘/Gold V 2024. 3. 5. 01:02
1. 문제 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 2. 접근 방법 시간 제한: 0.5초 메모리 제한: 128MB 다익스트라 우선순위 큐 3. 파이썬 코드 import sys import heapq input = sys.stdin.readline N = int(input()) M = int(input()) matrix = [ [] for _ in range(N+1)] # 다익스트라 거리 distance ..
-
1753. [Python]최단경로Python_알고리즘/Gold IV 2024. 3. 3. 23:59
1. 문제 https://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 2. 접근 방법 시간 제한: 1초 메모리 제한: 256MB 다익스트라 3. 파이썬 코드 import sys import heapq input = sys.stdin.readline # 시작점을 기준으로 다익스트라 시작 def BFS(init): # queue 리스트 생성 queue = [] # 우선순위 큐 생성 heapq.heappush(queue,(..