문제:

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


문제:

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


문제:

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


문제:

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


문제:

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


2019/01/29 - [Language/Python] - [Python 따라하기]1. Python 설치하기

2019/02/05 - [Language/Python] - [Python 따라하기]2. 자료형_part 1(String, Int,Float, List)

2019/02/12 - [Language/Python] - [Python 따라하기]3. 자료형_part2(Tuple,Set,Dictionary)

2019/02/19 - [Language/Python] - [Python 따라하기]4.조건문

2019/02/26 - [Language/Python] - [Python 따라하기]5. 반복문(For, While, break, continue)

2019/03/05 - [Language/Python] - [Python 따라하기]6. 함수만들기(def, print, format)

2019/03/12 - [Algorithm/Python] - [Python 따라하기]7.파일 입출력 (File I/O)


클래스를 사용하는 이유

클래스를 사용하지 못하면 프로그램을 만들지 못하는 것은 아니다. 클래스를 사용하지 않더라도 충분히 좋은 프로그램을 만들 수 있다.

하지만 클래스를 사용할 수 있다면 조금 더 편한 프로그램을 만들 수 있을 뿐이다.

예를 들어 계산기가 있다고 하자. 계산기에서 연산을 할 때 값들을 계속 누적해서 진행해야 한다. 그러기 위해서는 계산기당 하나의 전역변수와 하나의 함수가 필요하다. 하나의 계산기가 있는 것이라면 문제가 없지만 만약 여러 개의 계산기를 동시에 사용을 해야 한다면 어떻게 해야할까? 계산기가 늘어날 수록 전역변수와 함수가 계속 추가되어야 한다. 그러면 추가될수록 메모리를 많이 차지하게 될 것이다.

하지만 클래스를 사용한다면 하나의 변수와 함수만으로도 독립적인 값들을 유지할 수 있다.

클래스와 객체

클래스와 객체의 관계는 다음과 같이 설명 할 수 있다.

* 신입생 -> 클래스(class)
* 학생1,학생2, .... -> 객체(object)

클래스란 똑같은 무엇인가를 계속해서 만들어낼 수 있는 하나의 틀 같은 것이고(신입생), 객체란 클래스에 의해서 만들어진 것을 뜻한다.

클래스에 의해서 만들어진 객체는 서로 독립적인 성격을 가진다. 하나의 학생의 학적사항이 변동되더라도 다른 학생들에겐 영향을 주지 못하는 것과 같다. 다음은 하나의 간단한 클래스 예시이다.


위의 클래스는 아무런 기능을 가지고 있지 않다. 그래도 이 클래스는 객체를 생성할 수 있다. 다음은 객체를 만드는 방법이다.


학생정보 클래스 만들기

본격적으로 신입생들을 위한 학생정보를 만들어보도록 하자.

학생정보에 들어갈 수 있는 변수로는 이름, 학번, 성별 그리고 듣는 과목들이 있을 것이다. 학생정보에 들어갈 수 있는 함수들로는 각 변수를 설정하는 함수와 총 듣는 과목의 수를 반환해주는 함수, 과목을 추가해주는 함수가 있다고 하자. 다음은 학생정보를 담고 있는 Student 클래스이다.

위의 클래스를 하나씩 뜯어서 확인해보자.

__init__(생성자)

클래스 부분에서 __int__이 있다. 여기서 init 앞 뒤에 있는 것은 '_' 두 개씩 있는 것이다.
클래스에서 이 함수를 생성자라고 부른다. 생성자란 객체가 생성될 때 자동으로 호출되는 메소드이다. 객체의 초기값의 설정을 해줘야 할 때 사용을 한다.

Student의 클래스는 name, s_id, gender ,course라는 변수를 받고 이를 객체의 정보에 저장을 한다. 이 때 self를 사용하는데 지금 생성된 객체에 작용하는 작업이라고 생각하면 된다. 만약 기본 초기값이 설정되어 있지 않으면 변수들중 하나의 값이라도 넣지 않는다면 TypeError가 발생한다.


__str__(출력)

클래스 부분에서 __str__이 있다. 이것을 문자열화 함수라고 한다. 객체를 출력할 때의 형식을 지정해주는 함수이다.

__eq__(비교자)

클래스 부분에서 __eq__가 있다. 이것을 비교 함수라고 한다. 객체간의 값을 비교(==)할 때 사용을 한다.

클래스 내장 함수

일반적으로 string이나 list에서 제공해주는 함수처럼 이 클래스에서 제공해주는 함수이다.


상속

여기서 상속은 "재산을 상속받다" 라고 할 때의 상속과 같은 의미이다. 어떤 클래스를 만들 때 다른 클래스의 기능을 물려받을 수 있는 것이다. 이 상속의 개념을 이용해서 각 학과 별로 신입생에게 기능을 추가할 수 있다. 예를 들어 컴퓨터공학과 학생들에게는 파이썬을 할 수 있는지 물어보는 함수가 있다고 하자. 그러면 다음과 같이 Student 클래스를 상속받아 기능을 추가 할 수 있다. 그리고 상속 클래스를 만들 때는 다음과 같은 형식을 가진다.

class <<자식 클래스 이름>>(<<부모 클래스 이름>>):
<<내용>>



Computer_Student에서 구현을 하지 않았지만 Student의 내용들을 상속받았으므로 Student의 생성자, 문자열화 함수등의 내용들을 사용할 수 있다.

그리고 또한 Computer_Student에서만 구현된 canDoPython도 사용이 가능하다.



메소드 오버라이딩

메소드 오버라이딩은 상속받은 클래스에서 부모 클래스에 정의된 함수를 상속받은 클래스에서 재정의함으로써 사용을 하는 것이다. 컴퓨터 공학과 학생들은 수강신청을 할 때 6과목이 넘는다면 신청을 할 수 없다는 기능을 추가해주고 싶다. 그러면 동일한 이름으로 재정의를 해서 부모클래스의 함수를 덮어버리는 것이다.





문제:

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


문제:

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

문제:

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


문제:

길이가 같은 배열 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


'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

+ Recent posts