본문 바로가기
반응형

알고리즘6

[자료구조 | Data Structure] 그래프 이론 Graph Theory 안녕하세요,오늘은 알고리즘에 사용되는 자료구조를 정리해보려고 합니다.알고리즘 문제 풀이에 대표적으로 사용되는 자료구조증 하나, 그래프에 대하여 정리해보겠습니다.그래프(Graph), 혹은 그래프 이론(Graph Theory)라고 불리는 이 자료구조는, DFS, BFS 문제를 푸는 데 기초가 되는 이론이고,나아가 위상정렬 등의 문제를 푸는 데도 기초가 됩니다.트리 문제도 그래프 이론에서 출발하죠!그래서 저도 기초를 다시 다지기 위해서 정리해봅니다. :)그래프 이론(Graph Theory) 기초 개념 정리그래프는 현실 세계의 네트워크, 관계, 연결구조를 수학적으로 표현한 자료구조 입니다.소셜 네트워크, 지도, 컴퓨터 네트워크, 알고리즘 문제 등에서 필수적으로 사용됩니다. 그래프란?: 그래프란 정점(Vertex.. 2025. 5. 26.
[알고리즘/Algorithm] 유클리드 호제법 Euclidean Algorithm / BOJ 2609 최대공약수와 최소공배수 안녕하세요!이번에는 수학 알고리즘 중 최대공약수, 최소공배수를 구할 때 활용할 수 있는 '유클리드 호제법'에 대해서 정리해보려고 합니다 :)알고리즘이 수학과 관련이 높은 만큼 종종 접하는 문제 유형인 듯 합니다. 수학 알고리즘이 생각보다 정수론이나 특정 이론과 관련있는 경우가 많아서인지,수학 공부를 하지 않은 상태에서는 떠올리기가 쉽지 않은 경우도 종종 있습니다.이렇게 문제 풀면서 정리해보는 것도 좋을 듯 하여,수학 알고리즘 중 하나인 '유클리드 호제법'도 정리해봅니다 !! 유클리드 호제법 Euclidean Algorithm유클리드 호제법은두 수의 최대공약수(Greatest Common Divisor)를 구하는 알고리즘 으로,나눗셈을 반복해 계산하며 최대공약수를 찾습니다. 두 수 a, b (단, a ≥ .. 2025. 4. 17.
[알고리즘/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.
반응형

티스토리툴바