'프로그래머스' 태그의 글 목록 (11 Page)

문제:

Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 빨간색으로 칠해져 있고 모서리는 갈색으로 칠해져 있는 격자 모양 카펫을 봤씁니다.

Leo는 집으로 돌아와서 아까 본 카펫의 빨간색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.

Leo가 본 카펫에서 갈색 격자의 수 brown, 빨간색 격자의 수 red가 매개변수로 주어질 때 카펫의 가로,세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

풀이 방법:

이 카펫은 내부에 있는 빨간색의 모양에 따라서 갈색으로 칠한 수가 정해지게 된다. 이 문제가 완전탐색이므로 빨간색의 갯수로 나올수 있는 경우의 수를 모두 구해서 알맞은 경우를 찾도록 한다.

안의 빨간색의 모양은 사각형의 모양이므로 red의 약수마다 갈색의 갯수를 구한다. 이때 brown과 같아진다면 그 경우가 답이 되는 것이다.

1
2
3
4
5
6
7
8
9
10
def solution(brown, red):
    answer=[]
    for i in range(1,int(red/2)+2):
        if red%i==0:
            a,b=max(red//i,i),min(red//i,i)
            if 2*a+(b+2)*2==brown:
                answer.append(a+2)
                answer.append(b+2)
                break
    return answer
cs

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

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

[Programmers]Lv 2. 타겟 넘버 (0)	2019.02.28
[Programmers]Lv 3. 정수 삼각형 (0)	2019.02.27
[Programmers]:Lv 3. 예산 (0)	2019.02.25
[Programmers]Lv 2. 구명 보트 (0)	2019.02.24
[Programmers]Lv 3.타일 장식물 (0)	2019.02.23

문제:

국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것입니다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있습니다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정합니다.

1. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정합니다.

2. 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정합니다.

상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정합니다.

예를 들어, 전체 국가예산이 485이고 4개 지방의 예산요청이 각각 120,110,140,150일 때, 상한액을 127로 잡으면 위의 요청들에 대해서 각각 120,110,127,127을 배정하고 그 합이 484로 가능한 최대가 됩니다.

각 지방에서 요청하는 예산이 담긴 배열 budgets과 총 예산 M이 매개변수로 주어질 때, 위의 조건을 모두 만족하는 상한액을 return 하도록 solution 함수를 작성해주세요.

풀이 방법:

이 문제는 처음 봤을 때, 예시를 보면 120~150 사이의 수를 모두 넣어보아서 최대가 되는 상한액을 찾으면 되는 것이 아닌가 라고 생각 할 수 있지만 그렇게 푼다면 아마 시간초과가 발생할 것이다.(총 예산이 1,000,000,000 이하인 수이다..)

따라서 이 문제의 태그가 이분탐색인 만큼 이분탐색을 사용해야 시간초과가 발생하지 않고 풀 수 있다. 이분탐색의 문제의 핵심은 '찍기'라고 생각하면 된다. 이 문제의 예시로 예를 들어보면 0~150의 수를 이분탐색의 방법으로 찍어가면서 최대 상한액을 찾아나가는 것이다.

처음에는 75를 상한액으로 고를 수 있고 75*4<=485이므로 왼쪽 값을 75+1로 선택하여 이분탐색을 진행한다.

그 다음엔 113을 상한액으로 고를 수 있고 이 역시 113*3+110<=485이므로 왼쪽값을 113+1로 선택하여 이분탐색을 진행한다.

그 다음엔 132를 상한액으로 고를 수 있고 120+110+132*2>=485이므로 오른쪽 값을 132-1로 선택하여 이분탐색을 진행한다.

이와 같이 계속 반복하다보면 127이 상한액일 때 최대가 됨을 알 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def solution(budgets, M):
    left=0
    right=max(budgets)
    temp=0
    answer=0
    while(right>=left):
        mid=(left+right)//2
        result=0
        for i in budgets:
            if mid>i:
                result+=i
            else:
                result+=mid
        if result>M:
            right=mid-1
        else:
            if result>=temp:
                answer=mid
            left=mid+1
    return answer
cs

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

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

[Programmers]Lv 3. 정수 삼각형 (0)	2019.02.27
[Programmers]Lv 2. 카펫 (0)	2019.02.26
[Programmers]Lv 2. 구명 보트 (0)	2019.02.24
[Programmers]Lv 3.타일 장식물 (0)	2019.02.23
[Programmers]Lv 2. 숫자 야구 (0)	2019.02.22

문제:

무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다.

예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다.

구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다.

사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요.

풀이 방법:

구명보트는 작아서 한 번에 최대 2명만 탈 수 있다는 점이 가장 중요하다. 또한 탐욕적 방법으로 해결해야 하므로 사람들의 몸무게를 정렬하고 가장 몸무게가 작은 사람과 무거운 사람과 매칭을 해보는 방법으로 진행을 해보았다. 만약 가장 작은 사람의 무게와 무거운 사람의 무게가 limit보다 작다면 탑승할 수 있는 것 이므로 count를 하나 늘리고 light의 인덱스를 1증가, heavy의 인덱스를 1감소 시킨다. 만약 limit보다 크다면 heavy의 인덱스만 1감소 시킨다.

이를 light의 인덱스가 heavy의 인덱스를 앞지를 때까지 반복한다.

이후 최종 구명보트의 수는 people의 전체 길이에서 count 값을 뺀 값이 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def solution(people,limit):
    people.sort()
    length=len(people)
    light=0
    heavy=length-1
    count=0
    while(light<heavy):
        if people[light]+people[heavy]<=limit:
            count+=1
            light+=1
            heavy-=1
        else:
            heavy-=1
    return length-count
cs

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

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

[Programmers]Lv 2. 카펫 (0)	2019.02.26
[Programmers]:Lv 3. 예산 (0)	2019.02.25
[Programmers]Lv 3.타일 장식물 (0)	2019.02.23
[Programmers]Lv 2. 숫자 야구 (0)	2019.02.22
[Programmers]Lv 3. 2 X N 타일링 (0)	2019.02.21

문제:

대구 달성공원에 놀러 온 지수는 최근에 새로 만든 타일 장식물을 보게 되었다. 타일 장식물은 정사각형 타일을 붙여 만든 형태였는데, 한 변이 1인 정사각형 타일부터 시작하여 마치 앵무조개의 나선모양처럼 점점 큰 타일을 붙인 형태였다. 타일 장식물의 일부를 그리면 다음과 같다.

그림에서 타일에 적힌 수는 각 타일의 한 변의 길이를 나타낸다. 타일 장식물을 구성하는 정사각형 타일 한 변의 길이를 안쪽 타일부터 시작하여 차례로 적으면 다음과 같다..

[1,1,2,3,5,8,...]

지수는 문들 이러한 타일들로 구성되는 큰 직사각형의 둘레가 궁금해졌다. 예를 들어 처음 다섯 개의 타일이 구성하는 직사각형(위에서 빨간색으로 표시한 직사각형)의 둘레는 26이다.

타일의 개수 N이 주어질 때, N개의 타일로 구성된 직사각형의 둘레를 return 하도록 solution 함수를 작성하시오.

풀이 방법:

다음 직사각형의 한 변의 길이는 이전의 두 개의 직사각형 한 변의 길이 합으로 만들어진다. 이 말은 직사각형의 길이가 피보나치 수열을 따른 다는 것이다. 따라서 피보나치 수열을 이용해서 직사각형의 변의 길이를 구한 뒤에 둘레를 구해주면 된다.

1
2
3
4
5
6
7
def solution(N):
    a,b=1,1
    while(N>1):
        a,b=b,a+b
        N-=1
    answer=a*2+b*2
    return answer
cs

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

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

[Programmers]:Lv 3. 예산 (0)	2019.02.25
[Programmers]Lv 2. 구명 보트 (0)	2019.02.24
[Programmers]Lv 2. 숫자 야구 (0)	2019.02.22
[Programmers]Lv 3. 2 X N 타일링 (0)	2019.02.21
[Programmers]Lv 2. 위장 (0)	2019.02.20

문제:

숫자 야구 게임이란 2명이 서로가 생각한 숫자를 맞추는 게임입니다.

각자 서로 다른 1~9까지 3자리 임의의 숫자를 정한 뒤 서로에게 3자리의 숫자를 불러서 결과를 확인합니다. 그 결과를 토대로 상대가 정한 숫자를 예상한 뒤 맞힙니다.

* 숫자가 맞지만, 위치가 틀렸을 때는 볼

* 숫자와 위치가 모두 맞을 때는 스트라이크

* 숫자와 위치가 모두 틀렸을 때는 아웃

질문한 세 자리의 수, 스트라이크의 수, 볼의 수를 담은 2차원 배열 baseball이 매개변수로 주어질 때, 가능한 답의 개수를 return 하도록 solution 함수를 작성해주세요.

풀이 방법:

완전 탐색 문제이므로 모든 경우의 수를 따져주면 된다. 우선 123~987까지 모든 경우를 만들어준다(중복은 허용하지 않는다)

이 후 123에 대해 1S, 1B인 경우들만 살려두고 나머지는 0으로 만들어 제거해버린다. 예를 들면 125이면 2S이므로 0으로 바뀌고 142와 같은 경우가 1S 1B이므로 살려둔다. 이와 같은 방법으로 baseball에 있는 모든 경우를 진행한 뒤 남은 경우의 길이를 반환하면 된다.

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
29
def solution(baseball):
    answer=[]
    for i in range(1,10):
        for j in range(1,10):
            for k in range(1,10):
                if (i==k or i==j or j==k):
                    pass
                else:
                    answer.append(str(i*100+j*10+k))
    for i in baseball:
        for j in range(len(answer)):
            st_cnt=0
            bl_cnt=0
            for k in range(3):
                for l in range(3):
                    if (answer[j][k]==str(i[0])[l] and k==l):
                        st_cnt+=1
                    elif (answer[j][k]==str(i[0])[l] and k!=l):
                        bl_cnt+=1
            if st_cnt==int(i[1]) and bl_cnt==int(i[2]):
                pass
            else:
                answer[j]=0
        answer=list(set(answer))
        if (0 in answer):
            answer.remove(0)
        else:
            pass
    return len(answer)
Colored by Color Scripter
cs

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

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

[Programmers]Lv 2. 구명 보트 (0)	2019.02.24
[Programmers]Lv 3.타일 장식물 (0)	2019.02.23
[Programmers]Lv 3. 2 X N 타일링 (0)	2019.02.21
[Programmers]Lv 2. 위장 (0)	2019.02.20
[Programmers]Lv 1.N으로 표현 (0)	2019.02.19

문제:

가로 길이가 2이고 세로의 길이가 1인 직사각형 모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다.

타일을 가로로 배치 하는 경우

타일을 세로로 배치 하는 경우

직사각형 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요.

풀이 방법:

보통 이러한 문제는 패턴이 있기 때문에 패턴을 찾으려고 했다.

n이 1일때 1가지 방법, 2일 때 2가지 방법, 3일 때 3가지 방법, 4일 때 5가지 방법, 5일 때 8가지 방법...

1,2,3,5,8,13,.....

n이 증가함에 따라 방법의 갯수는 피보나치 수열을 따르면서 증가하고 있었다. 즉 피보나치를 활용해서 풀면 된다. 다음과 같이 간단하게 구할 수 있다.

1
2
3
4
5
def solution(n):
    a,b=1,1
    for i in range(n):
        a,b=b,a+b
    return a%1000000007
cs

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

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

[Programmers]Lv 3.타일 장식물 (0)	2019.02.23
[Programmers]Lv 2. 숫자 야구 (0)	2019.02.22
[Programmers]Lv 2. 위장 (0)	2019.02.20
[Programmers]Lv 1.N으로 표현 (0)	2019.02.19
[Programmers]Lv 2. H-Index (0)	2019.02.18

문제:

스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다.

스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.

풀이 방법:

해시 태그를 가진 문제이므로 clothes를 해시로 바꾸었다. 의상의 이름은 문제에서 크게 필요하지 않으므로 의상의 종류가 몇 개있는지를 나타내는 딕셔너리 타입으로 바꾸었다. 해시 타입인 count에 있으면 그 의상의 종류에 +1을 하고 없다면 새로 추가하도록 하였다.

각 의상별로 갯수를 파악했으면 경우의 수 문제이므로 다음과 같이 구할 수 있다.

입출력의 예시 중 첫번째이다.

eyewear \| headgear	안입는다	yellow_hat	green_turban
안입는다.	안입는다	yellow_hat	green_turban
blue_sunglasses	blue_sunglasses	blue_sunglasses+yellow_hat	blue_sunglasses+green_turban

이 중 하나도 안 입는 경우는 없으므로 이 경우만 제외해야 한다.

즉 각 의상의 종류에 1씩 더한 값들을 모두 곱한 뒤에 하나도 안 입는 경우를 제거해야 하므로 -1을 빼서 반환하도록 한다.

1
2
3
4
5
6
7
8
9
10
11
12
def solution(clothes):
    count={}
    for i in clothes:
        if i[1] in count:
            count[i[1]]+=1
        else:
            count[i[1]]=1
    count_list=count.values()
    answer=1
    for i in count_list:
        answer*=i+1
    return answer-1
cs

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

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

[Programmers]Lv 2. 숫자 야구 (0)	2019.02.22
[Programmers]Lv 3. 2 X N 타일링 (0)	2019.02.21
[Programmers]Lv 1.N으로 표현 (0)	2019.02.19
[Programmers]Lv 2. H-Index (0)	2019.02.18
[Programmers]Lv 2.전화번호 목록 (0)	2019.02.16

문제:

아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.

12 = 5 + 5 +(5/5) +(5/5)

12 = 55/5 + 5/5

12 = (55 + 5)/5

5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.

이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

풀이 방법:

이 문제는 절대로 1단계에 있을 문제라고 생각이 들지 않는다.

숫자를 표현하는 방법에는 총 5가지가 있다.

1. 더하기 2. 곱하기 3. 빼기 4.나누기 5. 숫자 붙이기

따라서 위 방법에 따라 숫자를 생성하는 generator(N,n) 이라는 함수를 만들었다. 이 함수는 숫자 N과 그 숫자를 사용할 횟수 n이 주어지면 N을 n개 사용해서 생기는 모든 경우를 반환해준다.

DP(동적계획법)을 사용하는 문제임을 인지하고 풀었다. 최솟값이 8보다 크면 -1을 반환하기에 경우의 수가 엄청 많지는 않다.

예를 들어 N을 4번 사용해서 number를 만들 수 있다고 하자. generator(N,4) 는 generator(N,3)에다가 N을 하나씩 더 연산해준 것이다. 즉 3+1=4 연산을 했다. 하지만 2+2=4 인 경우도 있다. 하지만 내가 고안한 generator로는 2+2를 바로 얻을 수 없기 때문에 generator(N,2) 2개를 활용해 얻도록 하였다.

또한 작은 경우에서부터 시작하므로 answer의 min 값보다 큰 경우를 시행하는 경우에는 break로 바로 빠져 나오도록 하였다.

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
def generator(N,n):
    answer = [N]
    if n==1:
        return answer
    for i in range(2,n+1):
        temporary=[]
        for j in answer:
            temporary.append(j+N)
            if abs(j-N)!=0:
                temporary.append(abs(j-N))
            a,b=max(j,N),min(j,N)
            temporary.append(a//b)
            temporary.append(j*N)
        answer+=temporary
        answer.append(int(str(N)*i))
    return answer
 
def solution(N, number):
    answer= [9]
    if N==number:
        return 1
    for i in range(1,8):
        if number in generator(N,i):
            answer.append(i)
    for i in range(2,5):
        answer1=generator(N,i)
        for j in range(i,9-i):
            answer2=generator(N,j)
            if min(answer)<i+j:
                pass
            else:
                temporary=[]
                for l in answer2:
                    for k in answer1:
                        temporary.append(k+l)
                        temporary.append(abs(k-l))
                        c,d=max(l,k),min(l,k)
                        if d!=0:
                            temporary.append(c//d)
                        temporary.append(l*k)
                if number in temporary:
                    answer.append(i+j)
    if answer==[9]:
        return -1
    else:
        return min(answer)
        return min(answer)
cs

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

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

[Programmers]Lv 3. 2 X N 타일링 (0)	2019.02.21
[Programmers]Lv 2. 위장 (0)	2019.02.20
[Programmers]Lv 2. H-Index (0)	2019.02.18
[Programmers]Lv 2.전화번호 목록 (0)	2019.02.16
[Programmers]Lv 1.모의고사 (0)	2019.02.15

문제:

H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과에 따르면 H-Index는 다음과 같이 구합니다.

어떤 과학자가 발표한 논문 n 편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h가 이 과학자의 H-Index입니다.

어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요.

풀이 방법:

어려운 알고리즘을 필요를 하지는 않는다. 반복문을 활용해서 풀면 된다. 첫 반복문을 설정할 때 정렬을 한 뒤 citations의 길이부터 거꾸로 진행을 하도록 하였다. 또한 문제에서 딱히 말은 없었지만 H-Index가 여러개라면 최댓값을 리턴해야하므로 배열에 담아서 최대값을 반환하도록 하였다.

1
2
3
4
5
6
7
8
9
10
11
12
13
def solution(citations):
    answer=[]
    citations.sort(reverse=True)
    for i in range(len(citations),0,-1):
        count=0
        for j in citations:
            if j >= i:
                count+=1
        if count <= i:
            answer.append(count)
        else:
            count=0
            answer.append(count)
    return max(answer)
cs

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

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

[Programmers]Lv 2. 위장 (0)	2019.02.20
[Programmers]Lv 1.N으로 표현 (0)	2019.02.19
[Programmers]Lv 2.전화번호 목록 (0)	2019.02.16
[Programmers]Lv 1.모의고사 (0)	2019.02.15
[Programmers]Lv 2. 소수 찾기 (0)	2019.02.14

문제:

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

풀이 방법:

해시를 사용해서 푸는 문제이므로 Python의 set의 특징을 이용한다면 쉽게 풀 수 있었다. Python에서의 set은 중복을 제거해주고, 차집합과 같은 연산도 지원을 해주었다. set을 통해서 중복을 제거할 수 있다는 특징을 이용해서 동명이인이 완주를 못 한 사람인지 아닌지를 판단 할 수 있다. 두 개의 배열에 set을 취한 뒤 차집합을 해주었을 때, 1이라면 동명이인이 범인이 아닌경우이며, 0이라면 동명이인이 범인인 경우이다.

따라서 이를 판별하기 전에 각각의 배열을 정렬해준 뒤에 차집합의 길이가 1이라면 두 개의 차 집합에서 남은 사람이 완주를 하지 못한 사람이며, 0일 경우에는 하나씩 탐색했을 때 서로 다른 부분에서 완주를 하지 못한 사람을 찾을 수 있다.

1
2
3
4
5
6
7
8
9
10
def solution(participant,completion):
    participant.sort()
    completion.sort()
    if not bool(set(participant)-set(completion)):
        for i in range(len(completion)):
            if participant[i]!=completion[i]:
                return participant[i]
    else:
        answer=list(set(participant)-set(completion))[0]
    return answer
Colored by Color Scripter
cs

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

'Algorithm' 카테고리의 다른 글

[BOJ]11559. Puyo Puyo (0)	2021.09.07
[BOJ]3190. 뱀 (0)	2021.08.19
[BOJ]1520. 내리막길 (0)	2021.08.17
[BOJ]1987. 알파벳 (0)	2021.08.10
[BOJ]14425. 문자열 집합 (0)	2021.06.24