Heap이란? 완전 이진 트리에 있는 노드 중 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해 만든 자료구조 우선순위 큐를 위해 고안된 완전 이진 트리 형태의 자료구조 이진탐색트리(BST)와 달리 중복된 값이 허용된다. 최대 힙(Max Heap) 부모 노드의 키값이 자식 노드의 키값보다 항상 크거나 같은 크기의 관계이다. 완전 이진 트리이다. 최대 힙에서는 키값이 가장 큰 노드가 루트 노드가 된다. 최소 힙(Min Heap) 부모 노드의 키값이 자식 노드의 키값보다 항상 작거나 같은 크기의 관계이다. 완전 이진 트리이다. 최소 힙에서는 키값이 가장 작은 노드가 루트 노드가 된다. 완전 이진 트리(Complete Binary Tree)란? 노드를 삽입할 때, 왼쪽부터 차례대로 삽입하는 트리이..

소수(Prime Number)란? 2보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어떨어지지 않는 자연수 예를 들어 '6'은 1,2,3,6으로 나누어 떨어져서 소수가 아니고 '7'은 1과 7을 제외하고는 나누어 떨어지지 않아서 소수이다.(소수 3, 5, 7, 11, 13..) 코드로 보면 def is_prime_number(x): # 2부터 (x - 1)까지의 모든 수를 확인하며 for i in range(2, x): # x가 해당 수로 나누어떨어진다면 if x % i == 0: return False # 소수 아님 return True 알고리즘 개선 예를 들어 16이라는 수의 약수는 1 X 16 = 16 2 X 8 = 16 4 X 4 = 16 8 X 2 = 16 16 X 1 = 16 가..

백트래킹이란? "퇴각 검색"이라고도 하며 한정조건을 가진 문제를 푸는 전략이다. 즉, 모든 경우의 수를 시도하여 정답을 찾는 것이 아닌, 한정 조건에서의 모든 경우의 수를 시도하기 때문에 상당한 경우의 수들이 배제된다. 따라서 다중 for문 보다 빠르고 해결되는 경우가 많다. 해를 찾는 도중에 막히면 더 깊이 들어가지 않고, 이전 단계로 되돌아가서 해를 찾아나가는 기법이다. 백트래킹의 구현 보통 백트래킹의 구현은 BFS나 DFS와 함께 구현한다. 모든 경우의 수에서 한정 조건을 만족하는 경우를 탐색하기 떄문에 완전 탐색 기법인 BFS/DFS가 모두 구현이 가능하다. But. 백트래킹의 특성에서 한정 조건에 부합하지 않으면 이전 수행으로 돌아와야하기 때문에 DFS에서의 구현이 더 편하다. 주로 문제풀이에서..

완전탐색, 브루트 포스란? 사전적 의미로 브루트(Brute) : 무식한 + 포스(Force) : 힘 발생할 수 있는 모든 경우의 수를 무식하게 탐색한다는 뜻이다. 브루트 포스의 장점 알고리즘을 설계하고 구현하기 매우 쉽다. 복잡한 알고리즘 없이 빠르게 구현할 수 있다. 브루트 포스의 단점 알고리즘 실행시간이 매우 오래 걸린다. 메모리 효율이 매우 비효율적이다. 브루트 포스의 종류 브루트 포스는 크게 선형 구조와 비선형 구조로 나뉜다. 선형 구조 : 순차 탐색 비선형 구조 : 백트래킹, DFS, BFS

🍃 기타 그래프 알고리즘 : 배운 내용을 알아보자 노드와 노드 사이에 연결된 간선의 정보를 가지고 있는 자료구조 DFS/DFS와 최단경로도 그래프 알고리즘의 한 유형이라고 볼 수 있다. 그래프 자료구조 중에서 트리 자료구조는 다양한 알고리즘에서 사용되므로 꼭 기억해야 한다. 그래프 트리 방향성 방향 그래프 혹은 무방향 그래프 방향 그래프 순환성 순환 및 비순환 비순환 루트 노드 존재 여부 루트 노드가 없음 루트 노드가 존재 노드간 관계성 부모와 자식 관계 없음 부모와 자식 관계 모델의 종류 네트워크 모델 계층 모델 그래프 구현 방식 인접 행렬: 2차원 배열을 사용하는 방식 - 간선 정보 저장 : O(v²), 특정 노드에서 특정 노드로 이어진 간선 비용 : O(1) 인접 리스트: 리스트를 사용하는 방식 -..

🍃 최단경로(Shortest Path) 알고리즘 최단 경로 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 이는 길 찾기 문제라고도 불린다. 최단 경로 유형에는 다양한 종류가 있는데, 상황에 맞는 효율적인 알고리즘이 이미 정립되어 있다 최단 경로 문제는 보통 그래프를 이용해 표현하는데 각 지점은 그래프에서 "노드"로 표현되고, 지점간 연결된 도로는 그래프에서 "간선"으로 표현된다. 실제 코딩 테스트에서는 최단 경로를 모두 출력하는 문제보다는 단순히 최단 거리를 출력하도록 요구하는 문제가 많이 출제된다. 다익스트라 최단 경로 알고리즘, 플로이드 워셜, 벨만 포드 알고리즘이 학부 수준의 알고리즘인데 이 세개 중 코딩테스트에서는 다익스트라 최단경로와 플로이드 워셜이 가장 많이 출제된다. 그리디 알고..