코딩묻은 디자이너

https://www.acmicpc.net/problem/4673

문제

셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다.

양의 정수 n이 주어졌을 때, 이 수를 시작해서 n, d(n), d(d(n)), d(d(d(n))), ...과 같은 무한 수열을 만들 수 있다. 

예를 들어, 33으로 시작한다면 다음 수는 33 + 3 + 3 = 39이고, 그 다음 수는 39 + 3 + 9 = 51, 다음 수는 51 + 5 + 1 = 57이다. 이런식으로 다음과 같은 수열을 만들 수 있다.

33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, 141, ...

n을 d(n)의 생성자라고 한다. 위의 수열에서 33은 39의 생성자이고, 39는 51의 생성자, 51은 57의 생성자이다. 생성자가 한 개보다 많은 경우도 있다. 예를 들어, 101은 생성자가 2개(91과 100) 있다. 

생성자가 없는 숫자를 셀프 넘버라고 한다. 100보다 작은 셀프 넘버는 총 13개가 있다. 1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86, 97

10000보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 출력하는 프로그램을 작성하시오.

입력

입력은 없다.

출력

10,000보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 증가하는 순서로 출력한다.

풀이

드디어 푼 셀프 넘버 문제

처음에는 문제 자체를 이해 못했는데 알고보니 어렵지 않은 문제다

지금 현재수 + 수를 쪼갠 수가 list 안에 속하면 지워준다. 그리고 남아있는 list를 출력해준다.

효율적이라고는 할 수 없지만 모든 수를 탐색하는 방법으로 풀었다.

python코드

# 4673 셀프 넘버

arr = []
for i in range(1,10001):
    arr.append(i)

for i in range(1, 10001):
    nums=list(str(i))
    num = i
    for j in range(len(nums)):
        num += int(nums[j])
    if num in arr:
        arr.remove(num)

for i in arr:
    print(i)

https://www.acmicpc.net/problem/3003

문제

동혁이는 오래된 창고를 뒤지다가 낡은 체스판과 피스를 발견했다.

체스판의 먼지를 털어내고 걸레로 닦으니 그럭저럭 쓸만한 체스판이 되었다. 하지만, 검정색 피스는 모두 있었으나, 흰색 피스는 개수가 올바르지 않았다.

체스는 총 16개의 피스를 사용하며, 킹 1개, 퀸 1개, 룩 2개, 비숍 2개, 나이트 2개, 폰 8개로 구성되어 있다.

동혁이가 발견한 흰색 피스의 개수가 주어졌을 때, 몇 개를 더하거나 빼야 올바른 세트가 되는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 동혁이가 찾은 흰색 킹, 퀸, 룩, 비숍, 나이트, 폰의 개수가 주어진다. 이 값은 0보다 크거나 같고 10보다 작거나 같은 정수이다.

출력

첫째 줄에 입력에서 주어진 순서대로 몇 개의 피스를 더하거나 빼야 되는지를 출력한다. 만약 수가 양수라면 동혁이는 그 개수 만큼 피스를 더해야 하는 것이고, 음수라면 제거해야 하는 것이다.

풀이

자신감 키우는 날~!

list로 받아서 인덱스 순서대로 접근했다.

개수가 정해져 있기 때문에 그 갯수에서 인덱스에 해당하는 것을 뺐다!

python코드

#3003 킹, 퀸, 룩, 비숍, 나이트, 폰

chess = list(map(int,input().split()))

print(1-chess[0], 1-chess[1], 2-chess[2], 2-chess[3], 2-chess[4], 8-chess[5])

https://www.acmicpc.net/problem/11722

문제

수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10}  이고, 길이는 3이다.

입력

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

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 감소하는 부분 수열의 길이를 출력한다.

풀이

https://namu.wiki/w/%EC%B5%9C%EC%9E%A5%20%EC%A6%9D%EA%B0%80%20%EB%B6%80%EB%B6%84%20%EC%88%98%EC%97%B4

동적 계획법으로 풀어내는 문제

python 코드

#11722 가장 긴 감소하는 부분 수열

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

dp = [1] * N

for i in range(1,N):
    for j in range(0,i):
        if arr[i] < arr[j]:
            dp[i] = max(dp[i], dp[j]+1)
ans = max(dp)
print(ans)

https://www.acmicpc.net/problem/1991

문제

이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.

예를 들어 위와 같은 이진 트리가 입력되면,

• 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
• 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
• 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)

가 된다.

입력

첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파벳 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현한다.

출력

첫째 줄에 전위 순회, 둘째 줄에 중위 순회, 셋째 줄에 후위 순회한 결과를 출력한다. 각 줄에 N개의 알파벳을 공백 없이 출력하면 된다.

풀이

트리 문제를 풀 때 가장 고민이 저것을 어떻게 코드로 표현하느냐 인데

노드의 연결상태를 이런식으로 생각하니깐 쉬웠다!

형태는

[A,B,C]

[B,D,.]

.

.

.

이런 식으로 표현해서 0번 인덱스 1번 인덱스, 2번 인덱스로 접근했다

전위 순회 규칙을 찾아내면 중위와 후위는 비슷하게 풀이할 수 있다

python 코드

# 1991 트리 순회
def preorder(n):
    print(arr[n][0],end='')
    if arr[n][1] != '.':
        for i in range(len(arr)):
            if arr[i][0] == arr[n][1]:
                preorder(i)
    if arr[n][2] != '.':
        for i in range(len(arr)):
            if arr[i][0] == arr[n][2]:
                preorder(i)
def inorder(n):
    if arr[n][1] != '.':
        for i in range(len(arr)):
            if arr[i][0] == arr[n][1]:
                inorder(i)
    print(arr[n][0],end='')
    if arr[n][2] != '.':
        for i in range(len(arr)):
            if(arr[i][0]) == arr[n][2]:
                inorder(i)
def postorder(n):
    if arr[n][1] != '.':
        for i in range(len(arr)):
            if arr[i][0] == arr[n][1]:
                postorder(i)
    if arr[n][2] != '.':
        for i in range(len(arr)):
            if(arr[i][0]) == arr[n][2]:
                postorder(i)
    print(arr[n][0],end='')

N = int(input())
arr = []

for t in range(N):
    arr.append(list(map(str,input().split())))

preorder(0)
print()
inorder(0)
print()
postorder(0)

https://www.acmicpc.net/problem/11724

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.

풀이

연결요소를 구해야 하는 문제인데 처음에는 연결요소가 뭘 출력하라는건지 헷갈렸는데

뭉쳐진 덩어리의 갯수를 구하는 문제였다.

더이상 연결된 요소가 없을 때 까지 탐색해야 하므로 dfs 깊이 탐색을 사용했다.

연결관계를 나타낼 리스트 arr과 방문 여부를 체크할 visited 리스트를 만들었다

입력을 받을 때 방향이 없는 그래프라서

arr[u].append(v)
arr[v].append(u)

양방향으로 입력했다.

재귀를 돌면서 만약 방문 했을 경우 visited에 1을 입력하고, 방문하지 않은 경로만 이동한다

dfs를 완료한것은 더이상 탐색할 노드가 없다는 뜻이니 ans += 1을 했다

python코드

# 11724 연결 요소의 개수
import sys
sys.setrecursionlimit(10**6)

def dfs(n):
    for i in range(len(arr[n])):
        if visited[arr[n][i]] == 0:
            visited[arr[n][i]] = 1
            dfs(arr[n][i])

N, M = map(int,input().split())
arr = [[] * (N+1) for _ in range(N+1)]
visited = [0] * (N+1)
ans = 0
for m in range(M):
    u,v = map(int,sys.stdin.readline().rstrip().split())
    arr[u].append(v)
    arr[v].append(u)

for i in range(1, N+1):
    if visited[i] == 0:
        visited[i] = 1
        dfs(i)
        ans += 1
print(ans)

https://www.acmicpc.net/problem/11656

문제

접미사 배열은 문자열 S의 모든 접미사를 사전순으로 정렬해 놓은 배열이다.

baekjoon의 접미사는 baekjoon, aekjoon, ekjoon, kjoon, joon, oon, on, n 으로 총 8가지가 있고, 이를 사전순으로 정렬하면, aekjoon, baekjoon, ekjoon, joon, kjoon, n, on, oon이 된다.

문자열 S가 주어졌을 때, 모든 접미사를 사전순으로 정렬한 다음 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000보다 작거나 같다.

출력

첫째 줄부터 S의 접미사를 사전순으로 한 줄에 하나씩 출력한다.

풀이

처음에는 재귀를 통해 풀었는데 RecursionError가 나와서 그냥 단순 for문을 통해 풀이하도록 바꿨다

슬라이싱을 통해 문자열값의 범위를 지정해서 받아와 배열에 저장한 후 sort로 정렬하였다

python코드

# 11656 점미사 배열

text = input()
arr = []

for i in range(len(text)):
    arr.append(text[i:len(text)])

arr.sort()
for i in arr:
    print(i)

https://www.acmicpc.net/problem/16165

문제

정우는 소문난 걸그룹 덕후이다. 정우의 친구 준석이도 걸그룹을 좋아하지만 이름을 잘 외우지 못한다는 문제가 있었다. 정우는 친구를 위해 걸그룹 개인과 팀의 이름을 검색하여 외우게 하는 퀴즈 프로그램을 만들고자 한다.

입력

첫 번째 줄에는 총 입력 받을 걸그룹의 수 N(0 < N < 100)과 맞혀야 할 문제의 수 M(0 < M < 100)을 입력받는다.

두 번째 줄부터는 각 걸그룹마다 팀의 이름, 걸그룹의 인원 수, 멤버의 이름을 한 줄씩 차례대로 입력받는다. 팀과 멤버의 이름은 최대 100글자이며, 모든 글자는 알파벳 소문자이다. 하나의 걸그룹이나 서로 다른 두 걸그룹에 이름이 같은 두 멤버가 있는 경우는 없다.

그 다음 줄부터는 M개의 퀴즈를 입력받는다. 각각의 퀴즈는 두 줄로 이루어져 있으며, 팀의 이름이나 멤버의 이름이 첫 줄에 주어지고 퀴즈의 종류를 나타내는 0 또는 1이 두 번째 줄에 주어진다. 퀴즈의 종류가 0일 경우 팀의 이름이 주어지며, 1일 경우 멤버의 이름이 주어진다.

출력

첫 번째 줄부터 차례대로 퀴즈에 대한 답을 출력한다. 퀴즈의 종류가 0일 경우 해당 팀에 속한 멤버의 이름을 사전순으로 한 줄에 한 명씩 출력한다. 퀴즈의 종류가 1일 경우 해당 멤버가 속한 팀의 이름을 출력한다.

풀이

그룹명으로 멤버 '리스트'를 구하는 딕셔너리 하나, 멤버 이름으로 그룹명을 구하는 딕셔너리 하나 총 두개의 딕셔너리를 만들었다.

걸그룹명으로 멤버 리스트르 구하는 딕셔너리에서는 그룹명을 받은 후 멤버는 리스트로 받아왔다

python코드

# 16165 걸그룹 마스터 준석이
import sys

N, M = map(int,sys.stdin.readline().rstrip().split())
g_m={}
m_g={}
for n in range(N):
    group = input()
    num = int(input())
    g_m[group] = []
    for i in range(num):
        member = input()
        g_m[group].append(member)
        m_g[member] = group

for m in range(M):
    text = sys.stdin.readline().rstrip()
    game = int(sys.stdin.readline().rstrip())
    if game == 1:
        print(m_g[text])
    else:
        g_m[text].sort()
        for i in g_m[text]:
            print(i)

https://www.acmicpc.net/problem/2002

문제

대한민국을 비롯한 대부분의 나라에서는 터널 내에서의 차선 변경을 법률로 금하고 있다. 조금만 관찰력이 있는 학생이라면 터널 내부에서는 차선이 파선이 아닌 실선으로 되어 있다는 것을 알고 있을 것이다. 이는 차선을 변경할 수 없음을 말하는 것이고, 따라서 터널 내부에서의 추월은 불가능하다.

소문난 명콤비 경찰 대근이와 영식이가 추월하는 차량을 잡기 위해 한 터널에 투입되었다. 대근이는 터널의 입구에, 영식이는 터널의 출구에 각각 잠복하고, 대근이는 차가 터널에 들어가는 순서대로, 영식이는 차가 터널에서 나오는 순서대로 각각 차량 번호를 적어 두었다.

N개의 차량이 지나간 후, 대근이와 영식이는 자신들이 적어 둔 차량 번호의 목록을 보고, 터널 내부에서 반드시 추월을 했을 것으로 여겨지는 차들이 몇 대 있다는 것을 알게 되었다. 대근이와 영식이를 도와 이를 구하는 프로그램을 작성해 보자.

입력

입력은 총 2N+1개의 줄로 이루어져 있다. 첫 줄에는 차의 대수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 대근이가 적은 차량 번호 목록이 주어지고, N+2째 줄부터 N개의 줄에는 영식이가 적은 차량 번호 목록이 주어진다. 각 차량 번호는 6글자 이상 8글자 이하의 문자열로, 영어 대문자('A'-'Z')와 숫자('0'-'9')로만 이루어져 있다.

같은 차량 번호가 두 번 이상 주어지는 경우는 없다.

출력

첫째 줄에 터널 내부에서 반드시 추월을 했을 것으로 여겨지는 차가 몇 대인지 출력한다.

풀이

해시(딕셔너리)를 통해 풀었다

처음에는 하나하나 돌아가면서 현제 인덱스를 비교하고 만약 인덱스 값이 다르다면 인덱스에서 하나 뺀 값을 계산하여(?) 풀려고 하였으나 아예 근본부터 틀린 로직이라는걸 파악하고(여기까지 한시간)

그냥 간단하게 딕셔너리 가장 앞에 있는 값과 현재 값이 다르다면 추월한 차 이므로 ans에 1추가하는 간단한 방법을 사용했다.

딕셔너리의 가장 앞에 있는 값을 찾기 위해

next(iter(dict))를 사용하였다

python코드

# 2002 추월
import sys

n = int(sys.stdin.readline().rstrip())
ans = 0
arr = {}
for i in range(n):
    arr[sys.stdin.readline().rstrip()] = i
for i in range(n):
    car = input()
    if next(iter(arr)) != car:
        ans += 1
    arr.pop(car)
print(ans)

https://www.acmicpc.net/problem/4358

문제

생태학에서 나무의 분포도를 측정하는 것은 중요하다. 그러므로 당신은 미국 전역의 나무들이 주어졌을 때, 각 종이 전체에서 몇 %를 차지하는지 구하는 프로그램을 만들어야 한다.

입력

프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어진다.

출력

주어진 각 종의 이름을 사전순으로 출력하고, 그 종이 차지하는 비율을 백분율로 소수점 4째자리까지 반올림해 함께 출력한다.

풀이

입력 값의 범위가 정해져있지 않기 때문에 while문을 사용해서 계속해서 값을 받고 값이 없을 경우 while문에서 빠져나오도록 하였다.

각 종의 이름을 사전순으로 출력하기 위해 lambda식을 사용하여 정렬하였고,

소수점 4째 자리까지 반올림하기 위해서

print('{:.4f}'.format())형식을 사용했다

python코드

# 생태학
import sys

tree = ''
arr = {}
total = 0

while True:
    tree = sys.stdin.readline().rstrip()
    if not tree:
        break
    if tree in arr:
        arr[tree] += 1
    else:
        arr[tree] = 1
    total += 1
sorted_arr = sorted(arr.items(), key=lambda x:x[0])
for i in range(len(arr)):
    print('{} {:.4f}' .format(sorted_arr[i][0], (sorted_arr[i][1]/total)*100))

https://www.acmicpc.net/problem/14490

문제

대열이는 욱제의 친구다.

• “야 백대열을 약분하면 뭔지 알아?”
• “??”
• “십대일이야~ 하하!”

n:m이 주어진다. 욱제를 도와주자. (...)

입력

n과 m이 :을 사이에 두고 주어진다. (1 ≤ n, m ≤ 100,000,000)

출력

두 수를 최대한으로 약분하여 출력한다.

풀이

유클리드 호제법을 사용해서 풀이!

유클리드 호제법:

if a > b:
	while b > 0:
    	a, b = b, a % b

python코드

# 14490 백대열

n, m = map(int,input().split(':'))
a, b = n, m
if n > m:
    while m > 0:
        n, m = m, n % m
    print(a // n, end='')
    print(':', end='')
    print(b // n)
else:
    while n > 0:
        n, m = m % n, n
    print(a//m,end='')
    print(':',end='')
    print(b//m)

똑같은 코드를 두번 반복;;;