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
반응형
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
반응형
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
반응형
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
반응형
728x90
반응형

문제:

길이가 같은 배열 A,B 두개가 있습니다. 각 배열은 자연수로 이루어져 있습니다. 배열 A,B에서 각각 한 개의 숫자를 뽑아 두 수를 곱합니다. 이러한 과정을 배열의 길이만큼 반복하며, 두 수를 곱한 값을 누적하여 더합니다. 이때 최종적으로 누적된 값이 최소가 되도록 만드는 것이 목표입니다. (단, 각 배열에서 k번째 숫자를 뽑았다면 다음에 k번째 숫자는 다시 뽑을 수 없습니다.)

예를 들어 A=[1,4,2], B=[5,4,4] 라면

* A에서 첫번째 숫자인 1, B에서 첫번째 숫자인 5를 뽑아 곱하여 더합니다. (누적된 값: 0 + 5(1x5) = 5)
* A에서 두번째 숫자인 4, B에서 두번째 숫자인 4를 뽑아 곱하여 더합니다. (누적된 값: 5 + 16(4x4) = 21)
* A에서 세번째 숫자인 2, B에서 세번째 숫자인 4를 뽑아 곱하여 더합니다. (누적된 값: 21 + 8(2x4) = 29)

즉, 이 경우가 최소가 되므로 29를 return 합니다.

배열 A,B가 주어질 때 최종적으로 누적된 최솟값을 return 하는 solution 함수를 완성해주세요.

풀이 방법:

 최소값을 만들기 위해서는 A에서 작은 값을 선택하면 B에서 가장 큰 값을 골라서 곱하는 방식으로 누적하는 것이 가장 최소가 된다.

1
2
3
4
5
6
7
def solution(A,B):
    answer=0
    A.sort()
    B.sort(reverse=True)
    for i in range(len(A)):
        answer+=A[i]*B[i]
    return answer
cs


728x90
반응형

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

[Programmers]Lv 2. 피보나치 수  (0) 2019.03.18
[Programmers]Lv 3.줄 서는 방법  (0) 2019.03.17
[Programmers]Lv 3. 야근 지수  (2) 2019.03.15
[Programmers]Lv 2. 최댓값과 최솟값  (0) 2019.03.14
[Programmers]Lv 3. 방문길이  (0) 2019.03.13
728x90
반응형

문제:

회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도를 최소화하도록 일할 겂니다. Demi가 1시간 동안 작업량 1만큼을 처리할 수 있다고 할 때, 퇴근까지 남은 N 시간과 각 일에 대한 작업량 works에 대해 야근 피로도를 최소화한 값을 리턴하는 함수 solution을 완성해주세요.

풀이 방법:

야근 지수를 최소화하려면 일정 값들을 0으로 바꾸는 것보다 각 원소들을 가능한 작게 만드는 것이 더 도움이 된다. 즉 n만큼의 수를 감소시키는 것을 몇 개의 값들에 집중해서 하는 것이 아니라 골고루 사용해야 하는 것이다. 따라서 n번 works의 최댓값을 1씩 빼주는 작업을 하면 된다.

1
2
3
4
5
6
7
8
9
10
def solution(n, works):
    answer = 0
    if n > sum(works):
        return answer
    for i in range(n):
        works.sort()
        works[-1]-=1
    for i in works:
        answer+=i*i
    return answer
cs


728x90
반응형
728x90
반응형

문제:

문자열 s에는 공백으로 구분된 숫자들이 저장되어 있습니다. str에 나타나는 숫자 중 최소값과 최대값을 찾아 이를 "(최소값) (최대값)"형태의 문자열을 반환하는 함수, solution을 완성하세요.
예를 들어 s가 "1 2 3 4"라면 "1 4"를 리턴하고, "-1 -2 -3 -4"라면 "-4 1"을 리턴하면 됩니다.

풀이 방법:

map과 split을 사용하면 쉽게 풀 수 있다. s를 공백을 기준으로 분할한 뒤 map을 사용해서 다 int로 바꾸고 그 중 min값과 max를 찾으면 된다.

1
2
3
4
def solution(s):
    s=list(map(int,s.split(" ")))
    answer = "{} {}".format(min(s),max(s))
    return answer
cs


728x90
반응형

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

[Programmers]Lv 2. 최솟값 만들기  (0) 2019.03.16
[Programmers]Lv 3. 야근 지수  (2) 2019.03.15
[Programmers]Lv 3. 방문길이  (0) 2019.03.13
[Programmers]Lv 2.숫자의 표현  (0) 2019.03.12
[Programmers] Lv 3. 멀리 뛰기  (0) 2019.03.11
728x90
반응형

문제:

게임 캐릭터를 4가지 명령어를 통해 움직이려 합니다. 명령어는 다음과 같습니다.

U: 위쪽으로 한 칸 가기
D: 아래쪽으로 한 칸 가기
R: 오른쪽으로 한 칸 가기
L: 왼쪽으로 한 칸 가기

캐릭터는 좌표평면의 (0,0) 위치에서 시작합니다. 좌표평면의 경계는 왼쪽 위(-5,5), 왼쪽 아래(-5,-5), 오른쪽 위(5,5), 오른쪽 아래(5,-5)로 이루어져 있습니다.



예를 들어, "ULURRDLLU"로 명령했다면 1번 명령어부터 7번 명령어 까지 다음과 같이 움직입니다.



8번 명령어부터 9번 명령어까지 다음과 같이 움직입니다.



이때, 우리는 게임 캐릭터가 지나간 길 중 캐릭터가 처음 걸어본 길의 길이를 구하려고 합니다. 예를 들어 위의 예시에서 게임 캐릭터가 움직인 길이는 9이지만, 캐릭터가 처음 걸어본 길의 길이는 7이 됩니다. (8,9 번 명령어에서 움직인 길은 2,3번 명령어에서 이미 거쳐 간 길입니다.)


단, 좌표평면의 경계를 넘어가는 명령어는 무시합니다.


예를 들어, "LULLLLLLU"로 명령했다면 1번 명령어부터 6번 명령어대로 움직인 후, 7,8번 명령어는 무시합니다. 다시 9번 명령어대로 움직입니다.



이때 캐릭터가 처음 걸어본 길의 길이는 7이 됩니다.

명령어가 매개변수 dirs로 주어질 때, 게임 캐릭터가 처음 걸어본 길의 길이를 구하여 return 하는 solution 함수를 완성해 주세요.

풀이 방법:

기본적인 풀이 방법은 튜플값을 사용해 좌표를 나타냈다. 명령어대로 움직였을 때, 좌표평면 밖으로 나가거나 이미 중복된 길을 지나는 경우가 발생할 수 있다. 이를 방지하기 위해서 x_count, y_count 라는 x 좌표, y 좌표 값을 만들었고, answer_list를 만들어서 이미 지나간 경로인지 확인해보았다.
dirs에 따라서 좌표평면밖으로 나가는지 확인하고, 나가지 않았다면 이미 지나간 경로인지 파악을 하였다. 두 조건에 모두 해당하지 않았다면 answer_list에 담고 dirs를 끝낸 뒤엔 answer_list의 길이를 반환하였다.

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
def solution(dirs):
    answer_list=[]
    x_count=0
    y_count=0
    for i in dirs:
        if i=="U":
            if (y_count<5):
                y_count+=1
                if ((x_count,y_count-1),(x_count,y_count)) in answer_list:
                    pass
                else:
                    answer_list.append(((x_count,y_count-1),(x_count,y_count)))
        elif i=="D":
            if (y_count>-5):
                y_count-=1
                if ((x_count,y_count),(x_count,y_count+1)) in answer_list:
                    pass
                else:
                    answer_list.append(((x_count,y_count),(x_count,y_count+1)))
        elif i=="L":
            if (x_count>-5):
                x_count-=1
                if ((x_count,y_count),(x_count+1,y_count)) in answer_list:
                    pass
                else:
                    answer_list.append(((x_count,y_count),(x_count+1,y_count)))
        elif i=="R":
            if (x_count<5):
                x_count+=1
                if ((x_count-1,y_count),(x_count,y_count)) in answer_list:
                    pass
                else:
                    answer_list.append(((x_count-1,y_count),(x_count,y_count)))
    return len(answer_list)
cs


728x90
반응형

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

[Programmers]Lv 3. 야근 지수  (2) 2019.03.15
[Programmers]Lv 2. 최댓값과 최솟값  (0) 2019.03.14
[Programmers]Lv 2.숫자의 표현  (0) 2019.03.12
[Programmers] Lv 3. 멀리 뛰기  (0) 2019.03.11
[Programmers]Lv 2.폰켓몬  (0) 2019.03.10
728x90
반응형

문제:

Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개라는 사실을 알게 되었습니다. 예를 들어 15는 다음과 같이 4가지로 표현 할 수 있습니다.

1+2+3+4+5=15
4+5+6=15
7+8=15
15=15

자연수 n이 매개변수로 주어질 때, 연속된 자연수들로 n을 표현하는 방법의 수를 return하는 solution를 완성해주세요.

풀이 방법:

연속한 자연수들의 합으로 표현을 해야하기 때문에 자연수 n의 절반이 넘는 수는 사용할 수가 없다. 따라서 1부터 n//2+2 까지 반복문으로 돌려서 합이 n이 되는 경우들을 찾아주면 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
def solution(n):
    answer=0
    a=range(1,n//2+2)
    for i in a:
        s=0
        for j in range(i,n//2+2):
            s+=j
            if s==n:
                answer+=1
            elif s > n:
                break
    answer+=1
    return answer
cs


728x90
반응형

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

[Programmers]Lv 2. 최댓값과 최솟값  (0) 2019.03.14
[Programmers]Lv 3. 방문길이  (0) 2019.03.13
[Programmers] Lv 3. 멀리 뛰기  (0) 2019.03.11
[Programmers]Lv 2.폰켓몬  (0) 2019.03.10
[Programmers]Lv 3.베스트앨범  (0) 2019.03.09

+ Recent posts