IT-garden

문제

바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다.

암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다.

새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 C가지가 있다고 한다. 이 알파벳을 입수한 민식, 영식 형제는 조교들의 방에 침투하기 위해 암호를 추측해 보려고 한다. C개의 문자들이 모두 주어졌을 때, 가능성 있는 암호들을 모두 구하는 프로그램을 작성하시오.

입력

첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다.

출력

각 줄에 하나씩, 사전식으로 가능성 있는 암호를 모두 출력한다.

예제 입력과 출력

알고리즘 분류

백트래킹 

정답

from itertools import combinations

l,c=map(int,input().split())
a=sorted(input().split())
b=set('aeiou')

com=list(combinations(a,l))

for i in com:
    c=set(i)-b
    if 2 <= len(c) and l-len(c) >= 1:
        print(''.join(i))

알파벳이 중복되는 것은 없다는 것에 주의!
리스트 a에서 l개의 조합을 뽑습니다.
각 조합에서 모음의 수를 뺏을때 최소 2개의 자음이 남는지 확인하고
모음의 수가 1개 이상인지 확인하고 맞으면 출력합니다.

from itertools import combinations

l,c=map(int,input().split())
a=sorted(input().split())
com=list(combinations(a,l))

for i in com:
    num_v = 0
    num_c = 0
    for c in i:
        if c in "aeiou": #모음이 있는지 확인
            num_v +=1
        else:
            num_c +=1
    
    if num_v >=1 and num_c >=2:
        print(''.join(i))

set이 아닌 if문을 통해 모음이 있는지 확인할 수 있습니다.

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

문제 설명

프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.

또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.

먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.

제한조건

• 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다.
• 작업 진도는 100 미만의 자연수입니다.
• 작업 속도는 100 이하의 자연수입니다.
• 배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정합니다. 예를 들어 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 배포는 2일 뒤에 이루어집니다.

입출력 예

입출력 예 설명

첫 번째 기능은 93% 완료되어 있고 하루에 1%씩 작업이 가능하므로 7일간 작업 후 배포가 가능합니다.
두 번째 기능은 30%가 완료되어 있고 하루에 30%씩 작업이 가능하므로 3일간 작업 후 배포가 가능합니다. 하지만 이전 첫 번째 기능이 아직 완성된 상태가 아니기 때문에 첫 번째 기능이 배포되는 7일째 배포됩니다.
세 번째 기능은 55%가 완료되어 있고 하루에 5%씩 작업이 가능하므로 9일간 작업 후 배포가 가능합니다.

따라서 7일째에 2개의 기능, 9일째에 1개의 기능이 배포됩니다.

나의 풀이

def solution(progresses, speeds):
    c = 0
    answer = [0] * len(progresses)
    while True:
        c += 1
        for i in range(len(progresses)):
            if progresses[i] < 100:
                progresses[i] += speeds[i]
            if progresses[i] >= 100 and speeds[i] != 0:
                progresses[i] = 100
                speeds[i] = 0
                answer[i] = c
        if 0 not in answer:
            break
    
    k = answer[0]
    cou = 1
    r = []
    for i in range(1,len(answer)):
        if k >= answer[i]:
            cou += 1
        else:
            r.append(cou)
            cou = 1
            k = answer[i]
    r.append(cou) 
    return r

1. progresses에 각 작업의 개발 속도를 더해줍니다.
2. progresses의 요소가 완료되면 걸린 날을 리스트 answer에 넣습니다.
3. 1, 2과정을 모든 작업이 완료될때까지 합니다.
4. 한번에 몇 개의 기능이 배포되는지 확인해 리스트 r을 리턴합니다.

프로그래머스 '기능개발' : programmers.co.kr/learn/courses/30/lessons/42586

문제 설명

선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다.

예를 들어 선행 스킬 순서가 스파크 → 라이트닝 볼트 → 썬더일때, 썬더를 배우려면 먼저 라이트닝 볼트를 배워야 하고, 라이트닝 볼트를 배우려면 먼저 스파크를 배워야 합니다.

위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관없이 배울 수 있습니다. 따라서 스파크 → 힐링 → 라이트닝 볼트 → 썬더와 같은 스킬트리는 가능하지만, 썬더 → 스파크나 라이트닝 볼트 → 스파크 → 힐링 → 썬더와 같은 스킬트리는 불가능합니다.

선행 스킬 순서 skill과 유저들이 만든 스킬트리1를 담은 배열 skill_trees가 매개변수로 주어질 때, 가능한 스킬트리 개수를 return 하는 solution 함수를 작성해주세요.

제한조건

• 스킬은 알파벳 대문자로 표기하며, 모든 문자열은 알파벳 대문자로만 이루어져 있습니다.
• 스킬 순서와 스킬트리는 문자열로 표기합니다.
  • 예를 들어, C → B → D 라면 CBD로 표기합니다
• 선행 스킬 순서 skill의 길이는 1 이상 26 이하이며, 스킬은 중복해 주어지지 않습니다.
• skill_trees는 길이 1 이상 20 이하인 배열입니다.
• skill_trees의 원소는 스킬을 나타내는 문자열입니다.
  • skill_trees의 원소는 길이가 2 이상 26 이하인 문자열이며, 스킬이 중복해 주어지지 않습니다.

입출력 예

입출력 예 설명

• BACDE: B 스킬을 배우기 전에 C 스킬을 먼저 배워야 합니다. 불가능한 스킬트립니다.
• CBADF: 가능한 스킬트리입니다.
• AECB: 가능한 스킬트리입니다.
• BDA: B 스킬을 배우기 전에 C 스킬을 먼저 배워야 합니다. 불가능한 스킬트리입니다.

나의 풀이

def solution(skill, skill_trees):
    answer = 0
    skill=list(skill)

    for i in skill_trees:
        a = [-1] * len(skill)
        tree=list(i)
        
        for j, v in enumerate(skill):
            if v in tree:
                a[j]=tree.index(v)

        if sum(a) == (-1)*len(a): # 아무것도 속하지 않는 경우
            answer += 1
            continue    
        if a[0] == -1:
            continue
                            
        while True:
            if a[-1] == -1:
                a.pop()
            else:
                break
            
        b=sorted(a)
        a=list(filter((-1).__ne__ ,a))
        if a == b:
            answer += 1
        
    return answer

1. 스킬을 리스트로 만들고 스킬트리의 값들을 하나씩 리스트로 만듭니다.

2. 스킬에 있는 값이 스킬트리에 있는지 확인하고 있다면 스킬트리에서의 위치를 리스트 a에 넣습니다.

3. 스킬트리에 스킬의 값이 하나도 없다면 스킬트리가 가능한 경우이기 때문에 가능한 스킬트리의 개수 answer를 1 올려줍니다.

4. 스킬트리에 첫번째 스킬이 있어야 스킬트리가 될 가능성이 있기 때문에 첫번째 스킬트리가 있는지 확인합니다.

5. 리스트 a의 마지막 요소가 -1이면 -1을 전부 지워줍니다. 해당 위치의 스킬이 없는것으로 생각합니다.

6. 그 후 정렬한 리스트와 리스트 a에서 -1을 제거한 것을 비교합니다. (-1을 제거한 이유는 중간에 -1이 있다면 해당 스킬을 배우지 않은 것으로 간주하기 때문입니다.)

7. 두 리스트가 같으면 스킬트리의 개수 answer에 1 올려줍니다.

8. 위의 과정들을 반복한 뒤 answer를 리턴합니다.

다른 사람의 풀이

def solution(skill, skill_trees):
    answer = 0

    for skills in skill_trees:
        skill_list = list(skill)

        for s in skills:
            if s in skill:
                if s != skill_list.pop(0):
                    break
        else:
            answer += 1

    return answer

프로그래머스 '스킬트리' : programmers.co.kr/learn/courses/30/lessons/49993

문제

준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다.

준규는 현재 (1, 1)에 있고, (N, M)으로 이동하려고 한다. 준규가 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있고, 각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두 가져갈 수 있다. 또, 미로 밖으로 나갈 수는 없다.

준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수의 최댓값을 구하시오.

입력

첫째 줄에 미로의 크기 N, M이 주어진다. (1 ≤ N, M ≤ 1,000)

둘째 줄부터 N개 줄에는 총 M개의 숫자가 주어지며, r번째 줄의 c번째 수는 (r, c)에 놓여져 있는 사탕의 개수이다. 사탕의 개수는 0보다 크거나 같고, 100보다 작거나 같다.

출력

첫째 줄에 준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수를 출력한다.

예제 입력과 출력

알고리즘 분류

다이나믹 프로그래밍

정답

n,m=map(int,input().split())

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

ch[0][0] = a[0][0]

for i in range(1,m):
    ch[0][i] = a[0][i] + ch[0][i-1]

for i in range(1,n):
    ch[i][0] = a[i][0] + ch[i-1][0]

for i in range(1,n):
    for j in range(1,m):
        ch[i][j] = max(ch[i-1][j-1], ch[i-1][j], ch[i][j-1] ) + a[i][j]

print(ch[n-1][m-1])

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

문제

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

예제 입력과 출력

알고리즘 분류

다이나믹 프로그래밍 

정답

import sys

n=int(input())
m=[0]*(n+1)

def _11727(n):
    if n == 1:
        return 1
    if n == 2:
        return 3
    if m[n] != 0:
        return m[n]  
     
    m[n] = (_11727(n-1) + 2 * _11727(n-2) ) % 10007
    return m[n]

sys.setrecursionlimit(10000)
print(_11727(n))

sys.setrecursionlimit(10000)
sys 모듈을 이용해 재귀 한도를 10000까지 바꿔줍니다.
파이썬에서는 재귀호출을 무한이 아닌 1000번으로 제한중입니다.

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

문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. n은 90보다 작거나 같은 자연수이다.

출력

첫째 줄에 n번째 피보나치 수를 출력한다.

예제 입력과 출력

정답

n=int(input())

dp=[0] * (n+1)
dp[1] = 1

for i in range(2, n+1):
    dp[i] = dp[i-1] + dp[i-2]

print(dp[n])

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