깊이 우선 탐색 ( Depth-First Search )루트 노드에서 시작해 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 특징1. 모든 노드를 방문하고자 하는 경우에 사용한다.2. 단순 검색 속도는 너비 우선 탐색(BFS)에 비해 느리다.3. 검색이 아닌 순회를 할 경우 많이 사용한다.공통 상위를 가지는 아래 리프 노드들을 한방에 잘라내는게 가능하기 때문에 백트래킹에 사용된다.미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다.  장점1. 현 경로상의 노드들만 기억하면 되기 때문에 저장 공간의 수요가 비교적 적다.2. 목표 노드가 깊은 단계에 있을 ..

너비 우선 탐색 ( Breadth-first search )트리나 그래프를 방문 또는 탐색하는 방법으로 루트 노드에서 시작해서 인접 노드를 먼저 탐색하는 방법.   탐색 방법1. 루트노드에서 시작한다.  2. 자식노드들을 저장한다.  3. 저장되어있는 노드를 방문하며 저장되어있는 노드들의 자식들을 저장하며  4. 위의 과정을 모든 노드를 방문할 때 까지 반복하며 완료 시 탐색을 종료한다.   특징1. 어떤 노드를 방문했는지 반드시 검사 해야 한다.2. Queue를 사용하는 경우가 일반적이며 재귀적으로 동작하지 않는다.3. Prim, Dijkstra알고리즘과 유사하다.  장점1. 노드의 수가 적고 깊이가 얕은 경우 빠르게 동작할 수 있다.2. 단순 검색 속도가 깊이 우선 탐색(DFS)보다 빠르다.3. 너비..

트리구조란? 한 노드에서 시작해서 다른 정점들을 순회하여 자기 자신에게 돌아오는 순환이 없는 연결그래프이다. 회사의 조직도 내 컴퓨터\C:\Program Files\..... 트리 용어 용어 설명 루트(root) 노드 맨 위에 위치한 노드이며, 부모노드 라고 함 리프(leaf) 노드 자식이 없는 최하단 노드, 단말(terminal) 노드 라고도 함 내부(internal) 노드 리프노드가 아닌 노드, 가지(branch) 노드 라고도 함 간선/엣지/링크/브랜치 노드들끼리의 연결선 노드의 차수 한 노드가 가진 서브트리의 차수 트리의 차수 트리노드들의 차수 중 최대차수 서브트리(sub-tree) 트리에서 어떤 한 노드와 그 노드의 자손들로 이루어진 트리 레벨(level) 0이나 1부터 시작하며 높이를 정의함 높..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해당 문제는 프로그래머스에서 탐욕법(Greedy) 카테고리 안에 있는 문제이다. 탐욕 알고리즘은 정리해 두었던 내용이다 ( 링크 ) 문제 풀이 아직 익숙치않은 Comparator 인터페이스로 이중배열인 costs의 값을 cost순으로 오름차순 했다는 것 정도다 Comparator의 사용법은 간단히 정리 해 두었다 ( 링크 ) 알고리즘 활용에 미숙해서인지 모르겠지만 내 생각엔 탐욕법이나 기타 알고리즘들을 사용해서 푼 것 같지는 않다 물론 이게 어떤 알고리즘이라고 한다면 공부를 더 깊게 해야 할 것 같다 1. 섬..

탐욕법(Greedy Algorithm)※ Greedy : 탐욕스러운, 욕심 많은...탐욕 알고리즘 : 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법최적해를 구하는 데에 사용되는 근사적인 방법이다.여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달하지만 그것이 최적이라는 보장은 없다.탐욕 알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들이다.     탐욕 알고리즘 문제를 해결하는 방법선택 절차(Selection Procedure) : 현재 상태에서의 최적의 해답을 선택한다.적절성 검사(Feasibility Check) : 선택된 값이 문제의 조건을 만족하는..

문제 설명 n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다. 선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요. 제한사항 선수의 수는 1명 이상 100명 이하입니다. 경기 결과는 1개 이상 4,500개 이하입니다. results 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의..