출처: [백준] 11723번 집합

문제

비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오.

• add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다.
• remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다.
• check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20)
• toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20)
• all: S를 {1, 2, …, 20} 으로 바꾼다.
• empty: S를 공집합으로 바꾼다.

입력

첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다.

둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다.

출력

check 연산이 주어질때마다, 결과를 출력한다.

예제 입력 1

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

26
add 1
add 2
check 1
check 2
check 3
remove 2
check 1
check 2
toggle 3
check 1
check 2
check 3
check 4
all
check 10
check 20
toggle 10
remove 20
check 10
check 20
empty
check 1
toggle 1
check 1
toggle 1
check 1

예제 출력 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

1
1
0
1
0
1
0
1
0
1
1
0
0
0
1
0

출처

• 문제를 만든 사람: baekjoon
• 빠진 조건을 찾은 사람: djm03178
• 데이터를 추가한 사람: houma757
• 문제의 오타를 찾은 사람: pichulias://www.acmicpc.net/user/djm03178)

알고리즘 분류

• 구현
• 비트마스킹

소스코드

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

import sys

input = sys.stdin.readline

M = int(input())
S = set()

for _ in range(M):
    comm = input().strip().split()

    if comm[0] == 'add':
        S.add(int(comm[1]))
    elif comm[0] == 'remove':
        S.discard(int(comm[1]))
    elif comm[0] == 'check':
        if int(comm[1]) in S:
            print(1)
        else:
            print(0)
    elif comm[0] == 'toggle':
        if int(comm[1]) in S:
            S.discard(int(comm[1]))
        else:
            S.add(int(comm[1]))
    elif comm[0] == 'all':
        S = set([i for i in range(1, 21)])
    elif comm[0] == 'empty':
        S = set()

출처: [백준] 2504번 괄호의 값

문제

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을 출력해야 한다.

예제 입력 1

1

(()[[]])([])

예제 출력 1

1

28

출처

• Olympiad > 한국정보올림피아드 > 한국정보올림피아드시․도지역본선 > 지역본선 2008 > 초등부 4번
• Olympiad > 한국정보올림피아드 > 한국정보올림피아드시․도지역본선 > 지역본선 2008 > 중등부 2번
  • 데이터를 추가한 사람: 906bc, djm03178, eatgugbab, leedongbin, sang7, sankim90
  • 잘못된 데이터를 찾은 사람: djm03178

알고리즘 분류

• 구현
• 자료 구조
• 스택
• 재귀

소스코드

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

import sys

input = sys.stdin.readline

input_string = list(input().rstrip())

stack = []


def solution(string):
    for bracket in string:

        if bracket == ')':
            tmp = 0
            while stack:
                top = stack.pop()
                if top == '(':
                    if tmp == 0:
                        stack.append(2)
                    else:
                        stack.append(tmp * 2)
                    break
                elif top == '[':
                    return 0
                else:
                    tmp += int(top)

        elif bracket == ']':
            tmp = 0
            while stack:
                top = stack.pop()
                if top == '[':
                    if tmp == 0:
                        stack.append(3)
                    else:
                        stack.append(tmp * 3)
                    break
                elif top == '(':
                    return 0
                else:
                    tmp += int(top)
        else:
            stack.append(bracket)
    return stack


if solution(input_string):
    print(0 if '(' in stack or '[' in stack else sum(stack))
else:
    print(0)

출처: [백준] 2167번 2차원 배열의 합

문제

2차원 배열이 주어졌을 때 (i, j) 위치부터 (x, y) 위치까지에 저장되어 있는 수들의 합을 구하는 프로그램을 작성하시오. 배열의 (i, j) 위치는 i행 j열을 나타낸다.

입력

첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는 합을 구할 부분의 개수 K(1 ≤ K ≤ 10,000)가 주어진다. 다음 K개의 줄에는 네 개의 정수로 i, j, x, y가 주어진다(i ≤ x, j ≤ y).

출력

K개의 줄에 순서대로 배열의 합을 출력한다. 배열의 합은 231-1보다 작거나 같다.

예제 입력 1

1
2
3
4
5
6
7

2 3
1 2 4
8 16 32
3
1 1 2 3
1 2 1 2
1 3 2 3

예제 출력 1

1
2
3

63
2
36

출처

• 빠진 조건을 찾은 사람: iriszero
• 잘못된 데이터를 찾은 사람: tncks0121

알고리즘 분류

• 구현
• 누적 합

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

import sys

input = sys.stdin.readline

N, M = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(N)]
K = int(input())

dp = [[0] * (M + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
    for j in range(1, M + 1):
        dp[i][j] = matrix[i - 1][j - 1] + dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1]

for _ in range(K):
    i, j, x, y = map(int, input().split())
    print(dp[x][y] - dp[x][j - 1] - dp[i - 1][y] + dp[i - 1][j - 1])

소스코드 (시간초과)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

import sys

input = sys.stdin.readline

N, M = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(N)]
K = int(input())

for _ in range(K):
    i, j, x, y = map(int, input().split())
    arr_sum = 0
    for a in range(i, x + 1):
        for b in range(j, y + 1):
            arr_sum += matrix[a - 1][b - 1]
    print(arr_sum)

출처: [백준] 3046번 R2

문제

두 숫자 R1과 R2가 있을 때, 두 수의 평균 S는 (R1+R2)/2와 같다. 상근이는 정인이 생일 선물로 두 숫자 R1과 R2를 주려고 한다. 생일 파티에서 상근이는 정인이에게 이 두 숫자를 말해주고, 정인이는 이 숫자를 받아 적는다. 그리고 나서 기쁜 마음으로 1년동안 이 숫자를 외우면서 산다.

상근이는 R1과 R2를 엄청난 고민 끝에 정했다. 작년에는 R1과 R2를 까먹어서 아무 숫자나 정해서 주었기 때문에, 올해는 까먹지 않기 위해서 평균 S도 같이 기억하려고 한다.

오늘은 정인이 생일이다. 5분 후에 상근이는 생일 선물로 두 숫자 R1과 R2를 말해주어야 하지만, 안타깝게도 R2를 까먹고 말았다. 하지만 R1과 S는 기억하고 있다!

상근이를 도와 R2가 몇 인지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 두 정수 R1과 S가 주어진다. 두 수는 -1000보다 크거나 같고, 1000보다 작거나 같다.

출력

첫째 줄에 R2를 출력한다.

예제 입력 1

1

11 15

예제 출력 1

1

19

예제 입력 2

1

4 3

예제 출력 2

1

2

출처

• Contest > Croatian Open Competition in Informatics > COCI 2006/2007 > Contest #2 1번
  • 문제를 번역한 사람: baekjoon

알고리즘 분류

• 수학
• 구현
• 사칙연산

소스코드

1
2
3
4

R1, S = map(int, input().split())

print(S * 2 - R1)

출처: [백준] 10797번 10부제

문제

서울시는 6월 1일부터 교통 혼잡을 막기 위해서 자동차 10부제를 시행한다. 자동차 10부제는 자동차 번호의 일의 자리 숫자와 날짜의 일의 자리 숫자가 일치하면 해당 자동차의 운행을 금지하는 것이다. 예를 들어, 자동차 번호의 일의 자리 숫자가 7이면 7일, 17일, 27일에 운행하지 못한다. 또한, 자동차 번호의 일의 자리 숫자가 0이면 10일, 20일, 30일에 운행하지 못한다.

여러분들은 일일 경찰관이 되어 10부제를 위반하는 자동차의 대수를 세는 봉사활동을 하려고 한다. 날짜의 일의 자리 숫자가 주어지고 5대의 자동차 번호의 일의 자리 숫자가 주어졌을 때 위반하는 자동차의 대수를 출력하면 된다.

입력

첫 줄에는 날짜의 일의 자리 숫자가 주어지고 두 번째 줄에는 5대의 자동차 번호의 일의 자리 숫자가 주어진다. 날짜와 자동차의 일의 자리 숫자는 모두 0에서 9까지의 정수 중 하나이다.

출력

주어진 날짜와 자동차의 일의 자리 숫자를 보고 10부제를 위반하는 차량의 대수를 출력한다.

예제 입력 1

1
2

1
1 2 3 4 5

예제 출력 1

1

1

예제 입력 2

1
2
3

1
1
1

예제 출력 2

1

2

예제 입력 3

1
2

5
1 3 0 7 4

예제 출력 3

1

0

출처

• Olympiad > 한국정보올림피아드 > 한국정보올림피아드시․도지역본선 > 지역본선 2015 > 초등부 1번
  • 데이터를 만든 사람: baekjoon
  • 잘못된 데이터를 찾은 사람: jh05013

알고리즘 분류

• 구현

소스코드

1
2
3
4
5
6
7
8
9
10
11

N = int(input())
car_list = list(map(int, input().split()))

count = 0

for car in car_list:
    if N == car:
        count += 1

print(count)

출처: [백준] 2902번 KMP는 왜 KMP일까?

문제

KMP 알고리즘이 KMP인 이유는 이를 만든 사람의 성이 Knuth, Morris, Prett이기 때문이다. 이렇게 알고리즘에는 발견한 사람의 성을 따서 이름을 붙이는 경우가 많다.

또 다른 예로, 유명한 비대칭 암호화 알고리즘 RSA는 이를 만든 사람의 이름이 Rivest, Shamir, Adleman이다.

사람들은 이렇게 사람 성이 들어간 알고리즘을 두 가지 형태로 부른다.

• 첫 번째는 성을 모두 쓰고, 이를 하이픈(-)으로 이어 붙인 것이다. 예를 들면, Knuth-Morris-Pratt이다. 이것을 긴 형태라고 부른다.
• 두 번째로 짧은 형태는 만든 사람의 성의 첫 글자만 따서 부르는 것이다. 예를 들면, KMP이다.

동혁이는 매일매일 자신이 한 일을 모두 메모장에 적어놓는다. 잠을 자기 전에, 오늘 하루 무엇을 했는지 되새겨 보는 것으로 하루를 마감한다.

하루는 이 메모를 보던 중, 지금까지 긴 형태와 짧은 형태를 섞어서 적어 놓은 것을 발견했다.

이렇게 긴 형태로 하루 일을 기록하다가는 메모장 가격이 부담되어 파산될 것이 뻔하기 때문에, 앞으로는 짧은 형태로 기록하려고 한다.

긴 형태의 알고리즘 이름이 주어졌을 때, 이를 짧은 형태로 바꾸어 출력하는 프로그램을 작성하시오.

입력

입력은 한 줄로 이루어져 있고, 최대 100글자의 영어 알파벳 대문자, 소문자, 그리고 하이픈 (‘-‘, 아스키코드 45)로만 이루어져 있다. 첫 번째 글자는 항상 대문자이다. 그리고, 하이픈 뒤에는 반드시 대문자이다. 그 외의 모든 문자는 모두 소문자이다.

출력

첫 줄에 짧은 형태 이름을 출력한다.

예제 입력 1

1

Knuth-Morris-Pratt

예제 출력 1

1

KMP

예제 입력 2

1

Mirko-Slavko

예제 출력 2

1

MS

예제 입력 3

1

Pasko-Patak

예제 출력 3

1

PP

출처

• Contest > Croatian Open Competition in Informatics > COCI 2009/2010 > Contest #4 1번
  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: eric00513
  • 빠진 조건을 찾은 사람: hoy9090

알고리즘 분류

• 구현
• 문자열

소스코드1

1
2
3
4
5
6
7

input_string = list(input().split('-'))
output_string = ''

for x in input_string:
    output_string += x[0]

print(output_string)

소스코드2

1
2
3
4
5
6
7
8
9

input_string = list(input().rstrip())
output_string = ''

for x in input_string:
    if 'A' <= x <= 'Z':
        output_string += x

print(output_string)

출처: [코딩테스트 연습 타겟넘버]

문제

n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

1
2
3
4
5

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

제한

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

입출력

풀이

-

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

from collections import deque


def solution(numbers, target):
    answer = 0
    queue = deque()
    queue.append((0, 0))
    while queue:
        idx, total = queue.popleft()

        if idx == len(numbers):
            if total == target:
                answer += 1
        else:
            num = numbers[idx]
            queue.append((idx + 1, total + num))
            queue.append((idx + 1, total - num))
    return answer

출처: [코딩테스트 연습 이중우선순위큐]

출처

문제

이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.

이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요.

제한

• operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다.
• operations의 원소는 큐가 수행할 연산을 나타냅니다.
  • 원소는 “명령어 데이터” 형식으로 주어집니다.- 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다.
• 빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.

입출력

입출력 예 1

16을 삽입 후 최댓값을 삭제합니다. 비어있으므로 [0,0]을 반환합니다.
7,5,-5를 삽입 후 최솟값을 삭제합니다. 최대값 7, 최소값 5를 반환합니다.

풀이

• 조건 대로 시행
• 최대값은 heapq.nlargest() 이용

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

import heapq


def solution(operations):
    answer = []
    heapq.heapify(answer)
    for comm in operations:
        com, num = comm.split()
        if com == 'I':
            heapq.heappush(answer, int(num))
        elif com == 'D':
            if not answer:
                continue
            else:
                if num == '1':
                    answer.pop(answer.index(heapq.nlargest(1, answer)[0]))
                elif num == '-1':
                    heapq.heappop(answer)

    if not answer:
        return [0, 0]
    else:
        return [heapq.nlargest(1, answer)[0], answer[0]]

출처: [코딩테스트 연습 카펫]

문제

Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.

Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.

Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한

• 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
• 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.
• 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.

입출력

출처

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14

def solution(brown, yellow):
    answer = []
    carpet = brown + yellow
    for i in range(1, carpet + 1):
        col = i
        row = carpet / col

        if col >= row:
            if (col - 2) * (row - 2) == yellow:
                answer.append(col)
                answer.append(int(row))
                break

    return answer

출처: [코딩테스트 연습 등굣길]

문제

계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다.

아래 그림은 m = 4, n = 3 인 경우입니다.

가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다.

격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요.

제한

• 격자의 크기 m, n은 1 이상 100 이하인 자연수입니다.
  • m과 n이 모두 1인 경우는 입력으로 주어지지 않습니다.
• 물에 잠긴 지역은 0개 이상 10개 이하입니다.
• 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.

입출력

입출력 예 1

풀이

-

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

def solution(m, n, puddles):
    matrix = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
    matrix[1][1] = 1

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if i == 1 and j == 1:
                continue
            if [j, i] in puddles:
                continue
            else:
                matrix[i][j] = matrix[i - 1][j] + matrix[i][j - 1]
    return matrix[n][m] % 1000000007


print(solution(4, 3, [[2, 2]]))