목록알고리즘 (70)
개발자 블로그
문제 설명 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 나의 풀이 from collections import deque def bfs(graph, start_node): if graph[start_node[0]][start_node[1]] == "0": return False visited = [] q = deque() q.append(start_node) visited.append(start_node) graph[start_node[0]][start_node[1]] = "0" dx = [-1, 1, 0, ..
문제 설명 더보기 추석 트래픽 이번 추석에도 시스템 장애가 없는 명절을 보내고 싶은 어피치는 서버를 증설해야 할지 고민이다. 장애 대비용 서버 증설 여부를 결정하기 위해 작년 추석 기간인 9월 15일 로그 데이터를 분석한 후 초당 최대 처리량을 계산해보기로 했다. 초당 최대 처리량은 요청의 응답 완료 여부에 관계없이 임의 시간부터 1초(=1,000밀리초)간 처리하는 요청의 최대 개수를 의미한다. 입력 형식 solution 함수에 전달되는 lines 배열은 N(1 ≦ N ≦ 2,000)개의 로그 문자열로 되어 있으며, 각 로그 문자열마다 요청에 대한 응답완료시간 S와 처리시간 T가 공백으로 구분되어 있다. 응답완료시간 S는 작년 추석인 2016년 9월 15일만 포함하여 고정 길이 2016-09-15 hh:..
흔히 우리가 탐색을 할 때, 모든 배열을 확인하는 방법을 지양한다. 예를 들어 100까지 수 중에서 하나를 골라 up/down 게임을 한다고 하자. 우리는 보통 중간부터 수를 불러 좁혀나가는 식으로 하는 것이 빠르다는 것을 알고 있다. 따라서 모든 배열을 탐색하는 배열의 길이만큼의 시간 복잡도 대신 log2n의 시간복잡도를 갖을 수 있다. 이를 코드로 구현해보자! # 이진 탐색 - 정렬이 되어있는 배열에서 가능 finding_target = 14 finding_numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16] def is_existing_target_number_binary(target, array): current_min_idx = 0..
문제 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 나의 풀이(시간 초과) s = input() n = int(input()) s_list = list(s) cur = len(s_list) for _ in range(n): user_commend = input() if user_commend[0] == 'L' and cur != 0: cur -= 1 if user_commend[0] == 'D' and cur != len(s_list): cur += 1 if user_commend[0] == 'B' and c..
문제 보기 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 나의 풀이 - 병합정렬 O(nlogn) # 정렬이 된 두 배열을 합치면서 정렬시키는 함수 def merge(array1, array2): result = [] array1_index = 0 array2_index = 0 while array1_index < len(array1) and array2_index < len(array2): if array1[array1_index] < array2[array2_index]: result.appen..
문제 보기 10610번: 30 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한 www.acmicpc.net 나의 풀이 n = list(input()) n.sort(reverse=True) if int(n[-1]): print(-1) else: s = sum([int(n[i]) for i in range(len(n))]) if s % 3: print(-1) else: print(''.join(n)) 3의 배수의 특징을 알면 풀이가 쉽다... 각 자리 수의 합이 3의 배수이라는 특징을 활용하자. 1) 그 중 가장 큰 수를 구하기 위해 정렬 메소드를 사용. 2) 문..
문제 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 나의 풀이 # 투포인터 한개는 left 나의 위치, right는 나보다 작은 노드의 위치 # right 노드와의 거리까지 주유를 한다. # right가 left의 가격을 비교하고 더 작은 값이 나올 때 까지 이동 n = int(input()) distance_lst = list(map(int, input().split())) price_lst = list(map(int, input().split())) answer = 0 left = 0 rig..
문제 링크 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 나의 풀이 n = int(input()) meeting_times = [tuple(map(int, input().split())) for _ in range(n)] meeting_times.sort(key=lambda x: (x[1], x[0])) stack = [meeting_times[0]] for i in meeting_times[1:]: if i[0] >= stack[-1][1]: stack.append(i) print(len(stack)) 1) 입력값을 튜플형태로 리스트로 받는다. 2) 우선순위 정렬을 끝나는 시간 -> 시작하는 시간 순으로 정렬 * 정렬을 ..
문제 설명 더보기 선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다. 예를 들어 선행 스킬 순서가 스파크 → 라이트닝 볼트 → 썬더일때, 썬더를 배우려면 먼저 라이트닝 볼트를 배워야 하고, 라이트닝 볼트를 배우려면 먼저 스파크를 배워야 합니다. 위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관없이 배울 수 있습니다. 따라서 스파크 → 힐링 → 라이트닝 볼트 → 썬더와 같은 스킬트리는 가능하지만, 썬더 → 스파크나 라이트닝 볼트 → 스파크 → 힐링 → 썬더와 같은 스킬트리는 불가능합니다. 선행 스킬 순서 skill과 유저들이 만든 스킬트리1를 담은 배열 skill_trees가 매개변수로 주어질 때, 가능한 스킬트리 개수를 return 하는 solution 함수를 작성해주세요. 제한..
문제 설명 더보기 후보키 프렌즈대학교 컴퓨터공학과 조교인 제이지는 네오 학과장님의 지시로, 학생들의 인적사항을 정리하는 업무를 담당하게 되었다. 그의 학부 시절 프로그래밍 경험을 되살려, 모든 인적사항을 데이터베이스에 넣기로 하였고, 이를 위해 정리를 하던 중에 후보키(Candidate Key)에 대한 고민이 필요하게 되었다. 후보키에 대한 내용이 잘 기억나지 않던 제이지는, 정확한 내용을 파악하기 위해 데이터베이스 관련 서적을 확인하여 아래와 같은 내용을 확인하였다. 관계 데이터베이스에서 릴레이션(Relation)의 튜플(Tuple)을 유일하게 식별할 수 있는 속성(Attribute) 또는 속성의 집합 중, 다음 두 성질을 만족하는 것을 후보 키(Candidate Key)라고 한다. 유일성(unique..