Algorithm/파이썬 코딩테스트

DFS(깊이우선탐색)기초 -4. 바둑이 승차

나의 풀이 강의 풀이

DFS(깊이우선탐색)기초 -3. 합이 같은 부분집합

나의 풀이 강의 풀이

DFS(깊이우선탐색)기초 - 2. 부분집합 구하기

DFS(깊이우선탐색)기초 - 1. 이진트리 순회(깊이우선탐색)

이진 트리(Binary Tree)를 탐색하는 방법에는 크게 다음의 4가지가 있다. 전위순회(Preorder Traversal) 중위순회(Inorder Traversal) 후위순회(Postorder Traversal) 레벨순회(Levelorder Traversal) 또는 BFS(Breadth-First Search; 너비 우선 탐색) 레벨순회(;BFS)를 제외한 나머지 순회방식은 DFS(Depth-First Search; 깊이 우선 탐색)으로 분류할 수 있다. 전위순회(preorder traversal) 전위순회는 루트 노드를 먼저 탐색하고, 자식 노드를 탐색 부모-왼쪽-오른쪽 중위순회(inorder traversal) 중위순회는 왼쪽 자식 노드를 탐색하고 , 루트 노드를 탐색하고 , 오른쪽 자식 노드를 ..

DFS(깊이우선탐색)기초 - 1. 재귀함수를 이용한 이진수 출력

나의 풀이 강의 풀이

DFS(깊이우선탐색)기초 - 0. [선수지식] 재귀함수와 스택

재귀함수 자기 자신을 호출하는 함수 재귀함수 작동할때 스택 자료구조를 사용 반복문의 효과를 낼 수 있다 (반복문의 대체, 3중4중 for문 ) 출력 후 재귀함수 호출 재귀함수 호출 후 출력 1을 반환하며 이전에 return 하였던 값들을 곱한 뒤 다시 반환해가는 과정을 거칩니다 https://m.blog.naver.com/jsky10503/221248164066 재귀(Recursion)호출로 알아보는 알고리즘기초 함수 내에서 자기자신의 함수를 다시 호출하는 방법을 재귀호출이라고 합니다. Recursion이라고도 많이 알... blog.naver.com

자료구조 활용 (힙) - 11. 최대힙

나의 풀이 최대힙 heapq에서는 최대 힙을 제공하지 않는다. 따라서 다음과 같이 부호를 변경하는 방법을 사용해서 최대 힙을 구현한다. 부호를 바꿔서 최소 힙에 넣어준 뒤에 최솟값부터 pop을 해줄 때 다시 부호를 바꿔주면 최대 힙과 동일하다. import heapq heap = [] values = [1,5,3,2,4] # 아래 for문을 실행시키고 나면 heap은 [-5,-4,-3,-1,-2]가 된다. for value in values: heapq.heappush(heap, -value) # 아래 for문을 실행시키면 5,4,3,2,1이 출력된다. 즉, 큰 숫자부터 출력이 된다. for i in range(5): print(-heapq.heappop(heap))

자료구조 활용 (힙) - 10. 최소힙

나의 풀이 최소 힙: 부모 노드의 키값이 자식 노드의 키값보다 항상 작은 힙 최대 힙: 부모 노드의 키값이 자식 노드의 키값보다 항상 큰 힙 힙 생성 & 원소 추가 import heapq heap = [] heapq.heappush(heap, 50) 이미 생성해둔 리스트가 있다면 heapify 함수를 통해 즉각적으로 힙 자료형으로 변환할 수 있다. heap2 = [50 ,10, 20] heapq.heapify(heap2) 힙에서 원소 삭제 heappop 함수는 가장 작은 원소를 힙에서 제거함과 동시에 그를 결괏값으로 리턴한다. result = heapq.heappop(heap) print(result) https://littlefoxdiary.tistory.com/m/3 [Python] 힙 자료구조 / ..