알고리즘

[오늘의 코테연습장] - 백준 5052 번

트라이 - 문자열을 빠르게 검색할 수 있는 자료 구조 - 트라이의 Root노드는 항상 빈 문자열 상태 단어 사전을 트라이에 insert 후, 트라이를 사용하여 검색 트라이 구축하기 트라이 노드 설계 class Node { boolean isfinish = false; TrieNode[] chlid = new TrieNode[10]; } void insert 함수 단어 사전의 입력할 단어를 트라이에 삽입 root 노드부터 시작해서 단어의 첫글자 부터 탐색 현재 노드의 자식이 null 일 경우 : 새로운 child를 추가 현재 노드의 자식이 있을 경우 : 현재 노드를 해당하는 자식 노드로 이용한다. 단어를 삽입한 후, 탐색된 마지막 노드에 현재 입력된 단어의 정보를 추가한다. static void inser..

[알고리즘] - Graph Algorithms

Graphs의 기본 - Graph : 쌍들의 집합, 쌍을 이루는 원소 사이의 관계 (두 개의 객체를 묶어 놓으면 관계가 생겨) - Graoh의 구성 요소 : (V,E) / V : vertex, 정점 들의 집합 / E : edge , 간선 들의 집합 - Dirextex : 방향 그래프 -undirexted graphp: 방향이 없는 무향 그래프 - simple graph : loop 혹은 mutiplae edge(같은 하나의 정점에 두개 이상의 간선이 존재하는 경우) 가 없다 - Neighbor : 이웃, - Degree : vertex에 달려있는 간선들의 갯수(정점에 달려잇는 이웃들의 개수) (차수) - Subgraph : 부분 그래프, 주어진 그래프 G에서 vertex와 간선들의 부분집합을 꺼내와서 만..

[알고리즘] - Greedy 알고리즘

-본 내용은 학교 수업을 바탕으로 제가 이해한 것을 정리한 거여서 약간의 오류가 있을 수 도 있습니다 GREEDY Algorithm에 대해 선택지가 여러 개있을 때, 그걸 다 꼼꼼히 보는 게 아니라 좋은 것같아 보이는 것을 선택한다. 전체를 보는 것이 아니라 주변을 보고 선택 이게 무슨 말인가 그건 이제 차차 살펴보도록 하자 문제하나를 예시를 들겟다. 더보기 Coin Change Problem - input : 0이상의 정수 k - output : K를 만들 수 있는 최소 동전 갯수 ● 대부분의 나라에서 통하는 알고리즘 1. k=0이면 그만한다. 2. K>0이면, K보다 작은 동전 중 가장 액면가가 큰 것을 선택 3. 그 액면가를 c라고 하면, k 그래서 이런 방법이 제대로 동작될리가 없는데 가끔 되는 ..