그래프
-
백준 2668 숫자고르기Algorithm/BOJ 2021. 6. 4. 23:05
출처: https://www.acmicpc.net/problem/2668 분류: 그래프, dfs 접근방식 1~n 까지에 각각 숫자가 매겨져 있을 때, 매겨진 숫자와 자신의 숫자의 집합이 같아지도록 최대한 많이 뽑아내는 문제입니다. 1~n을 노드 자신의 인덱스로, 매겨진 숫자를 다음 노드를 가리키는 그래프로 생각해보면, 결국 자기 자신으로 돌아오는 사이클이 아니면 절대 같은 집합이 될 수 없다는 걸 알 수 있습니다. 이렇게 각 사이클들을 더해주면 끝입니다 :) 전체 defaultVisit과 방문하면서 체크할 visit 배열을 만들어두고 탐색해서 사이클이 생겼다면 해당 visit을 defaultVisit으로 업데이트 시켜주는 방식으로 구현했습니다. for i in 0.. 0 { defaultVisit = v..
-
TreeComputer Science/DataStructure 2021. 1. 14. 18:00
- 객체간의 계층적인 관계를 나타낸다 - 빠르고 효율적으로 탐색할 수 있다 - 데이터의 정렬된 형태를 보여준다 - 사이클이 없는 그래프 - 텍스트의 prefix 매칭을 빠르게 할 수 있다. ex) - 회사나 정부의 조직 구조 - 나라, 지방, 시•군별 등 계층적인 데이터 - 인덱스 오늘은 기본적이지만 아주 중요한 Tree에 대해 알아보겠습니다. Tree 자체보다도 여기서 파생된 트리들이 더 중요하지만 그래도 기본부터 정리해보려고 해요 :) 자료구조란 데이터들을 잘 관리하게 생겨났을텐데요, 트리는 왜, 언제 필요할까요? 트리는 계층적인 관계를 나타내기 위해 사용합니다. 계층 관계는 우리 일상 생활과 아주 많이 밀접해있습니다. 먼저 우리 가족의 관계도를 그려본다고 생각해봅시다. 부모님 형제 자매가 있고, 다..