본문 바로가기

[C++] 알고리즘 교육119

[알고리즘 5.3.2] 기본정렬 - beehive 문제 위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌을 때, 벌집의 중앙 1에서 N번 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나가는지(시작과 끝을 포함하여)를 계산하는 프로그램을 작성하시오. 예를 들면, 13까지는 3개, 58까지는 5개를 지난다. 입력 첫째 줄에 N(1 ≤ N ≤ 1,000,000)이 주어진다. 출력 입력으로 주어진 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나는지 출력한다. 예제 입력 13 예제 출력 3 예제 입력 58 예제 출력 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1.. 2019. 4. 25.
[알고리즘 5.3.1] 기본정렬 - nextnum 문제 위키피디아에 따르면 등차수열 AP는 연속되는 두 숫자의 차가 같은 숫자들이 연속되는 수열이다. 예를 들어, 수열 3,5,7,9,11,13…. 은 공차(연속된 숫자의 차이) 2를 가지는 등차수열이다. 이 문제에서 공차는 0이 아닌 정수이다. 등비수열 GP는 이전의 숫자에 0이 아닌 공비(연속된 숫자의 비율)를 곱하여 구하는 수열이다. 예를 들어 수열 2,6,18,54 는 공비가 3인 등비수열이다. 이 문제에서 공비는 0이 아닌 정수이다. 수열을 구성하는 세 개의 숫자가 주어졌을 때, 주어진 수열이 등차 수열인지 등비수열인지를 결정하고, 다음에 연속될 숫자를 결정하는 프로그램을 작성하시오. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각각의 케이스는 3개의 정수 a1, a2, a3가 한줄로 .. 2019. 4. 25.
[알고리즘 5.2.1] 기본정렬 - k번째 큰 수 찾기 문제 N개의 자연수가 주어질 때, 이 자연수들 중에서 k번째로 큰 수를 찾는 프로그램을 작성하시오. 만약 k=1 이라면, 가장 큰 수를 찾으면 된다. 입력 첫 번째 줄에 자연수 N, k가 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ k ≤ 10) 두 번째 줄에 N개의 자연수가 주어진다. 출력 첫 번째 줄에 k번째 수를 출력한다. 예제 입력 10 3 1 5 2 3 8 4 7 3 2 10 예제 출력 7 예제 입력 5 4 5 5 1 2 3 예제 출력 2 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 #include int main() { int n, k; scanf("%d",&n); s.. 2019. 4. 25.
[알고리즘 6.2.10] 문자열 - 큰 자릿수 곱셈 문제 두 자연수가 주어질 때 그들의 곱셈을 계산하는 프로그램을 작성하시오. 각 수는 1 이상 10^100 미만의 범위를 가진다. 입력 첫 번째 줄과 두 번째 줄에 각각 하나의 자연수가 주어진다. 출력 첫 번째 줄에 곱셈의 결과를 출력한다. 예제 입력 123112981293812938139 1298928491101221811 예제 출력 159914959026945386297336486942660549729 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 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60.. 2019. 4. 25.
[알고리즘 6.2.9] 문자열 - 큰 자릿수 뺄셈 문제 두 자연수가 주어질 때 그들의 덧셈을 계산하는 프로그램을 작성하시오. 각 수는 1 이상 10^100(10의 100 거듭제곱) 미만의 범위를 가진다. 입력 첫 번째 줄과 두 번째 줄에 각각 하나의 자연수가 주어진다. 출력 첫 번째 줄에 덧셈의 결과를 출력한다. 예제 입력 123112981293812938139 1298928491101221811 예제 출력 124411909784914159950 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 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 .. 2019. 4. 25.
[알고리즘 6.2.8] 문자열 - 큰 자릿수 덧셈 문제 두 자연수가 주어질 때 그들의 덧셈을 계산하는 프로그램을 작성하시오. 각 수는 1 이상 10^100(10의 100 거듭제곱) 미만의 범위를 가진다. 입력 첫 번째 줄과 두 번째 줄에 각각 하나의 자연수가 주어진다. 출력 첫 번째 줄에 덧셈의 결과를 출력한다. 예제 입력 123112981293812938139 1298928491101221811 예제 출력 124411909784914159950 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 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 .. 2019. 4. 25.
[알고리즘 6.2.7] 문자열 - 문자열 압축 문제 문자열의 길이가 굉장히 길 경우, 이를 압축하여 짧게 만들어야 할 때가 종종 있다. 이 문제에서는 문자열이 주어졌을 때, 다음과 같은 방법으로 압축한 결과를 출력하는 프로그램을 작성한다. 예를 들어, 문자열이 AAABBBBBCCCCDDDDEFFF 라고 하자. 이 문자열을 압축하면, 연속으로 같은 문자가 나오는 부분에, 그 문자가 몇번 나왔는지를 적어줌으로써 압축한다. 즉, 이 문자열은 3A5B4C4DE3F 로 압축된다. E는 1개밖에 없기 때문에 따로 1을 적어주지 않는다. 입력 첫 번째 줄에 압축하고자 하는 문자열이 주어진다. 문자열의 길이는 1000보다 작다. 문자열에 구성된 알파벳은 대문자다. 출력 문자열을 압축한 결과를 출력한다. 예제 입력 AAABBBBBCCCCDDDDEFFF 예제 출력 3.. 2019. 4. 25.
[알고리즘 6.2.6] 문자열 - 팰린드롬 조사 문제 문자열이 주어질 때, 이것이 팰린드롬인지 조사하는 프로그램을 작성하시오. 팰린드롬이란, 앞으로 읽을 때와 뒤로 읽을 때의 결과가 같은 문자열을 말한다. 입력 첫 번째 줄에 문자열이 주어진다. ( 1 ≤ 문자열의 길이 ≤ 1,000 ) 출력 입력된 문자열이 팰린드롬이면 YES, 아니면 NO를 출력한다. 예제 입력 abcba 예제 출력 YES 예제 입력 abcbd 예제 출력 NO 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 #include #include int main() { char arr[1005]; fgets(arr, 1005, stdin); int arrLen = strlen(arr); int arrDiv = arr.. 2019. 4. 25.
[알고리즘 6.2.5] 문자열 - 문자열 포함관계 조사 문제 문자열 A와 B가 주어질 때, 문자열 B가 문자열 A에 포함되어 있는지를 조사하는 프로그램을 작성하시오. 단, 문자열 A와 B에는 알파벳으로만 이루어져 있으며, 공백은 포함되지 않는다고 가정한다. 입력 첫 번째 줄에 문자열 A, 두 번째줄에 문자열 B가 주어진다. 각각의 길이는 1,000을 넘지 않는다. 출력 문자열 B가 문자열 A에 포함되면 YES, 아니면 NO를 출력한다. 예제 입력 Watermelon melon 예제 출력 YES 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 35 36 37 38 39 40 #include #include int main() { char arr.. 2019. 4. 25.
[알고리즘 6.2.4] 문자열 - 문자열 정렬 문제 n개의 문자열이 주어질 때, 이 문자열을 사전순으로 빠른 순서대로 정렬하는 프로그램을 작성하시오. 입력 첫 번째 줄에 문자열의 개수 n이 주어진다 ( 1 ≤ n ≤ 100 ) 그 후 n개의 줄에 대하여 정렬하고자 하는 문자열이 주어진다 ( 1 ≤ 문자열의 길이 ≤ 100 ) 출력 문자열을 사전순으로 빠른 순서대로 정렬한 결과를 출력한다. 예제 입력 9 acid apple banana acquire cat crop crab power cat 예제 출력 acid acquire apple banana cat cat crab crop power 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 3.. 2019. 4. 25.
[알고리즘 6.2.3] 문자열 - 문자열 뒤집기 문제 문자열이 주어질 때, 이를 뒤집어서 출력하는 프로그램을 작성하시오. 입력 첫 번째 줄에 문자열이 주어진다. ( 1 ≤ 문자열의 길이 ≤ 1,000 ) 출력 문자열을 뒤집은 결과를 출력한다. 예제 입력 Hello World! 예제 출력 !dlroW olleH 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 #include #include int main() { char arr[1500]; fgets(arr, 1500, stdin); int su = strlen(arr); for(int i=su-1; i>=0; i--){ printf("%c",arr[i]); } return 0; } 2019. 4. 25.
[알고리즘 6.2.2] 문자열 - 과제물 망치기 문제 철수는 영희를 괴롭히는 것을 매우 좋아한다. 오늘도 철수는 영희를 어떻게 괴롭힐지 고민을 하다가, 영희가 최근에 작성하고 있던 문서가 떠올랐다. 이에 철수는 영희의 문서를 망쳐놓기로 결심한다. 바로 띄어쓰기를 모두 제거해버리는 것이다. 영희의 문서를 확인한 철수는, 띄어쓰기가 너무 많아 직접 모두 제거할 수는 없다는 것을 깨닫고 도움을 요청했다. 영희의 문서가 주어질 때, 띄어쓰기를 모두 제거하는 프로그램을 작성하시오. 입력 첫째 줄에 영희의 문서가 주어진다. 영희의 문서는 한 줄 짜리 문자열이며, 문서의 길이는 100,000을 넘지 않는다. 출력 문자열의 띄어쓰기를 모두 제거한 결과를 출력한다. 예제 입력 Please do not touch anything 예제 출력 Pleasedonottouch.. 2019. 4. 25.
[알고리즘 6.2.1] 문자열 - 대소문자 변환 문제 문자열이 주어질 때, 대문자는 소문자로, 소문자는 대문자로 바꾸는 프로그램을 작성하시오. 알파벳이 아닌 문자는 그대로 유지한다. 입력 첫 번째 줄에 문자열이 주어진다. ( 1 ≤ 문자열의 길이 ≤ 1,000 ) 출력 문자열 내의 대문자는 소문자로, 소문자는 대문자로 바꾼 결과를 출력한다. 예제 입력 hELLO wORLD! 예제 출력 Hello World! 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include #include int main() { char arr[1000]; fgets(arr,1000,stdin); //65~90 대문자 //97~122 소문자 int su = strlen(arr); for(int i=0; i=.. 2019. 4. 25.
[알고리즘 6.1.1] 문자 - 계산기 문제 덧셈, 뺄셈, 곱셈, 나눗셈을 할 수 있는 계산기 프로그램을 만드세요. 입력 첫째 줄에는 숫자 a가 입력되고, 둘째 줄에는 +, -, /, * 연산자가 입력된다. 마지막 줄에는 숫자 b가 입력된다. 출력 a와 b를 주어진 연산자를 활용하여 연산한 결과를 출력해라. 예제 입력 5 + 5 예제 출력 10 예제 입력 5 - 12 예제 출력 -7 예제 입력 2 * 105 예제 출력 210 예제 입력 125 / 5 예제 출력 25 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include int main() { int su1, su2; char mun; scanf("%d %c %d",&su1, &mun, &su2); if(mun == '+'){ print.. 2019. 4. 25.
[알고리즘 8.1.5] 재귀함수 - inequal 문제 부등호 기호 앞뒤에 넣을 수 있는 숫자는 0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다. 아래는 부등호 순서열 A를 만족시키는 한 예이다. 3 1 7 0 이 상황에서 부등호 기호를 제거한 뒤, 숫자를 모두 붙이면 하나의 수를 만들 수 있는데 이 수를 주어진 부등호 관계를 만족시키는 정수라고 한다. 그런데 주어진 부등호 관계를 만족하는 정수는 하나 이상 존재한다. 예를 들어 3456128790 뿐만 아니라 5689023174도 아래와 같이 부등호 관계 A를 만족시킨다. 5 0 1 4 여러분은 제시된 k 개의 부등호 순서를 만족하는 (k+1) 자리의 정수 중에서 최대값과 최소값을 찾아야.. 2019. 4. 25.

티스토리툴바