Level 0. 구슬을 나누는 경우의 수 처음에 아래와 같은 코드를 작성해 일부 케이스를 해결하지 못했다. 질문하기에서 힌트를 찾아보니 unsigned long long으로 해도 범위가 넘어간다는 것이었다. #include using namespace std; using ullong = unsigned long long; ullong solution(int balls, int share) { ullong denominator = 1; ullong numerator = 1; for (ullong i = 1; i

Level 0. 다항식 더하기 istringstream을 이용해 파싱하여 해결했다. 특별히 더 고민해 볼 것은 없는 문제 같다. #include #include #include using namespace std; string makePoly(int x, int c) { if (x == 0) return to_string(c); else return (x == 1 ? "" : to_string(x)) + "x" + (c == 0 ? "" : (" + " + to_string(c))); } string solution(string polynomial) { istringstream iss(polynomial); string s; int x = 0, c = 0; while (iss >> s) { size_t ..

Level 0. 분수의 덧셈 유클리드 호제법을 이용해 최대공약수와 최소공배수를 구하여 해결했다. #include #include using namespace std; int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } int lcm(int a, int b) { return a * b / gcd(a, b); } vector solution(int numer1, int denom1, int numer2, int denom2) { int denom = lcm(denom1, denom2); int numer = (numer1 * denom / denom1) + (numer2 * denom / denom2); int GCD = gcd(denom, numer); re..

Level 0. 겹치는 선분의 길이 각 선분이 지나는 점들의 값을 1씩 증가시켜 2 이상인 점의 개수를 찾아 해결했다. 값을 증가시키기 위해 순회하지 않고 범위를 이용해서 좀 더 효율적인 방법이 있나 찾아보았다. 겹치는 부분이 아니라 이어진 부분을 찾는 문제에서는 스위핑 기법 같은 것이 있었는데 이 문제에 대해서는 더 효율적인 방법을 찾을 수 없었다. #include #include #include using namespace std; int solution(vector lines) { vector v(200, 0); for (vector& line : lines) for (int i = line[0]; i < line[1]; ++i) ++v[100 + i]; return count_if(v.begin(..

Level 0. 가까운 수 sort() 함수에 커스텀 비교자를 지정하여 정렬하면 쉽게 해결할 수 있지만 O(nlog n) 시간이 소요된다. #include #include #include using namespace std; int solution(vector array, int n) { sort(array.begin(), array.end(), [n](const int a, const int b) { int distA = abs(n - a); int distB = abs(n - b); return (distA == distB) ? (a < b) : (distA < distB); }); return array[0]; } 코드가 다소 길어지긴 했지만 직접 순회하면 O(n) 시간에 해결 가능하다. #incl..

Level 0. 합성수 찾기 에라토스테네스의 체를 활용해 해결했다. 2부터 소수인 수는 자신을 제외한 자신의 배수들을 합성수로 표시하는 알고리즘이다. 가장 작은 소수는 2이기 때문에 last(n / 2)까지만 반복문을 수행하면 된다. #include #include #include using namespace std; int solution(int n) { int last = n / 2; vector v(n + 1, true); for (int i = 2; i