본문 바로가기
반응형

분류 전체보기43

[자료구조 | Data Structure] 그래프 이론 Graph Theory 안녕하세요,오늘은 알고리즘에 사용되는 자료구조를 정리해보려고 합니다.알고리즘 문제 풀이에 대표적으로 사용되는 자료구조증 하나, 그래프에 대하여 정리해보겠습니다.그래프(Graph), 혹은 그래프 이론(Graph Theory)라고 불리는 이 자료구조는, DFS, BFS 문제를 푸는 데 기초가 되는 이론이고,나아가 위상정렬 등의 문제를 푸는 데도 기초가 됩니다.트리 문제도 그래프 이론에서 출발하죠!그래서 저도 기초를 다시 다지기 위해서 정리해봅니다. :)그래프 이론(Graph Theory) 기초 개념 정리그래프는 현실 세계의 네트워크, 관계, 연결구조를 수학적으로 표현한 자료구조 입니다.소셜 네트워크, 지도, 컴퓨터 네트워크, 알고리즘 문제 등에서 필수적으로 사용됩니다. 그래프란?: 그래프란 정점(Vertex.. 2025. 5. 26.
[알고리즘/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] 유클리드 호제법 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.
반응형

티스토리툴바