99클럽 TIL (240826)

> [Middler] 전력망을 둘로 나누기

https://school.programmers.co.kr/learn/courses/30/lessons/86971

 

문제 풀이 과정

전력망을 두개로 나누기 위해 일단 간선을 하나하나 제외한 모든 송전탑의 차이를 구하고 최솟값을 리턴하는 식으로 생각했다... n이 커지면 이게 가능할까 싶은 생각이 들지만 우선 구현해보았다.

 

✨ 알아야하는 것!

abs('절댓값으로 만들 숫자') : 매개변수에 넣은 숫자에 대한 절댓값을 반환

 

문제 풀이

python 

• dfs 로 완전탐색

def solution(n, wires):
    def dfs(start, graph) :
        v = [False for _ in range(n+1)]
        stack = []
        stack.append(start)
        v[start] = True
        top = 1
        while stack :
            node = stack.pop()
            for i in graph[node] :
                if not v[i] :
                    top += 1
                    v[i] = True
                    stack.append(i)
        return abs(top - (n-top))
            
    dif = n
    for i, w in enumerate(wires) :
        temp = wires[:i] + wires[i+1:]
        graph = [[] for _ in range(n+1)]
        
        for t in temp :
            graph[t[0]].append(t[1])
            graph[t[1]].append(t[0])
        
        dif = min(dif, dfs(1, graph))
            
    return dif

 

회고 및 느낀점

 

---

> [Beginner] 적어도 대부분의 배수

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

 

🔥 다시 풀기 🔥

 

문제 풀이 방법

완전탐색으로 풀이 가능 3개로 배수가 나누어 떨어진다면 리턴

 

문제 풀이

python

• 완전탐색

import sys
input = sys.stdin.readline 
nums = list(map(int, input().split()))
a = min(nums)
while True :
    cnt = 0
    for i in nums :
        if a % i == 0 :
            cnt += 1
    if cnt > 2 :
        break
    a += 1
print(a)

 

 

다른 풀이 중 3개의 최대 공배수를 '유클리드 호제법'을 이용해 푼 풀이가 있어서 참고해보았다.

5개 숫자 중 가능한 모든 3가지 조합을 뽑은 다음 그 숫자들의 최소 공배수를 구한다.

• a,b의 최소 공배수 = (a*b) / a,b의 최대공약수
• 유클리드 호제법 : a = b * c + r 일 때, a,b의 최대 공약수는 b,r의 최대 공약수와 같다.

def gdc(a,b) :
    while b != 0 :
        a, b = b, a%b
    return a

nums = list(map(int, input().split()))
answer = []
for i in range(5) :
    for j in range(i+1,5) : 
        for k in range(j+1, 5) :
            c = gdc(nums[i], nums[j])
            temp = int((nums[i] * nums[j])/c)
            d = gdc(temp, nums[k])
            temp2 = int((temp*nums[k])/d)
            answer.append(temp2)
print(min(answer))

 

회고 및 느낀점

유클리드 호제법, 완전탐색 외울건 외우자

최소공배수와 최대공약수를 함께 생각해보자