소프트웨어학과 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) 알고리..

DFS(Depth First Search)DFS(Depth First Search)는 영어 번역 그대로 깊이 우선 탐색이며, 그래프에서 깊이를 기준으로 탐색하는 알고리즘이다. 이게 무슨 말인지 잘 이해가 안 갈 수도 있어서 그림을 준비했습니다. DFS 기본 동작 원리 시작점(루트 노드)에서 출발합니다.현재 노드의 인접 노드 중 하나를 선택하여 한쪽 방향으로 계속 깊게 들어갑니다.더 이상 진행할 수 없으면 바로 이전 노드로 돌아와(백트래킹) 다른 경로를 탐색합니다.모든 노드를 방문하거나, 원하는 목표를 찾을 때까지 이 과정을 반복합니다.e.g. in tree structure 루트 노드에서 시작하여 왼쪽 자식 노드로 내려간 후, 그 자식의 왼쪽 자식으로 계속 내려갑니다.더 이상 내려갈 수 없게 되면, 이전..

이진 탐색(Binary Search)이진 탐색(Binary Search)은 정렬된 배열에서 특정한 값을 효율적으로 찾는  탐색 알고리즘 이진 탐색의 동작배열 정렬: 이진 탐색을 진행하기 전에 찾고자 하는 배열은 무조건 정렬이 되어 있어야 합니다. 만약 배열이 정렬되어 있지 않은 경우 원하는 값을 못 찾을 수도 있습니다.중간 지점 선택: 배열 내에서 중간 위치의 요소를 선택합니다. 예를 들어 파이썬 기준 left = 0, right = len(arr) - 1이라고 가정하면 mid = (left + right) // 2로 놓을 수 있습니다.조건 비교: 중간 지점(mid)의 값과 찾고자 하는 값(target)을 비교mid == target → 원하는 값을 찾음 → 탐색 종료mid > target → 탐색 범위..

퀵 정렬(Quick Sort)란?퀵 정렬은 찰스 앤터니 리처드 호어(Charles Antony Richard Hoare)가 개발한 알고리즘으로, 분할 정복(divide and conquer) 방식을 활용하여 리스트를 정렬하는 알고리즘입니다.  작동 원리분할(Divide): 리스트에서 하나의 요소를 피벗(pivot)으로 선택합니다. 그다음, 피벗을 기준으로 리스트를 두 개의 부분 리스트로 분할합니다. 하나는 피벗보다 작은 요소들로, 다른 하나는 피벗보다 큰 요소들로 구성됩니다. 정복(Conquer): 부분 리스트들을 재귀적으로 정렬합니다. 결합(Combine): 정렬된 리스트들을 합쳐 전체 리스트를 완성합니다.  시간 복잡도평군 시간 복잡도 : O(n * log n)최악 시간 복잡도 : O(n^2) → 이..