# 2439 
N = int(input())
for i in range(N):
  print(('*'*(i+1)).rjust(N))

출력할 때 오른쪽 정렬은 .rjust(출력자리수) 왼쪽 정렬은 .ljust(출력자리수)

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())

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

2022.01.07

백준 2667 단지 번호 붙이기

#2667 단지번호붙이기
from collections import deque

N = int(input())
arr = [list(map(int,input())) for i in range(N)]
visited = [[False]*N for i in range(N)]  # 한 번 들른 곳은 방문처리

dx = [-1, 0, 0, 1]    # 상하좌우의 좌표를 이용하기 위해서
dy = [0, 1, -1, 0]

R = []  # 단지 내 아파트 숫자를 저장하려는 리스트

def BFS(x,y):
    queue = deque()
    queue.append((x,y)) # (x,y)로 append하면 pop할 때 두 x,y를 한 번에 꺼낼 수 있다
    num = 0             # 단지 내 아파트 숫자 세기
    if arr[x][y] == 1 and visited[x][y] == False:
        num += 1
        visited[x][y] = True
        
    while queue:
        v,b = queue.popleft()
        
        for i in range(4):
            nx = v + dx[i]
            ny = b + dy[i]
            if 0<=nx<N and 0<=ny<N:
                if arr[nx][ny] == 1 and visited[nx][ny] == False:
                    queue.append((nx,ny))
                    visited[nx][ny] = True
                    num += 1
    return R.append(num)

for i in range(N):
    for j in range(N):  # 반복문 두개 돌려서 좌표 (0,0) 부터 (N-1,N-1)까지 확인
        if arr[i][j] == 1 and visited[i][j] == False:
            BFS(i,j)
            
print(len(R))
for i in sorted(R):
    print(i)

deque에 좌표(x,y)를 append 해서 한 번에 꺼내는 것을 몰랐다면 더욱 지저분한 코드가 되었을 것 같다.

return을 해주는 위치랑 nx,ny 범위 지정을 잘못했는데 못 찾아서 한참을 헤맸다.

DFS로 풀 때와 다른점은 좌표의 범위 제한을 while구문 안에 넣은 것과 visited를 사용한 점이다.

숙달되려면 멀었다. 더 많은 관련 문제를 풀어봐야지

2022.01.06

백준 2606 바이러스

## 2606
from collections import deque

N = int(input())
C = int(input())
arr = [[] for i in range(N+1)]        # N+1 해준 이유는 숫자 인덱싱을 맞추려고

for i in range(C):
    a, b = map(int,input().split())
    arr[a].append(b)
    arr[b].append(a)

visited = []        # 방문한 컴퓨터 번호
def BFS(x):
    queue = deque([x])
    visited.append(x)
    
    while queue:
        v = queue.popleft()
        for i in arr[v]:
            if i not in visited:
                queue.append(i)
                visited.append(i)
                
BFS(1)
print(len(visited) -1) # 1번 컴퓨터는 제외

queue는 while 문이 핵심 같다.popleft를 통해서 나온 수를 인덱스로 사용해서 큐에 다시 삽입하고

다시 반복을 통해서 queue를 공백으로 만드는 것이 재귀를 이용하는 DFS와의 차이처럼 느껴진다.

2022.01.04

백준 1012 유기농 배추

# 1012
import sys
sys.setrecursionlimit(10**6)


def DFS(x,y):
    if 0 > x or x >= N or 0 > y or y >= M:           
        return False
    
    if arr[x][y] == 1:         
        arr[x][y] = 0                                  
        DFS(x-1,y)
        DFS(x,y+1)
        DFS(x+1,y)
        DFS(x,y-1)
        return True


T = int(input())    #테스트 케이스
    
for i in range(T):
    M, N, K = map(int, input().split())
    
    arr = [[0]*M for i in range(N)]  # 배추밭의 2차원 배열
    R = 0                            # 배추흰벌레 마리 수
       
    for j in range(K):
        a, b = map(int, input().split())
        arr[b][a] = 1

    for ii in range(N):
        for jj in range(M):
            if DFS(ii,jj) == 1: # 배추밭의 좌표(0,0)부터 끝까지 확인
                R += 1
    print(R)

편법?

import sys
sys.setrecursionlimit(10**6)

서버의 재귀 깊이를 늘려주는 함수를 사용해서 간신히 풀었다.

아무래도 DFS 함수의 재귀로 불러오는 게 너무 많아서 그런 듯하다.

재귀를 줄이고 반복문을 늘리는 함수를 짜 봐야겠다.

#2667 

N = int(input())
P = [list(map(int,input())) for i in range(N)]

def DFS(x,y):
    global R
    if 0 > x or x >= N or 0 > y or y >= N:
        return False
    
    if P[x][y] == 1:
        R += 1
        P[x][y] = 0
        DFS(x-1,y)
        DFS(x,y+1)
        DFS(x+1,y)
        DFS(x,y-1)
        return True
    return False           # 지워도 됨
        

arr = []                   # 단지 내 아파트 숫자를 저장
R = 0                      # 단지 내 아파트 숫자
for i in range(N):
    for j in range(N):
        if DFS(i,j) == 1:
            arr.append(R)
            R = 0
print(len(arr))
for i in sorted(arr):
    print(i)

2021.12.29

백준 2606 바이러스

#2606

F = int(input())
C = int(input())
W = [[] for i in range(F+1)]

for i in range(C):
    a,b = map(int, input().split())
    W[a].append(b)
    W[b].append(a)

arr = []
def DFS(x):
    arr.append(x)
    for i in W[x]:
        if i not in arr:
            DFS(i)
DFS(1)    
print(len(arr)-1)            # 1을 제외 갯수를 세어야 하기 때문     

DFS 함수를 정의하는데 조금 문제가 있었다.

처음에는 return을 사용해서 재귀적으로 만들려고 했는데

오류가 뜨거나 값이 제대로 안 나오거나 그랬는데

return 할 값이 없어서 그런 듯하다.

2021.12.17

백준 2798 블랙잭

#2798 블랙잭 /브루트포스 알고리즘

N,M = map(int, input().split())        # 카드의 개수, 목표값
arr = list(map(int, input().split()))  # 카드에 쓰여진 수
P = []                                 # 카드 3장의 합의 모든 경우의 수


for i in range(N):
    for j in range(i+1,N):
        for ii in range(j+1,N):
            S = arr[ii]+arr[i]+arr[j]
            P.append(S)
R = M                       # M - i의 최솟값을 저장하기 위한 변수            
Q = 0                       # R의 최솟값을 가지는 Q
for i in P:
    if M - i < R and M - i >= 0:
        R = M - i
        Q = i

print(Q)

모든 경우의 수를 구하는 문제라고 한다.

목푯값인 M과 카드 3장의 합인 P의 요소 중에 그 차이가 가장 작은 게 답이라는 아이디어로 풀었다.

#2798 블랙잭 /브루트포스 알고리즘

N,M = map(int, input().split())        # 카드의 개수, 목표값
arr = list(map(int, input().split()))  # 카드에 쓰여진 수
P = []                                 # 카드 3장의 합의 모든 경우의 수


for i in range(N):
    for j in range(i+1,N):
        for ii in range(j+1,N):
            S = arr[ii]+arr[i]+arr[j]
            if S <= M:
                P.append(S)

print(max(P))

풀고 나서 더 깔끔하게 만들어봤다. 메모리랑 시간도 미세하지만 아래 코드가 더 낫다.

combinations을 import해서 푸는 방법도 있는데 그건 나중에 알았으니 이제라도 잘 기억해야지

from itertools import combinations

2021.12.16

CodeUp 3120 리모컨

# CodeUp 3120 리모컨
a,b = map(int, input().split())
B = abs(a-b)                      # 두 온도차의 절대값
R = 0                             # 반복 횟수

while B != 0:
    if B >= 10:
        B = B - 10
        R += 1
    else:
        if B > 7:
            B += 1
            R += 1
        elif B > 4:
            B = B - 5
            R += 1
        elif B > 2:
            B += 1
            R += 1
        else:
            B = B -1
            R += 1
            
print(R)

처음에 짠 코드로 a-b의 절댓값을 0으로 만들어주면 된다는 아이디어로 짰다.

근데 8,9일 때는 10을 빼주고 +1 하는 게 더 최솟값이고 5,6,7일 때는 -5를 빼주는 게 최솟값이라 

세세히 조건을 줬다.

# CodeUp 3120 리모컨
a,b = map(int, input().split())
B = abs(a-b)                      # 두 온도차의 절대값
R = B//10                         # 반복 횟수


if B%10 in [1,5]:
    R += 1
elif B%10 in [2,4,6,9]:
    R += 2
elif B%10 in [3,7,8]:
    R += 3
            
print(R)

10 미만일 때 각각 0이되는 최솟값을 구하니 1,5는 1; 2,4,6,9는 2; 3,7,8은 3이 나오길래 간단히 짜 봤다. 

근데 시간은 첫 번째 코드가 조금 더 빠르다.

2021.12.13

백준 13305 주유소

# 13305 주유소
N = int(input())
R = list(map(int, input().split())) # 각 도시 간 거리
P = list(map(int, input().split())) # 각 도시의 기름값
del P[N-1]                          # 의미없는 마지막 값 삭제
Q = 0                               # 총 비용

while P != []:  
    sm = P.index(min(P))        # 가장 저렴한 기름값의 인덱스 
    Q = Q + P[sm]*sum(R[sm:])   # 가장 저렴한 기름값 * 이후 거리
    del P[sm:]
    del R[sm:]

print(Q)

처음 짰던 코드

반복문이 돌아가면서 리스트를 계속 확인해서 그런지 시간 초과가 떴다.

아이디어는 가장 작은 기름값이 있으면 그 뒤에 거리는 가장 작은 기름값과 거리를 곱한 

값을 할당하면 된다고 생각했다.

# 13305 주유소
N = int(input())
R = list(map(int, input().split())) # 각 도시 간 거리
P = list(map(int, input().split())) # 각 도시의 기름값
del P[N-1]                          # 의미없는 마지막 값 삭제
Q = 0                               # 총 비용
S = 1000000000                      # 기름의 초기값

for i in range(N-1):
    if S < P[i]:         # 작은 기름값이 나오면 그 기름값으로 교환
        Q = Q + S*R[i]
    else:
        S = P[i]
        Q = Q + S*R[i]
        
print(Q)

S에 10억을 할당한 이유는 기름값으로 주어질 수 있는 max값이 10억이길래 초기값으로 할당했다.

그 값을 도시의 기름값고 비교해서 S가 작으면 S와 거리를 곱해주고

S가 크면 S의 값을 P[i]값으로 바꿔준 다음 S와 거리를 곱해준다. 

반복문이지만 리스트를 한 번만 확인하면 풀린다.