본문 바로가기
728x90
반응형

알고리즘

Algorithm & Data Structure 2023. 3. 16. 프로그래머스 - 기능개발 https://school.programmers.co.kr/learn/courses/30/lessons/42586 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr from collections import deque def solution(progresses, speeds): answer = [] progresses = deque(progresses) speeds = deque(speeds) day = 0 tmp = 0 while progresses: p = progresses.popleft() s = speeds.popleft() for i in rang..
Algorithm & Data Structure 2022. 11. 28. 백준 - 16139번(누적합) https://www.acmicpc.net/problem/16139 16139번: 인간-컴퓨터 상호작용 첫 줄에 문자열 $S$가 주어진다. 문자열의 길이는 $200,000$자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 $q$가 주어지며, 문제의 수는 $1\leq q\leq 200,000$을 만족한다. 세 번째 www.acmicpc.net 50점 답안 import sys s = list(sys.stdin.readline().rstrip()) t = int(sys.stdin.readline()) for k in range(t): tmp = [0 for _ in range(len(s))] cache = 1 a,l,r = sys.stdin.readline().split() l = int(..
Algorithm & Data Structure 2022. 11. 2. 백준 - 11404번(플로이드) https://www.acmicpc.net/problem/11404 import sys n = int(sys.stdin.readline()) m = int(sys.stdin.readline()) arr = [[float('INF') for _ in range(n)] for _ in range(n)] bus = [] for i in range(n): arr[i][i] = 0 for _ in range(m): a,b,c = map(int,sys.stdin.readline().split()) if arr[a-1][b-1] > c: arr[a-1][b-1] = c for k in range(n): for i in range(n): for j in range(n): if arr[i][j] > arr[i][k] +..
플로이드 워셜(Floyd Warshall) 알고리즘
Algorithm & Data Structure 2022. 11. 2. 플로이드 워셜(Floyd Warshall) 알고리즘 로봇공학을 공부하다가 알고리즘 파트가 나와서 공부해볼 겸 정리를 해본다. pdf에는 단순히 DP를 이용한 최단거리 탐색 이라고 적혀 있지만, 사실상 플로이드 워셜 알고리즘을 설명하고 있다. 최단 거리를 찾는 알고리즘의 일종이다. "거쳐가는 정점을 기준으로 최단거리를 구하는 것" DP를 이용한다. 이러한 그래프의 방문의 최적 비용을 2차원 테이블로 표현해 보자. 이는 현재까지 계산된 최소비용이다. 2열 3행은 2-> 3으로 가는 현재까지 계산된 최소비용이고, 이는 9이다. 무한으로 표시된 것은 한 번의 이동으로는 갈 수 없는 즉, 필연적으로 다른 노드를 거쳐야 하는 경우이다.(만약 연결된 노드가 없는 경우 못 갈 수도 있다.) 예를 들어 1->3으로 가는 경우는 1 -> 4 -> 3을 거쳐서 비용 11, ..
Algorithm & Data Structure 2022. 8. 18. 백준 - 1956번(다익스트라) https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net import sys from heapq import heappush,heappop v,e = map(int,sys.stdin.readline().split()) arr = [[] for _ in range(v+1)] ans = [[float('inf') for _ in range(v + 1)] for _ in range(v+1)] q = [] for _ in ra..
Algorithm & Data Structure 2022. 8. 18. 백준 - 2573번(구현, 그래프) https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net import copy import sys from collections import deque # 조건에 따라 빙산이 녹는 것을 구현 여기서 주의점은 얼음은 동시에 녹기 때문에 # 옆에 있는 빙산이 녹아서 0이 되더라도 당장은 영향을 받지 않는다. def check(x,y): dx = [1,-1,0,0] dy = [0,0,1,-1] cnt = 0 for i in range(4): nx = x..
Algorithm & Data Structure 2022. 8. 18. 백준 - 1043번(그래프) https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net import sys from collections import deque def TrueOrFalse(ans): n, m = map(int, sys.stdin.readline().split()) known = deque(list(map(int, sys.stdin.readline().split()))) known.popleft() check = [False for _ in range(n + 1)] party ..
Algorithm & Data Structure 2022. 8. 17. 백준 - 1976번(유니온 파인드, 재귀) https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net import sys sys.setrecursionlimit(200000) def find(a): if a == arr[a]: return a x = find(arr[a]) arr[a] = x return arr[a] def union(a,b): a = find(a) b = find(b) if a == b: return arr[max(a,b)] = arr[min(a,b)] n = int(sys.st..
Algorithm & Data Structure 2022. 8. 16. 백준 - 1717번(유니온 파인드, 재귀, 집합) https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 문제 자체가 이해가 어렵지는 않은 문제다. 이 문제를 풀기 위해서는 유니온 파인드가 뭔지 알아야 한다. 그래프 풀이법의 일종으로 볼 수 있다. 노드들을 합치고(union), 부모를 찾아준다(find) 일련의 과정은 다음과 같다. 1. 원소 두 개를 입력받고 Union 함수를 호출한다. 2. 입력받은 원소의 부모를 find 함수를 이용해서 '재귀적으로' 찾아..
728x90
반응형

티스토리툴바