algorithm17 [Algorithm] 이진탐색(Binary Search), 반반 나누어서 찾자 [ Contents ] 1. 이진탐색 (Binary Search, 이분탐색) 이진탐색: 정렬된 자료를 절반씩 나누어서 탐색하는 방법 오름차순(또는 내림차순)으로 정렬된 자료에서 사용합니다. 찾고자 하는 숫자와 자료의 중간값과 비교하여 탐색 범위를 절반씩 줄여갑니다. 찾고자 하는 수보다 작으면 작은 쪽을, 크면 큰 쪽을 찾습니다. 이진탐색 과정 1) 찾는 값과 중앙값을 비교합니다. 2) 중앙값과 같다면 탐색 종료. 작다면 작은 쪽을 크다면 큰 쪽을 찾습니다. 3) 값을 찾을 때까지 1, 2 과정을 반복합니다. 예를 들어 32를 찾고자 한다면, 중앙값인 63과 값을 비교합니다. 63보다 작으니, 작은 쪽에서 찾습니다. 12, 32, 41의 중앙값은 '32'입니다. 32를 찾았으므로 종료합니다. 2. 이진탐색.. 2022. 2. 9. [Algorithm] 소수 판별 알고리즘, 에라토스 테네스의 체 에라토스 테네스의 체를 통해서 소수를 판별하는 알고리즘을 알아보겠습니다. [ Contents ] 1. 소수 소수(Prime): 약수가 1과 자기 자신밖에 없는 수 '소수'는 1과 자기 자신으로만 나누어 떨어지는 자연수입니다. 반대로 1과 자기 자신 외에 다른 약수가 있으면 '합성수'라고 합니다. '소수 판별'은 특별한 공식이 없으며, 정의대로 1과 자기자신 사이의 수 중 약수가 있는지 검증해야 합니다. 숫자가 클수록 검증해야 하는 숫자들이 많아지며, 계산복잡도도 높아집니다. 따라서 RSA와 같은 각종 보안 알고리즘에 응용되며, 소수 판별 알고리즘의 중요성도 커지고 있습니다. 만약 소수를 빠르게 찾아낼 수 있는 공식을 찾아낸다면, 블록체인을 비롯해서 사회 전반의 보안 알고리즘을 뚫어낼 수 있습니다. (그럴.. 2022. 2. 8. [Algorithm] 최대공약수(GCD) 구하기: 유클리드 호제법 유클리드 호제법을 이용하면 두 수의 최대공약수를 구할 수 있습니다. 최대공약수는 두 수의 공통인 최대 약수를 말합니다. [ Contents ] 1. 유클리드 호제법 (Euclidean Algorithm) 두 자연수 X, Y가 있을 때 (단, X > Y) 1) X와 Y의 최대공약수는 'X를 Y로 나눈 나머지'와 'Y'의 최대공약수와 같다. - 큰 수를 작은 수로 나눈 나머지가 0이 될 때까지 반복 2) X와 Y의 최대공약수는 'X를 Y로 뺀 값'과 'Y'의 최대공약수와 같다. - X와 Y가 같아질 때까지 큰 수를 작은 수로 빼며 반복 두 수의 최대공약수는 작은 수로 빼거나, 나눈 나머지로 구한 최대공약수와 같습니다. 유클리드 호제법을 이용하면, 1부터 Y까지 공약수 유무를 판별하지 않고도 최대공약수를 구할.. 2022. 2. 5. [Algorithm] 분할정복(DQ, Divide-and-Conquer), 각개격파 알고리즘 각개격파(各個擊破): 적을 하나하나 따로 떼어 무찌름 유독 외세의 침략을 많이 받았던 우리 민족의 대표적인 전술은 '매복'과 '각개격파'였습니다. 70%가 산악지형인 점을 이용해서, 산개된 적들을 각각 무찔렀습니다. 이런 각개격파 전술은 '알고리즘 문제'에서도 유효합니다. 사람 사는 세상의 이치는 만물이 통하니까요. [ Contents ] 1. 분할 정복 알고리즘 분할 정복(Divide-and-Conquer, DQ): 주어진 문제의 입력을 분할하여 해결하는 방식 알고리즘 문제도 분할해서 풀면, 쉽게 해결되는 경우가 많습니다. 예를 들어, 방대한 데이터(100GB)를 오름차순으로 정렬하는 문제는 그대로 해결할 수 없습니다. 한 번에 정렬을 하려면, 데이터베이스의 모든 데이터를 메인 메모리(RAM)에 올려야.. 2022. 1. 29. [Algorithm] 탐욕적인 그리디 알고리즘, 직관적이고 쉬운 문제해결 경주마들을 자세히 보면, 양쪽 시야를 차단하는 안대를 끼고 있습니다. 이를 '차안대' 라고 합니다. 말의 눈은 양 옆에 달려 있어 시야가 '350도'나 됩니다. 자기 자신 빼곤 다 보이기 때문에, 다른 말이 뒤나 앞에서 뛰고 있으면 주의가 산만해지고 피하게 된다고 합니다. 그래서 양 옆의 시야를 차단하는 '차안대'를 착용합니다. [ Contents ] 1. 그리디 알고리즘 그리디 알고리즘(Greedy Algorithm): 근시안적인 선택으로 부분적인 최적해를 얻고, 이를 통해 문제의 최적해를 찾는 방식 '그리디 알고리즘'도 이와 비슷합니다. 최적해를 찾기 위해, '앞'만 보고 달려갑니다. 다시 뒤로 되돌아가지 않으며, 현재 상황에서 최적인 결정을 합니다. 매번 전체적으로 최적인지 고려하는 과정이 없으므로.. 2022. 1. 26. [Algorithm] 단골 1번 문제, 구현 / 수학 [ Contents ] 1. 구현 단순히 '구현'만 하면 되는 문제 유형입니다. 문제를 이해하고 입력에 맞춰 적절한 출력만 하면 됩니다. 특별한 알고리즘이나 프로그래밍적 기법 없이, 단순 제어문만 사용하여 해결할 수 있는 쉬운 문제입니다. 그래서 코딩 시험이나 알고리즘 대회에서 손풀기 문제로 출제가 됩니다. 요즘은 구현 Part에 자료구조를 물어보는 경우도 늘고 있지만, 대체로 문제를 이해하기만 하면 풀 수 있는 문제입니다. 2. 수학 구현 문제는 특정 규칙을 찾아내야 하는 경우도 있습니다. 수열처럼 입력값이 증가함에 따라 변하는 출력값의 규칙을 찾아야 합니다. 패턴만 찾으면, 코딩은 쉽습니다. 반면, 직접적으로 수학 이론을 요구하는 경우도 있습니다. 소수 판별이 대표적인 예입니다. '에라토스 테네스의 .. 2022. 1. 19. [Algorithm] 브루트 포스(Brute Force)는 노가다 기법? [ Contents ] 1. 브루트 포스란? Brute(짐승 같은, 난폭한) + Force(힘, 폭력)의 합성어입니다. 무식하게 푸는 기법으로, '노가다'에 가까운 접근법입니다. 모든 경우의 수를 시험해보며 문제를 해결합니다. 브루트 포스 접근방법은 일상에서도 많이 사용합니다. 예를 들어, 자물쇠 비밀번호 4자리를 맞추기 위해 0000부터 9999까지 모두 시험해보는 것도 대표적인 '브루트 포스' 방식입니다. 2. 순열과 조합 경우의 수를 계산하다보니, 순열과 조합 기본지식이 필요합니다. 단순히 순서가 있는건 '순열', 순서가 없는 건 '조합'이라는 정도만 상기하시면 됩니다. 복잡한 수식을 외우지 않더라도, 이미 라이브러리로 구현되어 있습니다. 각 언어에서 지원하는 라이브러리를 불러오셔서 쓰시면 됩니다... 2022. 1. 16. [Algorithm] 게시판 소개 문제해결을 위한 다양한 알고리즘들의 원리를 이해하고, 응용 예제를 살펴봅니다. 예제는 백준 온라인 저지에 있는 문제들을 활용할 예정입니다. 구현 수학 그리디 알고리즘 다이나믹 프로그래밍 그래프 이론 탐색론 . . . Baekjoon Online Judge Baekjoon Online Judge 프로그래밍 문제를 풀고 온라인으로 채점받을 수 있는 곳입니다. www.acmicpc.net 알고리즘 예제 풀이에 사용되는 주 언어는 Python을 사용합니다. 2022. 1. 11. 이전 1 2 다음
