[elice] 인공지능 R&D 실무자 양성과정 - 프로그래밍 테스트 문제

날짜:

1. 가장 가까운 제곱근 구하기

본 문제에서는 n이 주어질 때, q^2 \geq n 을 만족하는 최소의 q를 구하는 문제입니다.
가장 간단하게는 q를 1부터 모두 테스트 해보면 문제를 해결할 수 있으며, 이는 최대 n번 테스트를 해 보아야 합니다. 때문에 n이 매우 클 경우에는 시간이 오래 걸릴 수 있습니다.
본 문제에서는 n이 매우 클 경우에도 빠르게 결과를 구할 수 있도록 이진탐색(binary search)를 이용하여 문제를 해결해 보고자 합니다.



입력

첫 번째 줄에 정수 n이 주어집니다. ( 1 \leq n \leq1,000,000,000,000,000 )

출력

q^2 \geq n 를 만족하는 최소의 q를 출력합니다.

입력 예시 1

5

출력 예시 1

3

입력 예시 2

11298419211

출력 예시 2

106295



 @@@문제풀이@@@


import elice_utils


def binary_search(lst, cond):
    '''
    (Optional) 이 함수를 반드시 구현할 필요는 없습니다. 즉, 이 함수는 채점에 포함되지 않습니다. 
    이진탐색을 활용하여 lst 내에서 cond 조건을 만족하는 최소의 원소를 반환하는 함수를 작성하세요.
    lst 는 오름차순으로 정렬되어있다고 가정해도 좋습니다. 
    
    ex) binary_search([1,2,3,4,5], lambda x: x>1) returns 2
    '''
    
    
def find_min_square_root(n):
    '''
    q^2 >= n 을 만족하는 최소의 q를 반환하는 함수를 작성하세요.
    경우에 따라 위에 제시되어 있는 binary_search 함수를 작성하여 사용하여도 좋습니다.
    '''
    
    #l = list(range(n))
    low, high = 1, n
    
    while low <= high:
        mid = int((low + high) / 2)
        
        if mid**2 >= n:
        
            if (mid-1)**2 < n:
                return mid
                
            high = mid-1
            
        else:
            low = mid+1
        
        
def main():
    '''
    Do not change this code
    '''
    n = int(input())
    print(find_min_square_root(n))

if __name__ == "__main__":
    main()

2. 최소 강의실 구하기

스타 강사인 현규씨는 드디어 대치동에 알고리즘 학원을 차렸습니다. 학원 원장이 된 현규씨는 N개의 강의를 최대한 적은 수의 강의실을 사용하여 운영하고 싶습니다.
한 강의실에서 동시에 2개 이상의 강의가 이루어질 수 없지만, 동작이 빠른 강사님들 덕분에 한 강의가 끝나면 바로 이어서 다음 강의가 진행될 수 있습니다.
필요한 최소 강의실의 수를 출력하는 프로그램을 작성하세요.

힌트

강의 시작시간과 종료시간을 따로 정렬해 봅시다.
가장 이른 강의 종료시간은 8인데 시작시간이 12인 강의부터 8에 끝나는 이 강의실을 이어 받을 수 있습니다.
시작시간이 15, 20인 강의도 마찬가지로 종료시간이 13, 14인 강의실 각각을 이어 받아 시작할 수 있습니다. 즉, 거꾸로 말하면 시작시간이 2, 3, 6, 6, 7인 강의들은 이어 받을 강의실이 없기 때문에 새로운 강의실을 배정 받아야만 합니다.

입력

첫줄에는 전체 강의 개수, N (1<=N<=100,000)이 주어지며, 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 세 개의 정수, 강의 번호, 강의 시작시간, 강의 종료시간이 주어집니다.
강의 시간은 모두 0 이상 10억 이하의 정수로 나타냅니다.

출력

첫째 줄에 필요한 최소 강의실의 개수를 출력합니다. (제한 시간은 2초입니다.)

입력 예시

8  
6 15 21  
7 20 25  
1 3 8  
3 2 14  
8 6 27  
2 7 13  
4 12 18  
5 6 20

출력 예시

5



@@@문제풀이@@@


import sys


def find_min_room(num_class, classes):
    # 구현해주세요!
    l = []
    for i in classes:
        l.append((i[0], i[1]))
        l.append((i[0], i[2]))
    l.sort(key=lambda x: x[1])

    current = [False] * 100001
    class_num = 0
    min_rooms = 0
    for i in range(len(l)):
        x = l[i][0]
        if (not current[x]):
            current[x] = True
            class_num += 1
        else:
            current[x] = False
            class_num -= 1
        if (i != len(l) - 1):
            if (l[i][1] < l[i + 1][1]):
                min_rooms = max(min_rooms, class_num)
    return min_rooms


def read_inputs():
    num_class = int(input())
    classes = []
    for i in range(num_class):
        line = [int(x) for x in input().split()]
        class_no = line[0]
        start = line[1]
        end = line[2]
        classes.append((class_no, start, end))

    return num_class, classes  # num_class=강의실번호 , classes=리스트 넣어져있는거


def main():
    num_class, classes = read_inputs()
    ans = find_min_room(num_class, classes)
    print(ans)


if __name__ == "__main__":
    main()

댓글

댓글 쓰기