본문 바로가기
반응형

전체 글70

그리디 알고리즘 (Greedy Algorithm) 그리디 알고리즘은 최적의 해를 구하기 위해 각 단계에서 가장 좋다고 생각되는 선택을 하는 알고리즘입니다. 이 방법은 문제를 해결하는 과정에서 부분적으로 최적의 선택을 반복하여 전체적으로 최적의 해답에 도달하려고 합니다.1. 그리디 알고리즘의 개념그리디 알고리즘은 다음 두 가지 속성을 만족하는 경우에만 올바른 결과를 도출할 수 있습니다:1.1 그리디 선택 속성 (Greedy Choice Property)정의: 각 단계에서의 선택이 전체 문제에 대한 최적의 해를 보장해야 합니다.설명: 현재 단계에서 최선이라고 판단되는 선택을 했을 때, 이 선택이 이후의 결정에 영향을 미치지 않고 최적의 결과를 이끌어낼 수 있어야 합니다.예시: 거스름돈 문제에서 가장 큰 단위의 동전을 먼저 선택하는 방식은 최적의 해를 보장합.. 2024. 12. 19.
DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색) 알고리즘 비교(차이점, 장단점, 예시코드, 활용도) 2024.12.19 - [알고리즘] - DFS (깊이 우선 탐색, Depth-First Search) 알고리즘 - C언어, Java, Python 예시코드, 시간복잡도 DFS (깊이 우선 탐색, Depth-First Search) 알고리즘 - C언어, Java, Python 예시코드, 시간복잡도DFS(Depth-First Search)는 그래프나 트리에서 널리 사용되는 탐색 알고리즘으로, 시작 정점에서 한 경로를 끝까지 탐색한 후에 다른 경로로 이동하는 방식으로 동작합니다. 모든 경로를 탐색하거나best-coding.tistory.com2024.12.19 - [알고리즘] - BFS(너비 우선 탐색, Breadth-First Search) 알고리즘 - C언어, Java, Python 예시코드 포함, 시간복.. 2024. 12. 19.
DFS (깊이 우선 탐색, Depth-First Search) 알고리즘 - C언어, Java, Python 예시코드, 시간복잡도 DFS(Depth-First Search)는 그래프나 트리에서 널리 사용되는 탐색 알고리즘으로, 시작 정점에서 한 경로를 끝까지 탐색한 후에 다른 경로로 이동하는 방식으로 동작합니다. 모든 경로를 탐색하거나 특정 경로를 찾는 데 유용하며, 다양한 문제 해결에 활용됩니다.1. DFS의 개념DFS는 스택(Stack) 자료구조를 기반으로 하거나 재귀를 사용하여 구현되며, 그래프의 한 경로를 깊게 탐색한 후, 더 이상 탐색할 노드가 없을 때 이전 경로로 되돌아갑니다. 이를 "백트래킹(Backtracking)"이라고 합니다.(일반적으로 코딩테스트 문제 풀이 시 재귀로 dfs를 구현합니다.) 2. DFS의 동작 원리시작 정점을 방문하고 스택 또는 재귀 호출을 통해 탐색합니다.현재 정점의 인접 정점 중 방문하지 않은.. 2024. 12. 19.
BFS(너비 우선 탐색, Breadth-First Search) 알고리즘 - C언어, Java, Python 예시코드 포함, 시간복잡도 BFS(Breadth-First Search)는 그래프나 트리에서 널리 사용되는 탐색 알고리즘으로, 시작 정점에서 가까운 노드부터 탐색을 진행합니다. 경로를 찾거나 최단 거리를 계산하는 데 유용하며, 다양한 문제 해결에 활용됩니다. 1. BFS의 개념BFS는 큐(Queue) 자료구조를 기반으로 작동하며, 그래프의 각 레벨을 순차적으로 탐색합니다. 그래프의 각 정점을 방문하면서 모든 인접한 정점을 차례대로 탐색하므로, 깊이보다는 너비를 우선시합니다. 2. BFS의 동작 원리시작 정점을 큐에 삽입하고 방문 처리합니다.큐에서 정점을 하나씩 꺼내어 해당 정점의 모든 인접 정점을 탐색합니다.인접 정점 중 방문하지 않은 정점을 큐에 삽입하고 방문 처리합니다.큐가 빌 때까지 위 과정을 반복합니다.동작 구조도다음은 B.. 2024. 12. 19.
해시(Hash) 자료구조(C언어,STL, Java, Python 예시코드 포함) 해시 자료구조(Hash Data Structure)는 데이터 검색, 삽입, 삭제 작업을 빠르게 수행할 수 있는 매우 효율적인 자료구조입니다. 많은 프로그램과 애플리케이션에서 사용되며, 특히 키-값(key-value) 쌍 데이터를 저장하고 빠르게 접근해야 하는 경우에 유용합니다. 또한 값 추가, 삭제, 조회의 시간복잡도가 O(1)이라서 코딩테스트 문제에도 많이 활용되고 있습니다.1. 해시의 개념해시는 키(key)와 값(value)의 쌍으로 데이터를 저장합니다. 각 키는 고유하며, 해시 함수(hash function)를 사용하여 특정 키가 저장될 위치를 결정합니다. 이 과정은 다음과 같습니다:키를 입력값으로 해시 함수를 호출됩니다.해시 함수는 키를 고유한 해시 값(hash value)으로 변환합니다.이 해시.. 2024. 12. 19.
반응형

티스토리툴바