Little Jay

마스크를 쓰지 않고는 밖을 다니면 안 되는 코로나19 시대입니다. 코로나19가 장기화되면서 코로나 블루라는 말이 나올 정도로 우울한 사람들이 많아지고 있습니다. 세계적인 전기자동차 회사 경영자인 '얼른 마스크'씨는 자신의 전기자동차를 타는 고객들이 조금이라도 행복할 수 있기를 바라며 판매하는 전기자동차 번호판 일련번호 4자리를 행복 수(happy number)로 채우고자 합니다. 행복 수는 각 자릿수의 제곱의 합으로 변환하는 과정을 반복할 때 언젠가는 1에 도달하는 수입니다. 예로, 13 → 1x1 + 3x3 = 10 → 1x1 + 0x0 = 1이므로 13은 행복 수입니다. 행복 수가 아닌 것은 슬픈(sad) 수 또는 불행(unhappy) 수라고 불립니다. 예로, 4 → 4x4 = 16 → 1x1 + 6..

피보나치 수에 대한 문제입니다. 피보나치 수는 아래와 같이 정의됩니다. f(1) = 1 f(2) = 2 f(3) = f(1) + f(2) = 1 + 2 = 3 f(4) = f(2) + f(3) = 2 + 3 = 5 f(5) = f(3) + f(4) = 3 + 5 = 8 ... f(n) = f(n-2) + f(n-1), n>=3 a와 b라는 두 수가 주어져 있을 때 두 수 사이에는 몇 개의 피보나치 수가 있을까요? 예를 들어 10과 100 사이에는 총 5개(13, 21, 34, 55, 89)의 피보나치 수가 있고 모두 더한 값은 212입니다. 12345678999과 99987654321 사이에도 몇 개의 피보나치 수가 있습니다. 이 구간 내의 모든 피보나치 수를 더한 값이 기념품을 받을 수 있는 열쇠입니다..

2학년때 정수론 배울때 잠깐 언급됬던 골드바흐 추측 에라토스테네스 체를 활용한 문제였다. 주어진 n의 max값이 1000000이기 때문에 접근할때 for문을 두개 돌려버리면 당연히 시간초과가 날 것 같았다. (실제로 시간초과가 났다) 그래서 algorithm stl에 들어있는 binary_search를 활용했다. 처음에 에라토스테네스의 체를 초기화해줄때 소수의 개수를 셌는데, 78498개나 나왔다. 어차피 배열에 저장할때는 오름차순으로 정렬이 되니, 정렬되어 있는 배열에서 이진탐색으로 찾으면 빠를거라고 예상했다. 찾기만 하면 나머지 수는 입력된 수에서 빼면 된다. 다른분의 숏코딩을 보니 문제에서 골드바흐 추측을 벗어나는 문제는 없었다. 이럴거면 나도 중간에 조건문 쓰지 말껄이라는 후회는 들긴 한다. 그리..

너무 어렵게 접근했던 문제이다. 뇌가 처음에는 너무 꼬여서 양수만 있을때, 음수있을때, 음수랑 0만 있을때, 0과 양수만 있을때 하나의 vector 컨테이너에서 조건문을 10개 이상 만들면서 처리를 하려고 했다. 너무 복잡해지자 이걸 어떻게 효율적으로 처리할까 고민하다가 양수와 음수를 따로 받는 방법을 생각하게 되었다. 1은 수를 묶을때 의미가 없다. 예를 들어 1 + 3 은 1 * 3 보다 무조건 크기 때문에 1이 들어올때는 바로 결과물을 담는 컨테이너에 담아주면 된다. 양수와 음수는 서로 묶어주지만 각 벡터의 개수가 홀수인지, 양수인지 구분해주면 된다. #include #include #include #define endl '\n' using namespace std; int n, cumsum; ve..

ascii 코드를 이용해서 잘 변환시키는게 중요했던 문제 처음에 알파벳 변환은 'A'의 아스키 값인 65를 빼주면 되고, 숫자를 임시적으로 문자열로 저장했을 때, 이를 다시 숫자로 변환할때는 0의 아스키 값인 48을 빼주면 된다. #include #define endl '\n' using namespace std; int alphabet[] = { 3, 2, 1, 2, 3, 3, 2, 3, 3, 2, 2, 1, 2, 2, 1, 2, 2, 2, 1, 2, 1, 1, 1, 2, 2, 1 }; string s1, s2; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> s1; cin >> s2; string..

dp 시작 #include #define endl '\n' using namespace std; long long dp[85]; int n; int main() { cin >> n; dp[0] = 0; dp[1] = 1; for (int i = 2; i

소인수를 구하는 다양한 방법이 있지만 효율적인 알고리즘을 위해서라면 O(n) 시간 안에 구하는 것이 최적인 것 같다. 에라토스테네스 체에서 영감을 얻어 나누어 떨어질때 수를 나누어주면 해결될 것 같다. '''어떤 수를 소수의 곱으로만 나타내는 것을 소인수분해라 하고, 이 소수들을 그 수의 소인수라고 합니다. 예를 들면 13195의 소인수는 5, 7, 13, 29 입니다. 600851475143의 소인수 중에서 가장 큰 수를 구하세요. ''' num = 600851475143 denom = 2 target = [] while num > 0: if num % denom == 0: num /= denom target.append(denom) elif num == 1: break else: denom += 1 ..

일반적으로 최대 힙(MAX HEAP), 최소 힙(MIN HEAP)을 통해 구현할 수 있겠지만 사실 이걸 자료구조 시간때 직접 구현하는 방법만 알았지 STL을 어떻게 써야 할 지 몰랐다. 당연히 다른 블로그들을 보게 되면 대부분 최대/최소 힙을 사용하여서 문제를 풀었었다. 그런데 어느 한 블로그를 보고 이걸 multiset으로 푸신분이 계셔 그분의 코드를 참고했다. multiset은 c++의 STL이며 set container와 달리 key가 중복 가능한 set을 구현할 수 있다. 트리 자료구조이다. multiset에 원소를 넣으면 자동으로 오름차순 정렬이 된다. 중위 순회로 원소에 접근한다. (중위 순회는 트리에서 루트 노드를 중간순서에 방문하는 순회) 자세한 개념은 아래의 블로그를 참고하자 https:..

map을 활용한 기본적인 문제 #include #include using namespace std; int n; map m; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; while (n--) { string s; cin >> s; ++(m[s]); } pair p; int max = 0; for (auto s : m) { if (s.second > max) { max = s.second; p = s; } } cout

#include #include using namespace std; class Node { public: int data; Node* next; Node(int data) { this->data = data; this->next = NULL; } }; class LinkedList { public: Node* f; Node* r; LinkedList() { f = NULL; r = NULL; } ~LinkedList() { } int front() { return f->data; } int end() { return r->data; } void addBack(int data) { Node* n = new Node(data); if (f == NULL) { f = r = n; } else { r->nex..