본문 바로가기

Algorithm7

백준 2606 바이러스 재채점 변경사항 반례: 컴퓨터가 1만 따로 있는 경우 OR 1번 컴퓨터가 존재하지 않는 경우 import collections n = int(input()) graph = [[] for _ in range(n+1)] for _ in range(int(input())): a, b = map(int, input().split()) graph[a].append(b) graph[b].append(a) visited_node = [] q = collections.deque() q.append(1) # 1번 컴퓨터 while q: frm = q.popleft() for to in graph[frm]: if to not in visited_node: q.append(to) visited_node.append(to) ## 반례: 1만.. 2023. 7. 2.
[알고리즘 분석 #6] 디스크 컨트롤러 프로그래머스 Python 사용 알고리즘 우선순위 큐 사용 자료구조 특징 1. Heap 기반 자료구조이다 2. Heap 은 일반적으로 완전 이진트리 구조를 가지고 있다. 3. 우선순위 큐는 우선순위가 높은 원소부터 처리된다. -> 넣으면 이진트리 형태로 들어가서 찾기, 변경하기가 O(log N) 4. 큐에 넣을때 자동으로 정렬된다. 5. python Heapq는 기본은 최소힙이다 ( 가장 작은 값이 부모노드 이다) ( 배열 맨 첫번째 요소 ) 파악하는 방법 ( 풀이를 고민하는 흐름 방식 ) 우선 모든 방법을 찾는다는 생각을 버린다 현재 시간에 따라서 어떤 디스크가 올지 고민해야한다 ( 실행시간이 짧은게 우선적으로 실행되야하는것을 안다면 더욱 좋다 ) 현재 시간에 따라 -> 어떤 디스크가 옳을지 -> 를 무한반벅 따라서 현재시간 기.. 2023. 3. 31.
[알고리즘 분석 #5] 1916 최소비용구하기 (파이썬) 알고리즘 다익스트라 알고리즘 BFS랑 구조가 비슷하다. 단, 해당 문제는 "비용" 이 들어가기 때문에 graph: 그래프의 간선을 저장하는 2차원 배열 costs: index 위치의 최소비용 저장 1차원 배열 2가지가 필요하다 BFS와 차이점은 방문여부를 따로 관리하지 않는다 이를 비용이 저장되있는것보다 더 크면, continue함으로써 비용 절약을 한다. 이를 통과하면 graph 배열을 통해 갈수있는 간선을 확인하고, 거쳐서 가는 비용이 더 적다면 갱신하고 q에 넣는다 기본 코드 import heapq # 우선순위 큐 구현을 위함 def dijkstra(graph, start): distances = {node: float('inf') for node in graph} # start로 부터의 거리 값을.. 2023. 2. 23.
[알고리즘 분석 #4] 백준 1987 알파벳 ( 메모리 초과, 시간 초과, Python ) 미친것 같다. 문제 링크: https://www.acmicpc.net/problem/1987 시간초과 및 메모리 초과 해결법 1. 값을 빨리 찾는것은 List 의 In 은 O(n) SET은 O(1) 2. 재귀 횟수도 잘 고려해 보아야한다 만약 10**9로 하면 시간초과 난다 sys.setrecursionlimit(10000) 3. 처음에 visited 라는 방문 여부를 확인하는 배열을 넣어놨는데, 어차피 똑같은 알파벳이 있으면 돌아가지 못함으로 해당 배열을 빼도 된다. 코드 import sys import time sys.setrecursionlimit(10000) input = sys.stdin.readline n, m = map(int, input().split()) visit = set() grap.. 2023. 2. 22.