전체 글

📌 - 중복되는 연산을 줄이자 최적의 해를 구하기에 시간이 매우 많이 필요하거나 메모리 공간이 매우 많이 필요한 문제 등이 컴퓨터로도 해결하기 어려운 문제가 있다. 컴퓨터 연산 속도에 한계가 있고, 메모리 공간을 사용할 수 있는 데이터의 개수도 한정적이라는 점이 많은 제약을 발생시킨다. ❗️- 연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘을 작성해야한다. 메모리 공간을 약간 더 사용해서 연산 속도를 비약적으로 증가시킬 수 있는 방법이 바로 다이나믹 프로그래밍이다. 👉 대표적인 예시 - 피보나치 수열 - n번째 피보나치 수 = (n-1)번째 피보나치 수 + (n-2)번째 피보나치 수 - 단, 1번째 피보나치 수 = 1, 2번째 피보나치 수 = 1 피보나치 수열을 재귀함수로 만들 수..

🗒️ 위상 정렬이란? 위상정렬이란 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것' 이해하기 쉽게 예를 들자면 위상 정렬을 수행하게 되는 예시로는 여러 게임들의 직업 시스템을 들 수 있다. 예를 들어 직업 시스템에는 '모험가'로 시작해서 '마법사'가 될 수 있다. 이때 '모험가' 및 '마법사'를 각각의 노드로 표현하고, '모험가'에서 '마법사'로 이어질 수 있도록 방향성을 갖는 간선을 그린다. 그래프에서 선후 관계가 있다면, 위상 정렬을 수행하여 모든 선후 관계를 지키는 전체 순서를 계산할 수 있다. 다시 예를 들면 직업의 단계가, '마법사'가 되기 위해선 '모험가'여야 하고, '대마법사'가 되기 위해서는 '마법사'여야 한다고 가정하자. 이 경우에서 '대마법사'가 되기 위해서..

1️⃣ - 처음 생각한 풀이 3차원 배열을 만들어서 데이터를 넣는다. 전부 방문하면서 1일 경우, 주변 토마토들을 익힌다. 토마토를 익힐 수 없을 때, 반복을 종료하고 년도, 상태를 확인하고 출력한다 이런 식으로 풀이를 생각했었는데, 3차원으로 생각을 하려다보니 계속 복잡해지고 헷갈려서 자꾸 답이 틀려서 다른 방식을 찾아봤다. 2️⃣ - 두 번째 풀이 3차원 배열에서 1을 전부 queue에 담는다. - 담으면서 방문처리 bfs로 queue에 있는 좌표들을 빼면서 근처 좌표들을 queue에 다시 넣고 익히는 과정을 반복한다. - queue에 다음 좌표들을 넣을 때 년도를 같이 넣어준다. 바뀐 배열을 처음부터 비교해서 가장 큰 값 -1을 출력한다 from sys import stdin as s from co..

1️⃣ - 처음 생각한 코드 그래프에 경로를 전부 저장 bfs로 시작지점부터 경로 시작해서 이전 경로까지 거리를 계속 비교해가면서 더 작은 값을 저장 반복해서 마지막 최종 목적지 배열의 값 출력 from sys import stdin as s from collections import deque import heapq s = open('input.txt','rt') N = int(s.readline()) M = int(s.readline()) graph = {} for _ in range(M): start, end , dis = list(map(int,s.readline().split())) graph[start] = graph.get(start,[]) + [(dis,end)] start , end = ..

보호되어 있는 글입니다.

🕹️ - 신장 트리 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 🕹️ - 크루스칼 알고리즘 가능한 한 최소한의 비용으로 신장 트리를 찾아야 할 때 필요한 알고리즘이다. 그리디 알고리즘으로 분류되고 기본적으로 모든 간선에 대하여 정렬을 수행한 뒤에 가장 거리가 짧은 간선부터 집합에 포함시키면 된다. 이때 사이클을 발생 시킬 수 있는 간선의 경우, 집합에 포함 시키지 않는다. 간선 데이터를 비용에 따라 오름차순으로 정렬한다. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다. - 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킨다. - 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않는다. 모든 간선에 대하여 2번의 과정을 반복한다. 1️⃣..