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 할 값이 없어서 그런 듯하다.

https://jealous-gasoline-34d.notion.site/73c3ee532c3f4f779f42b3503048c6e9

- 가계부 공유용 노션 링크

 가계부를 몇 년 전부터 쓰고 있는데 핸드폰을 바꾸게 되면 초기화가 되기도 하고

바꿀 때마다 데이터를 옮기는 게 귀찮아서 노션에다가 간단히 만들어두고

필요한 기능이 있을 때마다 고쳐가며 써보려고 합니다.

 지금 만들어둔 가계부는 정말 간단한 기능들로만 채워뒀고

매달 페이지만 복사해서 제목만 바꿔서 사용해주시면 됩니다.

사용처

 - 사용한 걸 적어주시면 됩니다.

 저는 점심, 저녁 등을 나눠서 작성하는데 이 또한 새로운 열을 만들어 태그를 추가해도 됩니다.

태그

 - 큰 태그로 나눠서 나중에 분류해서 보려고 합니다. 

식비, 미용, 옷, 전자기기, 경조사 등 큰 분류를 만들 예정이고

만들고 싶은 태그가 있으면 태그를 누르고 옵션에서 직접 쓴 다음

왼쪽 옆에 생성 버튼을 누르기만 하면 됩니다.

금액

 - 금액은 마지막 행에 다 더해진 값이 오도록 해뒀습니다.

수단

 - 결제를 무엇으로 했는지 고르면 됩니다.

현재는 네이버페이, 카카오페이, 현금, 체크카드, 신용카드만 추가해뒀는데

카드사별로 추가로 생성해서 사용하면 됩니다.

링크에 들어가 보시면 하위 페이지를 월별로 해두었기 때문에

새로운 월 가계부가 필요하면 페이지를 그대로 복사해서 사용하면 됩니다.

미리 1월처럼 서식만 있는 페이지를 복사해두세요 나중에 복사하면 내용 지우느라 귀찮잖아요

사용할 때에는 제목만 바꿔주세요. 

브루트포스 알고리즘이란?

 완전 탐색법이라고도 불리는 브루트포스 알고리즘은 무차별 대입법이라고도 하며,

어떤 문제에 관해서 가능한 모든 경우의 수를 구하고 답을 찾아내는 것을 말한다.

그렇기 때문에 답이 틀릴 수는 없지만 시간 효율성 측면에서 좋지 않다.

2021.12.17 - [Algorithm] - 백준 2798 파이썬

전에 올린 백준 문제 2798_블랙잭도 브루트포스 알고리즘으로 푸는 문제이다.

문제를 풀기위해서는 나올 수 있는 세 카드 합의 경우의 수를 모두 찾고

그중에서 M보다 작으면서 가장 큰 값을 찾아내면 되는 문제다. 

조사해보면서 문제를 풀기 위해서는 여러 방법이 있다고 한다.

선형구조형으로 만들거나 BFS/DFS를 사용하거나 재귀를 이용하기도 하고 반복문으로도 풀 수 있다.

때문에 문제를 풀 때 가장 먼저 고려해야 할 것은 '모든 경우의 수를 찾아야 하는가?'인 듯하다.

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와 거리를 곱해준다. 

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

2021.12.10

백준 1541 잃어버린 괄호

# 1541 잃어버린 괄호
a = list(input().split('-'))
n = 0

for i in range(len(a)):
    if i == 0:
        z = sum(list(map(int,a[i].split('+'))))
        n = z
    else:
        z = sum(list(map(int,a[i].split('+'))))
        n = n - z
        
print(n)

기초 문법의 중요성을 다시 한번 깨닫는다.

입력받아올 때 split()을 사용하고서 다음에 바보같이 '어떻게 나누지?'

이런 생각을 하고 있었다. 다시 split()을 사용하면 되는데

알고리즘을 공부하는 데 있어서 우선적으로 공부해야 하는 알고리즘이 있다면 세 가지가 있다고 한다.

• 그리디 알고리즘
• 탐색 알고리즘
• DP ( 동적계획법)

이 세 가지인데 그중에서 그리디 알고리즘에 대해 공부한 것을 정리하는 글

그리디 알고리즘(Greedy Algorithm)이란

탐욕법이라고도 부르며 현재 상황에서 가장 좋은 것을 고르는 알고리즘이다.

현재 상황에서 가장 좋은 것을 고른다는 것은 어떠한 문제가 여러 단계로 나뉘어

차례로 알고리즘이 이어지는 경우, 그 단계마다 가장 좋은 선택을 한다는 것을 의미한다.

그러나 현재 상황에서 가장 좋은 것을 고르는 행위가 그 문제의 모든 경우의 수에서 발생하는최적의 해라는 것을 담보하지는 않는다. 그렇기에 문제를 봤을 때 이 문제가 그리디 알고리즘으로 

풀 수 있는지 추론할 수 있는 능력이 필요하다.

 문제를 그리디 알고리즘으로 풀기 위한 조건

• 각각의 값이 서로 다른 값에 영향을 주지 않을 것
• 그리디 알고리즘으로 풀어낸 값이 모든 경우의 수에서 최적의 해일 것
• 주어진 상위의 값이 하위 값의 배수일 것

세 번째 조건이 그래도 문제를 파악하는데 가장 도움이 되지 않을까 싶다.

그런데 세 번째 조건을 만족해도 그리디로 풀 수 없는 문제가 있으니 문제같다......

예제

백준 11047번 문제

필요한 동전의 최솟값을 구하는 문제로 가장 큰 가치를 가진 동전부터 차례로 나누면 

동전의 최솟값을 구 할 수 있을 것으로 보인다.

거기에 그리디 알고리즘을 적용하게 만든 가장 중요한 문장은 노랗게 칠한 문장 같다.

주어진 상위의 값이 하위 값의 배수라는 것을 알려주었으니 말이다.

N, K = map(int, input().split())
arr = []

for i in range(N):
    arr.append(int(input()))
arr.reverse()                   # 동전을 큰 수부터 계산하기 위해서

R = 0                           # 필요한 동전의 갯수
for i in arr:
    if K//i != 0:               # 조건이 없어도 되긴하다.
        R += K//i                
        K = K%i

print(R)

문제풀이 코드

이제야 한 문제 풀어본 것이기 때문에 앞으로도 문제를 풀어보면서

내가 그리디 문제인지 잘 추론할 수 있는 능력을 기르도록 해야겠다.

2021.12.08

백준 11047 동전 O

N, K = map(int, input().split())
arr = []

for i in range(N):
    arr.append(int(input()))

R = 0
arr.reverse()
for i in arr:
    if K//i != 0:
        R += K//i
        K = K%i

print(R)    

본래 이번 주는 DP 문제 위주로 풀려고 했는데 

친구가 그전에 그리드와 탐색문제를 먼저 풀어보는 것이 좋다고 해서 

그리드 문제로 급히 노선을 갈아탔다.

그런데 지금 문제는 풀었지만

그리드 문제의 유형이 무엇인지 그리드 알고리즘이 무엇인지 모르기 때문에

공부하고 정리하는 시간을 가져야겠다.

2021.12.07

백준 9184 신나는 함수 실행

# 9184 ; 신나는 함수 실행
import sys

def W(a,b,c):
    if a <= 0 or b <= 0 or c <= 0:
        return 1
    if a > 20 or b > 20 or c > 20:
        return W(20,20,20)
    
    if dp[a][b][c]:
        return dp[a][b][c]
    
    if a < b < c:
        dp[a][b][c] = W(a,b,c-1) + W(a,b-1,c-1) - W(a,b-1,c)
        return dp[a][b][c]
    dp[a][b][c] = W(a-1,b,c) + W(a-1,b-1,c) + W(a-1,b,c-1) - W(a-1,b-1,c-1)
    return dp[a][b][c]
    
dp = [[[0 for i in range(21)] for i in range(21)] for i in range(21)]

while True:
    a,b,c = map(int, sys.stdin.readline().split())
    if a == -1 and b == -1 and c == -1:
        break
    print('w({}, {}, {}) = {}'.format(a,b,c,W(a,b,c)))

input()을 사용하기보다는 sys를 import 해서 시간 단축을 조금 더 해줬다.

다른 건 문제의 식을 전부 가져왔는데

중요한 아이디어는 삼차원 배열에 값을 저장해주는 것과

그 값이 있을 경우 바로바로 꺼내오는 것이 문제풀이의 핵심인 듯하다.

삼차원 배열에 저장해도 아래 코드를 쓰지 않으면 시간 초과가 뜬다.

    if dp[a][b][c]:
        return dp[a][b][c]

여담으로 아래 코드에서 공백을 안 넣어 줬더니 틀렸습니다만 계속 떠가지고 

뭐가 문제인지 한참을 찾았다...

print('w({}, {}, {}) = {}'.format(a,b,c,W(a,b,c)))