본문 바로가기
반응형

Algorithm/알고리즘 이론 | Algorithm6

[알고리즘/Algorithm] 깊이 우선 탐색 - DFS / BOJ 2606 바이러스 안녕하세요!드디어 그래프 이론을 활용한 알고리즘 공부를 하고 있습니다.이론을 정리하고 문제 푸는 게 재미있지만 시간이 좀 걸리는 작업이기는 하네요 ㅎㅎ제가 한창 알고리즘 공부할 때 정말 재미있게 배웠던 그래프 알고리즘 중,가장 많이 활용되고 기본적으로 쓰이는 탐색 알고리즘을 공부해보겠습니다 :)이번에는 DFS 알고리즘을 정리해보려고 합니다~DFS의 정의 (깊이 우선 탐색)🔹 깊이 우선 탐색/DFS(Depth-First-Search) 란?: 그래프 또는 트리에서 한 정점에서 시작하여, 한 방향으로 갈 수 있는 곳 까지 끝까지 깊이 탐색한 후,더 이상 갈 곳이 없으면 다시 돌아와서(백트래킹) 다른 경로를 탐색하는 알고리즘입니다. 🔹 DFS의 특징항목설명탐색 방식깊이 우선 (먼저 한 쪽 끝까지 파고 듦)자.. 2025. 6. 16.
[알고리즘/Algorithm] 분할정복 Divide and Conquer / BOJ 2630 색종이 만들기 안녕하세요, 이번에는 분할정복(Divide and Conquer)에 대하여 정리해보려고 합니다.동적계획법(Dynamic Programming)도 분할정복으로 문제를 푸는 경우가 많아서,그보다 먼저 정리를 할까 했는데 냅다 문제를 풀어버렸습니다 ㅎㅎ 따라서 이번엔 많은 문제해결에 적용이 되는 분할정복(Divide and Conquer)에 대해 정리해보겠습니다.분할정복 (Divide and Conquer) 이란?분할정복 (Divide and Conquer)이란, 큰 문제를 작은 문제로 분할(Divide)하여 작은 문제부터 해결(Conquer)하는 알고리즘 기법입니다. ◆ 핵심 개념문제를 작은 하위 문제(Subproblem)로 분할(Divide)하위 문제를 재귀적으로 정복(Conquer)하위 문제들의 결과를 .. 2025. 5. 13.
[알고리즘/Algorithm] 동적계획법 Dynamic Programming / BOJ 9095 1, 2, 3 더하기 & BOJ 2839 설탕 배달 안녕하세요!이번에는 바로! 알고리즘 문제풀이(Algorithm Problem Solving)의 꽃이라고 불리는 동적 계획법에 대해서 정리해보려고 합니다 :0분할정복이나 수학 관련 알고리즘을 먼저 공부할까 했는데, 문제를 풀어나가다 보니 DP에 대해서 먼저 정리하고 싶어졌습니다 ㅎㅎ 난이도가 있는 문제가 꽤 많이 나와서, 이 김에 정리해두려고 합니다!ㅎㅎ동적계획법(Dynamic Programming) 이란?먼저 동적계획법(Dynamic Programming; 다이나믹 프로그래밍)이 무엇일까요?동적계획법은 복잡한 문제를 작은 부분으로 나누고, 이를 저장하여 중복 계산을 줄이는 기법입니다.즉, 분할정복과 비슷하지만 중복되는 부분의 결과값을 저장하고 재사용하는 과정이 추가된 것입니다. ■ DP를 사용하는 경우중.. 2025. 3. 26.
[알고리즘/Algorithm] 소수 판별 - 에라토스테네스의 체 / Sieve of Eratosthenes / BOJ 4948 베르트랑 공준 예제 풀이 안녕하세요,이번에는 소수 판별 알고리즘인 '에라토스테네스의 체'에 대해서 포스팅 해 보려고 합니다 !에라토스테네스의 체 (Sieve of Eratosthenes)에라토스테네스의 체는 여러 개의 수 중에서 소수를 빠르게 찾아내는 알고리즘입니다. 소수란?1과 자기 자신만을 약수로 가지는 1보다 큰 자연수입니다. 예를 들어, 2, 3, 5, 7, 11, 13, 17 등은 소수입니다. ◆ 기본 원리 1. 2부터 N까지의 모든 숫자를 소수라고 가정합니다.2. 가장 작은 소수(2)부터 배수를 제거하여 소수가 아닌 숫자를 지웁니다.3. 남아 있는 숫자들이 소수가 됩니다. 위와 같은 기본 원리를 바탕으로 소수 판별 알고리즘을 구현합니다. 예를 들어, N = 30까지의 소수를 찾는다고 하면, 아래와 같은 과정으로 소수를.. 2025. 2. 20.
반응형

티스토리툴바