문제:

00 연구소는 한 번에 K 칸을 앞으로 점프하거나,(현재까지 온 거리) x 2에 해당하는 위치로 순간이동을 할 수 있는 특수한 기능을 가진 아이언 슈트를 개발하여 판매하고 있습니다. 이 아이언 슈트는 건전지로 작동되는데, 순간 이동을 하면 건전지 사용량이 줄지 않지만, 앞으로 K 칸을 점프하면 K 만큼의 건전지 사용량이 듭니다. 그러므로 아이언 슈트를 착용하고 이동할 때는 순간 이동을 하는 것이 더 효율적입니다. 아이언 슈트 구매자는 아이언 슈트를 착용하고 거리가 N 만큼 떨어져 있는 장소로 가려고 합니다. 단, 건전지 사용량을 줄이기 위해 점프로 이동하는 것은 최소로 하려고 합니다. 아이언 슈트 구매자가 이동하려는 거리 N이 주어졌을 때, 사용해야 하는 건전지 사용량의 최솟값을 return하는 solution 함수를 만들어 주세요.

예를 들어 거리가 5만큼 떨어져 있는 장소로 가려고 합니다.
아이언 슈트를 입고 거리가 5만큼 떨어져 있는 장소로 갈 수 있는 경우의 수는 여러가지입니다.

* 처음 위치 0에서 5칸을 앞으로 점프하면 바로 도착하지만, 건전지 사용량이 5만큼 듭니다.
* 처음 위치 0에서 2칸을 앞으로 점프한 다음 순간이동 하면 (현재까지 온 거리: 2) x 2에 해당하는 위치로 이동할 수 있으므로 위치 4로 이동합니다. 이때 1칸을 앞으로 점프하면 도착하므로 건전지 사용량이 3만큼 듭니다.
* 처음 위치 0에서 1칸을 앞으로 점프한 다음 순간이동 하면(현재까지 온 거리: 1) x 2에 해당하는 위치로 이동할 수 있으므로 위치 2로 이동합니다. 이때 다시 순간이동 하면 (현재까지 온 거리: 2) x 2만큼 이동할 수 있으므로 위치 4로 이동합니다. 이 때 1칸을 앞으로 점프하면 도착하므로 건전지 사용량이 2만큼 듭니다.

위의 3가지 경우 거리가 5만큼 떨어져 있는 장소로 가기 위해서 3번째 경우가 건전지 사용량이 가장 적으므로 답은 2가 됩니다.

풀이 방법:

건전지 사용량을 적게 사용하려면 순간 이동을 많이 사용할 수록 좋다. 따라서 거리가 1, 2 ,4 ,8 ,16,.......과 같은 경우 건전지 사용량이 1이 되게 된다. 처음에만 점프를 하고 그 뒤부턴 계속 순간 이동을 하면 되기 때문이다. 이 점에서 규칙을 찾을 수 있었다. 거리를 2진수의 숫자로 바꿨을 때 1의 갯수가 필요한 점프의 갯수이다. 점프의 갯수가 건전지의 사용량이 되기 때문에 답이 된다.

1
2
3
4
5
6
def solution(n):
    ans=0
    while (n!=0):
        n,b=divmod(n,2)
        ans+=b
    return ans
cs


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

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

[Programmers]Lv 2. 라면공장  (0) 2019.03.29
[Programmers]Lv 2. 영어 끝말잇기  (0) 2019.03.28
[Programmers]Lv 2.소수 만들기  (0) 2019.03.26
[Programmers]Lv 3.단어 변환  (0) 2019.03.25
[Programmers]Lv 2. N개의 최소공배수  (0) 2019.03.24

문제:

주어진 숫자 중 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


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

'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

문제:

두 개의 단어 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


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

'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

문제:

두 수의 최소공배수(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


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

'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

문제:

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


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

'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

문제:

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


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

'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

문제:

짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 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


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

'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

문제:

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


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

'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

문제:

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


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

'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

문제:

피보나치 수는 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


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

'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

+ Recent posts

티스토리툴바