문제 칸토어 집합은 0과 1사이의 실수로 이루어진 집합으로, 구간 [0, 1]에서 시작해서 각 구간을 3등분하여 가운데 구간을 반복적으로 제외하는 방식으로 만든다. 전체 집합이 유한이라고 가정하고, 다음과 같은 과정을 통해서 칸토어 집합의 근사를 만들어보자. 1. -가 3N개 있는 문자열에서 시작한다. 2. 문자열을 3등분 한 뒤, 가운데 문자열을 공백으로 바꾼다. 이렇게 하면, 선(문자열) 2개가 남는다. 3. 이제 각 선(문자열)을 3등분 하고, 가운데 문자열을 공백으로 바꾼다. 이 과정은 모든 선의 길이가 1일때 까지 계속 한다. 예를 들어, N=3인 경우, 길이가 27인 문자열로 시작한다. --------------------------- 여기서 가운데 문자열을 공백으로 바꾼다. ---------..

문제 오늘도 서준이는 병합 정렬 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. N개의 서로 다른 양의 정수가 저장된 배열 A가 있다. 병합 정렬로 배열 A를 오름차순 정렬할 경우 배열 A에 K 번째 저장되는 수를 구해서 우리 서준이를 도와주자. 크기가 N인 배열에 대한 병합 정렬 의사 코드는 다음과 같다. merge_sort(A[p..r]) { # A[p..r]을 오름차순 정렬한다. if (p < r) then { q

문제 정휘는 후배들이 재귀 함수를 잘 다루는 재귀의 귀재인지 알아보기 위해 재귀 함수와 관련된 문제를 출제하기로 했다. 팰린드롬이란, 앞에서부터 읽었을 때와 뒤에서부터 읽었을 때가 같은 문자열을 말한다. 팰린드롬의 예시로 AAA, ABBA, ABABA 등이 있고, 팰린드롬이 아닌 문자열의 예시로 ABCA, PALINDROME 등이 있다. 어떤 문자열이 팰린드롬인지 판별하는 문제는 재귀 함수를 이용해 쉽게 해결할 수 있다. 아래 코드의 isPalindrome 함수는 주어진 문자열이 팰린드롬이면 1, 팰린드롬이 아니면 0을 반환하는 함수다. #include #include int recursion(const char *s, int l, int r){ if(l >= r) return 1; else if(s[l..

문제 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 정수 N(0 ≤ N ≤ 20)이 주어진다. 출력 첫째 줄에 N!을 출력한다. 풀이 이 문제는 재귀에 대한 기본적인 내용을 담고 있다. 다만 주의할 점은 입력의 범위를 확인하고 int로 표현할 수 있는 수의 범위를 넘어가는 것을 알아야 한다.

[문제] & [결과] [해설] 이 문제는 두 수를 입력받고 그 두 수 사이에서 소수를 골라서 소수들의 합과 소수들의 최솟값을 구하는 문제이다. 아래의 코드의 메커니즘은 이렇다. 먼저 두 수를 입력받으면 두 수 사이에서 반복문을 시행한다. 이중반복문을 이용하여 i 변수를 j 변수로 나눠서 나머지가 0이라면 cnt값을 증가시켜준다. 이유는 간단하다. 소수는 나누어서 나머지가 0인 수가 자기자신 밖에 없기 때문이다. 1은 기본적으로 소수가 아니기 때문에 제외시켰다. 그래서 j도 2부터 시작하는 것이다. 2부터 시작했기 때문에 cnt가 1일 때, sum 변수에 값들을 더해준다. 그리고 이전에 초기화해놓았던 min 변수와 비교하면서 min보다 더 작은 수라면 min변수를 계속 업데이트 시켜준다. 그렇게 sum이 ..

[문제] & [결과] [해설] 이 문제는 제목에서 알 수 있듯이 어떤 특정 수의 약수를 구하는 문제이다. 문제에서 보면 약수의 특성을 알려주는데, 바로 특정한 수를 특정한 수의 약수로 나누면 나머지가 0인 것이다. 그런데, 문제는 단순히 약수가 무엇인지 묻는 것이 아니라 K번째로 작은 수를 출력하도록 원한다. K번째로 작은 수를 출력하기 위해서는 데이터가 정렬되어있거나 약수를 작은 순서대로 저장해놓는 방법이있다. 필자는 두 번째 방법을 이용했다. 그래서 vector을 이용해 반복문 i=1부터 비교해가면서 vector에 값을 저장했다. if(n%i==0)을 보면 이 조건을 만족할 때, vector에 저장하는 것을 알 수 있다. cnt는 출력의 세부 조건에 특정한 수의 약수의 개수가 K보다 작을 때 0을 출..

[문제] & [결과] [해결] 이 문제는 벡터를 이용해서 홀수를 만족했을 때, 벡터에 넣어준다. 그리고 홀수가 없을 경우를 대비해, cnt라는 변수를 만들어줘 cnt가 0이면 -1을 출력한다. algorithm 라이브러리에 있는 min함수를 이용해 최솟값을 구한다.

[문제] & [결과] [해설] 이 문제는 별 찍에서 층이 홀수일 때와 짝수일 때를 나눠서 해결하면 쉽습니다. 홀수일 때는 앞에 공백이 없고, 짝수일 때는 앞에 공백이 있는 별을 만들어주면 됩니다.

[문제] & [결과] [해설] 이 문제는 피보나치 수열을 구현하는 문제입니다. 피보나치 수열에 대한 간단한 설명은 위의 문제 설명에 있습니다. 그럼 바로 아래의 코드를 보시면, FIbo라는 함수에 첫 번째, 두 번째 값들은 초기화해주었습니다. 그리고 첫 번째, 두 번째일 때는 각각의 값들을 반환하도록 적어주었습니다. num까지의 수중에서 첫 번째와 두 번째를 제외한 부분은 반복문을 통해서 하나씩 옮겨가면서 처리해줍니다. c언어를 공부하면 자주 연습했던 swap이랑 비슷하지만 n2=n1+n2으로 처리해줬기 때문에 조금 다릅니다. 그렇게 하고 마지막에 n2를 반환해주면 끝! 참고로 Fibo함수에 주석처리되어 있는 부분은 반복문이 아니라 재귀함수로 풀은 것입니다. 재귀함수를 이용하면 코드의 길이는 더 짧아지고..