소프트웨어학과 k군

일단 이 수많은 삽질의 흔적이 보이십니까? 보고 모른 척해주십시오...일단 이 문제는 DP(Dynamic Programing)이지만 로직 자체는 피보나치 수열이랑 똑같습니다. 문제를 쪼개서 생각하고 작은 문제가 맞으면 큰 문제까지 잘 적용이 되냐 안되냐를 물어보는 문제입니다. 일단 오답 코드 먼저 보시죠배열을 이용한 피보나치import sysinput = sys.stdin.readlinedef binary(n): arr = [] arr.append(0) arr.append(1) arr.append(2) for i in range(3, n+1): arr.append(arr[i-1] + arr[i-2]) return arr[n] % 15746n = ..

다익스트라 알고리즘(Dijkstra Algorithm)다익스트라 알고리즘은 가중치가 있는 그래프에서 한 정점(출발점)으로부터 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다. 필수 조건 : 모든 간선의 가중치는 0 이상의 값이어야 하며, 음수 가중치가 존재하면 올바른 결과를 보장할 수 없습니다. → 음수 가중치는 나중에 배울 벨만-포드 알고리즘을 사용합니다.분류: 그리디 접근 방식으로 매 단계마다 "현재까지의 최단 경로"를 이용하여 다음 정점을 선택합니다.동작 과정 및 의사 코드1. 초기화모든 노드까지의 최단 거리를 무한대(INF)로 설정 → 최단 거리기 때문에 초기 값을 무한대로 설정시작 노드의 최단 거리는 0으로 설정우선순위 큐(힙)에 (거리, 노드) 형태로 시작 노드를 추가 → (거리, 노드)..

최소 신장 트리(MST, Minimum Spannig Tree)최소 신장 트리란 가중치가 있는 무방향 그래프에서 모든 정점을 연결하면서도 간선의 가중치 합이 최소가 되는 트리입니다. 위에 그림처럼 여러 신장 트리(모든 정점을 연결하는 트리)가 존재할 수 있으나, 간선의 가중치의 합이 가장 작은 트리가 최소 신장 트리입니다. 최소 신장 트리의 필요성과 활용네트워크 설계: 컴퓨터, 통신 기기를 최소 비용으로 연결도로망 구축: 도시 간의 도로를 최적 비용으로 설계클러스터링 및 데이터 분석: 데이터 포인트들 사이의 관계를 기반으로 군집 형성MST는 최적의 비용으로 모든 요소를 연결해야 할 때 유용한 개념입니다. MST 알고리즘 MST를 구하는 대표적인 알고리즘은 크루스칼(kruskal)과 프림(Prim) 알고리..

스택(Stack)사전적 의미로는 "쌓아 올리다, 포개지다."입니다. 알고리즘에서도 스택 자료구조도 이 사전적 의미를 따라갑니다. 흔히 예시로 책상에 책을 쌓아둘 때 차곡차곡 쌓아가고, 책을 꺼낼 때는 맨 위(Top)에서부터 하나씩 꺼내서 읽는다.(중간에서 빼는 경우 없다고 가정합니다.)하지만 혹시 프링글스를 아시나요? 감자칩 이거 감자칩 먹을 때 생각하면 편한게 가장 마지막(위)에 있는 걸 먼저 먹지 않나요? 그거 생각하면 편하게 생각할 수 있스습니다. 그리고 감자칩이 아니더라도 다른 것들을 넣을 때 가장 처음에 넣은 것이 가장 마지막에 나오게 될 것입니다.(다른 것은 2개 이상)스택은 감자칩 구조이다.라고 생각하면 좀 더 이해가 편해지실 겁니다.  스택의 특징 스택은 그림에서 말했다 싶이 LIFO(La..