문제:

자연수 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


저작자표시 비영리 동일조건

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

[Programmers]Lv 2.땅따먹기  (0) 2019.03.08
[Programmers] Lv 3. 등굣길  (2) 2019.03.07
[Programmers]Lv 2.올바른 괄호  (0) 2019.03.04
[Programmers]Lv 1. 체육복(테스트케이스 수정)  (0) 2019.03.03
[Programmers]Lv 3. 이중우선순위큐  (1) 2019.03.03

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를 붙여서 문자열 포맷팅을 할 수 있다.




저작자표시 비영리 동일조건

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

[Python 따라하기]8.클래스와 상속(Class, inheritance)  (2) 2019.03.19
[Python 따라하기]7.파일 입출력 (File I/O)  (0) 2019.03.12
[Python 따라하기]5. 반복문(For, While, break, continue)  (0) 2019.02.26
[Python 따라하기]4.조건문  (0) 2019.02.19
[Python 따라하기]3. 자료형_part2(Tuple,Set,Dictionary)  (0) 2019.02.12

문제:

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

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

'(' 또는 ')' 로만 이루어진 문자열 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


저작자표시 비영리 동일조건

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

[Programmers] Lv 3. 등굣길  (2) 2019.03.07
[Programmers]Lv 2.다음 큰 숫자  (0) 2019.03.06
[Programmers]Lv 1. 체육복(테스트케이스 수정)  (0) 2019.03.03
[Programmers]Lv 3. 이중우선순위큐  (1) 2019.03.03
[Programmers]Lv 2.가장 큰 정사각형 찾기  (0) 2019.03.02

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

저작자표시 비영리 동일조건

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

[Programmers]Lv 2.다음 큰 숫자  (0) 2019.03.06
[Programmers]Lv 2.올바른 괄호  (0) 2019.03.04
[Programmers]Lv 3. 이중우선순위큐  (1) 2019.03.03
[Programmers]Lv 2.가장 큰 정사각형 찾기  (0) 2019.03.02
[Programmers]Lv 3. 입국 심사  (2) 2019.03.01

문제:

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

명령어 

수신 탑(높이) 

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


저작자표시 비영리 동일조건

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

[Programmers]Lv 2.올바른 괄호  (0) 2019.03.04
[Programmers]Lv 1. 체육복(테스트케이스 수정)  (0) 2019.03.03
[Programmers]Lv 2.가장 큰 정사각형 찾기  (0) 2019.03.02
[Programmers]Lv 3. 입국 심사  (2) 2019.03.01
[Programmers]Lv 2. 타겟 넘버  (0) 2019.02.28

문제:

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




저작자표시 비영리 동일조건

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

[Programmers]Lv 1. 체육복(테스트케이스 수정)  (0) 2019.03.03
[Programmers]Lv 3. 이중우선순위큐  (1) 2019.03.03
[Programmers]Lv 3. 입국 심사  (2) 2019.03.01
[Programmers]Lv 2. 타겟 넘버  (0) 2019.02.28
[Programmers]Lv 3. 정수 삼각형  (0) 2019.02.27

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


저작자표시 비영리 동일조건

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

[Programmers]Lv 3. 이중우선순위큐  (1) 2019.03.03
[Programmers]Lv 2.가장 큰 정사각형 찾기  (0) 2019.03.02
[Programmers]Lv 2. 타겟 넘버  (0) 2019.02.28
[Programmers]Lv 3. 정수 삼각형  (0) 2019.02.27
[Programmers]Lv 2. 카펫  (0) 2019.02.26

문제:

 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

문제:


위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중,거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.


삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.


풀이 방법:

동적계획법 문제임을 이용해서 꼭대기에서 부터 업데이트 해가면서 풀어야 하는 문제이다. 한 칸을 업데이트를 할 경우에는 크게 두 가지가 경우가 있다.

1. 양쪽 끝일 때


양쪽 끝의 숫자들은 다음과 같이 그 전 칸의 처음 혹은 끝의 영향만을 받는다. 따라서 별도의 비교 없이 업데이트 해가면 된다.


2. 그 외의 경우



가운데에 있는 숫자들은 두 개의 숫자를 비교를 해야 한다. 가장 큰 경우를 구해야 하므로 둘 중 큰 경우를 선택해서 더해주면 된다.


위의 규칙을 따라서 다음과 같은 순서로 진행이 된다.


       7

      3 8

     8 1 0

    2 7 4 4

   4 5 2 6 5


예시와 같이 이러한 삼각형이 있다고 하면 처음에는 양쪽 끝에만 영향을 주는 경우 이므로 7을 각각 더해준다.


        7

     10 15

    8  1  0

   2  7  4  4

  4 5  2  6  5


8과 0의 경우에는 1번 경우이므로 10과 15를 각각 더해주면 되고 1은 10과 15중 15가 더 크므로 15를 더해 주도록 한다.


        7

     10 15

   18 16 15

   2   7  4   4

 4   5   2  6  5


2와 맨 끝의 4의 경우엔 1번이므로 18과 15를 각각 더해주고 7은 18과 16 중 18이 더 크므로 18을 더하고 4는 16과 15 중 16이 더 크므로 16을 더한다.


        7

     10 15

   18 16 15

  20 25 20 19

 4   5  2   6   5


위와 같은 방법으로 계속 더해가면 된다.


        7

     10 15

   18 16 15

  20 25 20 19

24 30 27 26 24


이후 맨 마지막 인덱스 배열의 최댓값을 구하면 30을 얻을 수 있다.


1
2
3
4
5
6
7
8
9
10
def solution(triangle):
    for i in range(1,len(triangle)):
        for j in range(i+1):
            if j==0:
                triangle[i][j]+=triangle[i-1][j]
            elif j==i:
                triangle[i][j]+=triangle[i-1][j-1]
            else:
                triangle[i][j]+=max(triangle[i-1][j],triangle[i-1][j-1])
    return max(triangle[-1])
cs



저작자표시 비영리 동일조건

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

[Programmers]Lv 3. 입국 심사  (2) 2019.03.01
[Programmers]Lv 2. 타겟 넘버  (0) 2019.02.28
[Programmers]Lv 2. 카펫  (0) 2019.02.26
[Programmers]:Lv 3. 예산  (0) 2019.02.25
[Programmers]Lv 2. 구명 보트  (0) 2019.02.24

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.조건문

반복문

 같은 작업을 반복적으로 해야할 때, 반복문을 사용한다면 작업의 양이 줄어들 뿐만 아니라 보기에도 깔끔해지게 된다.
반복문에는 크게 for와 while 두 가지가 있다.



For

for는 주로 list 혹은 String과 같이 반복가능한 객체를 한 번씩 훑어보기 위해서 사용한다. for의 구조는 다음과 같다.

for <<variable>> in <<iterable>>:
<<contents>>

if 절과 같이 for 즉 반복적으로 행할 내용들은 for에 속하는 것임을 나타내기 위해서 indentation(들여쓰기)을 설정해둔다.
if 절과 같이 들여쓰기는 스페이스바 4번이나 탭 한번으로 통일하여 사용한다.
variable은 사용자가 임의로 변수를 설정해서 사용하는데 주로 i , j, k .... 순으로 사용하는게 일반적이다.
다음과 같이 iterable에 String 값을 넣으면 한 글자(char)씩 반복하며 진행한다.


Range

for 반복문을 사용할 때 iterable 부분에 list나 String 값을 넣어서 직접 값을 탐색하며 진행을 하기도 하지만 range를 사용해서 인덱스로 접근을 하기도 한다.
range는 range((start),stop,(step))으로 구성되어 있다. start(선택사항)부터 stop(필수적)까지 step(선택사항)씩 연속적인 정수 객체를 만들어 준다.


range 함수로 만들어진 값은 list와 비슷하게 작동을 하지만 range라는 객체를 가지고 있다. 따라서 list에 사용하는 메소드들을 사용하는 것은 불가능 하므로 사용하기 위해서는 list로 변환 후 사용해야 한다.



다음은 range 와 len 함수를 사용해서 인덱스로 배열값들을 접근하는 경우이다. iterable 자리에 list 나 String을 넣어서 직접 값에 접근을 하게 되면 하나의 배열만 반복문을 사용할 수 있지만 다음과 같이 range와 len을 사용하면 길이가 같은 두 개의 배열을 동시에 반복문을 사용할 수 있다.



enumerate

range에선 인덱스로 접근할 수 없다는 단점을 보완하기 위해서 인덱스와 값을 동시에 접근 할 수 있도록 해주는 함수이다.
enumerate(iterable)로 사용을 하며 인덱스와 값을 쌍으로 가지는 튜플값을 하나의 원소로 가지는 enumerate 객체로 반환을 한다.
enumerate((0,iterable[0]),(1,iterable[1]),.....)



이중 반복문

이중 반복문이란 반복문안에 반복문을 사용하는 것으로 주로 행렬을 나타내고자 할 때, 서로 연관있는 두 개의 반복가능한 객체를 동시에 사용하고자 할 때 사용한다.


위처럼 두 개의 반복문을 사용할 때 서로 각각의 variable을 사용해야 하며 first의 한 값당 second가 한 루틴씩 실행됨을 알 수 있다.


또한 들여쓰기에 따라서 실행되는 횟수가 달라지는데 print(i+"번째 중"+j+"번째")는 i와 j 둘다 속해있는 부분이라 총 9번 실행됨을 알 수 있지만

print("---------------")는 i에만 해당하는 부분이므로 3번만 실행됨을 알 수 있다.


While

while 반복문은 내가 얼마나 반복문을 사용해야 할지 정확히 모를 때 사용하거나 중복적인 인덱스 혹은 값을 접근해야 할 경우에 사용한다.


while의 구조는 다음과 같다.


while <<condition>>:

<<contents>>


while은 for와 달리 순차적으로 진행을 하지 않고 condition이 참인 경우에만 while 내의 내용을 반복한다. 이 말은 condition이 거짓이 될 때까지 계속 반복한다는 뜻이다. 따라서 처음에는 condition이 참이어야 while문이 실행이 되지만 contents를 진행하면서 condition이 거짓이 되도록 만들어야 한다. 그렇지 않으면 무한반복에 빠지게 된다. 만약 무한반복에 빠지게 된다면 ctrl+c 혹은 쥬피터를 사용한다면 위의 정지버튼을 누르면 된다.



아래는 탈출 조건이 없으므로 무한반복에 빠지게 된다.



반복문을 더 효율적으로 활용하기 위해서 break와 continue를 사용할 수 있다.


break

반복문 진행중에 이미 원하는 바를 이뤄서 뒤의 진행이 필요가 없을 수 있다. 따라서 더 효율적으로 사용하기 위해 반복문이 한참 진행중이라도 일정 조건을 만나면 반복문이 끝나게 만들어주는 것이 break다. 또한 while에서는 condition이 아직 참이라도 break를 만나면 반복문이 바로 끝내도록 할 수 있다.
break는 다음과 같이 사용한다.

continue

break는 일정 조건을 만나면 반복문을 깨뜨리지만 continue는 일정 조건에서만 반복문이 진행되지 않도록 한다. 반복문 내에서 continue를 만난다면 아직 반복문 내에 남은 내용이 있더라도 작동하지 않고 다음 값으로 넘어간다. continue는 다음과 같이 사용한다.


저작자표시 비영리 동일조건

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

[Python 따라하기]7.파일 입출력 (File I/O)  (0) 2019.03.12
[Python 따라하기] 6. 함수만들기(def, print, format)  (0) 2019.03.05
[Python 따라하기]4.조건문  (0) 2019.02.19
[Python 따라하기]3. 자료형_part2(Tuple,Set,Dictionary)  (0) 2019.02.12
[Python 따라하기] 2. 자료형_part 1(String, Int,Float, List)  (0) 2019.02.05

+ Recent posts

티스토리툴바