반응형

문제풀이

1. 딕셔너리 자료구조를 활용하여 생성자의 개수를 세어줍니다. 딕셔너리 dic의 key는 생성자가 되고, value는 생성자의 개수가 됩니다.

2. 1부터 10000까지의 숫자 n의 d(n)을 구하여, 위의 딕셔너리에서 key d(n)의 value에 1을 더해줍니다.

3. 1부터 10000까지의 숫자들을 key로 하여, value가 0인 값을 출력합니다.

Python Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import sys
from collections import defaultdict
 
dic = defaultdict(int)
def d(n):
    return n + sum(int(s) for s in str(n))
def main():
    for i in range(1,10000):
        dic[d(i)] = dic[d(i)]+1
    for i in range(1,10000):
        if dic[i] ==0:
            print(i)
if __name__ == '__main__':
    main()
 cs

Line 8-9 : 과정 2입니다.

Line 10-11 : 과정 3입니다.

문제링크

 

4673번: 셀프 넘버

셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다. 양의 정수 n이 주어졌을 때,

www.acmicpc.net

 

반응형

'알고리즘 > 백준' 카테고리의 다른 글

백준 1946 신입 사원  (0) 2020.12.09
백준 4344 평균은 넘겠지 Python  (0) 2020.12.09
백준 20162 간식 파티 Python  (0) 2020.12.08
백준 1149 RGB거리 Python  (0) 2020.12.08
백준 1309 동물원  (0) 2020.12.07
반응형

문제풀이

1. 각 요소가 (서류 순위, 면접 순위)인 리스트 l을 만든 후, 서류 순위를 기준으로 l을 정렬해줍니다.

2. 정렬된 l에서 앞에서부터 튜플을 하나씩 꺼내며 면접 순위가 이전에 선발된 사람보다 높은(숫자가 낮은) 사람을 선발하게 됩니다.

백준의 두번째 예시

[(1, 4), (2, 5), (3, 6), (4, 2), (5, 7), (6, 1), (7, 3)]

를 살펴보면 다음과 같습니다.

- 먼저 서류 1등은 당연히 뽑히게 됩니다. 2, 3등은 서류 순위, 면접 순위 모두 서류 1등보다 낮으므로 선발되지 않습니다.

- 서류 4등의 경우, 서류 1등보다 면접 등수가 높으므로 선발됩니다.

- 서류 5등의 경우에는 서류 4등보다 면접 등수도 낮으므로 선발되지 않습니다.

- 서류 6등의 경우에는 서류 4등보다 면접 등수가 높으므로 선발됩니다.

- 서류 7등의 경우에는 면접 등수도 서류 6등보다 낮으므로 선발되지 않습니다.

Python Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import sys
readline = sys.stdin.readline
 
def main(n):
    for _ in range(n):
        #l = sorted([tuple(map(int,readline().split())) for _ in range(int(readline()))],key = lambda x : x[0])
        l = []
        for x in range(int(readline())):
            l.append(tuple(map(int,readline().split())))
        l = sorted(l,key = lambda x : x[0])
        tmp = l[0][1]
        ans = 1
        for n,m in l:
            if m < tmp :
                tmp = m
                ans += 1
        print(ans)
if __name__ == '__main__':
    n =int(readline())
    main(n)
 cs

Line 7 : l은 (서류 등수, 면접 등수)가 들어갈 리스트입니다. Line 7~10을 Line 6 한줄로 축약할 수 있습니다.

*축약할 경우 소요시간이 3584 -> 3996 ms로 길어지게됩니다.

문제 링크

 

1946번: 신입 사원

첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성

www.acmicpc.net

 

반응형

'알고리즘 > 백준' 카테고리의 다른 글

백준 4673 셀프 넘버 Python  (0) 2020.12.10
백준 4344 평균은 넘겠지 Python  (0) 2020.12.09
백준 20162 간식 파티 Python  (0) 2020.12.08
백준 1149 RGB거리 Python  (0) 2020.12.08
백준 1309 동물원  (0) 2020.12.07
반응형

문제풀이

1. 각 줄의 첫 번째 요소는 학생수, 그 다음 요소들은 학생들의 점수들이므로 평균을 구한 후, 평균 이상인 학생수를 구해 전체 학생수로 나눠준다.

2. *100을 한 후, 소수점 세자리로 끊어준다. '.3f' 포맷을 활용한다.

Python Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import sys
readline = sys.stdin.readline
 
def main(n):
    for _ in range(n):
        nums = list(map(int,readline().split()))
        # 평균 = (첫번째 요소를 제외한 요소들의 합)/(첫번째 요소를 제외한 요소들의 개수)
        mean = sum(nums[1:])/nums[0]
        # 평균보다 큰 요소만큼 리스트에 1을 넣고 리스트의 총합을 구하면 평균을 넘는 학생의 비율이 된다.
        print('%.3f'%(sum(1 for x in nums[1:] if x > mean)*100/nums[0]) + '%')
 
if __name__ == '__main__':
    n =int(readline())
    main(n)
 cs

문제 링크

 

4344번: 평균은 넘겠지

대학생 새내기들의 90%는 자신이 반에서 평균은 넘는다고 생각한다. 당신은 그들에게 슬픈 진실을 알려줘야 한다.

www.acmicpc.net

 

반응형

'알고리즘 > 백준' 카테고리의 다른 글

백준 4673 셀프 넘버 Python  (0) 2020.12.10
백준 1946 신입 사원  (0) 2020.12.09
백준 20162 간식 파티 Python  (0) 2020.12.08
백준 1149 RGB거리 Python  (0) 2020.12.08
백준 1309 동물원  (0) 2020.12.07
반응형

문제풀이

1. 배열 자료구조인 dp에 n번째 음식의 만족도를 담습니다. 즉, dp[i]는 i번째 음식의 만족도입니다.

2. 배열 자료구조인 dp2에는 n번째 음식을 먹었을 때의 만족도의 최댓값을 담습니다. 즉, dp2[i]는 i번째 음식을 먹었을 때의 만족도의 최댓값입니다.

3. dp2의 요소는 다음과 같은 과정을 통해 얻습니다.

3-1. n번째 음식의 인덱스를 n, 만족도를 nth라 할때, dp의 n번째 이전의 요소들 중 nth보다 작은 값들에 해당하는 dp2의 요소를 모읍니다.

3-2a. 위 과정에서 모은 요소들 중 최댓값+nth가 dp2[n]이 됩니다.

3-2b. 위 과정에서 모인 요소가 없다면, n번째 이전에 먹을 것이 없다는 의미이므로 dp2[n]은 nth가 됩니다.

 

** dp의 이름을 별 생각없이 dp로 지었는데, dp2가 실질적으로 메모리제이션이 이루어지는 배열이고, dp는 동적프로그래밍과 큰 관련이 없습니다.

Python Code

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
import sys
readline = sys.stdin.readline
 
def main(n):
    nth = int(readline())
    #n 번째 음식의 만족도
    dp = [nth]
    #n 번째 음식을 먹었을 때의 만족도의 최댓값
    dp2 = [nth]
 
    for _ in range(n-1):
        nth = int(readline())
        # 앞의 음식 중 먹을 수 있는 음식들을 먹었을 때의 만족도의 최댓값들
        tmp = []
        for i,v in enumerate(dp):
            if v < nth:
                tmp.append(dp2[i])
        dp.append(nth)
        if tmp:
            dp2.append(max(tmp)+nth)
        # 먹을 수 있는 게 없으면, 이번 음식만 먹는 것이 최댓값
        else:
            dp2.append(nth)
    print(max(dp2))
 
if __name__ == '__main__':
    n =int(readline())
    main(n)
 cs

문제 링크

 

20162번: 간식 파티

서울이는 입맛이 까다로운 고양이다. 입맛이 까다로운 서울이는 전에 먹었던 간식보다 더 맛있는 간식만 먹는다. 서울이는 간식의 평점이 높을수록 맛있다고 느낀다. 집사는 서울이에게 N 일

www.acmicpc.net

 

반응형

'알고리즘 > 백준' 카테고리의 다른 글

백준 1946 신입 사원  (0) 2020.12.09
백준 4344 평균은 넘겠지 Python  (0) 2020.12.09
백준 1149 RGB거리 Python  (0) 2020.12.08
백준 1309 동물원  (0) 2020.12.07
백준 20299 3대 측정  (0) 2020.12.04
반응형

문제풀이

1. dp의 각 요소의 의미는 다음과 같다.

dp[0] : 입력 받은 칸을 red로 칠했을 때 코스트의 최솟값
dp[1] : 입력 받은 칸을 green로 칠했을 때 코스트의 최솟값
dp[2] : 입력 받은 칸을 blue로 칠했을 때 코스트의 최솟값

2. 현재 칸의 페인트의 코스트 r,g,b를 입력받았다면, 위의 관계를 아래와 같이 쓸 수 있다.

dp[0] = min(dp[1],dp[2])+r
dp[1] = min(dp[0],dp[2])+g
dp[2] = min(dp[0],dp[1])+b

Python Code

1
2
3
4
5
6
7
8
9
10
11
12
import sys
readline = sys.stdin.readline
 
def main(n):
    dp = list(map(int,readline().split()))
    for _ in range(n-1):
        r,g,b = map(int,readline().split())
        dp = [min(dp[1],dp[2])+r, min(dp[0],dp[2])+g,min(dp[0],dp[1])+b]
    print(min(dp))
if __name__ == '__main__':
    n =int(readline())
    main(n)
 cs

문제 링크

 

1149번: RGB거리

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나

www.acmicpc.net

 

반응형

'알고리즘 > 백준' 카테고리의 다른 글

백준 4344 평균은 넘겠지 Python  (0) 2020.12.09
백준 20162 간식 파티 Python  (0) 2020.12.08
백준 1309 동물원  (0) 2020.12.07
백준 20299 3대 측정  (0) 2020.12.04
백준 11057 오르막 수 Python  (0) 2020.12.03
반응형

문제풀이

세 개의 요소를 활용한 dp로 문제를 풀겠습니다.

1. 배열 자료구조인 dp의 각 요소의 의미는 아래와 같습니다.

dp[n][0] : n번째 행의 왼쪽 칸에 사자가 있을 경우의 수.

dp[n][1] : n행의 오른쪽 칸에 사자가 있을 경우의 수.

dp[n][2] : n행에 사자가 없는 경우의 수.

2. 각 요소의 점화식은 다음과 같습니다.

2-1. dp[n][0] = dp[n-1][1]+dp[n-1][2] ; n행의 왼쪽에 사자를 넣기 위해서는 윗행의 오른쪽에 사자가 있거나(dp[n-1][1]) 윗행에 사자가 아예 없어야(dp[n-1][2]) 합니다.

2-2. dp[n][1] = dp[n-1][0]+dp[n-1][2] ; n행의 오른쪽에 사자를 넣기 위해서는 윗행의 왼쪽에 사자가 있거나 윗행에 사자가 아예 없어야 합니다.

2-3. dp[n][2] = dp[n-1][0]+dp[n-1][1]+dp[n-1][2] ; n행에 사자를 넣기 않으려면, 윗행에 사자가 어디에 있든 아예 없든 상관 없습니다.

3. dp의 요소가 너무 커지지 않도록 %9901을 해주며, n=1부터 입력받는 N까지 진행해준 후, sum(dp[n])%9901을 반환합니다.

 

Python Code

1
2
3
4
5
6
7
8
9
def main(n):
    dp = [1,1,1]
    for _ in range(n-1):
        tmp = [(dp[1]+dp[2])%9901, (dp[0]+dp[2]%9901), (dp[0]+dp[1]+dp[2])%9901]
        dp = tmp
    print(sum(dp)%9901)
    
if __name__ == '__main__':
    main(int(input()))
 cs

문제링크

 

1309번: 동물원

첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다.

www.acmicpc.net

 

반응형

'알고리즘 > 백준' 카테고리의 다른 글

백준 20162 간식 파티 Python  (0) 2020.12.08
백준 1149 RGB거리 Python  (0) 2020.12.08
백준 20299 3대 측정  (0) 2020.12.04
백준 11057 오르막 수 Python  (0) 2020.12.03
백준 4358 생태학  (0) 2020.10.21
반응형

문제풀이

1. n,k,l을 입력 받습니다.

2. n번 3개의 정수로 구성된 리스트를 입력 받습니다.

3. 입력받은 리스트의 최솟값과 합계를 각각 k와 l과 비교합니다.

4. 입력받은 리스트의 최솟값과 합계가 각각 k와 l보다 크다면 answer에 1을 더하고, vip 리스트에 3명의 기록을 넣습니다.

5. answer를 출력하고, vip에 들어있는 기록들을 출력합니다. 저는 vip 리스트를 스트링으로 변환 후, 맨 앞과 맨 뒤의 대괄호를 지우고, re의 sub함수를 활용하여 ','를 지워 출력하였습니다.

Python Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import sys, re
readline = sys.stdin.readline
def main():
    n,k,l = map(int,readline().split())
    ans = 0
    vip = []
    for _ in range(n):
        records = list(map(int,readline().split()))
        if min(records) >= l and sum(records) >= k :
            ans += 1
            vip += records
    print(ans)
    print(re.sub(',','',str(vip)[1:-1]))
if __name__ == '__main__':
    main()
 cs

문제 링크

 

20299번: 3대 측정

첫째 줄에 정수 $N$, $K$, $L$이 주어진다. $N$은 팀의 수, $K$는 팀원 $3$명의 레이팅 합에 대한 클럽 가입 조건, $L$은 개인 레이팅에 대한 클럽 가입 조건이다. ($1 \leq N \leq 500\ 000$, $0 \leq K \leq 12\ 000$, $

www.acmicpc.net

 

반응형

'알고리즘 > 백준' 카테고리의 다른 글

백준 1149 RGB거리 Python  (0) 2020.12.08
백준 1309 동물원  (0) 2020.12.07
백준 11057 오르막 수 Python  (0) 2020.12.03
백준 4358 생태학  (0) 2020.10.21
백준 1520 내리막 길  (0) 2020.10.20
반응형

2019 카카오 개발자 겨울 인턴십 문제입니다.

문제풀이

1. 정규표현식에서 '.'은 모든 문자 1개를 의미합니다. 따라서 banned_id의 모든 '*'을 '.'으로 바꾼 후 이를 컴파일러로 사용합니다.

2. user_id의 아이디 하나 u가 banned_id의 하나 b에 해당되기 위해서는 b로 만든 컴파일러에 u가 걸리고, b와 u의 길이가 같아야합니다. 저는 정규표현식의 match를 활용하였는데, match를 활용하면 'a.b'로 만든 컴파일러에 'aabb' 또한 매칭되므로 두번째 조건이 필요합니다.

3. 2 과정을 통해 모든 b에 해당하는 u의 리스트를 만듭니다.

user_id banned_id
["frodo", "fradi", "crodo", "abc123", "frodoc"] ["fr*d*", "abc1**"]

이 예를 사용하면 3의 결과는 다음과 같습니다.

{0: ['frodo', 'fradi'], 1: ['abc123']}

여기서 key값인 숫자는 b의 index입니다.

4. 3의 결과인 dictionary를 dfs 하여 최종 결과를 만들어냅니다.

 

*말로는 설명이 잘 안되어 아래 코드에서 자세히 다시 설명하겠습니다.

Python Code

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
import re
 
def solution(user_id, banned_id):
    # 가능한 제재id
    global answer
    answer = []
    # key : banned_id의 id의 index, value : 아래의 checked
    candidate = {}
    for i, b in enumerate(banned_id):
        # re.sub를 활용하여 b의 모든 *을 .으로 변환
        checker = re.compile(re.sub('\*','.',b))
        # banned_id 중 하나인 b에 매칭되는 user_id
        checked = []
        for u in user_id:
            # match가 안되면 결과가 None으로 두번째 조건 만족x
            if len(u) == len(b) and checker.match(u):
                checked.append(u)
        candidate[i] = checked
    # candidate를 활용하여 dfs
    for x in candidate[0]:
        dfs([x],candidate,len(banned_id))
 
    return len(answer)
 
'''
selected는 list로 selected[i]는 candidate[i]의 원소 중 하나. 즉 i번째 banned_id에 매칭되는 user_id 중 하나.
n은 banned_id의 길이.
dfs의 탈출 조건은 selected에 들어있는 원소의 수가 n이 되는 것이다.
'''
def dfs(selected,candidate, n):
    # 탈출조건
    if len(selected) == n:
        global answer
        # 중복을 제거하기 위해 selected를 정렬한 후 비교
        tmp = sorted(selected)
        if tmp not in answer:
            answer.append(tmp)
        return ;
    '''
    <selected의 원소 수가 n이 아닌 경우.>
    selected의 원소 수는 다음 banned_id의 index를 의미한다.
    ex) selected에 한개가 들어있으면 banned_id[1](banned_id의 두번째 요소)에 매칭되는 user_id의 집합인 
        candidate[1]의 원소 중 하나를 selected에 넣는다.
    '''
    for x in candidate[len(selected)]:
        if x not in selected:
            dfs(selected+[x],candidate,n)
 
 cs

문제링크

 

코딩테스트 연습 - 불량 사용자

개발팀 내에서 이벤트 개발을 담당하고 있는 무지는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량

programmers.co.kr

 

반응형

'알고리즘 > 프로그래머스' 카테고리의 다른 글

[프로그래머스] 신규 아이디 추천 - Python  (0) 2021.04.03
[프로그래머스] 3진법 뒤집기 - Python  (0) 2021.02.08
프로그래머스 캐시  (0) 2020.12.01
프로그래머스 튜플  (0) 2020.11.30
프로그래머스 n진수 게임  (0) 2020.11.10

+ Recent posts

티스토리툴바