728x90
반응형

문제:

에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다.

 

이 알고리즘은 다음과 같다.

 1. 2부터 N까지 모든 정수를 적는다.

 2. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.

 3. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.

 4. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.

입력:

첫째 줄에 N과 K가 주어진다. (1<=K<,max(2,K) < N <=1000)

출력:

첫째 줄에 K번째 지워진 수를 출력한다.

풀이방법:

우선 N까지 수가 있는 배열을 만들고 이를 에라토스테네스의 체 규칙에 따라서 하나씩 지워나간다. 이 때마다 하나씩 count를 늘려주면서 K번째가 되면 현재 지운 값을 출력하도록 한다.

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
def make(i):
    global answer
    idx=i
    count=1
    temp=0
    while idx*count <len(numbers):
        temp=numbers[idx*count]
        if numbers[idx*count]!=0:
            numbers[idx*count]=0
            answer+=1
            if answer==k:
                break
        count+=1
    return temp
 
 
n,k=map(int,input().split())
numbers=list(range(n+1))
numbers[1]=0
answer=0
conti=True
while conti:
    for i in range(len(numbers)):
        if numbers[i]!=0:
            temp=make(i)
            if answer==k:
                print(temp)
                conti=False
                break
cs

문제링크:

https://www.acmicpc.net/problem/2960

728x90
반응형

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

[BOJ]1159. 농구 경기  (1) 2019.10.16
[BOJ]1016. 제곱ㄴㄴ수  (0) 2019.10.15
[BOJ]2851. 슈퍼 마리오  (0) 2019.10.13
[BOJ]17144. 미세먼지 안녕!  (0) 2019.10.12
[BOJ]1834. 나머지와 몫이 같은 수  (0) 2019.10.11
728x90
반응형

문제:

풀이방법:

OUTS에 있는 값의 DATETIME과 INS의 DATETIME의 값 차이를 비교해야 하는 문제이다. 두 테이블에 공통된 값인 ANIMAL_ID으로 INNER JOIN을 한다. 조인을 한 뒤에 IN의 DATETIME이 OUTS의 DATETIME보다 큰 값을 찾아주도록 한다. 

1
2
SELECT I.ANIMAL_ID, I.NAME FROM ANIMAL_OUTS O, ANIMAL_INS I WHERE O.ANIMAL_ID=I.ANIMAL_ID AND
I.DATETIME > O.DATETIME ORDER BY I.DATETIME;
cs

문제링크:

https://programmers.co.kr/learn/courses/30/lessons/59043

728x90
반응형
728x90
반응형

문제:

슈퍼 마리오 앞에 10개의 버섯이 일렬로 놓여져 있다. 이 버섯을 먹으면 점수를 받는다.

슈퍼 마리오는 버섯을 처음부터 나온 순서대로 집으려고 한다. 하지만, 모든 버섯을 집을 필요는 없고 중간에 중단할 수 있다.

중간에 버섯을 먹는 것을 중단했다면, 그 이후에 나온 버섯은 모두 먹을 수 없다. 따라서 첫 버섯을 먹지 않았다면, 그 이후 버섯도 모두 먹을 수 없다.

마리오는 받은 점수의 합을 최대한 100에 가깝게 만들려고 한다.

버섯의 점수가 주어졌을 때, 마리오가 받는 점수를 출력하는 프로그램을 작성하시오.

입력:

총 10개의 줄에 각각의 버섯의 점수가 주어진다. 이 값은 100보다 작거나 같은 양의 정수이다. 버섯이 나온 순서대로 점수가 주어진다.

출력:

첫째 줄에 마리오가 받는 점수를 출력한다. 만약 100에 가까운 수가 2개라면 (예: 98, 102) 마리오는 큰 값을 선택한다.

풀이방법:

반복문을 사용해서 0개 버섯을 먹은 경우부터 10개의 버섯을 먹은 모든 경우를 모두 한 배열에 담아 넣는다. 그 다음에는 python의 sort의 key 기능을 사용해서 100과 가까운 수가 제일 앞에 오도록 정렬을 했다. (abs(x-100)을 이용해서) 그 다음에는 98과 102와 같이 간격이 같은 경우가 있을 수 있으므로 이 경우에는 1번째 인덱스를, 아닌 경우에는 0번째 인덱스를 출력하도록 했다.

1
2
3
4
5
6
7
8
9
10
11
12
answers=[]
summation=0
for i in range(10):
    score=int(input())
    answers.append(summation)
    summation+=score
answers.append(summation)
answers.sort(key=lambda x: abs(x-100))
if abs(100-answers[0])==abs(100-answers[1]):
    print(answers[1])
else:
    print(answers[0])
cs

문제링크:

https://www.acmicpc.net/problem/2851

728x90
반응형

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

[BOJ]1016. 제곱ㄴㄴ수  (0) 2019.10.15
[BOJ]2960. 에라토스테네스의 체  (0) 2019.10.14
[BOJ]17144. 미세먼지 안녕!  (0) 2019.10.12
[BOJ]1834. 나머지와 몫이 같은 수  (0) 2019.10.11
[BOJ]1357. 뒤집힌 덧셈  (0) 2019.10.08
728x90
반응형

문제:

풀이방법:

ANIMAL_OUTS에는 있지만 ANIMAL_INS에는 없는 값을 찾아야 하는 문제이다. 두 테이블이 있으므로 JOIN을 사용해서 풀어야 함을 알 수 있다. OUTS에만 있는 값을 찾아야 하므로 OUT을 기준으로 INS의 값을 합쳐주면 된다. 따라서 ANIMAL_OUTS O LEFT JOINT ANIMAL_INS I 를 사용해서 OUTS에 INS의 값이 붙게 된다. (ANIMAL_ID를 기준으로)

따라서 입양을 간 기록이 있지만 들어온 기록이 없는 동물들은 ANIMAL_INS의 ANIMAL_ID의 값이 NULL이 될 것이다. 따라서 WHERE절로 이 조건에 해당하는 O.ANIMAL_ID와 O.NAME을 출력하도록 한다.

1
2
SELECT O.ANIMAL_ID, O.NAME FROM ANIMAL_OUTS O LEFT JOIN ANIMAL_INS I  ON I.ANIMAL_ID=O.ANIMAL_ID
WHERE I.ANIMAL_ID is NULL ORDER BY O.ANIMAL_ID;
cs

문제링크:

https://programmers.co.kr/learn/courses/30/lessons/59042

728x90
반응형
728x90
반응형

문제:

미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 RxC인 격자판으로 나타냈고, 1x1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r,c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r,c)는 r행 c열을 의미한다.

 

공기청정기는 항상 왼쪽 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있고, (r,c)에 있는 미세먼지의 양은 Ar,c 이다.

 

1초 동안 적힌 일이 순서대로 일어난다.

1. 미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.

 - (r,c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.

 - 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.

 - 확산되는 양은 Ar,c / 5 이고 소주점은 버린다.

 - (r,c)에 남은 미세먼지의 양은 Ar,c - (Ar,c/5)x(확산된 방향의 개수) 이다.

2. 공기청정기가 작동한다.

 - 공기청정기에는 바람이 나온다.

 - 위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.

 - 바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다.

 - 공기청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기청저기로 들어간 미세먼지는 모두 정화된다.

 

다음은 확산의 예시이다.

공기청정기의 바람은 다음과 같은 방향으로 순환한다.

방의 정보가 주어졌을 때, T초가 지난 후 구사과의 방에 남아있는 미세먼지의 양을 구해보자.

입력:

첫째 줄에 R, C, T (6<=R,C<=50,1<=T<=1,000) 가 주어진다.

 

둘째 줄부터 R개의 줄에 Ar,c(-1<=Ar,c<=1,000)가 주어진다. 공기청정기가 설치된 곳은 Ar,c 가 -1이고, 나머지 값은 미세먼지의 양이다. -1은 2번 위아래로 붙어져 있고, 가장 윗 행, 아랫 행과 두 칸이상 떨어져 있다.

출력:

첫째 줄에 T초가 지난 후 구사과 방에 남아있는 미세먼지의 양을 출력한다.

풀이방법:

크게 두 함수로 구성되어 있다. 미세먼지가 확산되는 것을 나타내는 Spread와, 공기청정기가 작동하는 Clean()으로 구성되어 있었다. 매 초마다 Spread와 Clean이 반복된다.

Spread에서는 확산 될 때, 동시에 모든 곳에서 주변으로 퍼지기 때문에 nextD라는 빈 배열을 만들어서 이 곳에 값을 더하는 방식으로 했다.

Clean에서는 브루트포스 방식으로 진행했다. 공기청정기는 두 개의 인덱스를 차지하게 된다. 윗 부분에서는 반시계방향으로 회전하기 때문에 r의 인덱스가 0일 때, 윗 공기청정기 인덱스일 때, c의 인덱스가 0일 때, c-1일 때 공기청정기의 영향을 받는다.

아랫 부분에서는 시계방향으로 회전하면 r의 인덱스가 아랫 공기청정기 인덱스일때, r-1일때, 그리고 c의 인덱스가 0일 때, c-1일 때 영향을 받는다.

함수를 구성하고 나서 채점을 돌렸는데 Python에서는 시간초과가 발생하고, Pypy에서는 통과했다. 너무 비효율적으로 코드를 짠 것 같다.

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
def Spread():
    nextD=[[0 for i in range(c)]for j in range(r)]
    AirCleaner=[]
    for i in range(r):
        for j in range(c):
            if dusts[i][j]==-1:
                nextD[i][j]=-1
                AirCleaner.append(i)
            if dusts[i][j]>=1:
                count=0
                for k in range(4):
                    nx=i+dx[k]
                    ny=j+dy[k]
                    if 0<=nx<and 0<=ny<and dusts[nx][ny]!=-1:
                        count+=1
                        nextD[nx][ny]+=int(dusts[i][j]/5)
                nextD[i][j]+=dusts[i][j]-int(dusts[i][j]/5)*count
    return nextD,AirCleaner
 
def Clean(AC):
    nextD=[[0 for i in range(c)]for j in range(r)]
    for i in range(r):
        for j in range(c):
            if i<=AC[0]:
                if i==0:
                    if j==0:
                        nextD[i+1][j]=dusts[i][j]
                    else:
                        nextD[i][j-1]=dusts[i][j]
                    continue
                elif j==0:
                    if dusts[i][j]==-1:
                        pass
                    nextD[i+1][j]=dusts[i][j]
                elif j==c-1:
                    nextD[i-1][j]=dusts[i][j]
                    continue
                elif i==AC[0]:
                    if j==0:
                        pass
                    elif j==c-1:
                        nextD[i-1][j]=dusts[i][j]
                    else:
                        nextD[i][j+1]=dusts[i][j]
                    continue
                else:
                    nextD[i][j]=dusts[i][j]
            else:
                if i==AC[1]:
                    if j==0:
                        pass
                    elif j==c-1:
                        nextD[i+1][j]=dusts[i][j]
                    else:
                        nextD[i][j+1]=dusts[i][j]
                    continue
                elif j==0:
                    nextD[i-1][j]=dusts[i][j]
                    continue
                elif j==c-1:
                    if i==r-1:
                        nextD[i][j-1]=dusts[i][j]
                    else:
                        nextD[i+1][j]=dusts[i][j]
                    continue
                elif i==r-1:
                    if j==0:
                        nextD[i-1][j]=dusts[i][j]
                    else:
                        nextD[i][j-1]=dusts[i][j]
                    continue
                else:
                    nextD[i][j]=dusts[i][j]
                    continue
    nextD[AC[0]][0]=-1
    nextD[AC[1]][0]=-1
    return nextD
                       
r,c,t=map(int,input().split())
dusts=[]
for i in range(r):
    dusts.append(list(map(int,input().split())))
dx=[0,0,-1,1]
dy=[1,-1,0,0]
for i in range(t):
    dusts,AirCleaner=Spread()
    dusts=Clean(AirCleaner)
answer=0
for i in range(len(dusts)):
    answer+=sum(dusts[i])
print(answer+2)
cs

문제링크:

https://www.acmicpc.net/problem/17144

728x90
반응형

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

[BOJ]2960. 에라토스테네스의 체  (0) 2019.10.14
[BOJ]2851. 슈퍼 마리오  (0) 2019.10.13
[BOJ]1834. 나머지와 몫이 같은 수  (0) 2019.10.11
[BOJ]1357. 뒤집힌 덧셈  (0) 2019.10.08
[BOJ]1629. 곱셈  (0) 2019.10.07
728x90
반응형

문제:

풀이방법:

시간을 나타내는 데이터를 원하는 꼴로 만들어주는 함수를 사용해야 하는 문제이다. 오라클에서는 TO_CHAR를 사용하기도 하지만 MySQL에서는 DATE_FORMAT을 사용하는 것 같다. %Y가 연도를 네 글자로 나타내며, %m 과 %d를 사용한다.

1
SELECT ANIMAL_ID, NAME, DATE_FORMAT(DATETIME'%Y-%m-%d' ) AS "날짜" FROM ANIMAL_INS ORDER BY ANIMAL_ID;
cs

문제링크:

https://programmers.co.kr/learn/courses/30/lessons/59414

728x90
반응형
728x90
반응형

문제:

N으로 나누었을 때 나머지와 몫이 같은 모든 자연수의 합을 구하는 프로그램을 작성하시오. 예를 들어 N=3일 때, 나머지와 몫이 모두 같은 자연수는 4와 8 두 개가 있으므로, 그 합은 12이다.

 

입력:

첫째 줄에 2,000,000 이하의 자연수 N이 주어진다.

 

출력:

첫 줄에 구하고자 하는 수를 출력한다.

 

풀이방법:

몫과 나머지가 같다고 가정한 뒤에 역으로 그 자연수 값을 찾도록 하면 된다. 나머지가 나올 수 있는 경우의 수는 N일 때 0~N-1까지 있다. 따라서 몫과 나머지가 같은 수는 i*(N)+i, i는 0부터 N-1까지의 수로 구할 수 있다. 이는 반복문 하나만 사용하면 구할 수 있다.

1
2
3
4
5
n=int(input())
summation=0
for i in range(1,n):
    summation+=(i*n+i)
print(summation)
cs

문제링크:

https://www.acmicpc.net/problem/1834

 

728x90
반응형

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

[BOJ]2851. 슈퍼 마리오  (0) 2019.10.13
[BOJ]17144. 미세먼지 안녕!  (0) 2019.10.12
[BOJ]1357. 뒤집힌 덧셈  (0) 2019.10.08
[BOJ]1629. 곱셈  (0) 2019.10.07
[BOJ]1789. 수들의 합  (0) 2019.10.06
728x90
반응형

문제:

풀이방법:

특정한 값에 다른 값을 매칭시킬 때 사용할 수 있는 함수로는 DECODE와 CASE가 있다. 그 중 CASE를 사용해서 이 문제를 풀었다. SQL의 CASE를 이해하기 위해서 다른 프로그래밍 언어에 있는 switch와 비슷하고 생각하면 된다.

CASE

WHEN ~ THEN ~

WHEN ~ THEN ~

ELSE ~ END

Neutered 와 Spayed가 들어있으면 O, 그렇지 않다면 X라고 매칭을 해주고 나머지 값을 출력하도록 한다.

1
2
3
4
SELECT ANIMAL_ID, NAME, CASE 
WHEN SEX_UPON_INTAKE like '%Neutered%' THEN 'O'
WHEN SEX_UPON_INTAKE like 'Spayed%' THEN 'O'
ELSE 'X' END AS '중성화' FROM ANIMAL_INS;
cs

문제링크:

https://programmers.co.kr/learn/courses/30/lessons/59409

 

728x90
반응형
728x90
반응형

문제:

풀이방법:

문자열의 일부분을 포함하는 값들을 찾을 때 LIKE절을 사용한다. Column LIKE '표현식' 과 같은 방법으로 사용한다. '표현식'의 형태는 정규표현식과 유사하다. 이 문제에서는 el만 표함되면 된다 했으므로 앞 뒤로 몇개가 있어도 상관없는지를 나타내는 %를 앞뒤로 사용한다. 

1
SELECT ANIMAL_ID,NAME FROM ANIMAL_INS WHERE NAME LIKE '%el%' AND ANIMAL_TYPE = 'Dog'ORDER BY NAME;
cs

문제링크:

https://programmers.co.kr/learn/courses/30/lessons/59047

 

728x90
반응형
728x90
반응형

문제:

풀이방법:

Where 조건 절에서 한 컬럼이 여러 개의 값을 가져도 되는지에 대한 여부를 파악하기 위해서는 IN을 사용한다. IN과 tuple 값을 사용하며 tuple에 값들을 나열한다.

1
2
SELECT ANIMAL_ID,NAME,SEX_UPON_INTAKE FROM ANIMAL_INS
WHERE NAME in ('Lucy''Ella''Pickle''Rogan''Sabrina''Mitty');
cs

문제링크:

https://programmers.co.kr/learn/courses/30/lessons/59046

728x90
반응형

+ Recent posts