개요최근 게임 회사 코딩테스트를 몇 번 경험해보니 그리디 알고리즘에 관한 문제가 적어도 1문제 이상 출시되었고, 많은 어려움이 있었기에 이번 포스팅에서는 그리디 알고리즘에 대해 자세히 정리해보도록 하겠습니다.그리디 알고리즘 그리디 알고리즘(탐욕 알고리즘, Greedy Algorithm)은 매 순간 최선의 선택을 하여 문제를 해결하는 방법론입니다. 문제 해결 과정에서 한 번의 선택이 이후의 선택에 영향을 주기 때문에, 순간의 최적 선택이 결국 전체 문제의 최적 해답이 될 수 있다고 가정합니다. 즉, 각 단계에서 당장 최적인 해를 선택하고, 최종적으로 이러한 선택들이 모여 전체 문제의 최적 해답을 구성하는 방식입니다.그리디 알고리즘 필요 조건그리디 알고리즘을 사용하기 위해서는 다음의 두 가지 조건을 만족해야..

개요코딩테스트 문제를 풀다보면 10진수를 2진수로 변환하여 연산하는 로직을 구현해야 하는 부분이 종종 발생합니다.어렵지는 않지만, 간단한 것부터 수학적인 알고리즘을 정리해보기 위해 10진수를 2진수로 변환하는 방법에 대해 정리해보았습니다.2진법이란?우리는 일상적으로 0 ~ 9까지의 10개의 숫자를 사용하여 수를 나타내는 10진법을 사용합니다.하지만 컴퓨터는 내부적으로  0과 1이라는 두 개의 숫자만을 사용하여 수를 나타내는 2진법을 사용해서 계산합니다. 10진법에서는 10이 만들어지는 순간 자리수를 올리며, 2진수도 동일하게 2가 만들어지는 순간 자리수를 올린다고 생각할 수 있습니다. 예를 들어 "3"을 2진법으로 표현한다면 "11"이 되며, "4"는 "101"이 되는 것을 알 수 있습니다. 즉, 자리 ..

개요"에라토스테네스의 체" 알고리즘은 고대 그리스 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법으로, 마치 체로 치듯이 수를 걸러낸다고 하여 "에라토스테네스의 체"라고 부릅니다. 주로 대량의 수에서 소수를 판별하기 위해서 사용되는 알고리즘이며, 종종 코딩테스트 문제에서 보이기에 정리해보는 시간을 가지게 되었습니다.소수 판별 방법소수는 1과 자기 자신 만을 약수로 가지는 수입니다. 만약 2에서 100 사이의 소수를 구해야 하는 문제라면 각각의 수의 약수가 존재하는지 확인하는 방법을 사용할 수도 있습니다. 하지만 위 방법을 사용하면 2부터 100사이의 모든 수를 순회하며 자신을 제외한 약수가 존재하는지 체크해야 하므로 매우 비효율적입니다. 약간 발상을 바꿔 생각해보면 결국 2 ~ 100 사이의 수 중에..