개발/Python 알고리즘 공부16 [알고리즘] DFS/BFS 알고리즘 (그래프 탐색 알고리즘) * 그래프 탐색 알고리즘 (DFS/BFS) - 탐색 : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 -> DFS / BFS * DFS (Depth-First-Search) : 깊이 우선 탐색 -> 깊은 부분을 우선적으로 탐색하는 알고리즘 **** 스택 자료구조(혹은 재귀 함수)를 이용 **** 1. 탐색 시작 노드를 스택에 삽입하고 방문 처리 2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리 3. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다 4. 더 이상 2번,3번의 과정을 수행할 수 없을 때까지 반복 - 전체 노드의 탐색 순서 = 스택에 들어간 순서 [DFS 소스코드 예제] def dfs(graph, v, visited).. 2022. 11. 19. [알고리즘] 기본 문법 - 스택 & 큐 (Stack & Queue) *Stack : 먼저 들어온 데이터가 나중에 나가는 형식 (선입 후출) - 입구와 출구가 동일한 형태로 스택을 시각화할 수 있다. ex. 박스 쌓기 1. 삽입 - append() 2. 삭제 - pop() [스택 구현 예시] stack = [] stack.append(5) #가장 먼저 들어가는 원소 stack.append(2) stack.append(3) stack.append(7) stack.pop() stack.append(1) stack.append(4) stack.pop() print(stack[::-1]) #스택의 최상단 원소부터 출력 print(stack) #스택의 최하단 원소부터 출력 >>> [1,3,2,5] [5,2,3,1] *Queue : 먼저 들어온 데이터가 먼저 나가는 형식 (선입선출).. 2022. 11. 19. [알고리즘] 구현(Implementation) 알고리즘(시뮬레이션과 완전 탐색) *구현(Implementation) 알고리즘(시뮬레이션과 완전 탐색) : 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정 -> 아무리 알고리즘을 잘 세워도 실제로 구현할 수 있는 것이 더 중요하다! *풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제 - 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제 - 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제 - 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제 - 적절한 라이브러리를 찾아서 사용해야 하는 문제 *일반적으로 알고리즘 문제에서의 2차원 공간은 행렬을 의미로 사용된다. (=2차원 리스트) for i in range(n): for j in range(m): * 시뮬레이션 및 완전 탐색 문제에서는 2차원 공간에서의 방향.. 2022. 11. 19. [알고리즘] Greedy Algorithm(그리디 알고리즘) *Greedy Algorithm(그리디 알고리즘) : 일명 탐욕법. 현재 상황에서 지금 당장 좋은 것만 고르는 방법 최소한의 아이디어를 떠올릴 수 있어야 문제를 풀 수 있다. -> 정당성 분석이 가장 중요! * 상당수의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해라는 것을 추론할 수 있어야 풀리도록 출제! [대표 문제 1] 거스름 돈 : 최적의 해를 빠르게 구하기 위해서는 가장 큰 화폐 단위부터 돈을 거슬러 주면 된다. -> 가장 적은 양의 동전을 거슬러 주는 최적의 해 => 이것이 최적의 해라는 근거(정당성)? : 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문! -> 그렇지 않다면 가장 큰 화폐 단위부터 거슬러 주는 것이 최.. 2022. 11. 15. 이전 1 2 3 4 다음