알고리즘/알고리즘 개념
[알고리즘 특강]
수업목표 자료구조 및 알고리즘에 대한 개념 이해 파이썬 코딩을 통한 알고리즘 구현 교육내용 자료구조 기본 개념 수업 진행 교재 C로배우는 쉬운 자료구조 모두의 알고리즘 자료구조_분류 선형구조 순차리스트, 연결리스트, 스택, 큐, 데크 비선형 구조 트리, 그래프 컴퓨터의 추상화 자료 추상화 자판기 - 커피 한잔을 먹기 위해 굉장히 많은 일을 함. 실제로 자판기에서 커피를 뽑아먹는 사람을 내부에서 어떤 일이 벌어지는지 신경쓰지 않고, 그냥 동잔만 넣고 커피가 나오면 커피를 먹는다. => 이런게 자료의 추상화 C언어에서는 일일이 구현을 해야함 => 권장사항 : C언어 공부(장기적2-3년) WHY? C언어 잘하면 다른 언어는 금방 익힘 알고리즘 자료구조가 요리 재료면 알고리즘은 요리방법 공간복잡도 메모리를 얼마..
비트마스크 & minimum spanning tree & 플로이드 워셜
비트마스크 비트마스크 정수의 이진수 표현을 자료구조로 쓰는 기법 장점 수행시간이 빠르다 코드가 짧다 메모리 사용량이 적다 비트연산 spanning tree 그래프 내의 모든 정점을 포함하는 트리 그래프에 있는 n개의 정점을 정확히 n-1개의 간선으로 연결 minimum spanning tree spanning tree중에서 사용된 간선들의 가중치 합이 최소인 트리 간선에 가중치를 고려하여 최소 비용의 spanning tree를 선택하는 것 네트워크(가중치를 간선에 할당한 그래프)에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결 [구현방법] 1. Kruskal MST 알고리즘 [설명] 탐욕적방법을 이용하여 네트워크의 모든 정점을 최소비용으로 연결하는 최적 해답을 구하는 것 [과정] 그래프의 간선..
[알고리즘] 다익스트라
다익스트라 알고리즘이란? 다이나믹 프로그래밍을 활용한 대표적인 최단경로 탐색 알고리즘 다이나믹 알고리즘인 이유 : 최단거리는 여러 개의 최단 거리로 이루어져있기 때문 현재까지 알고 있던 최단 경로를 계속해서 갱신 인공위성 GPS소프트웨어 등에서 가장 많이 사용 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려줌 음의 간선은 포함할 수 없음 현실세계 -> 음의 간선 존재X => 현실세계에 사용하기 매우 적합 과정 1. 출발 노드 설정 2. 출발 노드를 기준으로 각 노드의 최소비용 저장 3. 방문하지 않은 노드 중에서 가장 비용이 적게드는 노드 선택 4. 해당 노드를 거쳐 특정한 노드로 가는 경우를 고려하여 최소비용 갱신 5. 3번과 4번 과정 반복
[알고리즘] 퀵정렬 / 병합정렬 / DFS&BFS / DP
불안정 정렬 다른 원소와의 바교만으로 정렬을 수행하는 비교정렬 분할 정복 알고리즘 --> 매우 빠른 수행속도 합병 정렬과 달리 리스트를 비균등하게 분할 분할정복방법 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략 대개 순환 호출을 이용하여 구현 과정 설명 1. 리스트 안에 있는 한 요소를 선택. --> 피벗 이라고 한다. 2. 피벗을 중심으로 왼쪽 : 피벗보다 작은 요소들, 오른쪽 : 피벗보다 큰 요소들로 옮겨진다. 3. 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬 분할된 부분 리스트에 대하여 순환호출을 이용하여 정렬을 반복 부분 리스트에서도 다시 피벗을 정하고 피벗을 기준으로 2개의 부분 리스트로 나누는 과정을 반복 4. 부분 리스트들이 더..
정렬 알고리즘
거품정렬(버블정렬) 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어있지 않으면 서로 교환한다. 선택정렬과 기본 개념이 유사 버블정렬 c언어 코드 # include # define MAX_SIZE 5 // 버블 정렬 void bubble_sort(int list[], int n){ int i, j, temp; for(i=n-1; i>0; i--){ // 0 ~ (i-1)까지 반복 for(j=0; jheap[i/2]; // 한 레벨 위로 올라단다. i /= 2; } h->heap[i] = item; // 새로운 노드를 삽입 } 2. 최대힙의 삭제 1. 최대 힙에서 최댓값은 루트 노드이므로 노드가 삭제된다. - 최대 힙에서 삭제 연산은 최댓값을 가진 요소..
자료구조와 알고리즘
input -> process -> output ↑↓ Store 데이터의 흐름과 저장 - 자료구조 시간과 공간 효율성 - 알고리즘 자료구조 때와 장소에 맞는 자료구조를 사용해야한다. 알고리즘 - 좋은 알고리즘의 조건 1. 적절한 입력.출력 2. 명확성(목적) 3. 유한성(무한루프X) 4. 효율성 - 자료구조와 알고리즘의 관계 자료구조가 알고리즘에 쓰인다.(자료구조를 활용하여 어떤 문제를 해결) 자료를 직접 구현하려면 알고리즘이 필요하다. => 서로 뗄 수 없는 사이
탐욕알고리즘(Greedy)
탐욕알고리즘이란? - 최적의 해에 가까운 값을 구하기 위해 사용됨 - 여거 경우 중 하나를 결정해야할 때마다, 매순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행해서 ,최종적인 값을 구하는 방식 탐욕 알고리즘의 예 문제1 : 동전문제 지불해야한느 값이 4720원 일 때 1원 50원 100원 500원 동전으로 동전의 수가 가장 적게 지불하기오. - 가장 큰 동전부터 최대한 지불해야하는 값을 채우는 방식으로 구현가능 - 탐욕알고리즘으로 매순간 최적이라고 생각되는 경우를 선택하면 됨 해결방법 coin_list = [500, 100, 50, 1] def main_coin_count(value, coin_list): total_coin_count = 0 details = list() coin_list.sor..
다이나믹 프로그래밍
- 큰 문제를 작은 문제로 나눠서 푸는 알고리즘 - 문제에는 크기가 있어야함 - 각각의 작은 문제를 풀고 원래대로 합친다. - Dynamic에 대한 어떠한 의미도 없음 -> 헷갈리지마셈 ㅎㅅㅎ - 다이나믹 알고리즘 : 작은 문제가 중복가능 - 분할정복 알고리즘 : 작은 문제가 중복되지 않음 1. Overlapping Subproblem : 부분문제 겹친다. 2. Optimal Substructure : 최적 부분 구조 * 큰 문제와 작은 문제를 같은 방법으로 풀 수 있다. * 문제의 정답을 작은 문제의 정답에서 구할 수 있다. * 문제를 작은 문제로 쪼갤 수 있다. * 예시(피보나치 수) - 문제 : N번째 피보나치 수를 구하는 문제 - 작은 문제 : N-1번째 피보나치 수를 구하는 문제, N-2번째 피..