문제:

n개의 원소 중에서 k개를 순서 없이 선택하는 방법의 수는 몇 가지 일까?

입력:

입력은 하나 또는 그 이상의 테스트 케이스로 이루어져 있다.

각 테스트 케이스는 한 줄로 이루어져 있으며, 2^31 -1 을 넘지 않는 두 자연수 n (n>=1) 과 k(0<=k<=n)로 이루어져 있다.

입력의 마지막 줄에는 0이 두 개 주어진다.

출력:

각 테스트 케이스에 대해서, 정답을 출력한다. 항상 정답이 2^31보다 작은 경우만 입력으로 주어진다.

풀이 방법:

일반적으로 nCk 를 구하는 문제와 동일하긴 하지만 n과 k의 크기가 많이 크므로 이를 정제하는 작업이 필요하다. 이전 문제에서 nCk를 구할 때 n!/k!*(n-k)!을 통해서 값을 얻는다고 하지만 실제로 사람이 계산할 때는 그렇게 하지 않는다. 10C4가 있다면 10!/4!6!을 통해서 계산을 해야겠지만 사람이라면 약분을 해서 10*9*8*7/4! 으로 구하게 된다. 따라서 이 문제도 약분을 통해서 간략화해야 한다. 또한 nCk=nCn-k와 동일하다는 공식도 존재하므로 k가 일정 값을 넘어가면 이를 통해서 k의 크기를 줄이도록 했다.

1
2
3
4
5
6
7
8
9
10
11
12
while(True):
    m,n=map(int,input().split())
    if m==0 and n==0:
        break
    if m-n<n:
        n=m-n
    answer=1
    for i in range(1,n+1):
        answer*=m
        m-=1
        answer/=i
    print(int(answer))
cs


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

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

[BOJ]10253. 헨리  (0) 2019.05.14
[BOJ]3036. 링  (0) 2019.05.13
[BOJ]2407. 조합  (0) 2019.05.11
[BOJ]1676. 팩토리얼 0의 개수  (0) 2019.05.10
[BOJ]11051. 이항 계수 2  (0) 2019.05.09

문제:

nCm 을 출력한다.

입력:

n과 m이 주어진다. (5<=n<=100,5<=m<100, m<=n)

출력:

nCm을 출력한다.

풀이 방법:

수학 공식으로 (n k)는 n!/k!(n-k)!과 같다. 따라서 math 모듈에 있는 factorial 함수를 이용해서 계산 하였다.

1
2
3
import math
n,m=map(int,input().split())
print(math.factorial(n)//(math.factorial(m)*math.factorial(n-m)))
cs


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

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

[BOJ]3036. 링  (0) 2019.05.13
[BOJ]2591. 이항 쇼다운  (0) 2019.05.12
[BOJ]1676. 팩토리얼 0의 개수  (0) 2019.05.10
[BOJ]11051. 이항 계수 2  (0) 2019.05.09
[BOJ]11050. 이항 계수 1  (0) 2019.05.08

문제:

N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N이 주어진다. (0<=N<=500)

출력:

첫째 줄에 구한 0의 개수를 출력한다.

풀이 방법:

뒷자리에 0이 생기기 위해서는 10을 곱해야 한다. 따라서 N! 중에서 0이 생기는 경우는 크게 두가지가 있다.

1. 10을 곱하는 경우
2. 5의 배수를 곱하는 경우

1번의 경우에는 0이 생기는 것이 자명하므로 설명을 생략한다. 2번의 경우에는 5의 배수의 값과 짝수를 곱하면 10이 생기게 된다. (2 x 5= 10)
즉 이 두경우를 합쳐서 1<=i <=N 인 i에 대해서 5로 나누어떨어질 경우 count를 1 더해주면 된다. 하지만 이 중에는 25와 같이 5의 배수가 두개인 경우도 있으므로 while문을 사용하도록 한다.

1
2
3
4
5
6
7
8
9
10
a=int(input())
answer=0
for i in range(1,a+1):
    while True:
        if i%5==0:
            answer+=1
            i/=5
        else:
            break
print(answer)
cs



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

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

[BOJ]2591. 이항 쇼다운  (0) 2019.05.12
[BOJ]2407. 조합  (0) 2019.05.11
[BOJ]11051. 이항 계수 2  (0) 2019.05.09
[BOJ]11050. 이항 계수 1  (0) 2019.05.08
[BOJ]11866. 조세퍼스 문제0  (0) 2019.05.07

문제:

자연수 N과 정수 K가 주어졌을 때 이항 계수 (N, K)를 10,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N과 K가 주어진다. (1<=N<=1,000, 0<=K<=N)

출력:

(N, K)를 10,007로 나눈 나머지를 출력한다.

풀이 방법:

N의 크기가 커짐에 따라서 더 이상 이항계수 문제를 재귀적방법으로 해결할 수 없다. 일반적으로 재귀함수가 가독성이 좋긴 하지만 동일한 함수를 자주 호출하다보니 N이 커질수록 stack overflow가 발생할 수 있다. 따라서 이를 해결하는 방법으로 dp (메모리제이션) 을 사용한다. 작은 값의 함수들 부터 배열에 값을 저장하면서 원하는 값까지 진행을 하는 방식이다. 
따라서 이항계수1 문제와 풀이는 비슷하나 함수를 호출하는 것이 아닌 배열의 값을 호출한다는 차이가 있다.

1
2
3
4
5
6
7
8
9
10
11
a,b=map(int,input().split())
def bin2(n,k):
    b=[[0 for i in range(k+1)] for j in range(n+1)]
    for i in range(1,n+1):
        for j in range(min(n,k)+1):
            if (j==0 or j==i):
                b[i][j]=1
            else:
                b[i][j]=b[i-1][j-1]+b[i-1][j]
    return b[n][k]%10007
print(bin2(a,b))
cs


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

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

[BOJ]2407. 조합  (0) 2019.05.11
[BOJ]1676. 팩토리얼 0의 개수  (0) 2019.05.10
[BOJ]11050. 이항 계수 1  (0) 2019.05.08
[BOJ]11866. 조세퍼스 문제0  (0) 2019.05.07
[Programmers]Lv 3.디스크 컨트롤러  (2) 2019.05.06

문제:

자연수 N과 정수 K가 주어졌을 때 이항 계수 (N K) 를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N과 K가 주어진다. (1<= N <=10, 0<=K <=N)

출력:

(N K)를 출력한다.

풀이 방법:

이 문제는 이항 계수를 재귀함수로 구현을 해서 풀어야 하는 문제 였다. 파스칼의 법칙에 의해서 이항계수는 다음과 같은 공식을 가진다.

  C(n ,k) =C(n-1,k-1)+C(n-1,k)

따라서 이를 general case, 즉 크기가 감소되는 케이스로 분류를 한다. 또한 이항계수는 C(n,0) ,C(n,n)일 때 항상 1이라는 값을 가진다. 따라서 이 경우는 base case로 재귀가 끝나는 경우로 분류를 한다.


1
2
3
4
5
6
7
8
9
10
11
a,b=map(int,input().split())
 
def binomial(n,k):
    if n==k:
        return 1
    elif k==0:
        return 1
    else:
        return binomial(n-1,k-1)+binomial(n-1,k)
    
print(binomial(a,b))
cs


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

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

[BOJ]1676. 팩토리얼 0의 개수  (0) 2019.05.10
[BOJ]11051. 이항 계수 2  (0) 2019.05.09
[BOJ]11866. 조세퍼스 문제0  (0) 2019.05.07
[Programmers]Lv 3.디스크 컨트롤러  (2) 2019.05.06
[BOJ]8979. 올림픽  (0) 2019.05.05

문제:

조세퍼스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(<=N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N,K)-조세퍼스 순열이라고 한다. 예를 들어 (7,3)-조세퍼스 순열은 <3, 6, 2, 7, 5, 1, 4> 이다.

N과 K가 주어지면 (N, K)-조세퍼스 순열을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1<=K<=N<=1,000)

출력:

예제와 같이 조세퍼스 순열을 출력한다.

풀이 방법:

 값을 빼기 전에 미리 idx를 저장을 해두는 것이 중요하다. 값을 먼저 빼버리면 다음 순환 반복을 못하기 때문이다. 또한 빼준 다음에는 idx 를 1 감소해서 인덱스가 하나 줄었음을 나타낸다. 또한 값을 뺄 당시에 출력 예시와 동일하게 만들어야 하므로 끝 값에만 따로 케이스를 분류를 해두었다.

이 문제는 태그가 큐로 되어 있었는데 아마도 순환 큐를 이용해서 풀어야 하는 문제인 것 같다.

1
2
3
4
5
6
7
8
9
10
11
12
a,b=map(int,input().split())
answer=list(range(1,a+1))
idx=-1
print("<",end="")
while(len(answer)!=0):
    idx+=b
    idx=idx%(len(answer))
    if len(answer)==1:
        print(answer.pop(idx),end=">")
    else:
        print(answer.pop(idx),end=", ")
    idx-=1
cs


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

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

[BOJ]11051. 이항 계수 2  (0) 2019.05.09
[BOJ]11050. 이항 계수 1  (0) 2019.05.08
[Programmers]Lv 3.디스크 컨트롤러  (2) 2019.05.06
[BOJ]8979. 올림픽  (0) 2019.05.05
[BOJ]1076. 저항  (0) 2019.05.04

문제:

올림픽은 참가에 의의가 있기에 공식적으로는 국가간 순위를 정하지 않는다. 그러나, 많은 사람들이 자신의 국가가 얼마나 잘 하는지에 관심이 많기 때문에 비공식적으로는 국가간 순위를 정하고 있다. 두 나라가 각각 얻은 금, 은, 동메달 수가 주어지면, 보통 다음 규칙을 따라 어느 나라가 더 잘 했는지 결정한다.

1. 금메달 수가 더 많은 나라
2. 금메달 수가 같으면, 은메달 수가 더 많은 나라
3. 금, 은메달 수가 모두 같으면, 동메달 수가 더 많은 나라

각 국가는 1부터 N 사이의 정수로 표현한다. 한 국가의 등수는 (자신보다 더 잘한 나라 수) + 1로 정의된다. 만약 두 나라가 금, 은, 동메달 수가 모두 같다면 두 나라의 등수는 같다. 예를 들어, 1번 국가가 금메달 1개, 은메달 1개를 얻었고, 2번 국가와 3번 국가가 모두 은메달 1개를 얻었으며, 4번 국가는 메달을 얻지 못하였다면, 1번 국가가 1등, 2번 국가와 3번 국가가 공동 2등, 4번 국가가 4등이 된다. 이 경우 3등은 없다.

각 국가의 금, 은, 동메달 정보를 입력받아서, 어느 국가가 몇 등을 했는지 알려주는 프로그램을 작성하시오.

입력:

입력의 첫 줄은 국가의 수 N(1<=N<=1,000)과 등수를 알고 싶은 국가 K(1<=K<=N)가 빈칸을 사이에 두고 주어진다. 각 국가는 1부터 N 사이의 정수로 표현된다. 이후 N개의 각 줄에는 차례대로 각 국가를 나타내는 정수와 이 국가가 얻은 금, 은, 동메달의 수가 빈칸을 사이에 두고 주어진다. 전체 메달 수의 총합은 1,000,000 이하이다.

출력:

출력은 단 한 줄이며, 입력받은 국가 K의 등수를 하나의 정수로 출력한다. 등수는 반드시 문제에서 정의된 방식을 따라야 한다.

풀이 방법:

입력을 받는 값을 다 유지를 해야 하고, 금메달 > 은메달 > 동메달 가중치 순으로 정렬을 해줘야 한다. 정렬을 하기 전에 원하는 나라의 정보를 미리 temp에 저장을 해둔다. 가중치에 따라 정렬을 하고 temp에 저장해둔 금메달, 은메달, 동메달과 같은 값을 찾을 때까지(공동 순위가 존재하므로 꼭 temp의 나라가 아니라도 괜찮다.) count를 증가시킨다. 이후 같은 값을 만나면 count를 출력하고 종료한다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
a,b=map(int,input().split())
countries=[]
for i in range(a):
    check=list(map(int,input().split()))
    if check[0]==b:
        temp=check
    countries.append(check)
countries.sort(key=lambda x: (x[1],x[2],x[3]),reverse=True)
count=0
for i in countries:
    count+=1
    if i[1]<=temp[1] and i[2]<=temp[2] and i[3]<=temp[3]:
        print(count)
        break
cs


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

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

[BOJ]11866. 조세퍼스 문제0  (0) 2019.05.07
[Programmers]Lv 3.디스크 컨트롤러  (2) 2019.05.06
[BOJ]1076. 저항  (0) 2019.05.04
[BOJ]1977. 완전제곱수  (0) 2019.05.03
[BOJ]1037. 약수  (0) 2019.05.02

문제:

전자 제품에는 저항이 들어간다. 저항은 색 3개를 이용해서 그 저항이 몇 옴인지 나타낸다.
처음 색 2개는 저항의 값이고, 마지막 색은 곱해야 하는 값이다.
저항의 값은 다음 표를 이용해서 구한다.

 색

값 

곱 

black 

0 

1 

brown 

1 

10 

red 

2 

100 

orange 

3 

1000 

yellow 

4 

10000 

green 

5 

100000 

blue 

6 

1000000 

violet 

7 

10000000 

grey 

8 

100000000 

white                                                        9                                                              1000000000


예를 들어, 저항에 색이 yellow, violet, red였다면 저항의 값은 4,700이 된다.


입력:

첫째 줄에 첫 번째 색, 둘째 줄에 두 번째 색, 셋째 줄에 세 번째 색이 주어진다. 색은 모두 위의 표에 쓰여 있는 색만 주어진다.


출력:

입력으로 주어진 저항의 저항값을 계산하여 첫째 줄에 출력한다.

풀이 방법:

항상 세 개의 명령을 받기 때문에 하나의 명령어 함수를 만들고 마지막 명령어일때에만 따로 구분을 두어서 곱하도록 만든다.
따라서 register라는 전역변수를 만든 후에 첫 번째, 두 번째 명령어일 때 이 값에 더해준다.

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
48
49
50
51
52
53
first=input()
second=input()
third=input()
register=''
def regis(first,last=True):
    global register
    if last==True:
        if first=="black":
            register+='0'
        elif first=="brown":
            register+='1'
        elif first=="red":
            register+='2'
        elif first=="orange":
            register+='3'
        elif first=="yellow":
            register+='4'
        elif first=="green":
            register+='5'
        elif first=="blue":
            register+='6'
        elif first=="violet":
            register+='7'
        elif first=="grey":
            register+='8'
        elif first=="white":
            register+='9'
    else:
        register=int(register)
        if first=="black":
            register*=1
        elif first=="brown":
            register*=10
        elif first=="red":
            register*=100
        elif first=="orange":
            register*=1000
        elif first=="yellow":
            register*=10000
        elif first=="green":
            register*=100000
        elif first=="blue":
            register*=1000000
        elif first=="violet":
            register*=10000000
        elif first=="grey":
            register*=100000000
        elif first=="white":
            register*=1000000000
        print(register)
regis(first)
regis(second)
regis(third,False)
cs


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

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

[Programmers]Lv 3.디스크 컨트롤러  (2) 2019.05.06
[BOJ]8979. 올림픽  (0) 2019.05.05
[BOJ]1977. 완전제곱수  (0) 2019.05.03
[BOJ]1037. 약수  (0) 2019.05.02
[BOJ]2156. 포도주 시식  (0) 2019.05.01

문제:

M과 N이 주어질 때 M이상 N이하의 자연수 중 완전제곱수인 것을 모두 골라 그 합을 구하고 그 중 최솟값을 찾는 프로그램을 작성하시오. 예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 완전제곱수는 64, 81, 100 이렇게 총 3개가 있으므로 그 합은 245가 되고 이 중 최솟값은 64가 된다.

입력:

첫째 줄에 M이, 둘째 줄에 N이 주어진다. M과 N은 10,000이하의 자연수이며 M은 N보다 같거나 작다.

출력:

M이상 N이하의 자연수 중 완전제곱수인 겻을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 완전제곱수가 없을 경우는 첫째 줄에 -1을 출력한다.

풀이 방법:

math의 sqrt를 사용해서 풀어야 하는 문제이다. 첫 숫자 M의 sqrt를 구한 후 floor함수를 써서 lower_bound 값을 구하고, N에 sqrt를 구한 후 ceil 함수를 써서 upper_bound를 구한다. 이 구간을 반복문을 돌리면서 합을 구한 뒤에 더해진 answer 값이 없다면 -1을 출력하고 더해진 값이 있다면 upper_bound의 제곱수 값을 출력다.

1
2
3
4
5
6
7
8
9
10
11
12
13
import math
lower=int(input())
upper=int(input())
lower_bound=int(math.ceil(math.sqrt(lower)))
upper_bound=int(math.floor(math.sqrt(upper)))
answer=0
for i in range(lower_bound,upper_bound+1):
    answer+=i*i
if answer!=0:
    print(answer)
    print(lower_bound*lower_bound)
else:
    print(-1)
cs


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

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

[BOJ]8979. 올림픽  (0) 2019.05.05
[BOJ]1076. 저항  (0) 2019.05.04
[BOJ]1037. 약수  (0) 2019.05.02
[BOJ]2156. 포도주 시식  (0) 2019.05.01
[BOJ]2193. 이친수  (0) 2019.04.30

문제:

양수 A가 N의 진짜 약수가 되려면, N이 A의 배수이고, A가 1과 N이 아니어야 한다. 어떤 수 N의 진짜 약수가 모두 주어질 때, N을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되지 않는다.

출력:

첫째 줄에 N을 출력한다. N은 항상 32비트 부호있는 정수로 표현할 수 있다.

풀이 방법:

진짜 약수는 1과 N을 포함하고 있지 않으므로 진짜 약수들을 정렬한 뒤에 가장 첫값과 가장 마지막 값을 곱한 값이 N이 될 것이다. 

1
2
3
a=int(input())
answer=sorted(list(map(int,input().split())))
print(answer[0]*answer[-1])
cs


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

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

[BOJ]1076. 저항  (0) 2019.05.04
[BOJ]1977. 완전제곱수  (0) 2019.05.03
[BOJ]2156. 포도주 시식  (0) 2019.05.01
[BOJ]2193. 이친수  (0) 2019.04.30
[BOJ]1003. 피보나치 함수  (0) 2019.04.26

+ Recent posts

티스토리툴바