Python_알고리즘
-
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..
-
1105. [Python]팔Python_알고리즘/Silver I 2024. 6. 20. 17:44
1. 문제 https://www.acmicpc.net/problem/1105 2. 접근 방법 시간 제한: 2초메모리 제한: 512MB수학그리디 알고리즘 3. 파이썬 코드 L, R = map(str,input().split())# 인풋 값의 길이 측정L_length = len(L)R_length = len(R)# 각 인풋에서 들어온 값들에 8 이 있는지 체크하고 없으면 무조건 0 이 나오게 된다.# 또한 각각 길이를 비교하여 두 길이가 다른경우도 무조건 0이 나오게된다.if L.count("8") == 0 or R.count("8") == 0 or L_length != R_length: print(0)# 외의 경우else: # cnt 변수를 선언해주고 cnt = 0 # 길이가 같기 때..
-
9252. [Python]LCS 2Python_알고리즘/Gold IV 2024. 6. 20. 16:03
1. 문제 https://www.acmicpc.net/problem/9252 2. 접근 방법 시간 제한: 2초 (Python)메모리 제한: 256MBLCSDP 3. 파이썬 코드 # 재귀 제한 해제import syssys.setrecursionlimit(10000)# 재귀함수를 통해서 문자 찾기def backtracking(start, value): global max_value global ans global word_two # 최대 길이 도달했을때 종료 if value == 0: print(max_value) print(ans[::-1]) exit() # 현재 칸에서 위로 간 값과 왼쪽으로 간 값을 비교해서 작은 값찾는 재귀 ..
-
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 이하..
-
11052. [Python]카드 구매하기Python_알고리즘/Silver I 2024. 5. 20. 19:36
1. 문제 https://www.acmicpc.net/problem/11052 2. 접근 방법 시간 제한: 1초메모리 제한: 256MBDP(다이나믹 프로그래밍) 3. 파이썬 코드 # i 장을 구매하기 위한 최대값 계산 방법 접근N = int(input())# 카드 리스트 저장card_list = list(map(int,input().split()))# dp 시작dp = [0] * (N+1)# dp[1] 값 card_list[0] 으로 초기화dp[1] = card_list[0]# N+1 까지 반복문for i in range(2,N+1): # i 값까지 반복문 시행 for j in range(1,i+1): # i 번 dp 에는 i 번째 카드를 구매하기 위해서 최대 값을 갱신해야함 ..
-
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*..