개발일지

문제설명 입출력 예제 개념 다양한 수를 처리하는 문제다. 산술 평균, 중앙값, 범위는 간단하게 해결할 수 있지만, 최빈값을 처리하는 과정이 까다롭고, 시간 초과에 자주 걸리므로 알고리즘 최적화를 잘해야 한다. 풀이 #include #include #include #include #include using namespace std; int main() { int N, sum = 0; cin >> N; vector v(N); unordered_map freq; 수의 개수 N, 산술 평균을 계산하기 위한 sum, 중앙값과 범위를 계산하기 위한 벡터 v, 최빈값을 계산하기 위한 해시맵 freq를 초기화한다. for (int i = 0; i > v[i]; sum += v[i]; fr..

문제설명 입출력 예제 개념 ChongChong과 만난 사람은 무지개 댄스를 추게 되므로, key로 아이디를 갖고 value로 무지개 댄스 여부를 확인할 수 있는 map 자료구조를 사용하면 쉽게 풀 수 있다. 즉, 문자열을 검사해 총총이를 만났으면 value값을 true로 바꾸면 된다. 풀이 #include #include using namespace std; int main() { int N, count = 0; cin >> N; map m; string str1, str2; 사람들이 만난 기록의 수 N, 무지개 댄스를 추는 사람의 수 count, 이러한 정보를 기록할 맵 자료구조 m, 사람들의 이름을 초기화할 문자열 str1, str2을 초기화한다. while (N--) { cin >> str1 >> ..

"; Insert(oldkey, count + 1, 2); } } else { int value = hash2(key); if (_table2[value] == -1) { std::cout

문제설명 입출력 예제 개념 엔터가 입력되고 난 후 들어온 사람의 숫자를 계산하는 문제다. enter가 입력되고 나서 중복되지 않은 사람의 수를 카운트하면 되므로, 자료구조 set을 이용하면 쉽게 풀 수 있다. 풀이 #include #include using namespace std; int main() { int N, count = 0; cin >> N; set m; string str; 채팅방의 기록 수 N, 곰곰티콘이 사용된 횟수 count, 집합 m, 유저 str을 초기화한다. while (N--) { cin >> str; if (str == "ENTER") { count += m.size(); m.clear(); continue; } m.insert(str); } count += m.size();..

문제설명 입출력 예제 개념 N번 째 창문이 열려 있으려면, 열고 닫은 횟수가 홀수번이어야 한다. 따라서 N의 약수의 개수가 홀수개여야 하고, 이런 특성을 만족하는 것은 제곱수다. 약수는 두 수가 짝을 이루어 곱해지므로 자연수의 약수의 개수는 짝수지만, 제곱수는 자기 자신을 곱하는 수가 추가되므로 홀수가 된다. 따라서 주어진 범위 내의 제곱수의 개수를 구하면 문제를 해결할 수 있다. 풀이 #include int main() { int N, count = 0; std::cin >> N; for(int i = 1; i * i

개요 게임을 진행하다 보면 NPC와 대화하는 일이 잦다. 이때 NPC가 출력하는 메시지를 보면, 마치 말을 하듯이 글자가 하나씩 출력되는 것을 볼 수 있는데, 이러한 효과를 어떻게 구현했는지 궁금증이 생겼다. 관련 자료들을 알아본 결과, 유니티에서 제공하는 코루틴 메서드를 이용하면 된다는 것을 알았다. 코루틴(Coroutine) 코루틴(coroutine)은 작업을 다수의 프레임에 분산할 수 있게 하는 기능이라고 한다. 즉, 원하는 시간만큼 함수를 멈춘 뒤 시작하게 할 수 있는 기능을 구현한 함수로서, 글자를 깜빡이게(twinkle) 출력하는 등의 기능을 구현할 때 유용하게 사용된다. 이때 시간 지연을 도입하려면 WaitForSeconds를 사용하면 된다. 예를 들어, 3초 뒤 텍스트의 색을 red로 바꾸..

문제설명 입출력 예제 개념 주어진 정수 N(짝수)을 두 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 문제다. 예를 들어, 10을 입력하면 10 = 3 + 7, 5 + 5로 2개가 출력된다. 이때 소수의 순서만 다른 것은 같은 파티션인 것에 유의하자. 문제의 시간 제한이 매우 빡빡하기 때문에, 에라토스테네스의 체 알고리즘을 사용하여 주어진 범위 내의 소수를 미리 구한 후, 구한 소수들을 활용하여 문제를 해결할 수 있다. 이러한 알고리즘은 시간 복잡도가 O(Nlog(log(N))) 으로 매우 빠르다. 풀이 #include #include #include using namespace std; const int n = 1000000; vector isprime(n + 1, true); int main() ..

문제설명 입출력 예제 개념 자연수 n과 2n 사이의 소수의 개수를 출력하는 문제다. O(sqrt(N)) 보다 조금 더 세밀한 시간 조정이 필요하다. 풀이 #include using namespace std; bool IsPrime(long long num) { if (num N; if (N == 0) break; for (int i = N + 1; i

충돌 해결체이닝(Chaining)　해시 충돌 문제를 해결하는 첫 번째 방법인 체이닝 기법에서는 충돌이 발생한 지점에서 연결 리스트를 만든다. 즉, 이 방법은 해시 테이블의 특정 위치에서 하나의 연결 리스트를 저장하여, 충돌이 발생하면 리스트의 맨 뒤에 새로운 키를 추가하는 방식이다.  　연결 리스트는 포인터를 이용하여 다음 노드를 가리키기 때문에, 메모리를 재사용하지 않아 중간에 요소를 삽입하거나 삭제하는 경우에도 O(1) 시간에 수행할 수 있다는 장점이 있다. 그리고 배열과 다르게 데이터가 흩어져 있지 않고 연속된 메모리 공간을 차지하지 않으므로, 캐시 효율성이 높다. 　이러한 체이닝 기법을 이용하여 이전 충돌 문제를 해결해 보자. #include #include #include #include cla..

문제설명 입출력 예제 개념 주어진 범위 내의 소수를 찾는 문제다. 이전에 포스팅했던 소수 찾는 알고리즘을 활용하면 쉽게 풀 수 있다. 풀이 #include bool IsPrime(int n) { if (n m >> n; for (int i = m; i