본문 바로가기

Programming

(40)

[Softeer][level4] 지우는 소수를 좋아해 (python) https://softeer.ai/practice/info.do?idx=1&eid=582 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 문제 풀이 dijkstra 알고리즘 문제. 최소 거리 찾을 때 정렬하지 않고 시간 복잡도 줄이기 위해 heapq를 이용하여 방문하지 않은 노드 중 최단 거리 가장 짧은 노드 선택. [소수 확인] - 2부터 확인하려는 수 N의 중심값인 √N 까지 나누기를 반복하며 나눠떨어지지 않는지 확인 -> O(√N) 코드 import sys import heapq N, M = map(int,input().split()) node = [[] for i in range(N + 1)] # node 정보 담는 리스트 INF = int(1e9) dist =..

[Softeer][level3] 강의실 배정 (python) https://softeer.ai/practice/info.do?idx=1&eid=392 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 문제 풀이 처음에 단순히 시작 시간 순으로 정렬하니 시간 초과 발생 import sys N = int(input()) schedule = [] for _ in range(N) : schedule.append(list(map(int, input().split()))) schedule.sort(key=lambda x:x[0]) cnt = 0 start_time = 1 for start, end in schedule : if start >= start_time : cnt += 1 start_time = end print(cnt) heapq..

[Softeer][level3] GINI야 도와줘 (python) https://softeer.ai/practice/info.do?idx=1&eid=583 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 문제 풀이 오래 걸렸는데 변수명 때문이었다,,, 0 -> 1분인 경우 소나기 확산 업데이트를 안해주어 90점. BFS를 통해 하나씩 탐색하는 문제. 코드 import sys from collections import deque R, C = map(int, input().split()) map = [list(sys.stdin.readline().rstrip()) for _ in range(R)] visited = [[0] * C for _ in range(R)] # 상, 하, 좌, 우 dc = [0, 0, -1, 1] dr = [-1,..

[Softeer][level3] 스마트 물류 (python) https://softeer.ai/practice/info.do?idx=1&eid=414 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 문제 풀이 문제대로 간단히 구현함. 조건만 잘 맞추면 간단. 로봇인 경우 주변 K개 위치를 확인하고 부품이면 갯수를 count하고 해당 위치의 물품을 없애줌 코드 import sys N, K = map(int, input().split()) line = list(str(sys.stdin.readline())) cnt = 0 for i in range(N) : if line[i] == 'P' : # 로봇인 경우 for j in range(i - K, i + K + 1) : # 좌,우 주변 K개 확인 if j = N :..

[Softeer][level3] 동계 테스트 시점 예측 (python) https://softeer.ai/practice/info.do?idx=1&eid=411 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 문제 풀이 BFS를 사용하여 탐색 적어도 2번 이상 외부 공기와 접촉한 얼음을 고려해야하므로 얼음을 만났을 때 count해주고 2번 이상 count된 경우 얼음을 녹이는 것으로 해결. 얼음이 아닌데 방문하지 않았던 경우, 주변 탐색을 위해 queue에 추가 코드 import sys from collections import deque N, M = map(int, input().split()) grid = [list(map(int, sys.stdin.readline().split())) for _ in range(N)] def BFS(..

[Softeer][level3] 택배 마스터 광우 (python) https://softeer.ai/practice/info.do?idx=1&eid=581 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 문제 풀이 itertools의 permutations(순열)을 사용하여 가능한 모든 택배 레일의 경우를 저장. 가능한 모든 택배 레일의 경우 각각에 대해 box에 택배 바구니 무게를 넘지 않도록 순서대로 담고 시행 횟수(K) 대비 가장 적은 택배 무게 출력. 코드 import sys from itertools import permutations N, M, K = map(int, input().split()) rail_weights = list(map(int, sys.stdin.readline().split())) # 전체 가능한 순열..

[Softeer][level3] 우물 안 개구리 (python) https://softeer.ai/practice/info.do?idx=1&eid=394 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 문제 풀이 그냥 조건가지고 구현함. db를 1로 초기화해서(0번째 index제외) 직접 index에 해당하는 무게를 비교하여 작은 경우 0으로 변경 db에 저장된 관계들 중 1인 경우의 갯수 출력 코드 import sys N, M = map(int, input().split()) weights = [0] + list(map(int, sys.stdin.readline().split())) relations = [list(map(int,input().split())) for _ in range(M)] db = [0] + [1] * N f..

[Softeer][level3] 조립 라인 (python) https://softeer.ai/practice/info.do?idx=1&eid=403 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 문제 풀이 dynamic programming 문제. 초기 시간을 dp테이블 첫 번째 index에 저장하고, i-1까지 line A, B의 작업 시간을 구하고(i-1까지 line A, i-1까지 line B에 B->A 중 적은 시간) i번째 A, B의 작업 시간을 각각 더해서 dp에 저장. N-1번째 dp의 저장된 line A, B마다 걸리는 시간 중 적은 시간 출력 코드 import sys N = int(input()) # [A작업시간, B작업시간, A->B시간, B->A 시간] lines = [list(map(int, sys.st..

이전 1 2 3 4 5 다음

티스토리툴바