Algorithm/Concept (10) 썸네일형 리스트형 Advance_MST 그래프의 최소 비용 문제 (Minimum Spanning Tree) 01 최소 신장 트리 그래프에서 최소 비용 문제 최소 신장 트리 문제 : 가중치 그래프에서 모든 정점들을 연결하는 간선들의 가중치의 합이 최소가 되는 트리를 찾는 문제 최단 경로 문제 : 시작 정점에서 목표 정점까지 가는 간선의 가중치의 합이 최소가 되는 경로를 찾는 문제 신장 트리(Spanning Tree) : 무향 그래프에서 n개의 정점과 n-1개의 간선으로 구성된 트리 최소 신장 트리(Minimum Spanning Tree) : 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 산장 트리 Prim Algorithm 하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 만들어 가는 방식 임의 정점 선택 선.. Advance_Graph 그래프의 기본과 탐색 01 그래프 기본 그래프 객체(사물 또는 추상적 개념)들과 객체들 사이의 연결 관계 표현 정점(Vertex)들의 집합과 정점을 연결하는 간선(Edge)들의 집합으로 구성된 자료 구조 : G = (V,E), V: 정점들의 집합, E: 간선들의 집합 |V|:정점 개수, |E|: 간선 개수 선형이나 트리 자료구조로 표현하기 어려운 N:N 관계를 가지는 원소들을 표현하기에 용이 그래프 종류 무향 그래프(Undirected Graph) : 서로 대칭적인 관계를 연결해서 나타낸 그래프 유향 그래프(Directed Graph) : 간선을 화살표로 표현하고 방향성의 개념 포함 가중치 그래프(Weighted Graph) : 간선(이동할때)에 가중치를 부여한 그래프 추가 정의 인접 : 두 개의 정점에.. Advance_Backtracking 백트래킹(Backtracking) 01 백트래킹 - 백트래킹(Backtracking) 해를 찾는 도중에 막히면 되돌아가서 다시 해를 찾아가는 기법 최적화(Optimization) 문제와 결정(Decision) 문제를 해결 가능 결정 문제: 해 존재 여부 → yes or no ex) 미로 찾기 - 입구 → 출구 경로 존재 여부 - 조건 만족하는 부분 집합 존재 여부 - 미로 찾기 최단 경로 문제 : 초기 상태에서 목표 상태로 가는 경로를 탐색하는 기법 여러 가지 선택지중 하나 선택 → 새로운 선택지 집합 생성 → 반복 후 최종 상태 - 트리의 루트 → 당첨(단말 노드) 가는 경로 찾기 dfs와 같은 방법 - 상태 공간 트리 해를 찾기 위한 선택의 과정을 트리로 표현한 것 Backtracking 과 DFS의.. Advance_Divided and Conquer 분할정복(Divided and Conquer) 01 분할 정복 기법 - 예제 : 가짜 동전 찾기 n 개의 동전들 중에 가짜 동전이 하나 포함 되어 있다. (무게가 다름) 양팔 저울을 최소로 사용해서 가짜 동전을 찾는 방법은 무엇일까..? 분할 정복 알고리즘의 설계 전략 분할(Divide) : 해결할 문제를 여러 개의 작은 부분 문제들로 분할 정복(Conquer) : 나눈 작은 문제를 각각 해결 통합(Combine) : 필요 시 해결된 해답을 모음 반복(Iterative) 알고리즘 : O(n) : C의 거듭제곱 = 1에 거듭제곱 만큼 C를 곱하는 방법 def Iterative_Power(C,n): result = 1 for _ in range(n): result *= C return result 분할 정복.. Advance_Greedy Algorithm 탐욕(그리디) 알고리즘(Greedy Algorithm) 01 탐욕 알고리즘 - 탐욕(그리디) 알고리즘 최적화 문제를 해결하는 알고리즘최적화 문제 : 최적(최대값 이나 최소값 같은) 값을 구하는 문제 - 수행 과정 - 해 선택 : 현재 상태에서 부분 문제의 최적해 구하고, 부분 해 집합(Solution Set)에 추가 - 실행 가능성 검사 실시 : 새로운 부분 해 집합의 실행가능 여부 확인 문제의 제약 조건 확인 - 해 검사 : 새로운 부분 해 집합이 문제의 해가 되는지 검사 문제 예시 1 : 동전 거스름돈 해 선택 : 현재 고를 수 있는 가장 단위가 큰 동전을 골라 거스름돈에 추가.(돈의 우선순위 존재) 실행 가능성 검사 : 거스름돈이 액수를 초과하는지 확인 해 검사 : 거스름돈 문제의 해 ⇔ 손님에게 .. Advance_Start 01 SW 문제 해결 - 소프트웨어(SW) 문제 해결 역량 : 프로그램 작성을 위한 많은 제약 조건들과 요구사항들을 이해하고 최선의 방법을 찾아내는 능력 프로그래머가 사용하는 언어, 라이브러리, 자료구조, 알고리즘에 대한 지식을 적재적소에 연결하여 큰크림을 만드는 능력 - 문제 해결 능력 향상 : 조합 방법 공부 ex) 새로운 언어, 프레임 워크, 개발 방법론 경험을 통해 나아지지 않는다 → 인위적인 상황을 만들어서 훈련해야 한다. - 문제 해결 과정 단계 문제 인지 문제를 익숙한 용어로 재정의 계획 세우기 계획 검증 프로그램 구현 풀이 검토 및 개선 방안 ⇒ 능력 향상을 위해 직관적인, 체계적인 접근이 필요하다. 비슷한 문제를 풀어본 적 있는가? 단순한 방법에서 시작할 수 있는가? 문제를 단순화 할 수.. Algorithm_Tree Tree(트리) 비선형 구조 원소들 간에 1:n 관계를 가지는 자료구조 원소들 간에 계층관계를 가지는 계층형 자료구조 상위 원소 -> 하위 원소로 내려가면서 확장되는 트리(나무)모양의 구조 - 용어 정리 노드(node) : 트리의 원소 간선(edge) : 노드를 연결하는 선. 부모 노드와 자식 노드를 연결 루트 노드(root node) : 트리의 시작 노드 형제 노드(sibling node) : 같은 부모 노드의 자식 노드들 조상 노드 : 간선들 따라 루트 노드까지 이르는 경로에 있는 모든 노드들 서브 트리(subtree) : 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리 자손 노드 : 서브 트리에 있는 하위 레벨의 노드들 나머지 노드들은 n개의 분리집합으로 분리될 수 있음. T1,...,TN은 각.. Algorithm_Queue Queue 큐(Queue) : 스택과 마찬가지로 삽입과 삭제의 위치가 제한적인 자료구조로써, 선입선출형식의 자료구조. 선입선출 (First In First Out) : 큐에 삽입한 순서대로 원소가 저장되어, 가장 먼저 삽입된 원소가 가장 먼저 삭제된다. 스택의 연산 enQueue(item) : 큐의 뒤쪽(rear 다음)에 원소를 삽입하는 연산 deQueue() : 큐의 앞쪽(front)에서 원소를 삭제하고 반환하는 연산 createQueue() : 공백 상태의 큐를 생성하는 연산 isEmpty() : 큐가 공백상태인지를 확인하는 연산 isFull() : 큐가 포화상태인지를 확인하는 연산 Qpeek() : 큐의 앞쪽(front)에서 원소를 삭제없이 반환하는 연산 큐(Queue)의 종류 : 선형큐, 원형큐,.. 이전 1 2 다음
