개발과 잡지식

탐색 알고리즘 - 1 DAG 난이도 별 3개? 탐색 알고리즘 -0 선행 개념 에서 DAG에 대한 개념을 설명 했다. 여기서 다시 요약해서 말하자면 DAG은 tree를 포함하는 개념으로 위상이라는 다시 말해 순서가 있는 그래프 이다. DAG에 관한 문제를 풀어보며 어떤 특이 점이 DAG이라고 하는지 확인 해보자. 문제 풀이 문제 : https://www.acmicpc.net/problem/2623 문제 설명 문제의 예를 문제에 적용해서 설명 하자면 1->4->3, 6->2->5->4, 2->3 처럼 순서가 정해져 있을 때 어떤 순서 규칙도 깨지 않고 이를 일렬로 정렬 가능 하냐는 문제이다. 전 포스트 글을 빌려 설명을 하자면 각 노드(1~6)들에 대해서 부모의 개수와 내가 가리키는 자식을 가리키도록 하는 ..

탐색 알고리즘 - 0 선행 개념 define 탐색 알고리즘 이라면 무엇을 탐색 하려는 걸까? 그래프 혹은 트리 이다. 어떤 상황에서 쓰고 싶은지에 따라서 다르겠지만 둘다 사용 가능하다. 그래프와 트리는 컴퓨터 전공인 이라면 한번쯤은 봤을 단어 들이다. 이는 많은 사람들의 동의 할 것 같다. 그렇다면 지금 바로 트리와 그래프의 차이가 무엇인지 말해 달라고 하면 말 해 줄 수 있나요? 없다면 다시 한번 짚고 가던지 검색 해보시는 걸 추천 합니다. DAG이라고 떠오른 분들은 이번 글은 생략 하셔도 좋을 것 같습니다. 그래프 출처 : https://ko.wikipedia.org/wiki/%EA%B7%B8%EB%9E%98%ED%94%84_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0) 그래..