목록알고리즘 (5)
이재호
탐욕 알고리즘은 간단합니다, 각각의 단계에서 최적의 수를 찾아내면 됩니다. 집합 커버링 문제 라디오쇼를 시작했다고 가정했을때 미국 50개의 주에 있는 모든 사람에게 이 라디오 쇼를 들려주고 싶다 하나의 방송국을 톨해 청취할수 있는 지역이 한정되어 있기 때문에 전국에 흩어져 있는 몇개의 라디오 방송국들을 방문해서 라디오쇼를 진행할 예정이다, 전국의 모든사람들이 최소한 한번은 쇼를 들을수 있도록 하려면 어떤 방송국을 방문해야할지 계산해한다 또 방송국을 방문하여 한번 쇼를 하는데 돈이 들기 때문에 최대한 적은 수의 방송국을 돌아야 한다. 근사 알고리즘 아직 방송하지 않은 지역중 가장 많은 지역에 방송할수 있는 방송국을 고릅니다. 이미 방송되고 있는 지역이 일부 포함되어 있어도 상관없습니다. 모든 주에 방송이 ..
다익스트라 알고리즘은 최단시간경로를 구할때 사용합니다, 너비우선탐색은 최단경로를 구할때 사용합니다. 다익스트라 알고리즘 4단계 가장 가격이 싼 정점을 찾는다, 가장 가격이 싼 정점이란 도달하는데 시간이 가장 적게 걸리는 정점을 말한다 이 정점의 이웃정점들의 가격을 조사한다. 그래프상 모든 정점에 이러한 일을 반복한다. 최종 경로 계산 다 익스트라 알고리즘을 사용할떄, 그래프의 각 간선은 어떤 숫자를 가진다 이 숫자를 가중치라고 하며 가중치를 가지는 그래프를 가중그래프(다익스트라 알고리즘) , 가중 그래프가 없는 그래프를 균일 그래프라고 한다(너비우선탐색) 다 익스트라 알고리즘을 사용하면 최소화가 가능합니다. 다익스트라 알고리즘을 사용한 물물교환 라마라는 친구는 악보를 팔아서 피아노를 구하고 싶어합니다 알..
큐(대기열)은 실생활에서 완전히 똑같이 동작한다. 만약 내가 버스정류에서 줄을 서고 있다고 가정하면 내가 만약 다른사람보다 앞에 서있으면 버스를 먼저 탄다 큐도 마찬가지다 큐는 큐 안의 원소에 임의로 접근할수 없다는점에서 스택과 비교된다 큐에는 삽입과 제거라는 두가지 연산이 있다 만약 내가 목록에 두개의 항목을 삽입하면 두번째로 삽인된 항목보다 첫번쨰로 삽입된 항목이 먼저 제거됩니다. 큐는 탐색 목록에도 사용할수 있고, 큐를 사용하면 목록에 먼저 추가된 사람을 먼저 꺼내서 탐색합니다. 큐는 선입선출이다!(버스정류장) , 스택은 후입 선출(팬케이크)
너비 우선 탐색을 사용하면 두 항목간의 최단 경로를 찾을수 있습니다. 그래프 알고리즘은 가장 유용한 알고리즘 입니다. 예 ) 체커 게임에서 가장 적은수로 승리할수 있는 방법을 계산하는 인공지능 맞춤법 검사기(실제 단어에서 가장 적은 개수의 글자를 고쳐서 올바른 단어를 만드는 방법을 찾는다) 우리 주변에 가까운 맛집 , 병원 , 편의점등을 찾는다 최단 경로 문제를 푸는 알고리즘을 너비 우선 탐색이라고 합니다. 그래프란 무엇인가 ? 그래프란 연결의 집합을 모형화 한것이다. 그래프는 정점과 간선으로 이루어집니다 정점은 여러개의 다른 정점과 바로 이어질수 있습니다. 이렇게 바로 이어진 정점을 이웃이라고 합니다. 너비 우선 탐색은 그래프를 대상으로 하는 다른 종류의 탐색 알고리즘 입니다. 너비 우선 탐색은 다음과..
1부터 100까지 임의의 숫자를 생각한다음 그 생각한 숫자를 맞추는 게임을 해보자! 술게임할때 업다운이 생각난다 ㅎㅎ 1부터 100까지 계속 올라가면서 맞출라고 하면 친구들한테 뺨을 맞거나 분위기를 곱창내며 벌주를 졸라 마실것이다 그래서 끊어서 맞추기로 했다 대충 50? 이라고 했는데 업! 이러길래 그럼 67? 이랬는데 다운이라고 한다 음.. 그럼 60? 이랬는데 다운이라고 한다 마지막 기회 55라고 했는데 맞췄다 그래서 술게임 한사람이 술마심 ㄱㅇㄷ 이렇게 크게크게 답을 맞춰나가는걸 이진탐색이라고 책에서 알려준다 로그를 잘 알아둬야 한다길래 까먹을거 같아서 남겨본다 log10 의 100은 몇일까 ? 답은 2다 ㅅㅂ 왜 2인지 이해가 안됐는데 100이 될라면 10을 두번곱해야하니까 답이 2라고 한다 수학..