출처: [백준] 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]]))

출처: [코딩테스트 연습 완주하지 못한 선수]

문제

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

제한

• 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
• completion의 길이는 participant의 길이보다 1 작습니다.
• 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
• 참가자 중에는 동명이인이 있을 수 있습니다.

입출력

입출력 예 1

예제 #1
“leo”는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #2
“vinko”는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #3
“mislav”는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.

출처

소스코드

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

from collections import Counter


def solution(participant, completion):
    participant.sort()
    completion.sort()
    answer = Counter(participant) - Counter(completion)
    return list(answer)[0]

# print(solution(["marina", "josipa", "nikola", "vinko", "filipa"], ["josipa", "filipa", "marina", "nikola"]))

'''
collection 라이브러리 사용
일반 dict는 빼기 불가,
counter를 사용하면 key, value로 되고...카운터 객체이므로 빼기 가능
마지막 리스트로 변환 후 0번째 출력--> 탈락자는 한명이다
'''

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

def solution(participant, completion):
    participant.sort()
    completion.sort()
    for p, c in zip(participant, completion):
        if p != c:
            return p
    return participant[-1]


# print(solution(["marina", "josipa", "nikola", "vinko", "filipa"], ["josipa", "filipa", "marina", "nikola"]))

'''
탈락자는 무조건 한명
참여자 명단의 인덱스와 완주자 명단의 인덱스 값이 다르다면,
그 때, 참여자는 완주자 명단에 없으므로, 반환
----
마지막까지 인덱스 값이 같다면, 참여자 명단 마지막 사람이 완주하지 못한 사람이다.
'''

출처: [백준] 1032번 명령 프롬프트

문제

시작 -> 실행 -> cmd를 쳐보자. 검정 화면이 눈에 보인다. 여기서 dir이라고 치면 그 디렉토리에 있는 서브디렉토리와 파일이 모두 나온다. 이때 원하는 파일을 찾으려면 다음과 같이 하면 된다.

dir *.exe라고 치면 확장자가 exe인 파일이 다 나온다. “dir 패턴”과 같이 치면 그 패턴에 맞는 파일만 검색 결과로 나온다. 예를 들어, dir a?b.exe라고 검색하면 파일명의 첫 번째 글자가 a이고, 세 번째 글자가 b이고, 확장자가 exe인 것이 모두 나온다. 이때 두 번째 문자는 아무거나 나와도 된다. 예를 들어, acb.exe, aab.exe, apb.exe가 나온다.

이 문제는 검색 결과가 먼저 주어졌을 때, 패턴으로 뭘 쳐야 그 결과가 나오는지를 출력하는 문제이다. 패턴에는 알파벳과 “.” 그리고 “?”만 넣을 수 있다. 가능하면 ?을 적게 써야 한다. 그 디렉토리에는 검색 결과에 나온 파일만 있다고 가정하고, 파일 이름의 길이는 모두 같다.

입력

첫째 줄에 파일 이름의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에는 파일 이름이 주어진다. N은 50보다 작거나 같은 자연수이고 파일 이름의 길이는 모두 같고 길이는 최대 50이다. 파일이름은 알파벳과 “.” 그리고 “?”로만 이루어져 있다.

출력

첫째 줄에 패턴을 출력하면 된다.

예제 입력 1

1
2
3
4

3
config.sys
config.inf
configures

예제 출력 1

1

config????

출처

• 문제를 번역한 사람: baekjoon

알고리즘 분류

• 구현
• 문자열

소스코드

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

import sys

input = sys.stdin.readline

N = int(input())
file_list = [list(input().rstrip()) for _ in range(N)]

input_word = file_list[-1]

for i in range(N - 1):
    for j in range(len(input_word)):
        if input_word[j] == file_list[i][j]:
            continue
        else:
            input_word[j] = '?'

print(''.join(input_word))