🗒️ 알고리즘 (45)

1. 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..
2. 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..
3. 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까지 순회하는 수 중에서,..
4. 2020.11.15 [Project Euler #4][C++] 세자리 수를 곱해 만들 수 있는 가장 큰 대칭수

   문제4 : 세자리 수를 곱해 만들 수 있는 가장 큰 대칭수 문제 앞에서부터 읽을 때나 뒤에서부터 읽을 때나 모양이 같은 수를 대칭수(palindrome)라고 부릅니다. 두 자리 수를 곱해 만들 수 있는 대칭수 중 가장 큰 수는 9009 (= 91 × 99) 입니다. 세 자리 수를 곱해 만들 수 있는 가장 큰 대칭수는 얼마입니까? 문제 해결 방법 팰린드롬 찾기 알고리즘 을 이용하여 문제를 해결하였다.우선, 팰린드롬 검사 함수(bool findPalindrome(string ary))를 만들었다.2중 for 문을 사용하여 100부터 999까지 순회를 하면서 곱한 수를 string형으로 바꾼 후(to_string(i * j)), 하나하나씩 팰린드롬 검사를 수행하였다. (findPalindrome(to_stri..
5. 2020.11.11 피보나치 수열(Fibonacci Sequence)

   피보나치 수열(Fibonacci Sequence)의 점화식은 다음과 같다. $F_{n}:=\begin{cases} 0 \quad (\text{if} \quad n = 1) \\ 1 \quad (\text{if} \quad n = 2) \\ F_{n-1} + F_{n-2} \quad (\text{if} \quad n > 2) \end{cases}$ 이 점화식을 바탕으로 구한 피보나치 수열의 항과 값은 다음과 같다. 항 1 2 3 4 5 6 7 8 9101112131415161718... 값 0 1 1 2 3 5 8 13 213455891442333776109871597... 피보나치 수열은 재귀 함수 또는 반복문을 이용하여 구현할 수 있다. 1. 반복문을 이용하여 구현하기 123456789101112131..
6. 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() ..
7. 2020.11.02 버블 정렬(Bubble Sort)

   *버블 정렬(Bubble Sort) 12345678910111213141516171819202122232425#include #define SIZE 5 int main() { int i, k; int list[SIZE] = {16, 7, 9, 1, 3}; // 배열의 요소 정렬 for (k = 0; k
8. 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..
9. 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백만 번 수행 하는 작업을 반복하였고, 계속 오답 처리가 되어 멘탈이 붕괴되는 상황을 맞닥드리게 되었다.문제 번역자가 변..
10. 2020.10.24 [Project Euler #1][C++] 1000보다 작은 자연수 중에서 3 또는 5의 배수를 모두 더하면?

    문제1 : 1000보다 작은 자연수 중에서 3 또는 5의 배수를 모두 더하면? 문제 10보다 작은 자연수 중에서 3 또는 5의 배수는 3, 5, 6, 9 이고, 이것을 모두 더하면 23입니다. 1000보다 작은 자연수 중에서 3 또는 5의 배수를 모두 더하면 얼마일까요? 문제 해결 방법 for 문을 사용하여 1이상 1000 미만의 범위에서 해당 수가 3 또는 5로 나누어질 경우, 그 값들의 축적합을 구하도록 프로그램을 구현하였다. 소스 코드 123456789101112131415161718#include using namespace std; #define MAX_NUM 1000 int main() { int sum = 0; for (int i = 1; i
11. 2020.10.24 [BOJ1712][C++] 손익분기점

    문제월드전자는 노트북을 제조하고 판매하는 회사이다. 노트북 판매 대수에 상관없이 매년 임대료, 재산세, 보험료, 급여 등 A만원의 고정 비용이 들며, 한 대의 노트북을 생산하는 데에는 재료비와 인건비 등 총 B만원의 가변 비용이 든다고 한다. 예를 들어 A=1,000, B=70이라고 하자. 이 경우 노트북을 한 대 생산하는 데는 총 1,070만원이 들며, 열 대 생산하는 데는 총 1,700만원이 든다. 노트북 가격이 C만원으로 책정되었다고 한다. 일반적으로 생산 대수를 늘려 가다 보면 어느 순간 총 수입(판매비용)이 총 비용(=고정비용+가변비용)보다 많아지게 된다. 최초로 총 수입이 총 비용보다 많아져 이익이 발생하는 지점을 손익분기점(BREAK-EVEN POINT)이라고 한다. A, B, C가 주어졌을..
12. 2020.10.24 [BOJ1193][C++] 분수 찾기

    문제무한히 큰 배열에 다음과 같이 분수들이 적혀있다. 1/11/21/31/41/5...2/12/22/32/4......3/13/23/3.........4/14/2............5/1.................................이와 같이 나열된 분수들을 1/1 -> 1/2 -> 2/1 -> 3/1 -> 2/2 -> … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자. X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다. 출력첫째 줄에 분수를 출력한다. 예제 입력 1 14 예제 출력 1 2/4 출처· 문제를 만든 사람: author6· 문제의 오타를 찾은 사람: dead..
13. 2020.08.13 탐욕 알고리즘(Greedy Algorithm)

    *탐욕 알고리즘 탐욕 알고리즘(Greedy Algorithm) - 결과값에 대하여 생각하지 않고 최선의 옵션을 선택하여 문제를 해결하는 알고리즘 - 즉, 지역적(locally)의 최선의 선택이 전역적(globally)의 최상의 결과값을 생성하도록 하는 것을 목표로 하는 알고리즘.- 미리 정한 기준에 따라서 매번 가장 좋아 보이는 답을 선택하는 알고리즘 - 탐욕 알고리즘은 해답에 포함될 원소들을 차례로 선택하는 과정을 거치게 됨 - 각 단계에서는 전체적인 상황을 종합적으로 판단하고, 고려하여 결정하는 것이 아니라 현 시점의 정보 를 바탕으로 가장 이익이 되는 원소들을 선택함. - 동적 계획법(Dynamic Programming)과 마찬가지로 최적화 문제(Optimization Problem) 를 푸는데 사..
14. 2020.06.08 Union-Find 알고리즘(서로소 집합 알고리즘)

    *Union-Find 알고리즘 - Disjoint-Set(서로소 집합) 알고리즘이라고 불린다. - 지금 추가하고자 하는 간선의 양끝 정점이 같은 집합에 속해 있는지를 검사하는 알고리즘.- 간선의 양끝 정점이 서로 다른 집합에 속하는 경우, 두 정점을 연결하여도 사이클이 형성되지 않는다.- Kruskal MST 알고리즘을 구현하는데 사용된다. #include #define MAX_VERTICES 100 int parent[MAX_VERTICES]; // 부모 노드int num[MAX_VERTICES]; // 각 집합의 크기 // 초기화void set_init(int n) { int i; for (i = 0; i < n; i++) { parent[i] = -1; num[i] = 1; }} // vertex가..
15. 2017.06.18 [C] 정렬(Sorting)

    정렬(Sorting) - 정렬(sorting) : 물건을 크기순으로 오름차순(ascending order)이나 내림차순(descending order)으로 나열하는 것. - 정렬은 컴퓨터공학을 포함한 모든 과학 기술 분야에서 가장 기본적이고 중요한 알고리즘 중의 하나로 일상생활에서 많이 사용됨. - 정렬은 자료 탐색에 있어서 필수적임. - 일반적으로 정렬시켜야 될 대상은 레코드(record)라고 불림. - 레코드는 다시 필드(field)라고 하는, 더 작은 단위로 나누어짐. - 여러 필드 중에서 특별히 레코드와 레코드를 식별해주는 역할을 하는 필드를 키(key)라고 함. 레코드 { [필드][필드][필드][필드][필드][필드][필드][필드][필드][필드] 레코드 { [필드][필드][필드][필드][필드][필..