둔필승총

www.acmicpc.net/problem/2108

문제

수를 처리하는 것은 통계학에서 상당히 중요한 일이다. 통계학에서 N개의 수를 대표하는 기본 통계값에는 다음과 같은 것들이 있다. 단, N은 홀수라고 가정하자.

1. 산술평균 : N개의 수들의 합을 N으로 나눈 값
2. 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값
3. 최빈값 : N개의 수들 중 가장 많이 나타나는 값
4. 범위 : N개의 수들 중 최댓값과 최솟값의 차이

N개의 수가 주어졌을 때, 네 가지 기본 통계값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다.

출력

첫째 줄에는 산술평균을 출력한다. 소수점 이하 첫째 자리에서 반올림한 값을 출력한다.

둘째 줄에는 중앙값을 출력한다.

셋째 줄에는 최빈값을 출력한다. 여러 개 있을 때에는 최빈값 중 두 번째로 작은 값을 출력한다.

넷째 줄에는 범위를 출력한다.

예제 입력 1

5 1 3 8 -2 2

예제 출력 1

2 2 1 10

예제 입력 2

1 4000

예제 출력 2

4000 4000 4000 0

예제 입력 3

5 -1 -2 -3 -1 -2

예제 출력 3

-2 -2 -1 2

[문제 해설]

문제에서 구할 것이 꽤 많다. 평균, 중앙값, 최빈값, 최대값과 최솟값의 차이이다. 하나씩 해결해 나가면 된다.

먼저 1번부터 구해보자.

n = int(sys.stdin.readline())

datas=[]
for _ in range(n):
    datas.append(int(sys.stdin.readline()))

def first(datas):
    return round(sum(datas)/len(datas))

여기서 까다로운 점은 소수점 첫째 자리에서 반올림한 값을 출력해야된다는 것이다. round함수를 사용하자. round함수에서 두번째 인수를 생략하면 앞에 인자에 가장 가까운 정수를 출력한다. 소수 첫째자리에서 반올림하고 싶은 것을 해결해 줄 수 있다. 

2번은 중앙값을 출력하는 것이다. 중간 인덱스를 변수로 저장하여 풀면 된다.

def second(datas):
    datas.sort()
    mid = (len(datas))//2
    return datas[mid]

3번은 어떻게 풀지 감이 아예 오지 않았다. 배열을 2개씩 만들어서도 풀려고 했는데 계속 실패하였다. 

찾아보니 최빈값은 모듈을 이용해서 쉽게 해결할 수 있었다. 

collections모듈에서 Counter클래스를 사용하는 것이다. 데이터의 개수를 셀 때 파이썬의 collections모듈의 Counter클래스가 유용하다.

Counter클래스는 파이썬의 기본 자료구조인 사전형을 확장하고 있기 때문에, 사전에서 제공하는 API를 그대로 사용할 수 있다. Counter 클래스는 데이터의 개수가 많은 순으로 정렬된 배열을 리턴하는 most_common이라는 메서드를 제공하고 있기 때문에 최빈값을 구하는데 사용할 수가 있다.

from collections import Counter

Counter('hello world').most_common() 
# [('l', 3), ('o', 2), ('h', 1), ('e', 1), (' ', 1), ('w', 1), ('r', 1), ('d', 1)]

다음과 같이 많은 순서대로 리턴할 수 있다. 이것을 최밴값에 사용해보자.

from collections import Counter

def third(datas):
    mode_dict = Counter(datas)
    modes = mode_dict.most_common()

    if len(datas) > 1:
        if modes[0][1] == modes[1][1]:
            mod = modes[1][0]
        else:
            mod = modes[0][0]
    else:
        mod = modes[0][0]

    return mod

modes[0][1]은 datas에서 제일 많이 나온 값의 개수를 의미 한다. 최빈값이 여러 개일 경우 두번째로 작은 값을 출력하라고 했으니 modes[0][1] == modes[1][1]일때 modes[1][0]을 출력하고 그렇지 않을때는 modes[0][0]을 출력하면 된다.

4번은 최대값에서 최소값을 빼면 된다.

모든 코드는 아래와 같다.

from collections import Counter
import sys
n = int(sys.stdin.readline())

datas=[]
for _ in range(n):
    datas.append(int(sys.stdin.readline()))

def first(datas):
    return round(sum(datas)/len(datas))

def second(datas):
    datas.sort()
    mid = (len(datas))//2
    return datas[mid]

def third(datas):
    mode_dict = Counter(datas)
    modes = mode_dict.most_common()

    if len(datas) > 1:
        if modes[0][1] == modes[1][1]:
            mod = modes[1][0]
        else:
            mod = modes[0][0]
    else:
        mod = modes[0][0]

    return mod

def fourth(datas):
    return max(datas)-min(datas)

print(first(datas))
print(second(datas))
print(third(datas))
print(fourth(datas))

www.acmicpc.net/problem/11047

문제

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

출력

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

예제 입력 1

10 4200

1

5

10

50

100

500

1000

5000

10000

50000

예제 출력 1

6

예제 입력 2

10 4790

1

5

10

50

100

500

1000

5000

10000

50000

예제 출력 2

12

[문제 해설]

n종류의 동전으로 k금액을 만들면 된다. 그리디 알고리즘을 이용해 풀 수 있는 대표적인 문제로 간단한 아이디어만 떠올릴 수 있으면 된다. 그것은 바로 '가장 큰 화폐 단위부터' 나누어 주는 것이다. 물론 k보다 큰 금액이면 나눌 수 없으므로 k보다 작은 것중에 제일 큰 수부터 나누면 된다.

n,k=map(int,input().split())
a=[]
for _ in range(n):
    a.append(int(input()))
a.sort(reverse=True)
ans=0
for i in range(n):
    if a[i]>k:
        continue
    else:
        ans+=k//a[i]
        k=k%a[i]
print(ans)

그리디 알고리즘은 모든 알고리즘 문제에 적용할 수 있는 것은 아니다. 대부분의 문제는 그리디 알고리즘을 이용했을 때 '최적의 해'를 찾을 수 없을 가능성이 많다. 

사실 그냥 머리에 떠올린대로 그리디 해법을 생각했을때 해법이 정당한지 컴토해야 한다. 여기서 그리디 알고리즘을 검증하려면 조건을 유심히 봐야된다.

 괄호 안에 주어진 조건을 자세히 살펴보자. 이 문제에서는 조건이 중요하다.

(1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) Ai는 Ai-1의 배수라는 점. 그리디 알고리즘의 정당성을 부여하려면 예시를 들어보자. 만약 k의 값이 800원이고 Ai 배열에서 500원, 400원, 100원이라면 우리가 짠 그리디 알고리즘으로는 500원 1개, 100원 3개가 최적의 답으로 나온다. 그러나 사실 400원 2개 주는 것이 더 이득이다. 이 문제는 다이나믹 알고리즘으로 따로 풀 수 있다.

 이 문제에서 그리디 알고리즘을 쓸 수 있었던것은 Ai는 Ai-1의 배수라는 사실 때문이다.

아래에서 더 자세히 설명해 두었다.

2020.10.02 - [알고리즘/알고리즘 이론] - 그리디(Greedy) 알고리즘

www.acmicpc.net/problem/2667

문제

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

출력

첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

예제 입력 1

7
0110100
0110101
1110101
0000111
0100000
0111110
0111000

예제 출력 1

3
7
8
9

[문제 풀이]

일단 <그림1>에서 1이 적힌 곳을 찾아서 0이 나올때까지 끝까지 탐색을 시켜줘야된다. 여기서 깊이 우선 탐색을 생각해 낼 수 있다. 지도에서 공간이 상, 하, 좌, 우로 연결되어 있다고 표현할 수 있으므로 그래프 형태로 모델링 할 수 있다. 

1. 특정한 지점의 주변 상, 하, 좌, 우를 살펴본 뒤에 주변 지점 중에서 값이 '0'이면서 아직 방문하지 않은 지점이 있다면 해당 지점을 방문한다.

2. 방문한 지점에서 다시 상, 하, 좌, 우를 살펴보면서 방문을 다시 진행하면, 연결된 모든 지점을 방문할 수 있다.

n = int(input())
graph=[]#지도
apt=[]
for _ in range(n):
    graph.append(list(map(int,input())))

def dfs(x,y):
    global cnt
    if x<=-1 or x>=n or y<=-1 or y>=n:
        return False
    if graph[x][y]==1:
        graph[x][y]=0
        cnt+=1
        dfs(x-1,y)
        dfs(x+1,y)
        dfs(x,y+1)
        dfs(x,y-1)
        return True
    return False
cnt=0
for i in range(n):
    for j in range(n):
        if dfs(i,j)==True:
            apt.append(cnt)
            cnt =0
apt.sort()
print(len(apt))
for i in range(len(apt)):
    print(apt[i])

코드를 설명해보겠다.

일단 출력해야 되는 것은 2개이다. 아파트 단지의 개수와 단지 안에 아파트 수이다. apt 리스트에는 아파트 수가 담겨있게 하고 단지 수는 len(apt)로 구할 생각을 했다.

위에서 말했듯이 dfs로 풀었다. 일단 dfs함수에서 x,y 가 갈 수 없는 곳을 갔을 때는 False를 return해 주었다.

그리고 graph에서 값이 1일때 단지 수를 세면 되니까 1일때 graph의 값을 방문했다는 의미로 0을 대입해주고 아파트 수 즉 cnt를 1씩 늘여간다. 

그리고 dfs함수로 상, 하, 좌, 우를 방문한다.

n*n 반복문으로 apt를 구한다.

www.acmicpc.net/problem/2798

문제

카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다.

한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다.

김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다.

이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다.

N장의 카드에 써져 있는 숫자가 주어졌을 때, M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 구해 출력하시오.

입력

첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다.

합이 M을 넘지 않는 카드 3장을 찾을 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 출력한다.

예제 입력 1

5 21

5 6 7 8 9

예제 출력 1

21

예제 입력 2

10 500

93 181 245 214 315 36 185 138 216 295

예제 출력 2

497

[문제 해설]

먼저 해볼 수 있는 생각은 카드를 3개 뽑아서 m을 넘지않는 수를 뽑는 것이다. 간단하게 3중 포문을 돌려서 3개의 카드가 같지 않고 m을 넘지 않을때 값을 저장해 둔다. 이 값들 중 최대의 것을 뽑으면 된다. m보다 작은 값이 나올 수도 있으므로 나온 값들 중 최대를 뽑으면 되는것이다.

1. m을 넘는 경우 출력을 안하는 것을 생각해 주어야 한다.

2. 3중 for문을 돌릴 때 3개가 동일한 값이 들어가면 안되니까 조건을 추가해준다.

n,m = map(int,input().split())
cards=list(map(int,input().split()))
answer=0
for i in cards:
    for j in cards:
        for k in cards:
            if i!=j and i!=k and j!=k:
                sum=i+j+k
                if sum>m:
                    continue
                else:
                    answer=max(answer,sum)
print(answer)

www.acmicpc.net/problem/10814

문제

온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 온라인 저지 회원의 수 N이 주어진다. (1 ≤ N ≤ 100,000)

둘째 줄부터 N개의 줄에는 각 회원의 나이와 이름이 공백으로 구분되어 주어진다. 나이는 1보다 크거나 같으며, 200보다 작거나 같은 정수이고, 이름은 알파벳 대소문자로 이루어져 있고, 길이가 100보다 작거나 같은 문자열이다. 입력은 가입한 순서로 주어진다.

출력

첫째 줄부터 총 N개의 줄에 걸쳐 온라인 저지 회원을 나이 순, 나이가 같으면 가입한 순으로 한 줄에 한 명씩 나이와 이름을 공백으로 구분해 출력한다.

예제 입력 1

3

21 Junkyu

21 Dohyun

20 Sunyoung

예제 출력 1

20 Sunyoung

21 Junkyu

21 Dohyun

[문제 해설]

이 문제는 두 가지 조건이 있다. 먼저 나이순으로 정렬을 하고 그 다음 먼저 온 순서대로 정렬을 하면 된다. 

n = int(input())

data = []
for i in range(n):
    age, name = list(input().split())
    age=int(age)
    data.append((age, name, i))
data = sorted(data, key=lambda x: x[0])

for i in range(n):
    print(str(data[i][0]) + ' ' + data[i][1])

그리고 type에 따라 비교가 다르게 되기 때문에 나이는 int로 바꾸어서 계산해준다.

www.acmicpc.net/problem/1181

문제

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

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

입력

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

출력

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

예제 입력 1

13

but

i

wont

hesitate

no

more

no

more

it

cannot

wait

im

yours

예제 출력 1

i

im

it

no

but

more

wait

wont

yours

cannot

hesitate

[문제 해설]

이 문제는 두 가지 해결해야 될 점이 있다. 먼저 길이가 짧은 순서대로 단어를 정렬해야 되고, 두 번째 그 정렬된 상태를 단어 사전 순서대로 정렬하면 된다. 두 가지 조건이 있으면 lambda 함수를 떠올려서 정렬하는 방법을 생각하면 된다.

그리고 중복을 제거해야 하기 때문에 set으로 바꾼뒤에 다시 list형식으로 바꾸어 준다.

n = int(input())
datas=[]
for _ in range(n):
    word = input()
    word_c = len(word)
    datas.append((word,word_c))
#중복 값 제거
datas=list(set(datas))

datas.sort(key=lambda word:(word[1],word[0]))

for i in range(len(datas)):
    print(datas[i][0])

www.acmicpc.net/problem/1931

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용 표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 2^31-1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

예제 입력 1

11

1 4

3 5

0 6

5 7

3 8

5 9

6 10

8 11

8  12

2 13

12 14

예제 출력 1

4

[문제 해설]

출력에서 4는 힌트에 있듯이 (1,4), (5,7), (8,11), (12,14)을 이용한 경우이다. 배열에는 시작시간과 종료시간이 동시에 입력되어있고 동시에 고려해야 된다. 회의의 최대 개수를 구해야 한다. 파이썬 정렬을 다중 조건으로 하려고 할 때는 lambda함수를 사용하면 쉽게 할 수 있다.

#lambda함수

일반적으로 우리는 파이썬 내장 함수인 .sort() 또는 sorted()를 사용한다. 배열을 sort()를 이용하면 오름차순으로 바뀐다. 

sorted() 함수가 어떻게 작동하는지 자세히 살펴보자. 

data=[[1,2],[3,5],[3,4],[0,5],[1,7],[4,5]]
s_data=sorted(data)#[[0, 5], [1, 2], [1, 7], [3, 4], [3, 5], [4, 5]]

인자 없이 그냥 sorted()만 쓰면, 리스트 아이템의 각 요소 순서대로 정렬을 한다. key 인자를 함수에 넘겨주면 해당 함수의 반환 값을 비교하여 순서대로 정렬한다. 예를 들어 data의 첫 번째 요소로 정렬할 것인지, 두 번째 요소로 정렬할 것인지 정해줄 수 있다. 그리고 첫 번째 요소로 정렬하고 그다음 두 번째 요소로 정렬을 시도할 수도 있다.

data=[[1,2],[3,5],[3,4],[0,5],[1,7],[4,5]]
s_data=sorted(data) #[[0, 5], [1, 2], [1, 7], [3, 4], [3, 5], [4, 5]]
s2_data=sorted(data,key=lambda x:x[0])#[[0, 5], [1, 2], [1, 7], [3, 5], [3, 4], [4, 5]]
s3_data=sorted(data,key=lambda x:(x[0],x[1]))#[[0, 5], [1, 2], [1, 7], [3, 4], [3, 5], [4, 5]]

sorted()의 key의 인자로, 내가 정렬할 비교 함수를 넣어주면 된다. 비교 함수는 비교할 아이템의 요소를 반화하면 된다. lambda는 비교하는 익명 함수인 것이다. 

그럼 이 문제에서는 lambda함수를 사용할 수 있을까? 주어진 시작시간과 끝나는 시간들을 이용해서 가장 많은 회의의 수를 알기 위해서는 빨리 끝나는 회의 순서대로 정렬을 해야 한다. 빨리 끝날수록 뒤에서 고려해볼 회의가 많기 때문이다. 일단 시작 시간 기준으로 정렬을 하고 종료 시간 기준으로 정렬을 해준다. lambda함수를 사용해서 정렬한 뒤에 시작 시간이 제일 빠른 것을 저장해 둔 뒤 시작시간을 비교하여 만약 시작시간이 저장해둔 종료시간보다 크면 그 수업을 선택한 뒤 시작시간을 업데이트해준다. 코드는 다음과 같다.

n = int(input())
meeting=[]
for i in range(n):
    start,end= map(int,input().split())
    meeting.append((start,end))

#시작 시간 기준으로 정렬
meeting=sorted(meeting,key=lambda x:x[0])
#종료 시간 기준으로 정렬
meeting=sorted(meeting,key=lambda x:x[1])

start_time=0
result=0
for time in meeting:
    if time[0]>=start_time:
        start_time=time[1]
        result+=1

print(result)

www.acmicpc.net/problem/10989

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

예제 입력 1

10

5

2

3

1

4

2

3

5

1

7

예제 출력 1

1

1

2

2

3

3

4

5

5

7

[문제 해설]

 오름차순으로 n개의 수를 정렬하면 된다. 물론 배열에 저장해서 오름차순으로 정렬하는 방법을 맨 처음 떠올리겠지만 메모리가 8MB밖에 안된다는 것이 이 문제의 함정이다. 따라서 계수정렬을 이용하였다.

 계수정렬(Count Sort)알고리즘은 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다. 데이터의 개수가 N, 데이터 중 최댓값이 K일 떄, 계수 정렬은 최악의 경우에도 수행 시간 O(N+K)를 보장한다. 여기서 숫자의 크기가 10000보다 작기 때문에 계수정렬을 쓸 수 있는 것이다. 1부터 10000까지의 배열을 0으로 저장해두고 각 숫자가 나올때마다 크기를 1씩 증가시킨다. input을 받을때 같이 data에 숫자를 1씩 증가시키고 나중에 정답으로 출력시켜주면 된다.

import sys
input = sys.stdin.readline

n = int(input())
data=[0]*10001
for _ in range(n):
    num = int(input())
    data[num-1]+=1

for i in range(10000):
    if data[i]!=0:
        for j in range(data[i]):
            print(i+1)