해피 코딩/알고리즘9 [이론] 유니온 파인드 너무 쉬운데? 유니온 파인드유니온 파인드(Union-Find)는 여러 노드가 있을 때, 특정 두 노드를 연결해 하나의 집합으로 묶는 union 연산과, 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성된 알고리즘입니다. 근데 솔직히, 글로만 보면 알 듯 말 듯 애매하게 느껴지죠? 이건 마치 제 재능 같은 느낌이네요. 😅그래서 한 마디로 정리하면 이렇게 이해하면 됩니다:union(a, b) 는 "a와 b를 합치라는 거구나! 둘을 같은 집합으로 묶어주는 거구나!"find(a) 는 "a가 속한 집합의 대표 노드를 찾아달라는 거구나!" 아직도 애매하다고 느껴지신다고요? 괜찮습니다!이 글을 끝까지 읽으시면, 여러분도 유니온 파인드의 이론을 완벽하게 이해하실 수 있을 겁니다.이 블로그를 발견한 당신, 이미 .. 2024. 12. 24. [백준 10986] '나머지 합' 가장 쉽게 이해하기 JAVA https://www.acmicpc.net/problem/10986 주의❗이 문제를 해결하려면 먼저 '누적 합' 개념을 이해해야 합니다.이 글은 누적 합의 개념을 알고 있다는 가정을 바탕으로 작성되었습니다. 😊 문제 출력 분류 핵심 분석 ✅ 문제를 풀기 전에, 시각적 자료를 활용하여 문제의 핵심 분석해 보겠습니다. 문제만 보면 다소 이해하기 어려울 수 있으니, 그림과 함께 살펴보며 이해해 보겠습니다.보다 쉬운 설명을 위해 문제의 예제 입력값을 참고하여 분석하도록 하겠습니다.예제 입력5 31 2 3 1 2 그림을 활용해 연속된 부분의 합 (Ai + ... + Aj) 이 M(3) 으로 나누어떨어지는 구간의 개수를 구해보았습니다. 누적 합 S 배열 구하기먼저, 합 배열 S를 구한 뒤, S배열에서 M(3) 으.. 2024. 12. 21. [백준 1934] 문제로 이해하는 유클리드 호제법 JAVA 최대 공약수를 구하는 방법최대 공약수를 구하는 대표적인 알고리즘으로 "유클리드 호제법" 이 있습니다.일반적으로는 최대 공약수를 구할 때 소인수분해를 이용해 공통된 소수들의 곱으로 표현할 수 있습니다.하지만, 소인수분해는 코드로 구현하기 복잡하고 시간이 오래 걸릴 수 있다는 단점이 있습니다.따라서, 우리는 유클리드 호제법을 사용해 더 간단하고 효율적인 방법으로 최대 공약수를 구하는 법을 배워보겠습니다. 이름의 유래 ✍️"유클리드 호제법" 이라는 이름은 고대 그리스의 수학자 유클리드에서 유래했습니다.이 알고리즘은 유클리드의 원론에 적혀있는 내용으로, 인류 최초의 알고리즘이라고 합니다. "호제법"이라는 이름은 "번갈아 나누다" 라는 뜻에서 유래되었습니다.즉, 큰 수를 작은 수로 나누고, 그 나머지를 다시 나누.. 2024. 12. 16. [백준 1929] 문제로 이해하는 에라토스테니스의 체 JAVA 소수를 구하는 방법소수를 구하는 대표적인 알고리즘으로 "에라토스테네스의 체" 가 있습니다.이 알고리즘은 효율적으로 소수를 찾아내는 데 매우 유용하며,대부분의 코딩테스트에서도 소수 판별 문제를 해결할 때 이 이론을 사용합니다.오늘은 에라토스테네스의 체를 배워보며, 효율적인 소수 구하기의 원리를 이해해 봅시다! 😊 이름의 유래 ✍️"에라토스테네스의 체" 라는 이름은 고대 그리스의 수학자인 에라토스테네스의 이름에서 유래했습니다.그는 소수를 구하는 효율적인 방법을 체계적으로 처음 정리한 인물로 알려져 있습니다. 그리고 "체" 라는 이름은 우리가 곡식을 걸러내는 도구를 떠올리면 쉽게 이해할 수 있습니다.즉, 소수가 아닌 수를 체로 걸러내듯 제거해 나가면, 마지막에 남는 숫자들이 바로 소수가 되는 것이죠. "자.. 2024. 12. 16. [이론] 병합 정렬 알고가기 인류 역사상 최고의 천재는 누구인가. 바로 나야 그렇다, 인류 역사상 최고의 천재, 천재 중의 천재로 불리는 존 폰 노이만❗이번에는 그가 고안한 병합 정렬(Merge Sort)에 대해서 알아보자. 병합 정렬이란❓병합 정렬(Merge Sort)은 분할 정복 방식을 사용하여 데이터를 처리하는 정렬 알고리즘입니다.즉, 데이터를 작게 나누고, 나눈 데이터를 다시 정렬하고 합쳐서 최종적으로 정렬된 결과를 얻는 방식입니다. 병합 정렬의 시간 복잡도 평균값은 O(nlogn)입니다. ⌛ 병합 정렬의 동작 과정 정리 📝분할(Divide)배열을 더 이상 나눌 수 없을 때까지 쪼갠다.정복(Conquer)각 부분 배열을 정렬한다.병합(Merge)정렬된 두 배열을 합쳐 하나의 정렬된 배열로 만든다. 병합 정렬 그림으로 이해.. 2024. 12. 12. [이론] 버블 정렬 알고가기 버블 정렬은 왜 버블 정렬일까? 🤔버블 정렬이라는 이름은 딱 들었을 때 뭔가 귀엽고 친근한 느낌을 받았습니다. 처음 들었을 때 이름이 너무 매력적이라 "왜 이런 이름이 붙었을까?" 궁금했는데, 그 이유를 알고 나니 정말 딱 맞는 이름이라는 생각이 들었습니다! "버블"의 의미 🫧버블 정렬(Bubble Sort)은 배열의 요소들이 거품처럼 위로 보글보글 올라가는 모습과 비슷하다고 해서 붙여진 이름입니다.오름차순 기준 큰 값이 반복적으로 비교되어 점점 위로 올라가고, 가장 큰 값이 맨 끝에 위치하게 됩니다.마치 물속의 거품이 위로 올라가며 터지는 것과 유사하죠! 버블 정렬의 작동 원리 ✍️버블 정렬은 인접한 두 값을 비교하여 잘못된 순서를 가진 값들을 서로 교환합니다.가장 큰 값이 배열의 끝으로 밀려나면서.. 2024. 12. 5. 이전 1 2 다음
