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 ..

코딩 테스트를 위한 자료 구조와 알고리즘 with C++ 각 노드가 N개의 자식을 가질 수 있는 트리를 N-항 트리라고 한다. N-항 트리는 자식의 참조를 벡터로 저장하여 구현할 수 있다. struct node { int date; vectorchildren; } N-항 트리가 사용된 예 파일 시스템 구조 회사의 조직도

최대공약수(Greatest Common Divisor)를 구하는 알고리즘 중 하나이다. 유클리드 호제법은 다음의 성질을 이용한다. // a를 b로 나눈 나머지를 r이라고 할 때 r = a % b // a, b의 최대공약수는 b, r의 최대공약수와 같다. GCD(a, b) == GCD(b, r) 의사코드로 나타내면 다음과 같다. GCD(a, b): if b == 0 return a else return GCD(b, a % b) C++로 간단하게 작성할 수 있다. int GCD(int a, int b) { return b ? GCD(b, a % b) : a; } 최소공배수(Least Common Multiple)는 다음과 같이 구할 수 있다. // a, b의 최대공약수를 G라고 할 때 G = GCD(a, b..

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(..