[Algorithm - DFS/BFS] 그래프와 깊이/너비 우선 탐색 (Programmers - 여행경로)

1. 그래프 정점(vertex, node)과 간선(edge, link) 유향(directed)그래프와 무향(undirected)그래프 스택과 큐로 구현 가능 2. 깊이 우선 탐색 (DFS; Depth-First Serach) 한 정점에서 인접한 모든(아직 방문하지 않은) 정점을 방문하되, 각 인접 정점을 기준으로 깊이 우선 탐색을 끝낸 후 다음 정점으로 진행 순서가 정해져있진 않으나 일반적으로 가장 좌측에서 아래로 깊이 우선 탐색 진행 무향 그래프 예시 (0 > 1 > 3 > 7 > 4 > 5 > 2 >6) 스택을 이용하여 어느 정점에서 DFS를 하고 있는지를 기억하고 되돌아감 3. 너비 우선 탐색(BFS; Breadth-First Search) 한 정점에서 인접한 모든(아직 방문하지 않은) 정점을 방문..

• format_list_bulleted ETC/Algorithm
• · 2022. 6. 22.
• textsms

[Algorithm - DP] Dynamic Programming 이란 (Programmers - N으로 표현)

1. 동적계획법 (Dynamic Programming)문제에 답인지를 확인하기 위해 탐색해야하는 범위를 동적으로 결정하면서 탐색 범위를 한정할 수 있음(탐색범위가 굉장히 넓은 문제에서 범위를 조금 씩 좁혀가며 해를 찾을 수 있음)주어진 최적화 문제를 재귀적인 방식을 이용해 작은 부문으로 나누고 해를 조합해 전체 문제의 해답에 이르는 방식임 2. DP의 적용 예 - 피보나치 수열피보나치 수열 : 직전 두 열의 항이 해당열의 값이 되는 수열f(4)를 구하기 위해 재귀함수로 구현할 경우 복잡도는 지수함수의 형태로 엄청나게 증가한다.동적계획법으로 구현 시 부분문제에 대한 답을 구해놓고 그 답을 이용해서 큰 문제를 풀어가면서 해를 찾아간다.복잡도는 선형함수의 형태로 나타나게 된다. 3. Programmers - ..

• format_list_bulleted ETC/Algorithm
• · 2022. 6. 21.
• textsms

[Algorithm - Heap] Heap에 대해서 (Programmers - 더 맵게)

heap 최소/ 최대 원소를 빠르게 찾을 수 있도록 만들어진 자료구조 완전 이진트리(complete binary tree)로 구성됨 큐에 우선순위 개념을 도입한 우선순위 큐구조를 사용하며 우선순위가 높은 데이터가 먼저 나간다. Python heapq의연산종류와 시간복잡도 힙 구성 (heapify) - O(NlogN) 삽입 (heappush) - O(logN) 삭제 (heappop) - O(logN) Programmers heap 문제 - 더 맵게 https://programmers.co.kr/learn/courses/30/lessons/42626 import heapq def solution(scoville, K): answer = 0 heapq.heapify(scoville) for i in range..

• format_list_bulleted ETC/Algorithm
• · 2022. 6. 21.
• textsms