2022.01.27

백준 10845 큐

# 10845 큐
import collections 
import sys

N = int(sys.stdin.readline())
queue = collections.deque()

for i in range(N):
    q = sys.stdin.readline().split()
    if q[0] == 'push':
        queue.append(int(q[1]))
    elif q[0] == 'pop':
        try:
            print(queue.popleft())
        except:
            print(-1)
    elif q[0] == 'size':
        print(len(queue))
    elif q[0] == 'empty':
        if queue:
            print(0)
        else:
            print(1)
    elif q[0] == 'front':
        if not queue:
            print(-1)
        else:
            print(queue[0])
    elif q[0] == 'back':
        if not queue:
            print(-1)
        else:
            print(queue[-1])

조건문만 잘 만들어내면 되는 문제라 그리 어렵지는 않았는데

시간 초과가 뜨길래 sys를 사용했다.

백준 4153 직각삼각형

# 4153 직각삼각형
while True:
    d = list(map(int, input().split()))
    if 0 in d:
        break
    a = max(d)
    d.remove(a)

    if d[0]**2 + d[1]**2 == a**2:
        print('right')
    else:
        print('wrong')

세 변 중 하나라도 0이 있으면 무한루프를 빠져나오게 만들고

직각삼각형 세 변의 공식에 따라 가장 큰 값만 구할 수 있으면 됐다.

백준 2775 부녀회장이 될 테야

#2775 부녀회장이 될테야

T = int(input())

for i in range(T):
    k = int(input()) # 층 수
    n = int(input()) # 호
    B = [[i for i in range(15)]]
    
    for j in range(1,k+1):
        B.append([])
        for _ in range(n+1):
            B[j].append(sum(B[j-1][:_+1]))
            
    print(B[k][n])

B[0]은 0층을 미리 넣어둔 것이고, 전체 리스트인 B는 반복문 안에 넣어줘

리스트를 반복할 때마다 초기화시켜주는 게 필요했다.

그다음으로는 층의 호수에 맞는 값을 하나하나 인덱싱에 맞춰 추가해주려고 했는데

그건 해결 못하고 append로 해결했다.

백준 2292 벌집

# 2292 벌집

N = int(input())
r = 1
q = 1
while True:
    if r == N:
        break
        
    for i in range(q*6):
        if r == N:
            break
        else:
            r += 1
    q += 1

print(q)

식을 만들어서 풀면 더 쉬울텐데 못해서 이차원배열 각 리스트에 요소를 채워 넣듯이

반복문을 만들어봤다.

벌집이 넓어질 수 록 층을 넘어간다고 생각하여 리스트를 만들면

1층 = [1]

2층 = [2, 3, 4, 5, 6, 7]

3층 = [8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]

4층 = [20 ~ 37]

이런 식으로 6개씩 요소가 증가하는 리스트가 만들어진다.

이 규칙을 이용해 N이 주어졌을 때 그 N이 들어있는 리스트의 층을 출력하면 된다.

백준 2231 분해합

#2231 분해합
N = int(input())
result = []
for i in range(1,N):
    s = str(i)
    r = list(s)
    z = i
    for j in range(len(r)):
        z = z + int(r[j])
    if z == N:
        result.append(i)

if result == []:
    print(0)
else:
    print(min(result))

N이 주어지면 1부터 N-1까지 전부 분해합을 계산해서

N과 같은 숫자의 i가 있으면 리스트에 담아준다.

그리고 최솟값을 출력하면 된다.

2022.01.2

백준 14889 스타트와 링크

# 14889 스타트와 링크

# dfs = 가능한 팀의 경우의 수를 모두 추출한다. 
def dfs():
    if len(R) == (N//2):
        start.append(R[:])
        link.append(list(set(num) - set(R[:])))
    for i in range(1,N+1):
        if i > R[-1]:
            R.append(i)
            dfs()
            R.pop()

M = []
N = int(input())
for i in range(N):
    M.append(list(map(int, input().split())))
num = [i for i in range(1,N+1)]

# 모든 경우에 팀 안에 1번이 들어있으므로 1번이 들어간 모든 경우의 수를 출력하면 된다.
R = [1]
start = []
link = []
dfs()

# result = 스타트팀과 링크팀 점수차를 저장하는 리스트
result = []

for i in range(len(start)):
    start_sum = 0
    link_sum = 0
    for j in range(N//2):
        for _ in range(N//2):
            start_sum += M[start[i][j]-1][start[i][_]-1] 
            link_sum += M[link[i][j]-1][link[i][_]-1]
    result.append(abs(start_sum -link_sum)) 
print(min(result))

처음에 함수 dfs()에서 R을 저장하려고 할 때, 저장해서 출력하면 빈 리스트만 나와서 당황했었다.

그 이유는 R의 요소를 저장한게 아니라 R 자체를 저장한 것이라 pop()이 되어서 그렇다는데 정확하게 이해하지 못했다.

아무튼 그걸 해결하기 위해서 R[:]을 취해서 요소를 저장해줬더니 문제를 해결할 수 있었다.

문제풀이의 아이디어는 일단 팀으로 만들 수 있는 모든 경우의 수를 찾아내고

또 그팀 안에서 점수를 낼 수 있는 모든 조합을 계산한 다음, 두 팀 간 점수 차의 절댓값을 구하면 된다고 생각했다.

dfs() 함수를 통해서 가능한 start와 link 팀의 경우의 수를 구했고 각 인덱스는 서로 대비된다.

start팀에 start[1]의 요소가 배정되면 link팀에는 전체 팀원에서 start[1]을 뺀 link[1]이 배정된다.

그리고 경우의 수를 구할 때 R이라는 임의의 리스트에 1을 넣어둔 이유는 어떤 경우라도 1번은 둘 중 한 팀에

무조건 들어가 있어야 하기 때문에 그냥 1번이 들어갈 수 있는 모든 팀의 경우의 수를 뽑아내면 된다고 생각했다.

# 1978 소수 찾기

N = int(input())
arr = list(map(int, input().split()))
prime = [i for i in range(2,1001)]

for i in range(2,round(1000**(1/2))):
  for j in range(2,1000//i+1):
    if i*j in prime:
      prime.remove(i*j)
R = 0
for i in arr:
  if i in prime:
    R += 1

print(R)

문제의 범위가 1000까지라 for문을 통해 1000까지의 소수 리스트를 만들고

입력받은 값이 소수 리스트에 있으면 값을 세어 출력하게 코드를 짰다.

2022.01.21

백준 15652 N과 M (4)

# 15652 N과 M (4)

N, M = map(int, input().split())
R = []

def dfs():
    if len(R) == M:
        print(*R)
        return
    
    for i in range(1,N+1):
        try:
            if i >= R[-1]:
                R.append(i)
                dfs()
                R.pop()
        except:
            R.append(i)
            dfs()
            R.pop()

dfs()

예시 출력을 보면 뒤의 숫자가 항상 바로 앞 숫자보다 크거나 같은 것을 알 수 있다.

때문에 R[-1] 보다 크거나 같으면 되는데 그냥 하나만 넣어주면 R = [] 으로 요소가 없어서 range오류가 나온다.

이걸 try; except구문으로 해결해줬다.

2022.01.20

백준 15651N과 M (3)

#15651 N과 M (3)

N, M = map(int, input().split())
R = []

def dfs():
    if len(R) == M:
        print(*R)
        return
        
    for i in range(1,N+1):
        R.append(i)
        dfs()
        R.pop()

dfs()

처음에 return을 넣어주지 않았더니 무한 재귀가 되어버려서 depth오류가 나왔다.

재귀적 방법을 사용할 때는 return으로 어디서 빠져나올지 잘 생각해야겠다.

백트래킹 문제.. 그런데 백트래킹이 뭔지 잘 모르겠다.

dfs와 같이 재귀적으로 진행하고, 사이에 조건을 추가해서 아닌 가지를 잘라내는 것?

또 여러 문제를 풀어봐야지

#15649
import itertools

N, M = map(int, input().split())
arr = [ i for i in range(1,N+1)]

R = list(itertools.permutations(arr,M))

for i in R:
    print(' '.join(map(str,i)))

itertools의 permutations를 사용하면 중복을 제외하고 가능한 순열조합을 모두 만들어준다.

백트래킹으로 풀어보려고 했는데 재귀 조건을 어떻게 주어야 할지 떠오르지 않아서 다르게 풀어봤다.