본문 바로가기

Programming/Softeer

(26)

[Softeer][level3] 염기서열 커버 (python) https://softeer.ai/practice/info.do?idx=1&eid=1526 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 문제 풀이 해설영상 https://www.youtube.com/watch?v=wgw6i6jGc0A 다이나믹 프로그래밍 코드 import sys N, M = map(int, input().split()) dna = [list(input()) for _ in range(N)] superDNA = [None for _ in range(2 ** N)] superDNA[0] = ['.'] * M def merge(dna1, dna2) : dna = [] if dna1 == [] or dna2 == [] : return [] dna = [] ..

[Softeer][level3] 출퇴근길 (python) https://softeer.ai/practice/info.do?idx=1&eid=1529 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 문제 풀이 역방향 간선 그래프를 이용. 역방향 간선 그래프에서 T가 어떤 정점에 도달할 수 있다는 것은 정방향에서 해당 정점이 T에 도달할 수 있음을 활용. 아래는 오답 수가 많아 처음에 0점 나온 코드. 어떤 부분이 틀렸는지 지적해주시면 감사하겠습니다... import sys from collections import deque n, m = map(int, input().split()) adj = [[] for _ in range(n + 1)] adj_reverse = [[] for _ in range(n + 1)] for _ i..

[Softeer][level3] 자동차 테스트 (python) https://softeer.ai/practice/info.do?idx=1&eid=1717 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 문제 풀이 binary search 문제. python에는 bisect 라이브러리 활용 가능. bisect_left()를 통해 중간값이 들어갈 왼쪽 위치의 index를 찾고 중간값보다 작은 것들 중(중간값 기준 왼쪽) 하나, 중간값보다 큰 것들 중(중간값 기준 오른쪽) 하나 고르는 경우의 수를 찾아야함 -> 중간값 기준 왼쪽에 있는 수의 갯수 * 중간값 기준 오른쪽에 있는 수의 갯수 = 총 경우의 수 EX) 입력예제 1에서 연비를 정렬하면 [1,2,3,5,6]인데, 중간값이 3인 경우 bisect_left의 출력값은 2가 되고 [1..

[Softeer][level3] 순서대로 방문하기 (python) https://softeer.ai/practice/info.do?idx=1&eid=2050 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 문제 풀이 재귀적으로 DFS 활용 문제. 코드 import sys n, m = map(int, input().split()) Map = [list(map(int, input().split())) for _ in range(n)] points = [] for _ in range(m) : r, c = map(int, input().split()) points.append([r - 1, c - 1]) visited = [[0] * n for _ in range(n)] def DFS(loc, cnt) : global ans if loc =..

[Softeer][level3] 로봇이 지나간 경로 (python) https://softeer.ai/practice/info.do?idx=1&eid=577 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 문제 풀이 bfs로 풀이. 처음 시작점을 찾을 때, '#'인 경우를 찾고 주변에 '#'이 유일한 경우(이동할 수 있는 곳이 정해진 경우) 시작점으로 판단. 마지막에 경로 추가할 때, 이 전에 같은게 나왔는지 여부에 따라 flag로 구별하여 R, L이 추가될 수 있도록 설정. 코드 import sys from pprint import pprint from collections import deque H, W = map(int, input().split()) map = [list(sys.stdin.readline().rstrip()) f..

[Softeer][level3] 안전운전을 도와줄 차세대 지능형 교통시스템 (python) https://softeer.ai/practice/info.do?idx=1&eid=580 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 문제 풀이 BFS문제. 사전에 정의된 교차로 정보 저장하고 하나씩 방문해서 갯수 count 처음에 20점이 나오는데 틀린 부분을 찾느라 오래 걸림. 방문했던 곳이어도 다시 방문해도 괜찮았음 import sys from collections import deque from pprint import pprint N, T = map(int, input().split()) intersection = [[0] + [] for i in range(N + 1)] for i in range(1, N + 1) : for j in range(1, N ..

[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..

이전 1 2 3 4 다음

티스토리툴바