CS 지식/자료구조 (2) 썸네일형 리스트형 알고리즘 - DFS(깊이) BFS(너비) 우선탐색 DFS / BFS 개념 설명 그래프 탐색 알고리즘 여기서 말하는 그래프는 여러 개체들이 연결되어 있는 자료구조를 의미하고 이 개체들 중에서 특정 개체를 찾기 위한 알고리즘을 탐색 이라고 한다 대표적인 문제 유형 경로탐색 유형 : 최단거리, 시간 네트워크 유형 : 연결 조합 유형 : 모든 조합 만들기 EX. 프로그래머스 - 타겟 넘버, 네트워크, 단어 변환, 여행경로 등의 문제를 보고 위와 같은 문제 유형이구나를 인지할 줄 알아야 함 DFS / BFS 구현 방법 DFS : 한 놈만 패는 구현 방식이기 때문에, 재귀함수가 가장 일반적인 구현 방법 재귀를 타고, 타고, 타서 탈출 조건에 먼저 도달하고 그 다음 파라미터를 하나씩 바꿔가며 정답을 찾는 방식으로 구현 동작 검증이 쉬운 편 예시 타겟 넘버 BFS :.. [자료구조] Priority Queue / 우선순위 큐 Priority Queue 우선순위 큐 #자료구조 설명 : Priority Queue는 말 그대로 우선순위 큐로써, 일반적인 선입선출과는 다른 개념이다. 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조이다. 우선순위 큐는 데이터를 우선순위에 따라, 처리하고 싶을 때 사용하는 자료구조 예시) 물건 데이터를 자료구조에 넣었다가, 가치가 높은 물건부터 꺼내서 확인해야 하는 경우 자료구조 추출되는 데이터 스택 가장 나중에 삽입된 데이터 큐 가장 먼저 삽입된 데이터 우선순위 큐 가장 우선순위가 높은 데이터 그런데 그 우선순위를 어떻게 정함?...누구 맘대로... 구현 방법 : 첫번째 방법. 단순하게 리스트를 이용하여 구현 가능 두번째 방법. 힙을 이용하여 구현 가능 - 데이터 개수가 N개.. 이전 1 다음
