나만의 작은 도서관

최대공약수(GCD), 최소공배수(LCM) 구하는 법최대공약수(GCD, Greatest Common Divisor)는 두 자연수의 공통된 약수 중에서 가장 큰 수를 의미하며, 최소공배수(LCM, Least Common Muliple)는 두 자연수의 공통된 배수 중 가장 작은 수를 의미한다.  최대공약수는 두 자연수를 나누어 떨어지게 하는 최댓값을 찾으면 되며, 최소공배수는 두 자연수를 곱하고 GCD만큼 나눠주면 된다. 이를 코드로 구현하면 다음과 같다.// 시간복잡도 O(N)int gcd(int a, int b){ int res = 0; for(int i = 1; i   N개의 자연수의 최대공약수를 구하고 싶은 경우2개의 자연수에 대한 최대공약수가 아닌 N개의 자연수에 대한 최대공약수를 구하고 ..

소수 판별법소수는 양의 약수를 2개만 가지는 자연수, 즉 1과 자기자신으로만 나누어 떨어지는 자연수를 의미한다(1 제외). 임의의 수 N이 소수인지 판별하기 위해선 2~N-1까지의 수들로 N이 나누어 떨어지지 않는 지 확인하면 된다. 코드로 구현하면 다음과 같다.// 시간복잡도 O(N)bool isPrime(int num){ for(int i = 2; i  최적화를 할 수는 없을까?위 코드는 최적화가 가능하다. 2 이상의 자연수 N에 대해서 N의 약수는 짝이 반드시 존재하고, 짝이 되는 약수 중 작은 쪽에 속하는 약수는 √ N을 초과할 수 없기 때문에 num까지가 아닌 √ N이하의 자연수까지만 루프를 돌면 된다. 따라서 코드에 적용하면 다음과 같다.// 시간복잡도 O(√N)bool isPrime(i..

parametric search란?parametric search는 최적화 문제를 결정 문제로 바꾼 뒤 이진 탐색을 이용해 최적해를 찾는 방식이다.  최적화 문제와 결정 문제최적화 문제(mathematical optimization problem)는 주어진 조건을 만족하는 여러가지 해 중에서 가장 최적해를 구하는 문제이다. 우리가 접하는 대부분의 알고리즘 문제들이 최적화 문제이며, "OO을 만족하는 최솟값을 구하시오" 또는 "OO을 만족하는 최댓값을 구하시오" 와 같이 적혀있는게 특징이다. 결정 문제(decision problem)는 주어진 조건을 만족하는 해가 존재하는 지 여부를 구하는 문제로, YES 또는 NO 이렇게 단 두 가지의 결과만이 나온다는 것이 특징이다. 예로, "X라는 값이 배열 arr에..

개요내일부트캠프 참여 기간이 08/15를 기준으로 네 달이 지났고, 08/29을 기준으로 캠프를 수료하였다. 그동안 무슨 일들이 있었는지 어떤 생각이 들었는지, 그리고 얼마나 생각이 바뀌었는지 미래의 나를 위해서 기록해본다.최종 프로젝트 7/19 ~ 8/27시작타워 디펜스 팀 프로젝트가 끝나자마자 최종 프로젝트의 조편성이 되었고, 그렇게 바로 최종이 시작되었다. 기간은 5주. 이전 팀 프로젝트와 비교는 되지 않을 정도로 긴 시간동안 프로젝트를 진행하였다. 처음 5주동안 진행한다는 이야기를 들었을 때는 '다른 팀원들과 트러블없이 끝까지 갈 수 있을까?' 하는 걱정도 들었었고, '원하는 결과를 얻을 수 있을까?' 하는 걱정도 들었었다. 여러모로 걱정이 있었지만, 팀원들과 대화를 조금 하고나니 그런 걱정들은 ..

개요내일배움캠프 Node.js 트랙에서의 최종 프로젝트인 스파르탄 온라인 프로젝트가 마무리되었다. 5명의 팀원들과 함께 7/19~8/27까지 약 5주동안 협력하면서 무엇이 좋았고, 어떤 문제가 발생했었는지, 그리고 문제를 어떤 식으로 해결했는지 또는 어떤 식으로 해결하면 좋았을 지 KPT 방식으로 회고해보자. 팀에서의 내 역할: 팀원 참고이번 KPT 회고록은 개인적인 생각만을 담도록 하겠다. 팀원들에게 회고록을 작성하자는 의견을 제안했지만 부리더님이 이번 프로젝트는 너무 만족스러워서 딱히 적을게 없을 것 같다하여 그냥 나 혼자서 적기로 했다. 서버 코드 깃헙 링크https://github.com/pledge24/Project_F_Server GitHub - pledge24/Project_F_ServerC..

코드카타가 드디어 마무리 되었다. 풀었던 문제들을 글로 기록해놓는 것이 이렇게 힘든 일인줄은 몰랐다. 지금와서 말하지만 굳이 이렇게 글로 남기려 했던 이유는 항상 문제를 풀고 난 다음, 후에 비슷한 문제를 봤을 때 '이거 어떻게 풀었었는데...'라는 생각만 막연하게 나고 결국 생각해내지 못하는 일들이 있었기 때문이다. 이제와서 보면 '그래서 원하는 대로 잘 됐나?'라는 물음에 제대로 대답하지 못하겠지만... 어찌되었든 잘 마무리 되었으니 나름 뿌듯하다