문제:

땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.

예를 들면

|1|2|3|5|

|5|6|7|8|

|4|3|2|1|

로 땅이 주어졌다면, 1행에서 네번째 칸 (5)를 밟았으면, 2행의 네번째 칸(8)은 밟을 수 없습니다.

마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값을 return하는 solution 함수를 완성해 주세요. 위 예의 경우, 1행의 네번째 칸 (5), 2행의 세번째 칸 (7),3행의 첫번째 칸(4) 땅을 밟아 16점이 최고점이 되므로 16을 return 하면 됩니다.

풀이 방법:

이 문제도 동적계획법을 사용해서 풀 수 있다. 맨 위의 행부터 시작해서 아래로 진행을 하면서 행의 값들을 바꾸어 주면 된다. 행의 값들을 업데이트 할 때 같은 열을 연속해서 밟지는 못하므로 현재 열을 제외하고 이전 행에서 현재 열을 제외한 최댓값을 찾아서 현재 형,열에 값을 더해주면 된다. 이를 맨 밑의 행까지 계속해서 반복을 한다.

즉 예시는 다음과 같이 바뀔 수 있다.

|1|2|3|5|                       |1|2|3|5|                       |1|2|3|5|

|5|6|7|8|            -->      |10|11|12|11|         -->   |10|11|12|11|  

|4|3|2|1|                       |4|3|2|1|                       |16|15|13|13|

1
2
3
4
5
def solution(land):
    for i in range(1,len(land)):
        for j in range(len(land[0])):
            land[i][j]=land[i][j]+max(land[i-1][:j]+land[i-1][j+1:])
    return max(land[-1])
cs


'Algorithm > Python' 카테고리의 다른 글

[Programmers]Lv 2.폰켓몬  (0) 2019.03.10
[Programmers]Lv 3.베스트앨범  (0) 2019.03.09
[Programmers] Lv 3. 등굣길  (2) 2019.03.07
[Programmers]Lv 2.다음 큰 숫자  (0) 2019.03.06
[Programmers]Lv 2.올바른 괄호  (0) 2019.03.04

문제:

계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다.

가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1,1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m,n)으로 나타냅니다. 격자의 크기 m,n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어질 때, 학교에서 집에서 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요.

풀이 방법:

동적계획법을 사용하는 문제이므로 왼쪽 위 집에서 부터 하나씩 모든 경우의 수를 계산하며 학교를 가면 되는 문제이다.
예시로 (2,3)으로 가는 방법은 왼쪽에서 오는 방법과 위에서 오는 방법이 있다. 왜냐하면 최단 경로로 가기 위해서는 (1,1)에서 오른쪽이나 아래로만 움직여야 하기 때문이다. 따라서 (2,3)으로 오는 방법은 (1,3) 혹은 (2,2)에서 출발 해야 하는 것이다. 하지만 이 문제에선 물에 잠긴 지역이 있다면 아예 이동을 할  수 없으므로 puddles에 있는 원소 값들은 항상 0의 값을 가지도록 하면 된다.

이 문제의 예시로 표를 만들면 다음과 같이 만들어 진다.

 

 0

 1(집)

0(물 웅덩이) 

1

4(학교) 




계산의 용이성을 위해서 m,n 칸의 표가 아닌 m+1,n+1 칸의 0 행렬을 만들었다. 또한 우리가 알고 있는 좌표 평면과 표에서 그려지는 좌표가 반대로 구성되어 있음을 알 수 있다. 따라서 puddles에 있는지 확인 하기 위해선 i,j 의 위치를 바꾸어서 확인을 해야한다.

1
2
3
4
5
6
7
8
9
10
11
12
def solution(m, n, puddles):
    answers=[[0]*(m+1for i in range(n+1)]
    answers[1][1]=1
    for i in range(1,n+1):
        for j in range(1,m+1):
            if i==1 and j==1:
                continue
            if [j,i] in puddles:
                answers[i][j]=0
            else:
                answers[i][j]=answers[i-1][j]+answers[i][j-1]
    return answers[n][m]%1000000007
cs


문제:

자연수 n이 주어졌을 때, n의 다음 큰 숫자는 다음과 같이 정의 합니다.

조건 1. n의 다음 큰 숫자는 n보다 큰 자연수 입니다
조건 2. n의 다음 큰 숫자는 n은 2진수로 변환했을 때 1의 갯수가 같습니다.
조건 3. n의 다음 큰 숫자는 조건 1,2를 만족하는 수 중 가장 작은 수 입니다.

예를 들어서 78(1001110)의 다음 큰 숫자는 83(1010011)입니다.

자연수 n이 매개변수로 주어질 때, n의 다음 큰 숫자를 return 하는 solution 함수를 완성해주세요.

풀이 방법:

우선 자연수 n의 이진수 값을 구하기 위해서 내장함수인 bin을 사용하였다. bin은 십진수의 값을 이진수로 변환해주는 함수다. 단 이진수 앞 부분에 '0x' 가 붙으며 문자열로 반환을 한다. 하지만 문제에선 1의 갯만 필요하므로 상관 없이 1의 갯수를 세주도록 한다.
이 후 다음 큰 숫자를 찾기 위해서 n부터 1씩 증가하며 n의 1의 갯수와 같을 때까지 계속 반복하면 된다.

1
2
3
4
5
6
7
8
9
10
11
def solution(n):
    answer=n
    n_count=bin(n).count('1')
    conti=True
    while conti:
        answer+=1
        temp=answer
        n_next_count=bin(temp).count('1')
        if n_count == n_next_count:
            break     
    return answer
cs


2019/01/29 - [Language/Python] - [Python 따라하기]1. Python 설치하기

2019/02/05 - [Language/Python] - [Python 따라하기] 2. 자료형_part 1(String, Int,Float, List)

2019/02/12 - [Language/Python] - [Python 따라하기]3. 자료형_part2(Tuple,Set,Dictionary)

2019/02/19 - [Language/Python] - [Python 따라하기]4.조건문

2019/02/26 - [Language/Python] - [Python 따라하기]5. 반복문(For, While, break, continue)


함수를 사용하는 이유

수학에서는 함수는 f(x)=x^2와 같이 만들고, f(2)=4 와 같이 활용한다. 여기서 f(x)를 함수라고 부르고, x^2은 함수의 내용, 2는 입력값, 4는 결과값이라고 한다. 이와 동일한 구조로 프로그래밍에서도 함수를 만들어서 사용한다.

프로그래밍에서 수학연산을 하기 위해서 함수를 만드는 것은 아니다. 프로그래밍을 하다가 보면 반복적으로 똑같은 작업을 해야 하는 경우가 있을 것이다. 이 작업을 줄이고자 의미가 있는 부분들을 묶어서  함수로 만드는 것이다. 수학에서의 함수와 같이 '하나의 함수당 함수의 내용이 있고, 입력값을 넣으면 출력값이 나온다' 와 같은 방법으로 만든다.

함수의 구조

파이썬 함수의 구조는 다음과 같이 구성된다.

def 함수명(매개변수):
<<수행할 문장들>>

def는 함수를 만들겠다는 예약어이며 함수명, 매개변수, 수행할 문장들은 사용자가 임의로 작성하는 것이다. 조건문과 반복문처럼 함수의 속하는 부분임을 나타내기 위해서 들여쓰기를 사용한다.

다음은 함수의 간단한 예시이다.


여기서 return은 함수의 결과값을 반환해주는 명령어이다.

이 함수는 두 개의 변수 x,y를 받아서 두 개의 합을 반환해주는 함수이다.



위 함수의 구조는 입력값이 있고, 결과값이 있는 일반적인 구조이다.

만약 입력값이 없거나, 결과값이 없는 함수의 구조도 가능할까??



다음과 같이 입력값 혹은 결과값이 없더라도 함수가 동작하는데엔 아무런 문제가 없다.

만약 입력값이 몇 개가 될지 모를 경우

입력값이 여러 개일 때 그 입력값을 다 더해주는 함수를 만들어보자. 하지만 몇 개가 입력될지 모른다면 어떻게 해야할까?
이와 같은 경우에는 *를 사용하면 된다.


매개변수 앞에 *를 사용하면 몇 개가 들어가던지, 전부 모아서 튜플로 바꾸어주기 때문에 상관이 없다.

*매개변수는 단독으로 사용하는 것 이외에도 다른 일반 변수와도 함께 사용가능하다.


return 

return은 함수 값을 반환해주는 명령어로써 사용한다면 하나의 함수에서 한 개만 사용이 된다. 이 점을 이용해서 함수를 끝내는 용도로 사용할 수 있다.
다음 함수는 number로 5를 받으면 return을 만나서 number를 print를 하지 않고 종료됨을 알 수 있다.

초기값을 미리 설정해둘 경우

함수의 매개변수에 미리 초기값을 정해둘 수 있다. 초기값을 정해둔 함수의 경우 함수를 사용할 때 그 값을 넣어 주지 않으면 미리 정해진 값으로 함수를 실행한다. 만약 초기값을 무시하고 값을 넣어준다면 초기값이 아닌 내가 설정한 값으로 함수를 실행한다.

Global , local

함수내에서 사용되는 변수의 성격은 local이라고 할 수 있다. 즉 함수내에서 정의되어 있는 변수는 함수 외부에는 영향을 주지 않는다는 것이다. 다음을 보면 함수 밖에 있는 number가 1로 정의 되어 있고 함수를 통해 number가 2배로 증가 되었을 것 같지만 그렇지 않다.

우리가 정의한 number는 함수 외부의 정의이고 함수 내부에서 2배를 해준 number는 단지 함수 내에서만 사용하는 변수지 밖의 number에는 영향을 주지 못한다는 것이다.


만약 함수 내부의 변수를 외부에 영향을 주려면 어떻게 해야 할까??


두 가지 방법이 있다.

return 

우리가 지금까지 외부의 변수에 영향을 줄 수 있었던 이유는 return을 사용했기 때문이었다.

Global

이 방법은 외부의 변수를 global이라고 재정의를 해서 직접 외부의 변수를 사용하겠다고 명시를 하는 것이다.

보통 global이라고 명시를 해서 사용하기 보단 return을 사용한 방법을 이용한다. 그 이유는 단순한 함수의 경우에는 문제가 없지만 함수가 복잡해질수록 global한 변수는 제어하기 힘들어지기 때문이다. 


Print

지금까지 출력하는 함수인 print를 별다른 설명없이 사용하고 있었다. 하지만 print 내에서도 여러 기능을 제공하고 있었다.
print의 구조는 다음과 구성되어 있다,

print(value,....sep=' ',end='\n',file=sys.stdout,flush=False)

보통 print의 sep이나 end까지만 사용하고 file이나 flush는 사용하지 않는다.

print 내에서 여러 문자열을 + 로 이어가거나 콤마(,)를 사용해서 출력한다. 이 둘의 차이점은 + 은 띄어쓰기를 지원해주지 않지만 콤마로 구분을 하면 띄어쓰기를 해주기 때문이다. 이 이유는 콤마가 sep을 나타내는데, sep의 기본값은 공백으로 설정되어 있기 때문이다.


위에서도 말했듯이 콤마가 sep이 공백으로 설정되어 있기 때문에 띄어쓰기를 했다면 sep값을 주면 콤마를 사용했을 때 그 사이사이에 sep이 들어가게 된다.



또한 출력을 하면 하나의 print 당 한 줄에 나타나게 되는데, 그 이유는 print의 end의 기본값이 줄바꿈으로 설정되어 있기 때문이다.



따라서 end값을 공백으로 변경해준다면 한 줄에 모든 값을 표시해 줄 수 있다.


문자열 포맷팅

한 과일가게가 있다고 하자. 이 가게는 과일의 남은 양들을 공지해주는 프로그램을 만들었다. 그 프로그램은 다음과 같이 공지한다.

"사과가 7개 있습니다."

손님이 와서 사과를 2개 사갔다고 하자. 그러면 다음과 같이 수정된다.

"사과가 5개 있습니다."

위의 두 문자열은 동일한데 숫자 7과 5만 다르다. 이렇게 큰 틀이 있고 특정 부분만 바꾸어서 계속 사용해야하는 문자열이 있다면 문자열 포맷팅을 사용하면 더 편하게 사용할 수 있다.

문자열 포맷팅을 하는 방법에는 크게 세 가지 방법이 있다.

1. % 사용하기
2. format 함수 사용하기
3. f 사용하기

1. % 사용하기

%를 사용할 경우 문자열 포맷코드가 있다. %+"..."와 같은 형태로 사용한다.

코드 

설명 

%d 

 정수형

%s 

 문자열

%f 

부동소수점 

%% 

단어 '%' 


2. format 함수 사용하기

format 함수를 사용하면 좀 더 유연하게 문자열 포맷팅을 하는 것이 가능하다. 포맷팅을 하고 싶은 부분들을 { }로 표시를 하며 { }에 숫자를 집어 넣어서 포맷팅의 순서를 지정할 수 있고, 숫자를 생략한다면 가장 먼저 만나는 { }부터 차례대로 포맷팅해준다.

3. f 사용하기

파이썬 3.6버젼부터 제공하는 기능으로 그 이전 버젼에서는 사용할 수 없다. 문자열 앞에 f를 붙여서 문자열 포맷팅을 할 수 있다.




문제:

올바른 괄호란 두 개의 괄호 '(' 와 ')' 만으로 구성되어 있고, 괄호가 올바르게 짝지어진 문자열입니다. 괄호가 올바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 합니다.
예를 들어

"()()" 또는 "(())()"는 올바른 괄호입니다.
")()(" 또는 "(()("는 올바르지 않은 괄호입니다.

'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return하는 solution 함수를 완성해주세요.

풀이 방법:

'(' 는 +1의 값을 가지고 ')'이 -1의 값을 가진다고 하자.
모두 정상적으로 짝을 이뤘다. 즉 "(" 와 ")"의 갯수가 동일하다면 문자열 s를 반복문으로 한 번씩 탐색해보았을 때 count의 값이0이 되어야 할 것이다.
만약 count의 값이 양수가 나온다면 "("가 더 있는 것이고 음수면 그 반대일 것이다.
하지만 괄호의 갯수는 맞게 이루어져있지만 반대로 있을 수도 있다. (ex ")(" )
이와 같은 경우에는 문자열의 합은 0이 나오지만 올바르지 않은 괄호이다. 따라서 조건을 하나 더 추가를 해줘야 한다. 
문제가 발생 할 때에는 ")"에서 나오게 된다. "("로 열지도 않았는데 ")"로 닫아버릴 때 오류가 발생한다. 즉 count값이 순간적으로 마이너스가 될 경우가 오류가 발생하게 된다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
def solution(s):
    count=0
    for i in s:
        if i is '(':
            count+=1
        elif i is ')':
            count-=1
            if count < 0 :
                return False
    if count == 0:
        return True
    else:
        return False
cs


2019/02/13 - [Algorithm/Python] - [Programmers]Lv 1. 체육복


이전에 풀었던 문제인데 2.28일 이후로 테스트케이스가 추가되면서 하나의 케이스가 통과하지 못한다.

이전에는 조금 명시적으로 여분을 가지고 있는 학생이 구분이 되지 않았는데 더 명시적으로 여분을 가지고 있는 사람에게만 빌리게 하였더니 통과를 하였다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def solution(n,lost,reserve):
    cloth=[1]*n
    for i in range(n):
        if i+1 in reserve:
            cloth[i]=2
        if i+1 in lost:
            cloth[i]-=1
    if cloth[0]==0:
        if cloth[1]==2:
            cloth[0]+=1
            cloth[1]-=1
    for i in range(1,n-1):
        if cloth[i]==0:
            if cloth[i+1]==2:
                cloth[i]+=1
                cloth[i+1]-=1
            elif cloth[i-1]==2:
                cloth[i]+=1
                cloth[i-1]-=1
    if cloth[-1]==0:
        if cloth[-2]==2:
            cloth[-1]+=1
            cloth[-2]-=1
    count=0
    for i in cloth:
        if i != 0:
            count+=1
    return count
cs

문제:

이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.

명령어 

수신 탑(높이) 

I 숫자 

큐에 주어진 숫자를 삽입합니다. 

D 1 

큐에서 최댓값을 삭제합니다. 

D -1 

큐에서 최솟값을 삭제합니다. 


이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값,최솟값]을 return 하도록 solution 함수를 구현해주세요.

풀이 방법:

힙을 사용해서 풀어야 하는 문제지만 굳이 힙을 사용해서 풀지 않아도 상관 없다. operations를 반복문의 매개변수로 받아 각 원소들을 공백으로 구분해보아서 명령어대로 배열에서 처리를 하면 문제없이 풀 수 있다. 삽입을 할 때 정수형으로 변경을 해서 넣는데 그 이유는 음수값들도 들어가기 때문에 정렬을 하기 위해서는 정수형으로 바꾸는 것이 필수적이기 때문이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def solution(operations):
    answer=[]
    for i in operations:
        a,b=i.split(" ")
        if a=="I":
            answer.append(int(b))
        else:
            if len(answer)>0:
                if b=="1":
                    answer.pop()
                else:
                    answer.pop(0)
            else:
                pass
        answer.sort()
    if len(answer)==0:
        return [0,0]
    else:
        return [max(answer),min(answer)]
cs

만약 힙을 사용해서 풀고 싶다면 다음과 같이 하면 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import heapq
def solution(operations):
    h=[]
    for i in operations:
        a,b=i.split(" ")
        if a=="I":
            heapq.heappush(h,int(b))
        else:
            if len(h)>0:
                if b=="1":
                    h.pop(h.index(heapq.nlargest(1,h)[0]))
                else:
                    heapq.heappop(h)
            else:
                pass
    if len(h)==0:
        return [0,0]
    else:
        return [heapq.nlargest(1,h)[0],heapq.nsmallest(1,h)[0]]
cs


문제:

1과 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요.( 단, 정사각형이란 축에 평행한 정사각형을 말합니다.)

풀이 방법:

이 문제는 DP(dynamic programming), 동적계획법을 사용해서 풀어야 하는 문제이다. 왼쪽 위(1,1)부터 시작해서 오른쪽 아래로 진행을 하면서 정사각형을 나간다. 

정사각형으로 취급되는 경우는 다음과 같다.


1(1번)

1(2번) 

 1(3번) 

1(4번) 


4번의 값이 0이 아니라면 1,2,3번의 값을 비교해 최소값을 찾은 뒤에 4번 자리에 그 최솟값에 1을 더한 값을 넣어 준다. 즉 다음과 같이 된다.


1(1번)

1(2번) 

 1(3번) 

2(4번) 


최솟값을 찾는 이유는 하나의 0이 있다면 정사각형의 형태가 아니므로 1 이상의 값들만 이어나가기 위함이다. 또한 1을 더해주는 이유는 정사각형이라면 길이의 값을 누적하기 위해서이고 아니라면 남은 1의 값들이 다른 곳에서 정사각형을 이룰 수 있기 때문에 이어나가주는 것이다.

이 문제의 예시를 통해서 구하는 방법을 알아보자. 다음과 같이 처음 상태가 있다.


0 

1 

1 

1

1 

1 

1 

1

1 

1 

1

1

0

0

1

0


처음 왼쪽 위 (1,1)을 비교해 보았을 때 (0,0)이 0이기에 (1,1)의 값을 1로 바꾼다.


0 

1 

1 

1

1 

1 

1 

1

1 

1 

1

1

0

0

1

0


(1,2)의 값을 비교해 보았을 때  주위 최솟값이 1이므로 (1,2)의 값을 2로 바꾼다. 이 경우가 길이가 2인 정사각형을 찾은 경우이다. 하지만 가장 큰 정사각형을 찾는 것이 문제이므로 계속 탐색해보도록 한다.

0 

1 

1 

1

1 

1 

2

1

1 

1 

1

1

0

0

1

0


(1,3)의 값을 비교해보았을 때, 주위 최솟값이 1이므로 (1,3)의 값을 2로 바꾼다. 이 경우도 역시 길이가 2인 정사각형을 찾은 경우다. 이전 (1,2)에서도 정사각형을 찾았지만 이 둘로는 정사각형이 아닌 직사각형이 만들어지므로 서로 영향을 주진 못한다.

0 

1 

1 

1

1 

1 

2 

2

1 

1 

1

1

0

0

1

0


계속해서 이 방법대로 진행을 하면 (2,2)까지 다음과 같이 표를 바꿀 수 있다.

0 

1 

1 

1

1 

1 

2 

2

1 

2 

2

1

0

0

1

0


(2,3)에서는 주위의 최솟값이 2이므로 (2,3)의 값을 3으로 바꾼다 즉 길이가 3인 정사각형을 찾은 경우다. 이 처럼 주위의 값들이 모두 2,2,2 혹은 3,3,3 과 같이 이루어져 있을 경우에 가장 큰 정사각형의 길이가 바뀌게 되는 것이다.

0 

1 

1 

1

1 

1 

2 

2

1 

2 

2

3

0

0

1

0


마지막 줄은 계속 진행해보아도 변경되는 점이 없으므로 이 예시의 가장 큰 정사각형은 길이가 3인 정사각형이다.

다른 채점케이스에서 전부다 0인 경우에는 위와 같은 방법으로 길이가 1인 정사각형이 있다고 나오므로 따로 구분해서 구하도록 하였다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def solution(board):
    max_point=0
    for i in range(len(board)):
        max_point+=sum(board[i][:])
    if max_point==0:
        return 0
    max_point=0
    for i in range(1,len(board)):
        for j in range(1,len(board[0])):
            if board[i][j]==0:
                continue
            else:
                min_point=min(board[i][j-1],board[i-1][j],board[i-1][j-1])
                min_point+=1
                board[i][j]=min_point
                if max_point < board[i][j]:
                    max_point=board[i][j]
    if max_point==0:
        return 1
    else:
        return max_point**2
cs




2019/02/25 - [Algorithm/Python] - [Programmers]:Lv 3. 예산

문제:

n 명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.

처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그 곳으로 가서 심사를 받을 수도 있습니다.

모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.

입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.

풀이 방법:

이분탐색 문제이므로 이 문제도 예산 문제와 같이 심사를 다 받는 시간을 찍어보면 된다. 왼쪽 값을 0 우측 값을 times의 가장 큰 값에 n을 곱한 값으로 설정하고 이분 탐색을 진행해 나가면 된다. 중간에 n명을 통과를 할 수 있는 시간이 있더라도 최소값을 찾기 위해 끝까지 진행해본다.
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def solution(n, times):
    left=0
    right=max(times)*n
    temp=right
    answer=right
    while(right>=left):
        mid=(right+left)//2
        people=0
        for i in times:
            people+=mid//i
        if people==n:
            if answer>=mid:
                answer=mid
            right=mid-1
        elif people>n:
            right=mid-1
        else:
            left=mid+1
    if answer==temp:
        return right+1
    else:
        return answer
cs


문제:

 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1,1,1,1,1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1=3
+1-1+1+1+1=3
+1+1-1+1+1=3
+1+1+1-1+1=3
+1+1+1+1-1=3

 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟
넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

풀이 방법:

깊이/너비 우선 탐색(DFS/BFS)는 트리 구조를 만드는 것이 핵심이다. 이 문제에서 타겟 넘버를 만드는 방법은 더하거나 빼거나 둘 중 하나다. 따라서 하나의 숫자에 대해 다음 값을 더하는 경우, 빼는 경우로 트리 구조를 만들어 나갈 수 있는 것이다. 첫 수부터 빼는 경우가 있을 수 있으므로 미리 0을 담아 놓고 시작 하도록 한다. 이후 트리를 다 완성 시킨 후 타겟 넘버인 target의 갯수를 카운트 하면 된다.


1
2
3
4
5
6
7
8
9
10
def solution(numbers, target):
    answer_list=[0]
    for i in numbers:
        temporary_list=[]
        for j in answer_list:
            temporary_list.append(j+i)
            temporary_list.append(j-i)
        answer_list=temporary_list
    answer = answer_list.count(target)
    return answer
cs


'Algorithm > Python' 카테고리의 다른 글

[Programmers]Lv 2.가장 큰 정사각형 찾기  (0) 2019.03.02
[Programmers]Lv 3. 입국 심사  (2) 2019.03.01
[Programmers]Lv 3. 정수 삼각형  (0) 2019.02.27
[Programmers]Lv 2. 카펫  (0) 2019.02.26
[Programmers]:Lv 3. 예산  (0) 2019.02.25

+ Recent posts