🗒️ C++ (64)

1. 2021.04.13 [BOJ5618][C++] 공약수

   시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 256 MB 3857 1932 1682 59.205% 문제 자연수 n개가 주어진다. 이 자연수의 공약수를 모두 구하는 프로그램을 작성하시오. 입력 첫째 줄에 n이 주어진다. n은 2 또는 3이다. 둘째 줄에는 공약수를 구해야 하는 자연수 n개가 주어진다. 모든 자연수는 $10^8$ 이하이다. 출력 입력으로 주어진 n개 수의 공약수를 한 줄에 하나씩 증가하는 순서대로 출력한다. 예제 입력 1 2 75 125 예제 출력 1 1 5 25 출처 Olympiad > 일본정보올림피아드 > 일본정보올림피아드 예선 > JOI 2006 모의고사 1 2번 문제를 번역한 사람: baekjoon 데이터를 추가한 사람: njw1204 알고리즘 분류 수학 코드 1 2..
2. 2021.02.17 [C++] 정수를 입력 받아 각 자릿수의 합 구하기

   정수를 입력 받아 각 자릿수의 합 구하기 정수를 입력 받아 각 자릿수의 합을 구하려면 다음과 같이 사용하면 된다. ■ 알고리즘 1. 입력 받은 수(num)와 10을 나머지 연산을 수행한 후, 결과값을 sum 변수에 계속 더해준다. (sum += num % 10) 2. 입력 받은 수(num)을 10으로 계속 나누어준다. (num /= 10) 3. 입력 받은 수가 0이 될 때까지 1, 2번 과정을 반복한다. ■ 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 #include using namespace std; int main() { int num, sum = 0; cin >> num; while (num != 0) { sum += num % 10; num /= 10; } cout
3. 2021.02.08 [BOJ2455][C++] 지능형 기차

   문제 최근에 개발된 지능형 기차가 1번역(출발역)부터 4번역(종착역)까지 4개의 정차역이 있는 노선에서 운행되고 있다. 이 기차에는 타거나 내리는 사람 수를 자동으로 인식할 수 있는 장치가 있다. 이 장치를 이용하여 출발역에서 종착역까지 가는 도중 기차 안에 사람이 가장 많을 때의 사람 수를 계산하려고 한다. 단, 이 기차를 이용하는 사람들은 질서 의식이 투철하여, 역에서 기차에 탈 때, 내릴 사람이 모두 내린 후에 기차에 탄다고 가정한다. 내린 사람 수탄 사람 수1번역(출발역)2번역3번역4번역(종착역) 0 32 3 13 28 25 39 0 예를 들어, 위와 같은 경우를 살펴보자. 이 경우, 기차 안에 사람이 가장 많은 때는 2번역에서 3명의 사람이 기차에서 내리고, 13명의 사람이 기차에 탔을 때로, ..
4. 2021.02.05 [BOJ10757][C++] 큰 수 A + B

   문제 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 A와 B가 주어진다. (0 < A,B < $10^{10000}$) 출력 첫째 줄에 A+B를 출력한다. 예제 입력 1 9223372036854775807 9223372036854775808 예제 출력 1 18446744073709551615 출처 문제를 만든 사람: baekjoon 데이터를 추가한 사람: dlaud5379, gcon16 문제의 오타를 찾은 사람: jh05013 알고리즘 분류 수학 구현 사칙연산 임의 정밀도 / 큰 수 연산 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 3..
5. 2021.02.04 [BOJ15596][C++] 정수 N개의 합

   문제 정수 n개가 주어졌을 때, n개의 합을 구하는 함수를 작성하시오. 작성해야 하는 함수는 다음과 같다. C, C11, C (Clang), C11 (Clang): long long sum(int *a, int n); a: 합을 구해야 하는 정수 n개가 저장되어 있는 배열 (0 ≤ a[i] ≤ 1,000,000, 1 ≤ n ≤ 3,000,000) n: 합을 구해야 하는 정수의 개수 리턴값: a에 포함되어 있는 정수 n개의 합 C++, C++11, C++14, C++17, C++ (Clang), C++11 (Clang), C++14 (Clang), C++17 (Clang): long long sum(std::vector &a); a: 합을 구해야 하는 정수 n개가 저장되어 있는 배열 (0 ≤ a[i] ≤ ..
6. 2021.01.29 main(int argc, char* argv[])

   1 2 3 4 5 6#include using namespace std; int main(int argc, char* argv[]) { } main 함수는 프로그램에서 최초로 실행이 된다.main 함수의 매개변수로는 int형의 argc, char* 형의 argv[]가 있다. main 함수의 매개변수에 대한 설명은 각각 다음과 같다. int argc : main 함수에 전달되는 데이터의 개수char* argv[] : main 함수에 전달되는 실제적인 데이터, char형 포인터 배열로 구성됨. argv[0]에는 프로그램의 절대 경로가, argv[1] 부터는 입력받은 문자가 대입됨. > example.cpp 1 2 3 4 5 6 7 8 9 10 11#include using namespace std; int ..
7. 2021.01.20 Python Range() 함수 구현

   C++를 이용하여 Python의 Range 함수를 구현해보았다.
8. 2021.01.12 비교/관계 연산자 오버로딩 예

   123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114#include #include #include // using namespace std; class String { char* _chars;public: String(const char* chars) : _chars(new char[strlen(chars) + 1]) { strcpy(_cha..
9. 2021.01.04 [Project Euler #17][C++] 1부터 1000까지 영어로 썼을 때 사용된 글자의 개수는?

   문제17 : 1부터 1000까지 영어로 썼을 때 사용된 글자의 개수는? 문제 1부터 5까지의 수를 영어로 쓰면 one, two, three, four, five 이고, 각 단어의 길이를 더하면 3 + 3 + 5 + 4 + 4 = 19 이므로 사용된 글자는 모두 19개입니다. 1부터 1,000까지 영어로 썼을 때는 모두 몇 개의 글자를 사용해야 할까요? 참고: 빈 칸이나 하이픈('-')은 셈에서 제외하며, 단어 사이의 and 는 셈에 넣습니다. 예를 들어 342를 영어로 쓰면 three hundred and forty-two 가 되어서 23 글자, 115 = one hundred and fifteen 의 경우에는 20 글자가 됩니다. 문제 해결 방법 100 이상의 수의 경우, 100으로 나누어 떨어지는 수..
10. 2020.12.31 [Project Euler #16][C++] $2^{1000}$ 의 각 자릿수를 모두 더하면?

    문제16 : $2^{1000}$ 의 각 자릿수를 모두 더하면? 문제 $2^{15} = 32768$ 의 각 자릿수를 더하면 3 + 2 + 7 + 6 + 8 = 26 입니다. $2^{1000}$ 의 각 자릿수를 모두 더하면 얼마입니까? 문제 해결 방법 2^{1000}21000 은 너무나 큰 수이기에 C++ 의 정수형 변수에 대입할 수 없다. 그래서 string 자료형을 이용하여 문제를 해결하였다.내용 참고 : click참고char형 숫자 -> int형 숫자 : char형 숫자 - '0'int형 숫자 -> char형 숫자 : int형 숫자 + '0' 소스 코드 정답 1366 심화 공부 숫자의 거듭제곱 계산(Computing Powers of a Number) x를 nn번 곱한 수를 x^nxn이라 한다. 현재의..
11. 2020.12.28 프로그램 실행 시간 측정 방법 (clock())

    12345678910#include // clock() : ms 단위로 시간 측정 void main() { clock_t start = clock(); // algorithm clock_t end = clock(); std::cout
12. 2020.12.28 0부터 N까지 피보나치 수열 나열하기

    입력을 받으면, 입력한 수까지 피보나치 수열을 나열하는 프로그램 for 문/while 문/do while 문으로 간단하게 구현함.(+ 재귀 함수/ goto 문 이용하기) 시간 복잡도 : O(n) 200 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
13. 2020.12.28 [Project Euler #15][C++] 20×20 격자의 좌상단에서 우하단으로 가는 경로의 수

    문제15 : 20×20 격자의 좌상단에서 우하단으로 가는 경로의 수 문제 아래와 같은 2 × 2 격자의 왼쪽 위 모서리에서 출발하여 오른쪽 아래 모서리까지 도달하는 길은 모두 6가지가 있습니다 (거슬러 가지는 않기로 합니다). 그러면 20 × 20 격자에는 모두 몇 개의 경로가 있습니까? 문제 해결 방법 격자에서 최단 경로의 수 를 찾는 문제이다.규칙성을 찾아 문제를 해결하였다.배열 ary[20][20]에서 ary[n][n] = ary[n - 1][n] + ary[n][n - 1]이다.for 문을 사용하여 ary[x][0]과 ary[0][x]의 값을 모두 1로 설정하였다.그리고 또 다른 for 문을 사용하여 찾은 규칙성을 바탕으로 배열에 값을 채워서 최종적으로 ary[SIZE][SIZE]에 있는 값이 출..
14. 2020.12.28 [Project Euler #14][C++] 백만 이하로 시작하는 우박수 중 가장 긴 과정을 거치는 것은?

    문제14 : 백만 이하로 시작하는 우박수 중 가장 긴 과정을 거치는 것은? 문제 양의 정수 n에 대하여, 다음과 같은 계산 과정을 반복하기로 합니다.n → n / 2 (n이 짝수일 때) n → 3n + 1 (n이 홀수일 때) 13에 대하여 위의 규칙을 적용해보면 아래처럼 10번의 과정을 통해 1이 됩니다. 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 아직 증명은 되지 않았지만, 이런 과정을 거치면 어떤 수로 시작해도 마지막에는 1로 끝나리라 생각됩니다.(역주: 이것은 콜라츠 추측(Collatz Conjecture)이라고 하며, 이런 수들을 우박수(Hailstone Sequence)라 부르기도 합니다)그러면, 백만(1,000,000) 이하의 수로 시작했을 때 1까지 도달하는..
15. 2020.12.27 [Project Euler #13][C++] 50자리 수 100개를 더한 값의 첫 10자리 구하기

    문제13 : 50자리 수 100개를 더한 값의 첫 10자리 구하기 문제 아래에 50자리 수가 100개 있습니다. 이것을 모두 더한 값의 첫 10자리는 얼마입니까?37107287533902102798797998220837590246510135740250 46376937677490009712648124896970078050417018260538 74324986199524741059474233309513058123726617309629 91942213363574161572522430563301811072406154908250 23067588207539346171171980310421047513778063246676 89261670696623633820136378418383684178734361726757 28..
16. 2020.12.26 [Project Euler #12][C++] 500개 이상의 약수를 갖는 가장 작은 삼각수는?

    문제12 : 500개 이상의 약수를 갖는 가장 작은 삼각수는? 문제 1부터 n까지의 자연수를 차례로 더하여 구해진 값을 삼각수라고 합니다. 예를 들어 7번째 삼각수는 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28이 됩니다. 이런 식으로 삼각수를 구해 나가면 다음과 같습니다. 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ... 이 삼각수들의 약수를 구해 봅시다. 1: 1 3: 1, 3 6: 1, 2, 3, 6 10: 1, 2, 5, 10 15: 1, 3, 5, 15 21: 1, 3, 7, 21 28: 1, 2, 4, 7, 14, 28 위에서 보듯이, 5개 이상의 약수를 갖는 첫번째 삼각수는 28입니다.그러면 500개 이상의 약수를 갖는 가장 작은 삼각수는 얼마입니까? 문제 해..
17. 2020.12.26 숫자 N의 약수의 개수 구하기

    *숫자 N의 약수의 개수 구하기 1부터 N까지 for문을 돌리면서 나누어 떨어지는 수가 있으면(i % N == 0) 카운트를 증가시켜(count++) 최종적으로 카운터를 출력하면 끝. 123456789101112131415161718#include using namespace std; int checkCommonDivisor(int n) { int count = 0; for (register int i = 1; i
18. 2020.12.26 단축 평가 논리 계산법(Short-Circuit Evaluation)

    *단축 평가 논리 계산법(Short-Circuit Evaluation) AND 혹은 OR의 연산에 있어서 결과가 확실하게 예측이 되었을 때 뒤에 나머지 연산을 실행하지 않고 답을 내버리는 것AND 연산의 경우false가 우선 나와버리면 AND 뒤에 나오는 연산은 생략OR 연산의 경우true가 우선 나와버리면 OR 뒤에 나오는 연산은 생략#include using namespace std; int main() { bool result; // AND result = printf("") && printf("ABC"); result = printf("1") && printf("ABC"); cout
19. 2020.12.26 [Project Euler #11][C++] 20×20 격자에서 연속된 네 수의 곱 중 최댓값

    문제11 : 20×20 격자에서 연속된 네 수의 곱 중 최댓값 문제 아래와 같은 20×20 격자가 있습니다.08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00 81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65 52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91 22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80 24 47 32 60 99 03 45 02 44 75 33 53 78..
20. 2020.12.24 [Project Euler #10][C++]이백만 이하 소수의 합

    문제10 : 이백만 이하 소수의 합 문제 10 이하의 소수를 모두 더하면 2 + 3 + 5 + 7 = 17 이 됩니다. 이백만(2,000,000) 이하 소수의 합은 얼마입니까? 문제 해결 방법 하나하나씩 계산하는 방식(브루트 포스 방식)으로 문제를 해결하였다. (에라토스네스 체 알고리즘 사용)정답을 구하는데 약 20분 이 걸렸다. (...)for 문을 사용하여 문제를 해결하였다.2부터 N(2000000)까지 순회를 하며 소수를 찾으면 sum 변수에 대입하고 더하는 과정을 반복하였다.최종적으로 sum 변수에 할당된 값을 출력하도록 하였다. 소스 코드 1234567891011121314151617181920212223242526272829#include using namespace std; #define N..
21. 2020.12.23 [Project Euler #9][C++] a + b + c = 1000 이 되는 피타고라스 수

    문제9: a + b + c = 1000 이 되는 피타고라스 수 문제 세 자연수 a, b, c 가 피타고라스 정리 a² + b² = c² 를 만족하면 피타고라스 수라고 부릅니다 (여기서 a < b < c).예를 들면 3² + 4² = 9 + 16 = 25 = 5²이므로 3, 4, 5는 피타고라스 수입니다. a + b + c = 1000 인 피타고라스 수 a, b, c는 한 가지 뿐입니다. 이 때, a × b × c 는 얼마입니까? 문제 해결 방법 하나하나씩 계산하는 방식(브루트 포스 방식)으로 문제를 해결하였다.3중 for문을 사용하여1부터 N(1000)까지 순회를 하며 다음의 조건을 만족시켰을 때의 a, b, c 값의 곱을 ans 변수에 할당하였다.a < b < c(a * a) + (b * b) == (..
22. 2020.12.22 [Project Euler #8][C++] 1000자리 수 안에서 이어지는 5개 숫자의 곱 중 최댓값은?

    문제8: 1000자리 수 안에서 이어지는 5개 숫자의 곱 중 최댓값은? 문제 다음은 연속된 1000자리 수입니다 (읽기 좋게 50자리씩 잘라 놓음). 73167176531330624919225119674426574742355349194934969835203127745063262395783180169848018694788518438586156078911294949545950173795833195285320880551112540698747158523863050715693290963295227443043557668966489504452445231617318564030987111217223831136222989342338030813533627661428280644448664523874930358907296290..
23. 2020.12.22 [Project Euler #7][C++] 10001번째의 소수

    문제7: 10001번째의 소수 문제 소수를 크기 순으로 나열하면 2, 3, 5, 7, 11, 13, ... 과 같이 됩니다. 이 때 10,001번째의 소수를 구하세요. 문제 해결 방법 하나하나씩 계산하는 방식(브루트 포스 방식)으로 문제를 해결하였다.2중 for문을 사용하여1부터 N까지 순회를 하면서 소수의 조건(나머지가 1과 그 자신인 수) 을 만족시키는 수가 발견될 경우 count의 값을 1씩 증가시켰다.count의 값이 NUM(10001)이 되었을 때의 값을 ans 변수에 할당하고, 2중 for문에서 빠져나오도록 하였다.NUM(10001)번째 소수가 담긴 ans 변수의 값을 출력하도록 하였다.연산을 빠르게 하도록 하기 위해 register 변수를 사용하여 for문을 순회하도록 하였다. 소스 코드 1..
24. 2020.12.22 [Project Euler #6][C++] 1부터 100까지 "제곱의 합"과 "합의 제곱"의 차는?

    문제6: 1부터 100까지 "제곱의 합"과 "합의 제곱"의 차는? 문제 1부터 10까지 자연수를 각각 제곱해 더하면 다음과 같습니다 (제곱의 합). $1^{2} + 2^{2} + ... + 10^{2} = 385$ 1부터 10을 먼저 더한 다음에 그 결과를 제곱하면 다음과 같습니다 (합의 제곱). $(1 + 2 + ... + 10)^{2} = 55^{2} = 3025$ 따라서 1부터 10까지 자연수에 대해 "합의 제곱"과 "제곱의 합" 의 차이는 3025 - 385 = 2640 이 됩니다. 그러면 1부터 100까지 자연수에 대해 "합의 제곱"과 "제곱의 합"의 차이는 얼마입니까? 문제 해결 방법 하나하나씩 계산하는 방식(브루트 포스 방식)으로 문제를 해결하였다.for문을 사용하여자연수 1부터 N(100)..
25. 2020.11.16 [Project Euler #5][C++] 1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수

    문제5 : 1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수 문제 1 ~ 10 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 2520입니다. 그러면 1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 얼마입니까? 문제 해결 방법 하나하나씩 계산하는 방식(브루트 포스 방식)으로 문제를 해결하였다.문제의 조건을 만족시키는 범위를 알 수 없는 수를 찾기 위해 unsigned long long int 자료형을 사용하였다.표현 가능 범위 : 0 ~ 18,446,744,073,709,551,6152중 for 문을 사용하였다.시간 복잡도 : O(n²)1부터 ULLONG_MAX까지 순회하는 for 문1부터 N(20)까지 순회하는 for 문1부터 ULLONG_MAX까지 순회하는 수 중에서,..
26. 2020.11.05 [BOJ10773][C++] 제로

    문제나코더 기장 재민이는 동아리 회식을 준비하기 위해서 장부를 관리하는 중이다. 재현이는 재민이를 도와서 돈을 관리하는 중인데, 애석하게도 항상 정신없는 재현이는 돈을 실수로 잘못 부르는 사고를 치기 일쑤였다. 재현이는 잘못된 수를 부를 때마다 0을 외쳐서, 가장 최근에 재민이가 쓴 수를 지우게 시킨다. 재민이는 이렇게 모든 수를 받아 적은 후 그 수의 합을 알고 싶어 한다. 재민이를 도와주자! 입력첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경우 해당 수를 쓴다. 정수가 "0"일 경우에 지울 수 있는 수가 있음을 보장할 수..
27. 2020.11.03 [BOJ10808][C++] 알파벳 개수

    문제알파벳 소문자로만 이루어진 단어 S가 주어진다. 각 알파벳이 단어에 몇 개가 포함되어 있는지 구하는 프로그램을 작성하시오. 입력첫째 줄에 단어 S가 주어진다. 단어의 길이는 100을 넘지 않으며, 알파벳 소문자로만 이루어져 있다. 출력단어에 포함되어 있는 a의 개수, b의 개수, …, z의 개수를 공백으로 구분해서 출력한다. 예제 입력 1 baekjoon 예제 출력 1 1 1 0 0 1 0 0 0 0 1 1 0 0 1 2 0 0 0 0 0 0 0 0 0 0 0 알고리즘 분류· 구현· 문자열 코드 123456789101112131415161718192021222324#include #include using namespace std; #define SIZE 26 // a부터 z까지 int main() ..
28. 2020.10.26 [Project Euler #3][C++] 가장 큰 소인수 구하기

    문제3: 가장 큰 소인수 구하기 문제 어떤 수를 소수의 곱으로만 나타내는 것을 소인수분해라 하고, 이 소수들을 그 수의 소인수라고 합니다.예를 들면 13195의 소인수는 5, 7, 13, 29 입니다. 600851475143의 소인수 중에서 가장 큰 수를 구하세요. 문제 해결 방법 소인수 분해 알고리즘 을 이용하여 문제를 해결하였다.어떤 수 num를 소인수 분해 하려면 num를 2부터 차례대로 num의 제곱근까지의 숫자로 나누어 떨어지는지 검사하면 된다.플로우 차트를 기반으로 문제를 해결하여도 되지만, 코드가 길어지기 때문에 while 문을 사용하여 문제를 해결하였다. 소스 코드 1234567891011121314151617181920#include using namespace std; long long..
29. 2020.10.25 scanf() 입력 버퍼 비우는 방법

    *scanf() 입력 버퍼 비우는 방법 scanf()를 사용하다 보면, 입력을 정상적으로 받지 못할 경우가 생기게 된다.이러한 종류의 문제는 입력 버퍼(stdin Buffer)와 관련된 문제가 대부분이며, 이 문제를 해결하기 위해서는 입력 버퍼를 비워줘야 한다.입력 버퍼를 비우는 방법을 이 글에 총정리 해보았다. #pragma warning(disable: 4996) #include int main() { char ch; scanf("%c", &ch); printf("1, %c\n", ch); scanf("%c", &ch); printf("2, %c\n", ch); return 0; } a 1, a 2, ab 1, a 2, b 무슨 일이 일어났는지 확인해 보기 위하여 다음과 같이 코드를 수정해서 프로그램..
30. 2020.10.24 [Project Euler #2][C++] 피보나치 수열에서 4백만 이하이면서 짝수인 항의 합

    문제2 : 피보나치 수열에서 4백만 이하이면서 짝수인 항의 합 문제 피보나치(Fibonacci) 수열의 각 항은 바로 앞의 항 두 개를 더한 것입니다. 1과 2로 시작하는 경우 이 수열은 아래와 같습니다. 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...4백만 이하의 짝수 값을 갖는 모든 피보나치 항을 더하면 얼마가 됩니까? 문제 해결 방법 문제의 조건을 잘 확인해야 한다.4백만 이하의 짝수 값 을 갖는 모든 피보나치 항을 더하라.즉, 피보나치 항의 값이 4백만 이하인 수 중에서 짝수 값을 갖는 모든 피보나치 항을 더하는 문제이다.나는 문제를 잘못 이해해서 연산을 4백만 번 수행 하는 작업을 반복하였고, 계속 오답 처리가 되어 멘탈이 붕괴되는 상황을 맞닥드리게 되었다.문제 번역자가 변..