Python_알고리즘/Gold V
-
10026. [Python]적록색약Python_알고리즘/Gold V 2024. 6. 28. 12:51
1. 문제 https://www.acmicpc.net/problem/10026 2. 접근 방법 시간 제한: 1초메모리 제한: 128MB깊이 우선 탐색 3. 파이썬 코드 def DFS(start, flag): # DFS 진행 global count stack = [start] # 초기값 선언 visited[start[0]][start[1]] = True while stack: y,x = stack.pop() # 방향 배열 탐색 for k in range(4): ny = y + direction[k][0] nx = x + direction[k][1] # 범위내 존재 시 ..
-
5972. [Python]택배 배송Python_알고리즘/Gold V 2024. 6. 20. 18:50
1. 문제 https://www.acmicpc.net/problem/5972 2. 접근 방법 시간 제한: 1초메모리 제한: 128MB다익스트라 3. 파이썬 코드 import sysimport heapq# 다익스트라 알고리즘def dijkstra(start): # 항상 초기 거리 0 선언 및 시작 위치!!! 중요 distance[start] = 0 queue = [(0,1)] # 우선순위 큐를 통해서 구현 while queue: # 현재 비용과 노드 pop cost, now = heapq.heappop(queue) # 현재 거리에 cost 값과 노드에 cost 값이 더 큰 경우 반복문 마저 진행 if cost > distance..
-
9251. [Python]LCSPython_알고리즘/Gold V 2024. 6. 16. 15:14
1. 문제 https://www.acmicpc.net/problem/9251 2. 접근 방법 시간 제한: 0.1초메모리 제한: 256MB다이나믹 프로그래밍 3. 파이썬 코드 from pprint import pprint as printword_one = input()word_two = input()# 처음 단어의 길이one_length = len(word_one)# 두번째 단어의 길이two_length = len(word_two)# LCS 적용할 리스트LCS_matrix = [ [0]*(one_length+1) for _ in range(two_length+1)]# 최대값 체크할 변수max_value = 0# 처음단어 반복문for i in range(one_length+1): # 두번째 단어 반복..
-
12865. [Python]평범한 배낭Python_알고리즘/Gold V 2024. 6. 5. 01:27
1. 문제 https://www.acmicpc.net/problem/12865 2. 접근 방법 시간 제한: 2초메모리 제한: 512MBDP(다이나믹 프로그래밍) 3. 파이썬 코드 import sysinput = sys.stdin.readlineN, K = map(int,input().split())# 가방bag = []# weight, value 값 가방에 저장for _ in range(N): weight, value = map(int,input().split()) bag.append((weight,value))# dp 값을 K(무게) +1 만큼 생성dp = [0] * 100001# N개의 물건 개수만큼 반복for i in range(N): # weight, value 값 분해 w..
-
13549. [Python]숨바꼭질 3Python_알고리즘/Gold V 2024. 5. 22. 13:54
1. 문제 https://www.acmicpc.net/problem/13549 2. 접근 방법 시간 제한: 2초메모리 제한: 512MB다익스트라 3. 파이썬 코드 import heapq# 다익스트라def dijkstra(start): queue = [] # 우선순위 큐 heapq.heappush(queue, (0,start)) while queue: # 시간, 위치 time, now = heapq.heappop(queue) # +1 한 값, -1 한 값, *2 한 값 next_add = now+1 next_min = now-1 next_multi = now*2 # +1 한 값이 100000 이하..
-
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*..
-
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)..
-
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 ..