IT-garden

문제 설명

가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 따라 1cm × 1cm의 정사각형으로 잘라 사용할 예정이었는데, 누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다. 그러므로 현재 직사각형 종이는 크기가 같은 직각삼각형 2개로 나누어진 상태입니다. 새로운 종이를 구할 수 없는 상태이기 때문에, 이 종이에서 원래 종이의 가로, 세로 방향과 평행하게 1cm × 1cm로 잘라 사용할 수 있는 만큼만 사용하기로 하였습니다.
가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solution 함수를 완성해 주세요.

제한조건

• W, H : 1억 이하의 자연수
  
  

입출력 예

입출력 예 설명

입출력 예 #1
가로가 8, 세로가 12인 직사각형을 대각선 방향으로 자르면 총 16개 정사각형을 사용할 수 없게 됩니다. 원래 직사각형에서는 96개의 정사각형을 만들 수 있었으므로, 96 - 16 = 80 을 반환합니다.

나의 풀이

import math

def solution(w,h):
    if w > h:
        w, h = h, w
    
    return w*h - (h+w-math.gcd(w,h))

다른 사람의 풀이

def gcd(a,b): return b if (a==0) else gcd(b%a,a)    
def solution(w,h): return w*h-w-h+gcd(w,h)

import math 대신 직접 최대공약수 알고리즘을 만들었습니다.

프로그래머스 '멀쩡한 사각형' : https://programmers.co.kr/learn/courses/30/lessons/62048

문제

알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다.

입력

첫째 줄에 알파벳 대소문자로 이루어진 단어가 주어진다. 주어지는 단어의 길이는 1,000,000을 넘지 않는다.

출력

첫째 줄에 이 단어에서 가장 많이 사용된 알파벳을 대문자로 출력한다. 단, 가장 많이 사용된 알파벳이 여러 개 존재하는 경우에는 ?를 출력한다.

예제 입력과 출력

알고리즘 분류

문자열 처리 

정답

s=input().upper()
li=[0]*26
m=0
r=''

for i in s:
    li[ord(i)-ord('A')] += 1
    if m < li[ord(i)-ord('A')]:
        m=li[ord(i)-ord('A')]
        r=i

if li.count(m) >= 2:
    print('?')
else:
    print(r)

for문을 통해 각각 알파벳의 자리에 개수를 올려줍니다.
알파벳의 개수가 가장 많으면 해당 알파벳을 r에 저장합니다.
m이 2개 이상이면 '?'를 출력하고 그렇지 않으면 알파벳을 출력합니다.

백준 알고리즘 1157번 : https://www.acmicpc.net/problem/1157

문제

크리보드는 kriii가 만든 신기한 키보드이다. 크리보드에는 버튼이 4개만 있으며, 하는 역할은 다음과 같다.

1. 화면에 A를 출력한다.
2. Ctrl-A: 화면을 전체 선택한다
3. Ctrl-C: 전체 선택한 내용을 버퍼에 복사한다
4. Ctrl-V: 버퍼가 비어있지 않은 경우에는 화면에 출력된 문자열의 바로 뒤에 버퍼의 내용을 붙여넣는다.

크리보드의 버튼을 총 N번 눌러서 화면에 출력된 A개수를 최대로하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 100)이 주어진다.

출력

크리보드의 버튼을 총 N번 눌러서 화면에 출력할 수 있는 A 개수의 최댓값을 출력한다.

예제 입력과 출력

알고리즘 분류

다이나믹 프로그래밍

정답

import sys
input = lambda : sys.stdin.readline().strip()

n=int(input())

dp = [i for i in range(0, 102)]

for i in range(6, 101):
    dp[i] = max(dp[i-3]*2, max(dp[i-4]*3, dp[i-5]*4))
    
print(dp[n])

백준 알고리즘 11058번 : https://www.acmicpc.net/problem/11058

최대공약수(GCD : Greatest Common Divisor)
최대공약수는 두 자연수의 공통된 약수 중 가장 큰 수를 의미합니다.

최소공배수(LCM : Least Common Multiple)

최소공배수는 두 자연수의 공통된 배수 중 가장 작은 수를 의미합니다.

최소공배수 = 두 자연수의 곱 / 최대공약수

유클리드 알고리즘은 자연수 2개의 최대공약수를 구하는 알고리즘입니다.
2개의 자연수 a, b(a > b)에 대해 a를 b로 나눈 나머지를 r(0 < r < b)이라 하면 a와 b의 최대공약수는 b와 r의 최대공약수와 같습니다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수입니다. 이 알고리즘은 명시적으로 기술된 가장 오래된 알고리즘으로도 알려져 있습니다.

유클리드 알고리즘은
1. a, b 두 수가 주어집니다. (a > b)
2. b가 0이면 a을 리턴합니다.
3. a가 b로 나눠 떨어지지 않으면 a를 b로, b를 a에서 b로 나눈 나머지를 대입하고 1번으로 돌아갑니다.
3. a가 b로 나눠 떨어지면 b을 리턴합니다.

유클리드 알고리즘을 이용해 54, 20의 최대공약수를 구하는 예시입니다. (%는 나머지 구하기)
54 % 20 = 14
20 % 14 = 6
14 % 6 = 2
6 % 2 = 0

6 % 2가 0이 되기 때문에 최대공약수는 2가 됩니다.

이를 이용해 54*20/2=540를 계산하면 나오면 540이 최소공배수가 됩니다.

유클리드 알고리즘을 이용해 54, 24의 최대공약수를 구하는 예시입니다.
54 % 24 = 6
24 % 6 = 0
24 % 6가 0이 되기 때문에 최대공약수는 6이 됩니다.

최대공약수(GCD)와 최소공배수(LCM) 알고리즘의 파이썬 코드입니다.

def gcd(a,b): # 최대공약수
    if b == 0:
        return a
    if a % b == 0:
        return b
    else:
        return gcd(b, a % b)

x=54
y=20

# 최대공약수(GCD)
# 출력>>2
print(gcd(x,y))

# 출력>>6
print(gcd(54,24))

# 최소공배수(LCM)
# 출력>>540
print(int(x*y/gcd(x,y)))

문제

명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다.

먼저, 홍준이는 자연수 N개를 칠판에 적는다. 그 다음, 명우에게 질문을 총 M번 한다.

각 질문은 두 정수 S와 E(1 ≤ S ≤ E ≤ N)로 나타낼 수 있으며, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지를 물어보며, 명우는 각 질문에 대해 팰린드롬이다 또는 아니다를 말해야 한다.

예를 들어, 홍준이가 칠판에 적은 수가 1, 2, 1, 3, 1, 2, 1라고 하자.

• S = 1, E = 3인 경우 1, 2, 1은 팰린드롬이다.
• S = 2, E = 5인 경우 2, 1, 3, 1은 팰린드롬이 아니다.
• S = 3, E = 3인 경우 1은 팰린드롬이다.
• S = 5, E = 7인 경우 1, 2, 1은 팰린드롬이다.

자연수 N개와 질문 M개가 모두 주어졌을 때, 명우의 대답을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 크기 N (1 ≤ N ≤ 2,000)이 주어진다.

둘째 줄에는 홍준이가 칠판에 적은 수 N개가 순서대로 주어진다. 칠판에 적은 수는 100,000보다 작거나 같은 자연수이다.

셋째 줄에는 홍준이가 한 질문의 개수 M (1 ≤ M ≤ 1,000,000)이 주어진다.

넷째 줄부터 M개의 줄에는 홍준이가 명우에게 한 질문 S와 E가 한 줄에 하나씩 주어진다.

출력

총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다.

예제 입력과 출력

알고리즘 분류

다이나믹 프로그래밍 

정답

import sys
input = lambda : sys.stdin.readline().strip()

n=int(input())
a=list(map(int,input().split()))
m=int(input())
dp=[[0]*n for i in range(n)]

for i in range(n): # 길이가 1인 경우
    dp[i][i]=1

for i in range(n-1): # 길이가 2인 경우 
    if a[i] == a[i+1]:
        dp[i][i+1]=1

for i in range(1,n): # 길이가 3 이상인 경우
    for j in range(2,i+1):
        if a[i] == a[i-j] and dp[i-j+1][i-1] == 1:
            dp[i-j][i]=1
        
for i in range(m):
    s,e=map(int,input().split())
    print(dp[s-1][e-1])

백준 알고리즘 10942번 : https://www.acmicpc.net/problem/10942

문제

N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다.

각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 점프를 하는 두 경우만 존재한다.

가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 이동할 수 있는 경로의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 오른쪽 아래 칸에는 항상 0이 주어진다.

출력

가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 문제의 규칙에 맞게 갈 수 있는 경로의 개수를 출력한다. 경로의 개수는 263-1보다 작거나 같다.

예제 입력과 출력

알고리즘 분류

다이나믹 프로그래밍

힌트

정답

import sys
input = lambda : sys.stdin.readline().strip()

n=int(input())
a=[list(map(int,input().split())) for i in range(n)]

dp=[[0]*n for i in range(n)] # 방문 횟수 
dp[0][0]=1

for i in range(n):
    for j in range(n):
        if i == n-1 and j == n-1:
            break
        
        d=i+a[i][j] # 아래쪽
        r=j+a[i][j] # 오른쪽 
        
        if d < n: 
            dp[d][j] += dp[i][j]
        if r < n:
            dp[i][r] += dp[i][j]

print(dp[n-1][n-1])

dp[i][j]는 해당 위치를 방문할 수 있는 횟수입니다.

백준 알고리즘 1890번 : https://www.acmicpc.net/problem/1890