본문 바로가기
728x90
반응형

Algorithm & Data Structure

Algorithm & Data Structure 2023. 10. 13. 삼성SW 역량 기출 - 싸움땅(2022 하반기 오후 1번) https://www.codetree.ai/training-field/frequent-problems/problems/battle-ground/description?page=1&pageSize=20 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai n,m,k = map(int,input().split()) player = [] #x위치[0], y위치[1], 방향[2], 초기 능력치[3], 총[4]] arr = [[[0] for _ in range(n)] for _ in range(n)] # 하나의 칸에는 여러개의 총이 있을 수 있다. for i in r..
삼성 SW 역량평가 정리 보호되어 있는 글입니다.
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 ..
728x90
반응형

티스토리툴바