6.Breadth_first_search.md 너비 우선 탐색 (breadth-first-search)너비 우선 탐색을 사용하여 두 항목 간의 최단 경로를 찾을 수 있다.체커 게임에서 가장 적은 수로 승리할 수 있는 방법을 계산하는 인공지능맞춤법 검사기(실제 단어에서 가장 적은 개수의 글자를 고쳐서 올바른 단어를 만드는 방법을 찾는다.)네트워크에서 가장 가까운 의사 선생님을 찾기그래프란?연견의 집합을 모형화한 것.정점(node)과 간선(edge)으로 이루어져 있다.정점은 여러 개의 다른 정점과 바로 이어질 수 있고, 이러한 정점들을 이웃(neighbor) 이라고 한다.너비우선 탐색너비 우선 탐색은 그래프를 대상으로 하는 다른 종류의 알고리즘이다. 질문 유형 1 : 정점 A에서 정점 B로 가는 경로가 존재..
STUDY/알고리즘(Python)
5.Hash_table.md 해시테이블 (hash table)유용한 자료 구조의 하나인 해시 테이블에 대해서 알아봄.1. 해시 함수의 소개식료품 가게에서 일을 하고 있다고 생각해보자. 손님이 물건을 사러 왔을 때 물건의 가격이 적혀져있는 장부를 찾아서 가격을 봐야 한다. 만약 장부가 정렬이 정렬이 되어 있지 않다면 만큼의 시간이 걸릴 것이다.정렬이 되어있다면 이진 탐색을 통해 만큼의 시간이 소요될 것이다. 두 차이는 크다.정렬이 되어있더라도 지속적으로 장부를 보고 찾는 일은 힘들 것이다. 이때 가장 필요한 것이 가격을 외우고 있는 동료가 옆에 있는 것.이를 자료 구조 관점으로배열과 리스트 2개의 자료구조를 학습하였다.장부 구조 시간에 찾아내고 싶어하는데 이를 가능하게 하는 것이 이다.2. 해시 함수해시 ..
4.Quick_Sort.md 퀵정렬분할 정복가장 간단한 경우로 기본 단계를 찾는다.주어진 문제를 작게 줄여서 기본 단계가 되도록 만드는 방법을 찾는다.예 (덧셈 함수)[1,2,3,4] xxxxxxxxxxdef sum(arr): total = 0 for x in arr: total += x return total print(sum([1,2,3,4]))1단계 : 기본 단계를 찾는다. 가장 간단한 경우는 배열의 원소 개수가 0개 또는 1개인 배열을 받으면 합계를 구하는 것.2단계 : 재귀 함수 호출을 할 때마다 호출 대상이 되는 배열의 크기가 점점 감소시켜야 한다. 결론 리스트를 받으면 크기를 구해 비어있으면 0을 반환 그렇지 않으면 총합은 리스트의 첫 번째 숫자와 나머지 리스트의 총합을 더한 값이 된다.퀵 ..
3.Recursive_function.md 재귀함수 (Recursive function)재귀할머니의 비밀상자가 존재한다. 상자를 열어보니 또 안에 많은 상자가 존재한다. 그 중 하나에 키가 있다고 한다면...첫번째 (While)내부를 확인할 상자를 쌓아놓는다.상자를 하나 집어서 내부를 살핀다.만약 안에 상자가 있다면 꺼내어 나중에 확인할 상자 더미에 놓는다.만약 열쇠가 있으면 작업 종료.반복한다. xxxxxxxxxxdef look_for_key(main_box): pile = main_box.make_a_pile_to_look_through() while pile in not empty: box = pile.grab_a_box(): for item in box: if item.is_a_box(): pil..
2.Select Sort.md 그림으로 개념을 이해하는 알고리즘선택정렬(Select Sort)배열(Array) 와 연결리스트(Linked List)선택정렬 (Select Sort) 1. 메모리가 동작하는 방법예를 들어 물건을 보관하는 공간이 필요하다고 한다면 1개의 공간에 1개의 물건만 보관이 가능하다. 그렇다면 물건의 갯수만큼 공간의 갯수가 필요할 것이다.메모리도 마찬가지이다. 많은 공간 => 메모리 주소, 무엇인가를 저장할때마다 주소(공간)를 요청여러 개의 원소를 저장해야한다면 배열과 리스트라는 두 가지 방법 중 하나를 사용2. 배열과 연결리스트배열 : 일정 공간을 미리 할당받아 연속적으로 사용하는 방법 (영화관의 자리를 미리 예매해놓고 시청하는 방법, 누군가가 오지 않는다면 그대로 금액을 지불해야 ..
그림으로 개념을 이해하는 알고리즘 Chapter 2. 이진탐색 예를 들어 전화번호부를 찾는다고 치자 이 씨를 찾기위해서는 맨앞에서 시작하는 방법과 중간부터 시작하는 방법 등 다양한 방법이 있을 것이다. 처음에서 시작하는 것보다 중간에서 시작하는 것이 더 빨리 탐색 1~100 까지 숫자 있을 때 1부터 순서대로 찾게 된다면 100이 찾는 수라면 100번을 수행해야 찾게 된다. (Simple Search) 더 좋은 탐색 방법 100의 중간 50부터 시작하는 것. 해당 부분보다 적거나 많다면 다시 절반 이러한 방식으로 찾게 된다면 더 빨리 찾게 될 것이다. 예) 100 -> 50 -> 25 -> 13 -> 7 -> 4-> 2 -> 1과 같은 순서대로 진행 될 것이다. 240,000개의 단어가 있다면 최대 몇 ..
