코-다시풀기-흥-1주차

가장 먼 노드

가장 멀리 있는 노드를 최단 경로로 이동

bfs(또는 dfs)는 최소 , 가장빠른 이라는 단어가 나오면 사용하면 좋다

• 가중치가 적용되지 않을 때, BFS의 부가 효과를 이용한다면, 최소 이동 횟수도 계산 가능

from collections import deque
def main():
    print(solution(6,[[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]))

def solution(n,edge):
    answer = 0

    arr = [[]  for i in range (n+1)]
    visited = [0] *( n+1)

    for i , j in edge:
        arr[i].append(j)
        arr[j].append(i)
    
    visited[1] = 1

    bfs(1,arr,visited)

    for i in visited:
        if i == max(visited):
                answer += 1
    return answer


def bfs(start,arr,visited):
    que = deque([start]) # 양방향 큐

    while que:
        v = que.popleft() # Pop element from the start
        for i in arr[v]:
            if not visited[i]:
                visited[i] = visited[v] + 1
                que.append(i)
    
if __name__ == "__main__":
    main()

1. 인접행렬 만들기

2. 초기값 설정
   visited[1] = 1

3. bfs(start,adj,visited) → start에서 시작해 갈 수 있는 모든 정점

4. que = deque([start]).

• deque(데크)
  - 양방향 큐
  - popleft() : pop from the start

5. que가 비어있지 않은동안. pop해서. 방문하지 않았다면 pop한 값 인접한 곳 방문 방문해서 또 que에 넣기 .

전화번호 목록

String.startwith(String)

def solution(phone_book):
     phone_book.sort() # 정렬해서 앞뒤 비교 가능한 자원들이 위치하도록 한다.
     for i in range(len(phone_book)-1):
             # j가 접두어가 맞다면 : return false
             if phone_book[i+1].startswith(phone_book[i]): return False
     return True

타겟 넘버

dfs(depth,numbers,number + numbers[depth],target)
dfs(depth,numbers,number - numbers[depth],target)
를 통해 +와 -를 모두 순회한다.
depth와 target을 확인해 재귀를 종료한다.

def main():
    print(solution([1, 1, 1, 1, 1],3))

def solution(numbers, target):
    answer = 0
    answer += dfs(0,numbers,0,target)
    return answer

def dfs(depth,numbers,number,target):
    answer = 0
    if depth == len(numbers):
        if target == number:
            return 1
        else: return 0
    else:
        answer += dfs(depth+1,numbers,number+numbers[depth],target)
        answer += dfs(depth+1,numbers,number-numbers[depth],target)
    return answer
if __name__ == "__main__":
    main()

기능 개발

math.celi(x) # x의 올림 값을 반환
deque
while deque가 비어있지 않을 동안, index < len(progressess) ..

from collections import deque
import math

def main():
    print(solution([93, 30, 55],[1, 30, 5]))

def solution(progresses, speeds):
    answer = []
    
    for i in range(len(progresses)):
        progresses[i] = math.ceil((100 - progresses[i]) / speeds[i])
            
    queue = deque([progresses[0]])
    index = 1
    while queue and index < len(progresses):
        if progresses[index] <= queue[0]:
            queue.append(progresses[index])
        else:
            answer.append(len(queue))
            queue.clear()
            queue.append(progresses[index])
        index += 1
        
    answer.append(len(queue))
    
    return answer
    
if __name__ == "__main__":
    main()