문제:

RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이다.

각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠할 때 드는 비용의 최솟값을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 집의 수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 각 집을 빨강으로 칠할 때, 초록으로 칠할 때, 파랑으로 칠할 때 드는 비용이 주어진다. 비용은 1,000보다 작거나 같은 자연수이다.

출력:

첫째 줄에 모든 집을 칠할 때 드는 비용의 최솟값을 출력한다.

풀이 방법:

우선 입력으로 들어온 값들을 이차원 배열꼴로 만들어준다. 그리고 난 뒤 0번째 행부터가 아닌 1번째 행부터 각 원소에 대해 전 행에서 자신의 열과 다른 값들중 최솟값을 더해준다. 이를 계속 누적해서 끝 행까지 반복하고 최종적으론 끝 행의 최솟값을 반환하도록 한다.

1
2
3
4
5
6
7
8
9
10
array=[]
for i in range(int(input())):
    array.append([])
    houses=map(int,input().split())
    for house in houses:
        array[i].append(house)
for i in range(1,len(array)):
    for j in range(len(array[i])): 
        array[i][j]+=min(array[i-1][:j]+array[i-1][j+1:])
print(min(array[-1]))
cs


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

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

[BOJ]11052. 카드 구매하기  (0) 2019.04.23
[BOJ]10844. 쉬운 계단 수  (0) 2019.04.22
[BOJ]2163. 초콜릿 자르기  (0) 2019.04.20
[BOJ]1912. 연속합  (0) 2019.04.19
[BOJ]2504. 괄호의 값  (0) 2019.04.18

문제:

정화는 NxM 크기의 초콜릿을 하나 가지고 있다. 초콜릿은 금이 가 있는 모양을 하고 있으며, 그금에 의해 NxM개의 조각으로 나눠질 수 있다.

초콜릿의 크기가 너무 크다고 생각한 그녀는 초콜릿을 친구들과 나눠 먹기로 했다. 이를 위해서 정화는 초콜릿을 계속 쪼개서 총 NxM개의 조각으로 쪼개려고 한다. 초콜릿을 쪼갤 때에는 초콜릿 조각을 하나 들고, 적당한 위치에서 초콜릿을 쪼갠다. 초콜릿을 초콜릿을 쪼갤 때에는 금이 가 있는 위치에서만 쪼갤 수 있다. 이와 같이 초콜릿을 쪼개면 초콜릿은 두 개의 조각으로 나눠지게 된다. 이제 다시 이 중에서 초콜릿 조각을 하나 들고, 쪼개는 과정을 반복하면 된다.

초콜릿을 쪼개다보면 초콜릿이 녹을 수 있기 때문에, 정화는 가급적이면 초콜릿을 쪼개는 횟루를 최소로 하려 한다. 초콜릿의 크기가 주어졌을 때, 이를 1x1 크기의 초콜릿으로 쪼개기 위한 최소 쪼개기 횟수를 구하는 프로그램을 작성하시오.


입력:

첫째 줄에 두 정수 N,M(1<=N,M<=300)이 주어진다.

출력:

첫째 줄에 답을 출력한다.

풀이 방법:

원래 동적계획법을 사용해서 풀어야 하는 문제인데, 굳이 동적계획법을 사용할 필요는 없다. 단순한 사칙연산만으로도 쉽게 구할 수 있다.

1
2
a,b=map(int,input().split())
print(min(a,b)*(max(a,b)-1)+min(a,b)-1)
cs


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

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

[BOJ]10844. 쉬운 계단 수  (0) 2019.04.22
[BOJ]1149. RGB거리  (0) 2019.04.21
[BOJ]1912. 연속합  (0) 2019.04.19
[BOJ]2504. 괄호의 값  (0) 2019.04.18
[BOJ]9012.괄호  (0) 2019.04.17

문제:

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12 + 21 인 33이 된다.

입력:

첫째 줄에 정수 n(1<=n<=100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.


출력:

첫째 줄에 답을 출력한다.


풀이 방법:

DP를 활용해서 푸는 문제이다. 반복문은 여러개 써야 할 것 같지만 배열 한 번을 탐색하는 반복문 하나로도 풀 수 있다. 정답을 maxsum이라 하고 초기값을 -1000으로 잡아준다. 왜냐하면 모든 수는 -1,000보다는 크기 때문이다. 배열중 임의의 값과 그 전부터 누적해온 값 중 더 큰 값을 선택하고 이를 maxsum과 비교해서 maxsum보다 커지는 값들이 있다면 그 값을 maxsum으로 갱신해준다.

예시 케이스로 설명하면 다음과 같이 된다.
처음에는 max(10,0+10)이므로 temp가 10이 되고 maxsum은 당연히 10으로 최신화된다.
그 다음에는 max(-4,10-4)이므로 temp가 6이 되지만 maxsum은 유지된다.
max(3,6+3)이므로 temp가 9가 되지만 maxsum은 유지된다.
max(1,9+1)이므로 temp가 10이 되지만 maxsum은 유지된다.
max(6,10+6)이므로 temp가 16이 되고 maxsum이 16이 된다.
max(-35,16-35)이므로 temp가 -19가 되고 maxsum은 유지된다.
max(12,-19+12)이므로 temp가 12가 되고 maxsum은 유지된다.
max(21,12+21)이므로 temp가 33이 되고 maxsum은 갱신된다.
max(-1,33-1)이므로 temp가 32가 되고 maxsum은 유지된다.

따라서 12+21인 33이 정답이 된다.

1
2
3
4
5
6
7
8
9
n=int(input())
arr=list(map(int,input().split()))
temp=0
maxsum=-1000
for num in arr:
    temp=max(num,temp+num)
    if temp>maxsum:
        maxsum=temp
print(maxsum)
cs


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

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

[BOJ]1149. RGB거리  (0) 2019.04.21
[BOJ]2163. 초콜릿 자르기  (0) 2019.04.20
[BOJ]2504. 괄호의 값  (0) 2019.04.18
[BOJ]9012.괄호  (0) 2019.04.17
[BOJ]1874. 스택 수열  (0) 2019.04.16

문제:

4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다.


1. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 

2. 만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다. 

3. X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다.


예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()()[]’ 은 모두 올바른 괄호열이 아니다. 우리는 어떤 올바른 괄호열 X에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 값(X)로 표시한다. 


1. ‘()’ 인 괄호열의 값은 2이다.

2. ‘[]’ 인 괄호열의 값은 3이다.

3. ‘(X)’ 의 괄호값은 2×값(X) 으로 계산된다.

4. ‘[X]’ 의 괄호값은 3×값(X) 으로 계산된다.

5. 올바른 괄호열 X와 Y가 결합된 XY의 괄호값은 값(XY)= 값(X)+값(Y) 로 계산된다.


예를 들어 ‘(()[[]])([])’ 의 괄호값을 구해보자.  ‘()[[]]’ 의 괄호값이 2 + 3×3=11 이므로  ‘(()[[ ]])’의 괄호값은 2×11=22 이다. 그리고  ‘([])’의 값은 2×3=6 이므로 전체 괄호열의 값은 22 + 6 = 28 이다.


여러분이 풀어야 할 문제는 주어진 괄호열을 읽고 그 괄호값을 앞에서 정의한대로 계산하여 출력하는 것이다. 

입력:

첫째 줄에 괄호열을 나타내는 문자열(스트링)이 주어진다. 단 그 길이는 1 이상, 30이하이다.

출력:

첫째 줄에 그 괄호열의 값을 나타내는 정수를 출력한다. 만일 입력이 올바르지 못한 괄호열이면 반드시 0을 출력해야 한다.

풀이 방법:

문제에서 제공된 예시케이스를 보면 예시케이스는 다음과 같이 계산이 되어야 한다.  2×(2+3×3)+2×3 사람이 직접 괄호를 보고 계산을 하면 이렇게 하겠지만 컴퓨터에게 이렇게 연산을 하게끔 하는 것은 어렵다. 따라서 위 식을 다음과 같이 변경하도록 할 것이다. 2×2+2×3×3+2×3 와 같이 괄호를 분배법칙을 이용해 풀어내었다. 이 규칙대로 하기 위해서 ( 나 [ 를 만나면 temp에 2 나 3를 곱하고 stack에 담아두고, ) 나 ] 를 만날 경우에는 그 전의 값이 ( 나 [ 일 경우에만 answer에 더해줬다.. 그 이유는 이 경우에만 올바른 괄호열이기 때문이다. 물론 앞에서 미리 temp에서 곱하면서 움직였으므로 값은 올바르게 구해진다. 그리고 스택의 top 값이 ( 나 [ 이면 pop 해줬다. 계속 이과정을 반복하다가 중간에 스택이 비어버렸는데 빼야하는 경우가 온다거나 끝까지 다 진행했는데도 아직 stack에 남아있다면 올바르지 않은 괄호열이기때문에 0을 출력하고 그렇지 않으면 answer를 출력하도록 한다.

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
answer=0
stack=[]
temp=1
correct=True
string=input()
for i in range(len(string)):
    if string[i]=="(":
        temp*=2
        stack.append("(")
    elif string[i]=="[":
        temp*=3
        stack.append("[")
    elif string[i]==")":
        if string[i-1]=="(":
            answer+=temp
        if not len(stack):
            correct=False
            break
        if stack[-1]=="(":
            stack.pop()
        temp//=2
    else:
        if string[i-1]=="[":
            answer+=temp
        if not len(stack):
            correct=False
            break
        if stack[-1]=="[":
            stack.pop()
        temp//=3
if (len(stack) or not correct):
    print(0)
else:
    print(answer)
cs


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

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

[BOJ]2163. 초콜릿 자르기  (0) 2019.04.20
[BOJ]1912. 연속합  (0) 2019.04.19
[BOJ]9012.괄호  (0) 2019.04.17
[BOJ]1874. 스택 수열  (0) 2019.04.16
[BOJ]10828. 스택  (0) 2019.04.15

문제:

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 '(' 와 ')' 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PsS,VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 "()"문자열은 기본 VPS 이라고 부른다. 만일 x가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 "(x)"도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 "(())()"와 "((()))"는 VPS이지만 "(()(","(())()))", 그리고 "(()"는 모두 VPS 가 아닌 문자열이다.

여러분은 입력으로 주어진 괄호 문자열이 VPS인지 아닌지를 판단해서 그 결과를 YES 와 NO로 나타내어야 한다.

입력:

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 테이터로 주어진다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 테이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다 하나의 괄호 문자열의 길이는 2 이상 50이하이다.

출력:

출력은 표준 출력을 사용한다. 만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 "YES", 아니면 "NO"를 한 줄에 하나씩 차례대로 출력해야 한다.

풀이 방법:

스택을 사용해서 "(" 를 만난다면 +1을 해주고 ")"을 만난다면 -1을 해주는 작업을 하도록 한다. 이렇게 괄호 문자열을 모두 탐색하고 난다면 VPS와 같은 경우에는 count가 0이 된다. 그렇지 않다면 0이 아닌 값이 나올 것이다. 하지만 ")("와 같은 경우 VPS가 아니지만 count의 값이 0이 되게 된다. 그래서 ")"를 먼저 만나서 count가 음수가 되는 경우 역시 올바르지 않은 경우이다. 이를 조절해주면 문제 없이 문제가 풀릴 것이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
for i in range(int(input())):
    count=0
    for j in input():
        if count < 0:
            count=100
            break
        if j=="(":
            count+=1
        else:
            count-=1
    if count==0:
        print("YES")
    else:
        print("NO")
cs


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

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

[BOJ]1912. 연속합  (0) 2019.04.19
[BOJ]2504. 괄호의 값  (0) 2019.04.18
[BOJ]1874. 스택 수열  (0) 2019.04.16
[BOJ]10828. 스택  (0) 2019.04.15
[BOJ]4948.베르트랑 공준  (0) 2019.04.14

문제:

스택(stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는(pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO,Last In First out) 특성을 가지고 있다.

1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.

입력:

첫 줄에 n (1<=n<=100,000)이 주어진다. 둘때 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 정수가 두 번 나오는 일은 없다.

출력:

입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.

풀이 방법:

문제를 풀기에 앞서서 문제를 이해를 하는 것조차 어려웠다. 1~n까지의 수가 있을 때 각 수를 스택 구조를 유지하는 배열에 넣었다가 빼면서 우리가 입력으로 넣은 수열을 만드는 것이 문제의 목표이다. 


 처음에는 while로 넣었다가 빼는 과정을 조절하려고 했으나 적절한 조건을 찾기 어려웠다. 그래서 예외처리 구문을 사용해서 빈 리스트에서 pop을 하려 할 때 오류가 발생해서 빠져나오도록 만들었다. 

 

 우선 입력으로 처음 넣은 값을 만들기 위해서 그 값까지 모든 값들을 계속 순차적으로 넣어야 한다. 그래서 맨 처음 i로 반복되는 for 반복문이 첫 원소를 만들기 위한 과정이다. 이후 j 반복문을 통해서 본격적으로 원하는 수열을 만들고자 한다. 일단 우선적으로 answer가 비어있다면 하나 추가를 하는 과정을 거친 뒤 stack인 answer 배열의 맨 윗 값이 원하는 값인지 비교를 하는 조건문을 만들었다. 만약 원하는 값이라면 -를 하고 그렇지 않다면 아직 answer에 들어가 있지 않은 것이라면 반복문 i처럼 계속넣어주면 되기 때문에 이번에는 while로 넣어주도록 한다. 그리고 다시 끝 값을 비교하고 빼도록 한다. 


하지만 j-for를 반복하면서 더하거나 빼는 작업을 한 번도 하지 않았다면 이 것은 문제가 생긴 경우 이므로 somethingtodo라는 부울 함수를 사용해 NO를 출력하도록 한다. (주로 빼야할 수가 이미 들어가 있을 경우 발생한다.)


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
n=int(input())
def sol(n):
    answer_list=[int(input()) for i in range(n)]
    answer=[]
    ans=[]
    k=0
    try:
        for i in range(1,answer_list[0]+1):
            k+=1
            answer.append(k)
            ans.append("+")
        for j in range(n):
            somethingtodo=False
            if len(answer)==0:
                k+=1
                answer.append(k)
                ans.append("+")
                somethingtodo=True
            if answer[-1]==answer_list[j]:
                answer.pop()
                ans.append('-')
                somethingtodo=True
            else:
                while answer_list[j]>answer[-1]:
                    k+=1
                    answer.append(k)
                    ans.append("+")
                    somethingtodo=True
                if answer[-1]==answer_list[j]:
                    answer.pop()
                    ans.append("-")
                    somethingtodo=True
            if somethingtodo:
                pass
            else:
                print("NO")
                return
        print(*ans,sep="\n")
    except:
        print("No")
sol(n)
cs


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

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

[BOJ]2504. 괄호의 값  (0) 2019.04.18
[BOJ]9012.괄호  (0) 2019.04.17
[BOJ]10828. 스택  (0) 2019.04.15
[BOJ]4948.베르트랑 공준  (0) 2019.04.14
[BOJ]1929. 소수 구하기  (0) 2019.04.13

문제:

정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 다섯 가지이다.

-push X: 정수 X를 스택에 넣는 연산이다.
-pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
-size: 스택에 들어있는 정수의 개수를 출력한다.
-empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
-top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력:

첫째 줄에 주어지는 명령의 수 N(1<=N<=10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다.
주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력:

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

풀이 방법:

python의 배열은 push와 pop이 스택과 동일하게 작동하므로 명령어가 들어오는 대로 수행해주면 문제 없이 통과 할 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
answer=[]
for i in range(int(input())):
    a=input().split()
    if a[0]=="push":
        answer.append(int(a[1]))
    elif a[0]=="top":
        if len(answer):
            print(answer[-1])
        else:
            print(-1)
    elif a[0]=="size":
        print(len(answer))
    elif a[0]=="empty":
        if len(answer):
            print(0)
        else:
            print(1)
    else:
        if len(answer):
            print(answer.pop())
        else:
            print(-1)
cs


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

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

[BOJ]9012.괄호  (0) 2019.04.17
[BOJ]1874. 스택 수열  (0) 2019.04.16
[BOJ]4948.베르트랑 공준  (0) 2019.04.14
[BOJ]1929. 소수 구하기  (0) 2019.04.13
[BOJ]1181. 단어정렬  (0) 2019.04.12

문제:

베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다.

이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다.

예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23)

n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오.


입력:

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 케이스는 n을 포함하며, 한 줄로 이루어져 있다. (n<=123456)

출력:

각 테스트 케이스에 대해서, n보다 크고, 2n보다 작거나 같은 소수의 개수를 출력한다.


풀이방법:

이 문제도 에라토스테네스의 체의 원리를 사용해서 풀어야 하는 문제이다. 하지만 입력이 하나의 테스트 케이스가 아니라 여러 개의 테스트 케이스로 이루어져 있으므로 매번 에라토스테네스의 체를 이용해 배열을 만드는 것은 시간을 많이 소비하게 된다. 따라서 미리 한 번 최대케이스에 대해서 경우로 만들어 놓고 테스트케이스들에 대해서는 슬라이싱을 통해서 접근을 하도록 한다.

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
import math
def prime(n):
    is_prime=True
    if n==1:
        is_prime=False
    for i in range(2,int(math.sqrt(n))+1):
        if n%i==0:
            is_prime=False
    return is_prime
h=list(range(1,123456*2+1))
h[0]=0
for i in range(len(h)):
    if h[i]==0:
        pass
    elif prime(h[i]):
        for j in range(i+h[i],len(h),h[i]):
            h[j]=0
while True:
    a=int(input())
    if a==0:
        break
    temp=sorted(list(set(h[a:2*a])))
    try:
        temp.remove(0)
    except:
        pass
    print(len(temp))
cs


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

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

[BOJ]1874. 스택 수열  (0) 2019.04.16
[BOJ]10828. 스택  (0) 2019.04.15
[BOJ]1929. 소수 구하기  (0) 2019.04.13
[BOJ]1181. 단어정렬  (0) 2019.04.12
[BOJ]6064. 카잉 달력  (0) 2019.04.11

문제:

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력:

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1<=M,N<=1,000,000)

출력:

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

풀이 방법:

임의의 수 n이 소수인지 판별하기 위해서 n-1까지 다 나눠보는 것이 아니라 sqrt(n) 값까지 나눠서 나누어지지 않는다면 소수임을 알 수 있다는 것은 대부분 알고 있다. 하지만 1,000,000개의 수에 대해서 다 해보는 것은 아무리 sqrt(n) 값까지 나눠본다고 해도 많은 시간이 소요된다. 따라서 이렇게 큰 수가 소수인지 판별하기 위해서 사용되는 것이 에라토스테네스의 체이다.


 이 방법은 예를 들어 120이하의 소수들을 파악하기 위해서 120까지의 배열을 생성한 뒤에 우선 2가 소수인지 판별을 한다. 2는 소수인것이 자명하므로 2의 배수의 값을 0으로 바꾼다.(4,6,8,10,12,14,......) 다 바꾸고 난 뒤에 3도 소수이므로(쉽게 판별할 수 있다.) 3의 배수의 값들을 0으로 바꾼다.(6,9,12,15,.....)이후 원래 4의 값으로 이동을 했지만 이미 2의 배수의 경우일 때 0으로 바뀌어 있다. 0이면 어떤 소수의 배수임을 의미하므로 그냥 지나가게 설정을 한다. 이렇게 계속 0이 아닌 수를 만나면 소수인지 판별을 하고 0을 만나면 그냥 지나가도록 한다. 그러면 최종적으론 이 배열엔 소수와 0만 남아있는 배열이 된다.

그러면 set을 통해서 중복된 0의 값들을 다 제거하고 재정렬한뒤 0의 값을 빼준다면 소수만 남아있는 리스트가 된다. 따라서 이 문제도 에라토스테네스의 체 방법을 이용해서 풀면 시간초과가 발생하지 않고 풀 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import math
def prime(n):
    is_prime=True
    if n==1:
        is_prime=False
    for i in range(2,int(math.sqrt(n))+1):
        if n%i==0:
            is_prime=False
    return is_prime
a,b=input().split()
a=int(a)
b=int(b)
h=list(range(1,b+1))
h[0]=0
for i in range(len(h)):
    if h[i]==0:
        pass
    elif prime(h[i]):
        for j in range(i+h[i],len(h),h[i]):
            h[j]=0
h=sorted(list(set(h[a-1:])))
h.remove(0)
for i in h:
    print(i)
cs


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

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

[BOJ]10828. 스택  (0) 2019.04.15
[BOJ]4948.베르트랑 공준  (0) 2019.04.14
[BOJ]1181. 단어정렬  (0) 2019.04.12
[BOJ]6064. 카잉 달력  (0) 2019.04.11
[BOJ]1475. 방번호  (0) 2019.04.10

문제:

알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.

1. 길이가 짧은 것부터
2. 길이가 같으면 사전 순으로

입력:

첫째 줄에 단어의 개수 N이 주어진다. (1<=N<=20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.

출력:

조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다.

풀이 방법:

단어를 정렬하는 기준이 두가지 이다. 그래서 처음 리스트에 담을 때 단어와 단어의 길이를 함께 담아주도록 한다. 이후 단어를 정렬을 할 때 sorted의 key 파라미터를 이용하도록 한다. lambda l : (l[1],l[0]) 과 같이 key 값을 주었는데 이 말은 l[1]은 단어의 길이를 기준으로 우선 정렬을 하고, 만약 같다면 l[0] 단어를 기준으로 즉 사전 순으로 배열하도록 한다.


1
2
3
4
5
6
7
8
9
10
11
def dictionary(n):
    l=[]
    for i in range(n):
        s=input()
        l.append((s,len(s)))
    l=list(set(l))
    l=sorted(l,key=lambda l: (l[1],l[0]))
    for i in l:
        print(i[0])
n=int(input())
dictionary(n)
cs


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

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

[BOJ]4948.베르트랑 공준  (0) 2019.04.14
[BOJ]1929. 소수 구하기  (0) 2019.04.13
[BOJ]6064. 카잉 달력  (0) 2019.04.11
[BOJ]1475. 방번호  (0) 2019.04.10
[BOJ]2775. 부녀회장이 될테야  (0) 2019.04.09

+ Recent posts

티스토리툴바