728x90
반응형

문제:

주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.

풀이 방법:

nums를 3개의 for를 사용해서 nums 중 3개를 골라 더한 경우의 수를 구할 수 있다. 그리고 이 경우의 수들을 is_prime에 라는 함수에 넣어 소수인지 하나씩 판별을 한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def is_prime(x):
    if x > 1:
        for i in range(2, x):
            if x % i == 0:
                return False
    else:
        return False
    return True
 
def solution(nums):
    answer_list=[]
    for i in range(len(nums)-2):
        for j in range(i+1,len(nums)-1):
            for k in range(j+1,len(nums)):
                answer_list.append(nums[i]+nums[j]+nums[k])
    count=0
    for i in answer_list:
        if is_prime(i):
            count+=1 
        else:
            pass
    return count
cs


728x90
반응형
저작자표시 비영리 동일조건

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

[Programmers]Lv 2. 영어 끝말잇기  (0) 2019.03.28
[Programmers]Lv 2. 점프와 순간이동  (0) 2019.03.27
[Programmers]Lv 3.단어 변환  (0) 2019.03.25
[Programmers]Lv 2. N개의 최소공배수  (0) 2019.03.24
[Programmers]Lv 3. 숫자 게임  (0) 2019.03.23
728x90
반응형

문제:

두 개의 단어 begin,target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.

예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"] 라면 "hit" -> "hot" -> "dot" ->"dog" ->"cog"와 같이 4단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin,target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

풀이 방법:

깊이/너비 우선 탐색(DFS/BFS) 중 너비 우선 탐색을 사용하는 문제이다. begin에서 변환 할 수 있는 경우의 수를 만들어 주고 이 중에서 target이 있는지 확인한다. 없다면 이 경우의 수를 누적하여 다음 단계를 진행한다. 즉 1단계에서 만들어질수 있는 모든 경우, 2단계에서 만들어지는 경우..가 되는 것이다. 어짜피 target이 있는 층만 알면 되기에 문제 없다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def solution(begin,target,words):
    answer=[begin]
    if target not in words:
        return 0
    answer_count=0
    while(len(words)!=0):
        for i in answer:
            temp=[]
            for word in words:
                count=0
                for j in range(len(i)):
                    if i[j]!=word[j]:
                        count+=1
                    if count==2:
                        break
                if count==1:
                    temp.append(word)
                    words.remove(word)
        answer_count+=1
        if target in temp:
            return answer_count
        else:
            answer=temp
    return 0
cs


728x90
반응형
저작자표시 비영리 동일조건

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

[Programmers]Lv 2. 점프와 순간이동  (0) 2019.03.27
[Programmers]Lv 2.소수 만들기  (0) 2019.03.26
[Programmers]Lv 2. N개의 최소공배수  (0) 2019.03.24
[Programmers]Lv 3. 숫자 게임  (0) 2019.03.23
[Programmers]Lv 2.JadenCase 문자열 만들기  (0) 2019.03.22
728x90
반응형

문제:

두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.

풀이 방법:

일단 최소공배수를 구하기 위해서 최대공약수(gcd)를 구하는 함수도 필요하다. 왜냐하면 최소공배수는 두 수의 곱을 최대공약수로 나눈 값과 같기 때문이다. N개의 최소공배수를 구하는 것도 크게 다르지 않다. N개가 있다면 그 중 계속 2개를 골라서 최소공배수를 구하고 그 값을 다시 arr 배열에 담는다. 이 과정을 arr의 원소가 1개가 남을 때까지 하면 그 남은 원소가 N개의 수들의 최소공배수가 되는 것이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
def gcd(a,b):
    a,b=max(a,b),min(a,b)
    while b > 0:
        a,b=b,a%b
    return a
def solution(arr):
    while len(arr) !=1:
        a=arr.pop()
        b=arr.pop()
        c=gcd(a,b)
        arr.insert(0,int(a*b/c))
    answer=arr[0]
    return answer
cs


728x90
반응형
저작자표시 비영리 동일조건

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

[Programmers]Lv 2.소수 만들기  (0) 2019.03.26
[Programmers]Lv 3.단어 변환  (0) 2019.03.25
[Programmers]Lv 3. 숫자 게임  (0) 2019.03.23
[Programmers]Lv 2.JadenCase 문자열 만들기  (0) 2019.03.22
[Programmers]Lv 3.짝지어 제거하기  (0) 2019.03.21
728x90
반응형

문제:

xx 회사의 2xN명의 사원들은 N명씩 두 팀으로 나눠 숫자 게임을 하려고 합니다. 두 개의 팀을 각각 A팀과 B팀이라고 하겠습니다. 숫자 게임의 규칙은 다음과 같습니다.

먼저 모든 사원이 무작위로 자연수를 하나씩 부여받습니다.
각 사원은 딱 한 번씩 경기를 합니다.
각 경기당 A팀에서 한 사원이, B팀에서 한 사원이 나와 서로의 수를 공개합니다. 그때 숫자가 큰 쪽이 승리하게 되고, 승리한 사원이 속한 팀은 승점을 1점 얻게 됩니다.
만약 숫자가 같다면 누구도 승점을 얻지 않습니다.

전체 사원들은 우선 무작위로 자연수를 하나씩 부여받았습니다. 그 다음 A팀은 빠르게 출전순서를 정했고 자신들의 출전 순서를 B팀에게 공개해버렸습니다. B팀은 그것을 보고 자신들의 최종 승점을 가장 높이는 방법으로 팀원들의 출전 순서를 정했습니다. 이때의 B팀이 얻는 승점을 구해주세요.
A 팀원들이 부여받은 수가 출전 순서대로 나열되어있는 배열 A와 i번째 원소가 B팀의 i번 팀원이 부여받은 수를 의미하는 배열 B가 주어질 때,B 팀원들이 얻을 수 있는 최대 승점을 return 하도록 solution 함수를 완성해주세요.

풀이 방법:

B팀이 최대한 많이 이기려면 A팀의 숫자와 많이 차이 나지 않게 이기는 것이 중요하다. 즉 예를 들어서 A팀의 숫자가 4이고 B팀의 숫자 중에 5와 9가 남아 있다면 둘 중 어느 것을 내도 이기지만 5를 내서 이겨 9를 아끼는 방법을 사용하는 것이다. A,B를 내림차순으로 정렬을 하고, 각 A의 원소당 최소 차이가 나는 B를 선택한다. 만약 A의 값이 더 크다면 그냥 넘어가지만 A를 이기는 B가 있다면 그 값을 제거하고 answer을 1 증가시킨다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def solution(A, B):
    answer = 0
    A=sorted(A,reverse=True)
    B=sorted(B,reverse=True)
    for i in A:
        v_min=i
        for j in range(len(B)):
            if B[j]>v_min:
                v_min=B[j]
            else:
                break
        if v_min==i:
            pass
        else:
            B.remove(v_min)
            answer+=1
    return answer
cs


728x90
반응형
저작자표시 비영리 동일조건

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

[Programmers]Lv 3.단어 변환  (0) 2019.03.25
[Programmers]Lv 2. N개의 최소공배수  (0) 2019.03.24
[Programmers]Lv 2.JadenCase 문자열 만들기  (0) 2019.03.22
[Programmers]Lv 3.짝지어 제거하기  (0) 2019.03.21
[Programmers]Lv 2.행렬의 곱셈  (0) 2019.03.20
728x90
반응형

문제:

JadenCase란 모든 단어의 첫 문자가 대문자이고, 그 외의 알파벳은 소문자인 문자열입니다. 문자열 s가 주어졌을 때, s를 JadenCase로 바꾼 문자열을 리턴하는 함수, solution을 완성해주세요.

풀이 방법:

처음엔 title 함수를 사용하고자 했다. title은 문자열에서 각 단어의 첫단어를 대문자로 만드는 내장함수이다. 하지만 첫번째 입출력 예시와 같이 첫 문자가 숫자라면 그 다음 문자를 소문자로 유지해야 하지만 title은 대문자로 리턴을 해버린다.
그 이후로는 split 공백을 지우고 첫 단어만 대문자로 만든 뒤(숫자에도 upper 연산이 가능하다) 이를 배열에 담아 join으로 담으려고 했으나, 공백이 하나가 아닌 2개이상일 수도 있었다.
따라서 최종적으론 upper라는 bool 변수를 만들어서 공백을 만나면 True로 켜지고 upper연산을 하고 난 뒤에는 False로 꺼지게 하였다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def solution(s):
    s=s.lower()
    a=''
    upper=True
    for i in s:
        if upper:
            if i==" ":
                a+=i
                continue
            a+=i.upper()
            upper=False
        else:
            if i==" ":
                a+=i
                upper=True
            else:
                a+=i
    return a
cs


728x90
반응형
저작자표시 비영리 동일조건

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

[Programmers]Lv 2. N개의 최소공배수  (0) 2019.03.24
[Programmers]Lv 3. 숫자 게임  (0) 2019.03.23
[Programmers]Lv 3.짝지어 제거하기  (0) 2019.03.21
[Programmers]Lv 2.행렬의 곱셈  (0) 2019.03.20
[Programmers]Lv 3.최고의 집합  (0) 2019.03.19
728x90
반응형

문제:

짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다.

예를 들어, 문자열 S=baabaa라면 

baabaa -> bbaa -> aa ->

의 순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다.

풀이 방법:

스택의 개념을 이용해서 풀었다. 문자열 s를 한 개씩 answer_list에 넣으면서 끝 두 값이 일치하면 제거하고 그렇지 않다면 유지한채로 다시 쌓는 방식이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def solution(s):
    answer_list=[]
    s=list(s)
    idx=0
    while(idx!=len(s)):
        answer_list.append(s[idx])
        idx+=1
        if len(answer_list)>1:
            if (answer_list[-1]==answer_list[-2]):
                answer_list.pop()
                answer_list.pop()      
    if len(answer_list)==0:
        return 1
    else:
        return 0
cs


728x90
반응형
저작자표시 비영리 동일조건

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

[Programmers]Lv 3. 숫자 게임  (0) 2019.03.23
[Programmers]Lv 2.JadenCase 문자열 만들기  (0) 2019.03.22
[Programmers]Lv 2.행렬의 곱셈  (0) 2019.03.20
[Programmers]Lv 3.최고의 집합  (0) 2019.03.19
[Programmers]Lv 2. 피보나치 수  (0) 2019.03.18
728x90
반응형

문제:

2차원 행렬 arr1과 arr2를 입력받아, arr1에 arr2를 곱합 결과를 반환하는 함수, solution을 완성해주세요,


풀이 방법:


행렬의 곱셈을 구하는 방법은 위와 같다. 이를 구현하기 위해서 미리 0행렬인 C를 만들어두고 곱셈값들을 더하는 방식으로 구현하였다.


1
2
3
4
5
6
7
8
9
10
11
12
def solution(arr1, arr2):
    C=[]
    for m in range(len(arr1)):
        C.append([0,0])
        while len(C[m]) < len(arr2[0]):
            C[m].append(0)
    for i in range(len(arr1)):
        for j in range(len(arr2[0])):
            for k in range(len(arr1[0])):
                C[i][j]+=arr1[i][k]*arr2[k][j]
 
    return C
cs


728x90
반응형
저작자표시 비영리 동일조건

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

[Programmers]Lv 2.JadenCase 문자열 만들기  (0) 2019.03.22
[Programmers]Lv 3.짝지어 제거하기  (0) 2019.03.21
[Programmers]Lv 3.최고의 집합  (0) 2019.03.19
[Programmers]Lv 2. 피보나치 수  (0) 2019.03.18
[Programmers]Lv 3.줄 서는 방법  (0) 2019.03.17
728x90
반응형

문제:

자연수 n 개로 이루어진 집합 중에 다음 두 조건을 만족하는 집합을 최고의 집합이라고 합니다.

1.각 원소의 합이 S가 되는 수의 집합
2.위 조건을 만족하면서 각 원소의 곱이 최대가 되는 집합

예를 들어서 자연수 2개로 이루어진 집합 중 합이 9가 되는 집합은 다음과 같이 4개가 있습니다.

{1,8},{2,7},{3,6},{4,5}

그중 각 원소의 곱이 최대인 {4,5}가 최고의 집합입니다.

집합의 원소의 개수 n과 모든 원소들의 합 s가 매개변수로 주어질 때, 최고의 집합을 return 하는 solution 함수를 완성해주세요.

풀이 방법:

합이 s가 되는 것을 만드는 것은 어렵지 않다. 원소의 곱이 최대가 만드는 것이 중요한데, 하나의 큰 수를 만들면(예시 중 8)이 작은 수가 생길 수 밖에 없다(예시 중1). 즉 모든 원소들이 골고루 높을 경우에 원소의 곱이 최대가 되는 것이다. 따라서 s를 n으로 균등하게 나누어서 몫으로 answer을 길이 n만큼 만들고 나머지 부분들을 answer을 순환하며 1씩 더해주면 그 집합이 원소의 합이 s가 되며 곱이 최대가 되는 집합이 된다.
1
2
3
4
5
6
7
8
def solution(n, s):
    if n > s:
        return [-1]
    [portion,remain]=divmod(s,n)
    answer=[portion]*n
    for i in range(remain):
        answer[i]+=1
    return sorted(answer)
cs


728x90
반응형
저작자표시 비영리 동일조건

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

[Programmers]Lv 3.짝지어 제거하기  (0) 2019.03.21
[Programmers]Lv 2.행렬의 곱셈  (0) 2019.03.20
[Programmers]Lv 2. 피보나치 수  (0) 2019.03.18
[Programmers]Lv 3.줄 서는 방법  (0) 2019.03.17
[Programmers]Lv 2. 최솟값 만들기  (0) 2019.03.16
728x90
반응형

문제:

피보나치 수는 F(0)=0, F(1)=1일 때, 1 이상의 n에 대하여 F(n)=F(n-1)+F(n-2) 가 적용되는 수 입니다.


예를 들어


F(2)= F(0)+F(1)=0+1=1

F(3)= F(1)+F(2)=1+1=2

F(4)= F(2)+F(3)=1+2=3

F(5)= F(3)+F(4)=2+3=5


와 같이 이어집니다.


2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.


풀이 방법:

일반적으로 피보나치 수열을 푸는 방법으로 재귀를 많이 사용한다. 하지만 재귀 문제의 경우에는 일부 유형에는 좋은 효율을 보여주지만 적어도 피보나치 수열에서는 숫자가 커질수록 시간이 많이 걸린다. 따라서 이번에는 파이썬의 특성을 이용해서 빠르게 구할 수 있는 방법을 소개 하려고 한다.
파이썬에서는 a,b=b,a와 같이 값이 변경하는 것이 가능하다. 따라서 이를 이용해서 피보나치 수열을 풀 수 있다.

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


728x90
반응형
저작자표시 비영리 동일조건

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

[Programmers]Lv 2.행렬의 곱셈  (0) 2019.03.20
[Programmers]Lv 3.최고의 집합  (0) 2019.03.19
[Programmers]Lv 3.줄 서는 방법  (0) 2019.03.17
[Programmers]Lv 2. 최솟값 만들기  (0) 2019.03.16
[Programmers]Lv 3. 야근 지수  (2) 2019.03.15
728x90
반응형

문제:

n명의 사람이 일렬로 줄을 서고 있습니다. n명의 사람들에게는 각각 1번부터 n번까지 번호가 매겨져 있습니다. n명의 사람이 줄을 서는 방법은 여러가지 방법이 있습니다. 예를 들어서 3명의 사람이 있다면 다음과 같이 6개의 방법이 있습니다.

[1,2,3]
[1,3,2]
[2,1,3]
[2,3,1]
[3,1,2]
[3,2,1]

사람의 수 n과 자연수 k가 주어질 때, 사람을 나열 하는 방법을 사전 순으로 나열 했을 때, k번째 방법을 return하는 solution 함수를 완성해주세요.

풀이 방법:

1번부터 n명까지 줄을 서는 총 경우의 수를 보면 맨 앞에 서 있는 사람이 m번인 경우는 보통 (n-1)!개씩 있다.
왜냐하면 1번부터 n명까지 줄을 서는 총 경우의 수는 n!개 일 때, 맨 앞의 수를 임의의 m으로 잡고 난 뒤 나머지 수들을 배열하는 방법은 (n-1)! 이기 때문이다.
따라서 k를 (n-1)!으로 나눈다면 k번째 방법이 어떤 임의의 수 m번이 맨 앞으로 오는지 알 수 있게 된다. 맨 앞의 수를 정한 뒤 그 뒤에 올 수들도 앞의 방법가 동일하게 정해주면 사전순으로 나열이 될 것이다. k를 (n-1)!으로 나누고 몫은 맨 앞의 수를 정하는데 사용하고 나머지는 다시 한번 ((n-1)-1)!으로 나누어서 다음 수를 정해주는 방식으로 진행 하면 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
def solution(n,k):
    import math as m
    num_list=list(range(1,n+1))
    answer_list=[]
    while n > 0:
        n-=1
        p,r=divmod(k,m.factorial(n))
        if r == 0:
            p-=1
        answer_list.append(num_list[p])
        num_list.remove(num_list[p])
        k=r
    return answer_list
cs


728x90
반응형
저작자표시 비영리 동일조건

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

[Programmers]Lv 3.최고의 집합  (0) 2019.03.19
[Programmers]Lv 2. 피보나치 수  (0) 2019.03.18
[Programmers]Lv 2. 최솟값 만들기  (0) 2019.03.16
[Programmers]Lv 3. 야근 지수  (2) 2019.03.15
[Programmers]Lv 2. 최댓값과 최솟값  (0) 2019.03.14

+ Recent posts

티스토리툴바