오늘부터 시작합니둥 ~~~~ stepania99
[Algorithm] 백트래킹(Backtracking) 알고리즘
🌵백트래킹 알고리즘이란? 모든 경우의 수를 전부 고려하는 알고리즘이다. 일종의 트리 탐색 알고리즘이라고 봐도 된다. 방식에 따라서 깊이우선탐색(Depth First Search, DFS)과 너비우선탐색(Breadth First Search, BFS), 최선 우선 탐색(Best First Search/HeuristicSearch)이 있다. 즉, 백트래킹은 현재 상태에서 가능한 모든 후보군을 따라 들어가며 해결책에 대한 후보를 구축해 나아가다 가능성이 없다가 판단되면 즉시 후보를 포기하면서 정답을 찾아가는 범용적인 알고리즘이다. DFS의 비효율적인 경로를 차단하고 목표지점에 갈 수 있는 가능성이 있는 루트를 검사하는 방법이 백트래킹 알고리즘이다. 백트래킹은 가지치기(Purning)을 통해 효율을 극대화한다...
[Algorithm] 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) 알고리즘
🌵깊이 우선 탐색 DFS (Depth First Search) 란? 탐색(Search)이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 그 중 DFS는 깊이 우선 탐색이라고 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 즉, 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사 넓게(wide) 탐색하기 전에 깊게(deep) 탐색 모든 노드를 방문 하고자 하는 경우 사용 너비 우선 탐색(BFS)보다 간단하다 단순 검색 속도는 너비 우..
[자료구조] 우선순위 큐(Priority Queue), 힙(Heap)
🌵우선순위 큐(Priority Queue) 란? 큐(Queue)는 먼저 들어오는 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조 우선순위 큐(Priority Queue)는 들어온 순서와 상관없이, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조 일반적으로 힙(Heap) 구조를 사용해 구현한다. * 힙으로 구현하는 이유는? - 힙의 경우 삭제나 삽입 과정에서 모두 부모와 자식 간의 비교만 계속 이루어진다. 이진 트리의 높이가 하나 증가할 때마다 저장 가능한 자료의 개수는 2배 증가하며, 비교 연산 횟수는 1회 증가 즉, 삭제나 삽입 모두 최악의 경우에는 O(log2n)의 시간 복잡도를 가진다. 이처럼 배열이나 연결 리스트가 삭제에서는 시간 복잡도의 우위를 점할지라도,..
[자료구조] 스택(Stack), 큐(Queue), 덱(Deque)
🌵스택(Stack) 구조란? 스택(Stack)은 ‘쌓다’라는 의미로, 데이터를 차곡차곡 쌓아 올린 형태의 자료구조이다. 즉, 데이터가 들어온 순서대로 쌓이며 가장 마지막에 삽입된 자료가 가장 먼저 나오게되는 구조이다. LIFO (Last In First Out) 🌵특징 및 장단점 스택(Stack)은 정해진 방향으로만 쌓을 수 있으며, 새로 삽입된 자료는 stack.push를 사용해 스택의 top에 쌓일 수 있다. 삭제 연산은 stack.pop을 통해 이루어지며, top위치의 자료가 삭제된다. top 위치의 데이터에 바로 접근이 가능하기 때문에 데이터 삽입, 삭제의 시간 복잡도는 O(1) 장점 top 을 통해 접근하기 때문에 데이터 접근, 삽입, 삭제가 빠르다. 단점 top 위치 이외의 데이터에 접근할 수..
[Algorithm] 재귀함수(Recursive Function) , 재귀 알고리즘
🌵 관련 문제 🥈[백준 알고리즘 17478번 : 재귀함수가 뭔가요?] https://www.acmicpc.net/problem/17478 17478번: 재귀함수가 뭔가요? 평소에 질문을 잘 받아주기로 유명한 중앙대학교의 JH 교수님은 학생들로부터 재귀함수가 무엇인지에 대하여 많은 질문을 받아왔다. 매번 질문을 잘 받아주셨던 JH 교수님이지만 그는 중앙대 www.acmicpc.net [SOLUTION] https://gyurisinzorba.tistory.com/33 [Python] 백준 알고리즘 17478번 : 재귀함수가 뭔가요? https://www.acmicpc.net/problem/17478 17478번: 재귀함수가 뭔가요? 평소에 질문을 잘 받아주기로 유명한 중앙대학교의 JH 교수님은 학생들로부터..