2022.02.01

백준 11650 좌표 정렬

#11650 좌표 정렬
import sys
N = int(sys.stdin.readline())
arr = []
for i in range(N):
    arr.append( list(map(int, sys.stdin.readline().split())))
    
arr.sort()
for i in range(N):
    print(*arr[i])

아무래도 주어지는 숫자가 크다 보니 sys를 사용하는 게 시간적 측면에서 유리하다.

2차원 평면에 주어진 좌표를 정렬하는 문제이므로 

2차원 배열을 준비해주고 주어진 N만큼 리스트에 입력받는다.

그리고 sorted를 사용하지않고 sort를 사용해 정렬해 프린트해준다.

#11650 좌표 정렬
import sys
N = int(sys.stdin.readline())
arr = []
for i in range(N):
    arr.append( list(map(int, sys.stdin.readline().split())))
    
for i in sorted(arr):
    print(*i)

글을 작성 중에 sorted가 더 빠를 거 같아서 살짝 고쳐봤더니 

미세하게 더 빠르긴 했다.

이항 계수

# 11050 이항 계수
N, K = map(int, input().split())
n = 1
k = 1
z = N-K

for i in range(1,N+1):
    n = n*i
for i in range(1,K+1):
    k = k*i
for i in range(1,z):
    z = z*i

if K == 0 or N == K:
    print(1)
else:
    print(n//(k*z))

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로 해결했다.

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를 사용하면 중복을 제외하고 가능한 순열조합을 모두 만들어준다.

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

백준 7569 토마토

from collections import deque

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

graph = []

for _ in range(h):
    graph.append([ list(map(int,input().split())) for _ in range(n) ])

dx = [-1,1,0,0,0,0]
dy = [0,0,-1,1,0,0]
dz = [0,0,0,0,-1,1]

queue = deque()

def bfs():
    for i in range(h):
        for j in range(n):
            for k in range(m):
                if graph[i][j][k] == 1:
                    queue.append((i,j,k))
    
    while queue:
        x,y,z = queue.popleft()
        for i in range(6):
            nx = x + dx[i]
            ny = y + dy[i]
            nz = z + dz[i]

            if 0 <= nx < h and 0 <= ny < n and 0 <= nz < m :
                if graph[nx][ny][nz] == 0 :
                    queue.append((nx,ny,nz))
                    graph[nx][ny][nz] = graph[x][y][z] + 1

bfs()
R = []
for i in range(h):
    for j in range(n):
        if 0 in graph[i][j]:
            R.append(0)
        else:
            R.append(max(graph[i][j]))
if 0 in R:
    print(-1)
else:
    print(max(R)-1)

처음에 2차원 배열로 풀려다가 상자 층이 넘어가는 것을

인접면으로 탐색하는 걸 해결 못해서 포기했다.

결국 3차원으로 풀었는데 어제 풀었던 7576번 문제와 똑같고

차원이 하나 추가돼서 좌표설정만 헷갈리지 않으면 됐다.

2022.01.10

백준 2178 미로 탐색

# 2178
from collections import deque

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

def BFS(x,y):
    dx = [0,-1, 1, 0]
    dy = [1, 0, 0, -1]
    queue = deque()
    queue.append((x,y))
    
    while queue:   
        a, b = queue.popleft()
        for i in range(4):
            nx = a + dx[i]
            ny = b + dy[i]
            
            if 0<=nx<N and 0<=ny<M:
                if arr[nx][ny] == 1:
                    queue.append((nx,ny))
                    arr[nx][ny] = arr[a][b] + 1

BFS(0,0)
print(arr[N-1][M-1])

칸을 지나면 그다음 칸을 +1 해주는 아이디어로 풀었다.

방문처리를 안해서 중복 방문하기 때문에 다른 좌표들은 문제가 있지만

끝 좌표는 더이상 진행할 곳이 없어서 문제없다.

# 2178 방문처리 한 코드
from collections import deque

N, M = map(int, input().split())
arr = [list(map(int, input())) for i in range(N)]
visited = [[False]*M for i in range(N)]

def BFS(x,y):
    dx = [0,-1, 1, 0]
    dy = [1, 0, 0, -1]
    queue = deque()
    queue.append((x,y))
    
    while queue:   
        a, b = queue.popleft()
        for i in range(4):
            nx = a + dx[i]
            ny = b + dy[i]
            
            if 0<=nx<N and 0<=ny<M:
                if arr[nx][ny] == 1 and visited[nx][ny] == False:
                    queue.append((nx,ny))
                    visited[nx][ny] = True
                    arr[nx][ny] = arr[a][b] + 1

BFS(0,0)
print(arr[N-1][M-1])

방문처리 코드를 넣어도 시간이나 메모리에서 그다지 차이는 보이지 않았다.

F = list(input().lower()) # 문자를 소문자열로 받아옴
Q = list(set(F))          # 문자 갯수를 세기 위해서 중복 제거
cnt = 0                   # 가장 많은 문자 갯수 저장
R = []                    # 문자 갯수가 같은 문자 저장

# 가장 많은 문자의 갯수를 구하기 위한 반복문
for i in Q:               
  if F.count(i) > cnt:
    cnt = F.count(i)

# cnt와 중복값을 가진 문자를 R에 저장
for i in Q:
  if F.count(i) == cnt:
    R.append(i)
    
if len(list(set(R))) > 1:
  print('?')
else:
  print(R[0].upper())

맞추긴 했는데 메모리와 시간을 엄청 먹는다. 좀더 빠르게 푸는 방법은 없을까?