IT-garden

문제

두 전봇대 A와 B 사이에 하나 둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다.

예를 들어, <그림 1>과 같이 전깃줄이 연결되어 있는 경우 A의 1번 위치와 B의 8번 위치를 잇는 전깃줄, A의 3번 위치와 B의 9번 위치를 잇는 전깃줄, A의 4번 위치와 B의 1번 위치를 잇는 전깃줄을 없애면 남아있는 모든 전깃줄이 서로 교차하지 않게 된다.

전깃줄이 전봇대에 연결되는 위치는 전봇대 위에서부터 차례대로 번호가 매겨진다. 전깃줄의 개수와 전깃줄들이 두 전봇대에 연결되는 위치의 번호가 주어질 때, 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 위치의 번호가 차례로 주어진다. 위치의 번호는 500 이하의 자연수이고, 같은 위치에 두 개 이상의 전깃줄이 연결될 수 없다.

출력

첫째 줄에 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 출력한다.

예제 입력과 출력

알고리즘 분류

LIS

정답

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

n=int(input())
a=[]
dp=[1]*n

for i in range(n):
    a.append(list(map(int,input().split())))

a.sort(key = lambda x : x[0])

for i in range(n):
    for j in range(i):
        if a[i][1] > a[j][1]:
            dp[i]=max(dp[i],dp[j]+1)

print(n-max(dp))

a 전봇대 기준으로 정렬하고 b 전봇대에서 가장 긴 증가하는 부분수열을 구합니다.

a 전봇대를 정렬하면 a1, b1와 a2, b2라고 가정하면 a1 < a2이니까 b1 < b2일 경우에 두 선이 겹치지 않습니다.

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

문제

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

아래 그림은 원판이 5개인 경우의 예시이다.

입력

첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.

출력

첫째 줄에 옮긴 횟수 K를 출력한다.

두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.

예제 입력과 출력

알고리즘 분류

분할 정복

정답

def hanoi(n,frm,to,other):
    if n == 0: # 모두 옮긴 경우
        return

    # 가장 아래 원반을 제외한 원반들을 재귀적으로 목적지가 아닌 곳으로
    hanoi(n-1,frm,other,to) 
    print(frm,to) # 가장 아래 원반을 목적지로
    hanoi(n-1,other,to,frm) # 목적지가 아닌 곳으로 옮겼던 원반들을 재귀적으로 목적지로 

n=int(input())
print(2**n-1) # 최종 움직임 횟수
hanoi(n,1,3,2)

n : 원반 수
frm : 원반들이 위치한 곳 번호
to : 원반들을 옮길 목적지 번호
other : 나머지 한 곳(목적지가 아닌) 번호

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

isalpha()는 문자열이 모두 문자(영어 혹은 한글)이면 True를 반환하고 그렇지 않으면 False를 반환합니다.

a='abcd'
b='a1b1'
c='!@#$'
d='1234'
e='안녕'

# 출력>>True
print(a.isalpha())
# 출력>>False
print(b.isalpha())
# 출력>>False
print(c.isalpha())
# 출력>>False
print(d.isalpha())
# 출력>>True
print(e.isalpha())

a는 모두 문자(영어)로, e는 모두 문자(한글)로 구성되어 있어 True입니다.

b에는 숫자 1이 있어 False입니다.
c에는 특수문자가 있어 False입니다.
d에는 숫자 1234가 있어 False입니다.

isdigit()는 문자열이 모두 숫자인지 True를 반환하고 그렇지 않으면 False를 반환합니다.

a='abcd'
b='a1b1'
c='!@#$'
d='1234'
e='안녕'

# 출력>>False
print(a.isdigit())
# 출력>>False
print(b.isdigit())
# 출력>>False
print(c.isdigit())
# 출력>>True
print(d.isdigit())
# 출력>>False
print(e.isdigit())

d는 모두 숫자로 구성되어 있어 True입니다.
a는 문자(영어)가 있어 False입니다.
b에는 문자 a, b가 있어 False입니다.
c에는 특수문자가 있어 False입니다.
e에는 문자(한글)가 있어 False입니다.

isalnum()는 문자열이 영어, 한글 혹은 숫자이면 True를 반환하고 그렇지 않으면 False를 반환합니다.

a='abcd'
b='a1b1'
c='!@#$'
d='1234'
e='안녕'

# 출력>>True
print(a.isalnum())
# 출력>>True
print(b.isalnum())
# 출력>>False
print(c.isalnum())
# 출력>>True
print(d.isalnum())
# 출력>>True
print(e.isalnum())

a는 모두 문자(영어)로, b는 문자(영어)와 숫자로, d는 숫자로, e는 모두 문자(한글)로 구성되어 있어 True입니다.
c에는 특수문자가 있어 False입니다.

문제 설명

가로 길이가 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