실습_2. 문제해결절차, 완전탐색, 시간복잡도

Updated: August 21, 2020

실습

연속 부분 최대합

n개의 숫자가 주어질 때, 연속 부분을 선택하여 그 합을 최대화 하는 프로그램을 작성하시오. 예를 들어, 다음과 같이 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개입니다.

import sys

def getSubsum(data) :
    '''
    n개의 숫자가 list로 주어질 때, 그 연속 부분 최대합을 반환하는 함수를 작성하세요.
    '''
    sum = 0
    maxs = 0
    for i in range(1,len(data)+1):
        #print(i)
        for j in range(0, len(data) - i + 1):
            #print(" ",j)
            for k in range(j,j+i):
                sum+=data[k]
            maxs = max(sum,maxs)
            sum = 0
    
    return maxs

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

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

    print(getSubsum(data))

if __name__ == "__main__":
    main()

멱집합 구하기

집합 A에 다하여, A의 모든 부분집합을 원소로 가지는 집합을 A의 멱집합이라고 한다. 예를 들어, 집합 A의 원소가 {1, 2, 3} 일 경우, A의 멱집합은 다음과 같이 8개의 원소를 갖는 집합이다.

{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}

집합 A의 원소는 1부터 nn까지의 자연수로 구성된다. nn이 주어질 때, A의 멱집합의 원소를 사전 순서대로 모두 출력하는 프로그램을 작성하시오. 단, 공집합은 제외하고 출력한다.

입력 예시

출력 예시

문제 조건

원소의 개수는 10개를 넘지 않습니다.
공집합은 출력하지 않습니다.

import sys

def powerSet(n) :
    '''
    n개의 원소를 가지는 집합 A의 멱집합의 원소를 사전 순서대로 list로 반환하는 함수를 작성하시오.

    예를 들어, n = 3 일 경우 다음의 list를 반환한다.

    [ [1], [1, 2], [1, 3], [1, 2, 3], [2], [2, 3], [3] ]
    '''
    
    def ham(k, n):
        if k == n:
            return [[k]]
            
        re = ham(k+1,n)
        arr = [[k]]
        for i in range(len(re)):
            arr += [[k]+re[i]]
        arr += re
        print(arr)
        return arr
    
    return ham(1,n)

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

    n = int(input())

    result = powerSet(n)
    
    for line in result :
        print(*line)

if __name__ == "__main__":
    main()

균형 맞추기

nn개의 숫자가 주어진다. 이제 이 숫자를 두 개의 그룹으로 나눌 것이다. 예를 들어 5개의 숫자 [1, -3, 4, 5, -2] 가 주어진다면, 이를 두 개의 그룹으로 나누는 경우는 여러가지가 있을 수 있다. 가능한 경우로써 [1, -3], [4, 5, -2] 가 있을 수 있고, 또 다른 경우로는 [1, 4, -2], [-3, 5] 가 있을 수 있다.

나눈 두 그룹을 A, B라고 할 때, (A의 원소의 합) - (B의 원소의 합) 의 절댓값을 최소화 하는 프로그램을 작성하시오. 위의 예제에서는 A = [1, 4, -2], B = [-3, 5] 라고 하였을 때 (A의 원소의 합) - (B의 원소의 합) 의 절댓값 =

3 - 2

= 1 이며, 이보다 더 작은 값을 만드는 A, B는 존재하지 않는다.

이 경우 절댓값의 최솟값인 1을 출력하면 된다.

입력 예시

1 -3 4 5 -2

출력 예시

문제 조건

입력되는 수는 최대 20개를 넘지 않는다.

import sys

def makeEqual(data) :
    '''
    n개의 숫자를 두 그룹 A, B로 나눈다고 할 때,

    | (A의 원소의 합) - (B의 원소의 합) | 의 최솟값을 반환하는 함수를 작성하시오.
    
    '''

    print(data)
    
    check = [False for i in range(len(data))]
    
    mins = [987654321]

    def ham(check, cnt):
        if cnt == len(check):
            #print(check)
            t_sum = 0
            f_sum = 0
            
            for i in range(len(check)):
                if check[i]:
                    t_sum+=data[i]
                else:
                    f_sum+=data[i]
            mins[0] = min(mins[0],abs(t_sum - f_sum))
            
            return
            
        check[cnt] = True
        ham(check,cnt+1)
        check[cnt] = False
        ham(check,cnt+1)
    
    ham(check,0)
    print(mins[0])
    return mins[0]

def main():
    '''
    이 부분은 수정하지 마세요.
    '''
    data = [int(x) for x in input().split()]
    print(makeEqual(data))
    
if __name__ == "__main__":
    main()

미션

각 자릿수의 차이

두 자연수가 주어질 때, 각 자릿수의 숫자를 비교하여 다른 개수를 세는 프로그램을 작성하시오.

예를 들어, 두 자연수가 각각 212, 233 이라면 10의 자리와 1의 자리가 다르므로, 총 2개의 자리가 다르다.

입력 예시 1

212
233

출력 예시 1

입력 예시 2

123
123456

출력 예시 2

def diffDigit(a, b) :
    '''
    a, b의 서로 다른 자리수의 개수를 반환한다
    '''
    
    a_cnt = 0
    b_cnt = 0
    
    cnt = 0
    
    while a!=0 or b!=0:
        print(a,b)
        if a%10 != b %10 and a!=0 and b!= 0:
            cnt +=1
        if a!= 0:
            a_cnt+=1
        if b!=0:
            b_cnt+=1
        a//=10
        b//=10
    
    return cnt + abs(a_cnt - b_cnt);

def main():
    '''
    Do not change this code
    '''

    a = int(input())
    b = int(input())

    print(diffDigit(a, b))


if __name__ == "__main__":
    main()

기울기가 가장 큰 두 점 찾기

2차원 평면에 nn개의 점이 있다. 이 점들 중에서 두 점을 선택했을 때, 그 기울기의 절댓값의 최댓값을 출력하는 프로그램을 작성하시오. 단, 모든 점의 x좌표는 다르다고 가정한다. 또한, 두 점 (x1, y1), (x2, y2)의 기울기는 (y2 - y1) / (x2 - x1) 으로 정의된다.

예를 들어, 4개의 점이 각각 (0, 3), (1, 1), (2, 2), (4, 1) 에 위치해 있다고 하면, 기울기의 절댓값의 최댓값은 2가 된다.

이 경우 기울기 절댓값의 최댓값인 2를 출력합니다.

입력으로는 첫줄에 점의 개수가, 그 다음줄부터는 점의 xx좌표와 yy좌표가 입력됩니다.

입력 예시

출력 예시

2.000

문제 조건

점의 개수는 최대 100개를 넘지 않습니다.
점의 좌표는 모두 정수입니다.
출력은 소숫점 넷째자리에서 반올림하여 출력합니다.

import sys

def maxSlope(points) :
    '''
    n개의 점들 중에서 2개의 점을 선택했을 때, 얻을 수 있는 기울기의 절댓값 중에서 가장 큰 값을 반환하는 함수를 작성하세요.

    **주의** : 소숫점 넷째자리에서 반올림하는 것은 고려할 필요가 없습니다. 이는 main()에서 출력을 할 때에 처리가 되므로, 기울기의 최댓값을 구하는 것에 집중해 주시길 바랍니다.
    '''
    
    print(points)
    
    maxs = 0
    
    for i in range(len(points)-1):
        for j in range(i+1,len(points)):
            maxs = max(maxs,abs((points[i][1] - points[j][1])/(points[i][0] - points[j][0])))

    return maxs

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("%.3lf" % maxSlope(points))

if __name__ == "__main__":
    main()

가장 가까운 두 점 찾기

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개를 넘지 않습니다.
점의 좌표는 모두 정수입니다.

import sys

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

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

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

    이 때, 가장 가까운 두 점 사이의 거리의 제곱은 2입니다.
    '''
    print()
    
    mins = 987654321
    
    for i in range(len(points)-1):
        for j in range(i+1,len(points)):
            print(i,j)
            mins = min(mins,(points[i][0] - points[j][0])**2+(points[i][1] - points[j][1])**2)
    return mins

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(getDist(points))

if __name__ == "__main__":
    main()

N-Queen

nn x nn 의 체스 판에 n개의 Queen을 놓으려 합니다. 이 때, 다음의 규칙을 반드시 따라야 합니다.

같은 행에 2개 이상의 Queen이 존재해서는 안됩니다. 같은 열에 2개 이상의 Queen이 존재해서는 안됩니다. 하나의 대각선에 2개 이상의 Queen이 존재해서는 안됩니다. 이는 ‘\‘ 방향의 대각선과 ‘/‘ 방향의 대각선 모두에 대하여 해당되는 조건입니다.

입력 예시 1

출력 예시 1

입력 예시 2

출력 예시 2

문제 조건

퀸의 개수는 최대 10개입니다.

import sys
sys.setrecursionlimit(100000)

dr = [-1,-1,1,1]
dc = [-1,1,-1,1]

cnt = 0

def set_q(n,row,check,q_map):

    if row == n:
        global cnt
        cnt += 1

    for i in range(n):
        if check[i]:
            continue
            
        che = False
        for j in range(4):
            tmp_r = row
            tmp_c = i
            while True:
                tmp_r+=dr[j]
                tmp_c+=dc[j]
                if tmp_r<0 or tmp_r>=n or tmp_c<0 or tmp_c>=n:
                    break
                if q_map[tmp_r][tmp_c] == 1:
                    che = True
                    break
            if che:
                break
        if che:
            continue
        
        q_map[row][i] = 1
        check[i] = True
        
        set_q(n,row + 1,check,q_map)
        
        q_map[row][i] = 0
        check[i] = False

def nQueen(n) :
    '''
    n개의 Queen을 배치하는 경우의 수를 반환하는 함수를 작성하세요.
    '''
    q_map = [[0 for j in range(n)] for i in range(n)]
    check = [False for i in range(n)]
    
    set_q(n,0,check,q_map)
    
    global cnt
    
    tmp = cnt
    cnt = 0
    return tmp

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

    n = int(input())
    

    print(nQueen(n))
    cnt = 0

if __name__ == "__main__":
    main()

뒤집기

다음과 같이 nn x mm 의 판이 주어집니다. () 각각의 판에는 흰색 혹은 검은색이 칠해져 있으며, 흰색은 0, 그리고 검은색은 1로 주어진다.

이제 이 모든 판의 색깔을 흰색으로 만들려고 한다. 색을 바꾸는 것은 특정 칸을 ‘클릭’ 함으로써 이루어진다. 한 번에 한 칸을 ‘클릭’ 할 수 있으며, 한 칸을 ‘클릭’ 할 경우에는 그 칸의 색깔 뿐만 아니라 상, 하, 좌, 우의 모든 색깔이 바뀐다. 즉, 흰색일 경우에는 검은색으로, 검은색일 경우에는 흰색으로 바뀐다. 만약 (0, 0) 과 같이 상, 하, 좌, 우 중에서 몇몇 칸만 존재할 경우, 그 존재하는 칸의 색깔만 바뀌게 된다.

nn x mm 의 판의 상태가 주어질 때, 이를 모두 흰색으로 만들기 위하여 ‘클릭’ 해야하는 최소 칸의 수를 출력하는 프로그램을 작성하시오. 만약, ‘클릭’을 통하여 모두 흰색으로 바꾸는 것이 불가능하다면 -1을 출력한다.

입력 첫째 줄에 nn, mm이 주어진다. 두 번째 줄부터 각 칸의 상태가 주어진다. 0은 흰색을 의미하며, 1은 검은색을 의미한다.
입력 예시 1

출력 예시 1

설명 1 (2, 1)을 클릭한 후, (1, 1)을 클릭하면 모든 칸이 흰색이 된다.
입력 예시 2

출력 예시 2

설명 2

(1, 2), (2, 1), (1, 4), 그리고 (1, 1)을 차례대로 클릭하면 모든 칸을 흰색으로 만들 수 있다.

입력 예시 3

출력 예시 3

-1

문제 조건
- 10001≤n≤1000
- 101≤m≤10

import sys
import copy
sys.setrecursionlimit(100000)

dr = [0,-1,1,0,0]
dc = [0,0,0,-1,1]                

mins = 987654321

def cal(check,n,m,myMap):

    tmp_arr = copy.deepcopy(myMap)
    
    cnt = 0
    global mins

    for j in range(m):
        if check[j]:
            cnt+=1
            if cnt >=mins:
                return
            for k in range(5):
                i_tmp = 0
                j_tmp = j
                if i_tmp+dr[k]<0 or i_tmp+dr[k]>=n or j_tmp+dc[k]<0 or j_tmp+dc[k]>=m:
                    continue
                tmp_arr[i_tmp+dr[k]][j_tmp+dc[k]] = (tmp_arr[i_tmp+dr[k]][j_tmp+dc[k]]+1)%2
    
    ############ 출력
    # for i in range(n):
    #     for j in range(m):
    #         print(tmp_arr[i][j],end=' ')
    #     print()
    ########### 구현
    
    for i in range(1,n):
        for j in range(m):
            if tmp_arr[i-1][j] == 1:
                cnt += 1
                if cnt >= mins:
                    return
                for k in range(5):
                    i_tmp = i
                    j_tmp = j
                    if i_tmp+dr[k]<0 or i_tmp+dr[k]>=n or j_tmp+dc[k]<0 or j_tmp+dc[k]>=m:
                        continue
                    tmp_arr[i_tmp+dr[k]][j_tmp+dc[k]] = (tmp_arr[i_tmp+dr[k]][j_tmp+dc[k]]+1)%2
    che = True
    ############ 출력
#     print()
    
#     for i in range(n):
#         for j in range(m):
#             print(tmp_arr[i][j],end=' ')
#         print()
    
    for i in range(n):
        for j in range(m):
            if tmp_arr[i][j] == 1:
                return
    
    
    mins = min(mins, cnt)

def ham(cnt,n,m,check,myMap):
    if cnt == m:

        cal(check,n,m,myMap)
        return
    check[cnt] = False
    ham(cnt+1,n,m,check,myMap)
    check[cnt] = True
    ham(cnt+1,n,m,check,myMap)
    

def flip(myMap, n, m) :
    '''
    모든 칸을 흰색으로 바꾸기 위해 최소로 클릭해야 하는 횟수를 반환하는 함수를 작성하세요.
    '''
    
    check = [False for i in range(m)]
    
    ham(0,n,m,check,myMap)
    
    global mins
    
    tmp = mins
    
    mins = 987654321
    
    if tmp == 987654321:
        tmp = -1
    
    return tmp

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

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

    n = data[0]
    m = data[1]

    myMap = []

    for i in range(n) :
        line = [int(x) for x in input().split()]
        myMap.append(line)

    print(flip(myMap, n, m))

if __name__ == "__main__":
    main()

Share on

Twitter Facebook LinkedIn

Lim Junhyeong

실습_2. 문제해결절차, 완전탐색, 시간복잡도

실습

연속 부분 최대합

멱집합 구하기

균형 맞추기

미션

각 자릿수의 차이

기울기가 가장 큰 두 점 찾기

가장 가까운 두 점 찾기

N-Queen

뒤집기

Share on

Leave a comment

You may also enjoy

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

프로젝트에 필요한 Git

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

벽 부수고 이동하기 4_16946