실습_3. 분할정복법

Updated: August 23, 2020

실습

가장 가까운 값 찾기

오름차순으로 정렬된 nn개의 숫자가 주어지고, 정수 mm이 주어질 때, nn개의 숫자 중에서 mm과 가장 가까운 숫자를 출력하는 프로그램을 작성하시오. 만약 가장 가까운 숫자가 2개 이상이라면, 그 중 가장 작은 숫자를 출력한다.

입력 예시 1

1 4 6 7 10 14 16
8

출력 예시 1

입력 예시 2

1 4 6 7 10 14 16
12

출력 예시 2

문제 조건

입력되는 수의 개수는 최대 100,000개입니다.
만약 가장 가까운 숫자가 2개 이상일 경우, 그 중 가장 작은 값을 출력합니다.

import sys

def ham(data, start, end, m):
    print(start, end)
    mid = (start+end) // 2
    if data[mid] == m:
        return m
    if end - start == 1:
        if m - data[start] == data[end] - m:
            return data[start]
        if m - data[start] > data[end] - m:
            return data[end]
        else:
            return data[start]
    if data[mid] > m:
        return ham(data, start, mid, m)
    if data[mid] < m:
        return ham(data, mid, end, m)
    
    
def getNearest(data, m) :
    '''
    n개의 숫자가 list로 주어지고, 숫자 m이 주어질 때, n개의 숫자 중에서 m과 가장 가까운 숫자를 반환하는 함수를 작성하세요.
    '''
    
    return ham(data,0,len(data)-1,m)

def main():
    '''
    이 부분은 수정하지 마세요.
    '''

    data = [int(x) for x in input().split()]
    m = int(input())

    print(getNearest(data, m))

if __name__ == "__main__":
    main()

거듭제곱 구하기

본 연습문제에서는 m^n을 구하는 프로그램을 작성합니다.

입력으로는 m, n이 차례대로 입력됩니다.

만약 getPower 함수의 반환 값이 1,000,000,007 보다 클 경우, 반환 값을 1,000,000,007로 나눈 나머지 값을 반환하세요.

입력 예시

3 4

출력 예시

문제 조건

0≤n≤1,000,000,000,000

LIMIT_NUMBER = 1000000007

def ham(m,n):
    if n == 0:
        return 1
        
    if n % 2 == 0:
        x = ham(m, n//2)
        return (x * x) % LIMIT_NUMBER
    if n % 2 == 1:
        x = ham(m, n//2)
        return (x * x * m) % LIMIT_NUMBER

def getPower(m, n):
    '''
    m^n 을 LIMIT_NUMBER로 나눈 나머지를 반환하는 함수를 작성하세요.
    '''
    return ham(m,n)%1000000007

def main():
    '''
    이 부분은 수정하지 마세요.
    '''

    myList = [int(v) for v in input().split()]

    print(getPower(myList[0], myList[1]))

if __name__ == "__main__":
    main()

합병정렬 구현

nn개의 숫자를 합병정렬을 이용하여 정렬하는 프로그램을 작성하세요.

입력 예시

1 5 6 2 3 8 4 9 7 10

출력 예시

1 2 3 4 5 6 7 8 9 10

문제 조건

입력되는 수의 새구는 최대 100000개입니다.

import sys

def ham(data, start, end):
    if end - start == 1:
        print(data[start:end])
        return data[start:end]
    
    mid = (end + start) // 2
    
    left = ham(data,start,mid)
    right = ham(data,mid,end)
    
    result = []
    
    left_cnt = 0
    right_cnt = 0
    
    while True:
        if left[left_cnt] <= right[right_cnt]:
            result.append(left[left_cnt])
            left_cnt += 1
            if left_cnt == len(left):
                result+=right[right_cnt:]
                break
        if left[left_cnt] > right[right_cnt]:
            result.append(right[right_cnt])
            right_cnt += 1
            if right_cnt == len(right):
                result+=left[left_cnt:]
                break
    return result
    
def mergeSort(data) :
    '''
    n개의 숫자를 합병정렬을 이용하여 정렬한 결과를 list로 반환하는 함수를 작성하세요.
    '''
    
    return ham(data, 0, len(data))

def main():
    '''
    이 부분은 수정하지 마세요.
    '''

    data = [int(x) for x in input().split()]

    print(*mergeSort(data))

if __name__ == "__main__":
    main()

연속부분최대합 (Medium)

nn개의 숫자가 주어질 때, 연속 부분을 선택하여 그 합을 최대화 하는 프로그램을 작성하시오. 예를 들어, 다음과 같이 8개의 숫자가 있다고 하자.

1 2 -4 5 3 -2 9 -10

이 때, 연속 부분이란 연속하여 숫자를 선택하는 것을 말한다. 가능한 연속 부분으로써 [1, 2, -4], [5, 3, -2, 9], [9, -10] 등이 있을 수 있다. 이 연속 부분들 중에서 가장 합이 큰 연속 부분은 [5, 3, -2, 9] 이며, 이보다 더 합을 크게 할 수는 없다. 따라서 연속 부분 최대합은 5+3+(-2)+9 = 15 이다.

입력 예시

1 2 -4 5 3 -2 9 -10

출력 예시

문제 조건

입력되는 수의 개수는 최대 100,000개입니다.

import sys

def getSubsum(data) :
    '''
    n개의 숫자가 list로 주어질 때, 그 연속 부분 최대합을 반환하는 함수를 작성하세요.
    '''
    
    n = len(data)
    
    if n == 1 : 
        return data[0]
    
    '''
    왼쪽, 오른쪽, 양쪽
    '''
    
    mid = n//2
    
    left = getSubsum(data[:mid])
    right = getSubsum(data[mid:])
    
    Sum = 0
    
    leftSum = 0
    rightSum = 0
    
    for i in range(mid-1, -1,-1):
        Sum+=data[i]
        leftSum = max(Sum,leftSum)
    
    Sum = 0
    
    for i in range(mid,n):
        Sum += data[i]
        rightSum = max(Sum, rightSum)
    
    return max([left, right, leftSum+rightSum])
    
    return 0

def main():
    '''
    이 부분은 수정하지 마세요.
    '''

    data = [int(x) for x in input().split()]

    print(getSubsum(data))

if __name__ == "__main__":
    main()

미션

숫자 찾기

nn개의 수 중에서, mm이 존재하면 “Yes”, 존재하지 않으면 “No”를 반환하는 프로그램을 작성하세요.

첫째줄에 nn개의 수가 입력되며, 둘째줄에 mm이 입력됩니다.

입력 예시 1

1 4 6 7 10 14 16
7

출력 예시 1

Yes

입력 예시 2

1 4 6 7 10 14 16
9

출력 예시 2

No

문제 조건

1≤n≤100,000

import sys

def ham(data, start, end, m):
    if end - start == 1:
        if data[start] == m:
            return "Yes"
        return "No"
    mid = (end + start)//2
    
    if data[mid] > m:
        return ham(data,start,mid,m)
    else:
        return ham(data,mid,end,m)

def binarySearch(data, m) :
    '''
    n개의 숫자 중에서 m이 존재하면 "Yes", 존재하지 않으면 "No"를 반환하는 함수를 작성하세요.
    '''
    
    return ham(data, 0, len(data), m)

def main():
    '''
    이 부분은 수정하지 마세요.
    '''

    data = [int(x) for x in input().split()]
    m = int(input())

    print(binarySearch(data, m))

if __name__ == "__main__":
    main()

절갯값 순 정렬

n개의 숫자가 주어질 때, 이를 절댓값을 기준으로 오름차순 정렬하는 프로그램을 작성하세요. 만약 두 수의 절댓값이 같다면, 더 작은 숫자가 앞에 위치하게 됩니다. 이 실습 문제는 Quick sort로 구현해주세요.

입력 예시

-2 1 3 9 -5 6 7 -3

출력 예시

1 -2 -3 3 -5 6 7 9

def sortAbs(array):
    '''
    절댓값을 기준으로 오름차순 정렬한 결과를 반환하는 함수를 작성하세요.
    '''
    if len(array) == 0:
        return array
    if len(array) == 1:
        return array
    
    left = []
    right = []

    first = abs(array[0])
    
    for i in range(1,len(array)):
        if abs(array[i]) < first:
            left.append(array[i])
        elif abs(array[i]) > first:
            right.append(array[i])
        else:
            if array[i] < first:
                left.append(array[i])
            else:
                right.append(array[i])
    
    return sortAbs(left) + [array[0]] + sortAbs(right)

def main():
    line = [int(x) for x in input().split()]

    print(*sortAbs(line))

if __name__ == "__main__":
    main()

히스토그램

가로의 길이가 1, 세로의 길이가 각각 다른 nn개의 판자들이 주어진다. 이 판자들은 아래 그림과 같이 모두 붙어있다.

히스토그램_1

직사각형 모양의 판자가 필요해 진 엘리스씨는, 이 붙어있는 판자들을 적당히 잘라내어 넓이가 가장 큰 직사각형을 얻고싶어 한다. 예를 들어, 위의 그림에서 얻을 수 있는 최대 넓이의 직사각형은 아래 그림과 같다.

히스토그램_2

nn개 판자에 대한 정보가 주어질 때, 이를 적당히 잘라 얻을 수 있는 직사각형의 최대 넓이를 출력하는 프로그램을 작성하세요.

입력 예시

4 3 1 2 3 4 4 3 1

출력 예시

문제 조건

판자의 높이는 최대 100,000입니다.

import sys

Max = 0

def ham(heights):

    if len(heights) == 0:
        return
    
    Min = min(heights)
    
    num = Min * len(heights)
    
    print(heights)
    
    global Max
    
    Max = max(Max,num)
    print('min', Min)
    print(num)
    print()
    arr = []
    
    for i in range(len(heights)+1):
        if i == len(heights) or heights[i] == Min:
            ham(arr)
            arr = []
        else:
            arr.append(heights[i])

def getRect(heights) :
    '''
    n개의 판자의 높이가 주어질 때, 이를 적당히 잘라 얻을 수 있는 직사각형의 최대 넓이를 반환하는 함수를 작성하세요.
    '''
    
    ham(heights)
    
    global Max
    
    print(Max)
    
    tmp = Max
    Max = 0
    
    return tmp
            
            
def main():
    '''
    이 부분은 수정하지 마세요.
    '''

    data = [int(x) for x in input().split()]

    print(getRect(data))

if __name__ == "__main__":
    main()

Inversion counting

다시 한번 확인해야할 문제 힌트를 받아서 풀었다
아직 정확한 원리를 이해하지 못함

nn개의 숫자의 리스트 A가 주어질 때, inversion은 다음과 같이 정의된다.

만약 i < j 이고, A[i] > A[j]라면 A[i]와 A[j]는 inversion 관계이다.

예를 들어, A = [1, 4, 3, 2] 일 경우, 총 3개의 inversion이 존재하는데, 이는 그 값들을 나열해보면 (4, 3), (4, 2), (3, 2) 이다.

nn개의 숫자가 주어질 때, inversion 관계인 숫자 쌍의 개수를 출력하는 프로그램을 작성하시오.

입력 예시

1 4 3 2 

출력 예시

문제 조건

입력되는 수의 개수는 최대 100,000개입니다.

import sys

cnt = 0

def ham(data, start, end) :
    
    if end-start <= 1:
        return [data[start]]
        
    mid = (start+end) // 2
    
    left = ham(data, start, mid)
    right = ham(data, mid, end)
    
    left_cnt = 0
    right_cnt = 0
    
    count = 0
    
    result = []
    
    global cnt
    
    print(left, right)
    
    while True:
        if left[left_cnt] <= right[right_cnt]:
            result.append(left[left_cnt])
            left_cnt += 1
            count += 1
            if len(left) == left_cnt:
                result += right[right_cnt:]
                break
                
        elif left[left_cnt] > right[right_cnt]:
            result.append(right[right_cnt])
            right_cnt+=1
            cnt += (len(left) - count)
            if len(right) == right_cnt:
                result += left[left_cnt:]
                break
                
        # else:
        #     result.append(left[left_cnt])
        #     left_cnt+=1
        #     count+=1
        #     if len(left) == left_cnt:
        #         result += right[right_cnt:]
        #         break
                
    return result
    
def inversionCount(data) :
    '''
    n개의 숫자가 list로 주어질 때, inversion 관계에 있는 숫자 쌍의 개수를 반환하는 함수를 작성하세요.
    '''
    global cnt
    print(ham(data, 0, len(data)))
    print('cnt',cnt)
    tmp = cnt
    cnt = 0
    return tmp
    
def main():
    '''
    이 부분은 수정하지 마세요.
    '''

    data = [int(x) for x in input().split()]

    print(inversionCount(data))

if __name__ == "__main__":
    main()

가장 가까운 두 점 찾기 (Big)

단순구현으로 풀이를 하였다

2차원 평면에 nn개의 점이 있다. 이 점들 중에서 그 거리가 가장 가까운 두 점 사이의 거리의 제곱을 출력하는 프로그램을 작성하시오. 단, 두 점 (x1, y1)과 (x2, y2) 사이의 거리는 sqrt( (x1-x2)^2 + (y1-y2)^2 ) 로 정의된다.

예를 들어, 4개의 점이 각각 (0, 3), (1, 1), (2, 2), (7, 1) 에 위치해 있다고 하면, 가장 가까운 두 점은 (1, 1)과 (2, 2)이며, 그 거리의 제곱은 2이다.

이때 그 거리의 제곱인 2를 출력하면 됩니다.

입력 예시

출력 예시

문제 조건

점의 개수는 최대 100,000개를 넘지 않습니다.
점의 좌표는 모두 정수입니다.

import sys

def getDistBig(points) :
    '''
    n개의 점이 주어질 때, 가장 가까운 두 점 사이의 거리의 제곱을 반환하는 함수를 작성하세요.

    예를 들어, 점이 4개가 있고, 각각의 좌표가 (0, 3), (1, 1), (2, 2), (7, 1) 이라면 points에는 다음과 같이 그 정보가 저장됩니다.

    points = [ (0, 3), (1, 1), (2, 2), (7, 1) ]

    이 때, 가장 가까운 두 점 사이의 거리의 제곱은 2입니다.
    '''
    print(points)

    points = sorted(points, key=lambda x: x[0])
    
    print(points)
    
    Min = 987654321
    
    for i in range(len(points)-1):
        for j in range(i+1,len(points)):
            print(i,j)
            if points[j][0] - points[i][0] > Min**1/2:
                # 시간을 줄인 지점
                break
            if (points[i][0] - points[j][0])**2 + (points[i][1] - points[j][1])**2 < Min:
                Min = (points[i][0] - points[j][0])**2 + (points[i][1] - points[j][1])**2
            
    return Min

def main():
    '''
    이 부분은 수정하지 마세요.
    '''

    n = int(input())
    points = []

    for i in range(n) :
        line = [int(x) for x in input().split()]
        points.append( (line[0], line[1]) )

    print(getDistBig(points))

if __name__ == "__main__":
    main()

Share on

Twitter Facebook LinkedIn

Lim Junhyeong

실습_3. 분할정복법

실습

가장 가까운 값 찾기

거듭제곱 구하기

합병정렬 구현

연속부분최대합 (Medium)

미션

숫자 찾기

절갯값 순 정렬

히스토그램

Inversion counting

가장 가까운 두 점 찾기 (Big)

Share on

Leave a comment

You may also enjoy

mariaDB 환경설정 계정 생성 및 권한 부여

프로젝트에 필요한 Git

여러개의 원격 저장소(git)

벽 부수고 이동하기 4_16946