개발하는 리프터 꽃게맨입니다.

📕 개요그리디 알고리즘은 '욕심쟁이 알고리즘'이라는 별칭을 가지고 있습니다. 이는 '지금 이 순간 최적의 답을 선택하여, 전체 문제를 해결하자!'라는 아이디어로부터 출발합니다. 간단한 예시를 들어보겠습니다. 서울에서 부산으로 가고자 하는데, 무조건 대전, 대구를 경유해서 가야 한다고 가정해 보겠습니다. 어떻게 해야 가장 빠르게 부산에 도착할 수 있을까요? 서울 ~ 대전까지 가장 빠르게 도달하는 시간 + 대전 ~ 대구까지 가장 빠르게 도달하는 시간 + 대구 ~ 부산까지 가장 빠르게 도달하는 시간 = 서울 ~ 부산까지 가장 빠르게 도달하는 시간 일 겁니다. 그때그때 최적의 답을 선택하고, 그것을 모아서 전체 문제에 대한 해답을 찾고자 합니다. 그러나, 그리디 알고리즘이 항상 최적의 결과를 도출하는 것은 아닙..

참고: https://powerclabman.tistory.com/12 [C++/알고리즘] 분할정복 (Divide and Conquer) + 병합정렬 (Merge Sort) 📕 개요 '분할 정복 알고리즘'이란, 엄청나게 크고 방대한 문제를 해결할 수 있는 단위까지 쪼개서 해결한 다음 그것들을 다시 합쳐서 원래의 문제를 해결하고자 하는 알고리즘 기법입니다. 그 powerclabman.tistory.com 📕 개요 퀵 정렬 또한 '분할정복 알고리즘' 기법을 사용해서 빠르게 배열을 정렬하는 알고리즘입니다. 먼저, 퀵 정렬의 아이디어부터 한 번 살펴보도록 합시다. 1. 피벗(Pivot)을 정합니다. 피벗은 임의의 '기준'을 뜻합니다. 2. 피벗을 기준으로 피벗 왼쪽에는 '피벗 보다 작은 값'을 두고, 피벗 오른..

📕 개요 '분할 정복 알고리즘'이란, 엄청나게 크고 방대한 문제를 해결할 수 있는 단위까지 쪼개서 해결한 다음 그것들을 다시 합쳐서 원래의 문제를 해결하고자 하는 알고리즘 기법입니다. 그림처럼 '큰 문제'를 '부분 문제'로 계속해서 분할합니다. 그리고 '부분 문제'를 해결하고, 해답을 조합하여서 원래 문제에 대한 해답을 얻어 내고자 하는 것이 이 알고리즘의 핵심입니다. 논리는 다음과 같습니다. 1. 분할 (Divide) 큰 문제를 매우 작은 부분 문제로 분할합니다. 2. 정복 (Conquer) 가장 작은 단위의 부분 문제를 해결합니다. 3. 조합 (Combine) 하위 문제에 대한 결과를 조합하여, 원래 문제의 답을 얻어 냅니다. 분할 정복법은 대부분 '재귀' 로 구현됩니다. 다음은 분할 정복 알고리즘으..

📗 비둘기집 원리4개의 집이 있고 5마리의 비둘기가 있을 때 모든 비둘기에게 집을 할당하려면 '무조건' 중복된 집 할당이 생깁니다. 원리라고 부르기도 민망할 정도로 당연하고 직관적입니다. 살짝 확장을 해보자면 366명의 학생이 있을 때, 윤년을 고려하지 않으면 적어도 1명은 다른 한 명과 생일이 겹치겠죠? 이것이 '비둘기집 원리'입니다. 이 원리가 문제를 해결하는 데 있어, 존재를 증명할 때 종종 쓰이곤 합니다. 다음 예시를 통해 알아보도록 합시다. 📕 Decreasing Sequence 문제1. 문제 주어진 두 정수 L과 R이 있을 때 다음 조건을 만족하는 가장 작은 양의 정수 N을 찾아라. N% L > N%(L+1) >... > N%(R-1) > N% R 2. 입력 L = 4, R = 6을 입력했을 ..

📕 비트 연산자의 개념 비트 연산은 '2진수' 연산을 뜻하는데, 특정 연산자를 이용해서 이진 수로 표현된 정수에 대하여 논리적인 연산을 수행합니다. 2진수 연산은 10진수 연산에 익숙한 사람에겐 매우 생소한 개념일 수밖에 없습니다. 그러나, 컴퓨터와 같은 기계장치들의 근간은 2진수의 집합으로 이루어져 있기에 비트 연산을 사용하면, 컴퓨터 입장에서 매우 빠르게 연산할 수 있게 됩니다. 게임과 같은 매 프레임 반복적인 연산을 필요로 하는 프로그램을 개발할 때 단순한 곱셈이나 비교 연산을 비트 연산으로 치환해 주면 최적화하는데 도움이 될 수 있습니다. 📗 C++에서의 비트 연산자 1. & AND 연산입니다. 피연산자가 모두 1(참) 일 경우 결괏값은 참이 됩니다. A B A&B 0 0 0 0 1 0 1 0 0..