티스토리 뷰
it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비 - 인프런 | 강의
강의 저작권으로 인해 문제를 공개하지 않았으며, 답안 코드 혹은 성공한 코드가 작성된 게시글입니다.
5. 나이계산
2023년 2월 5일
#include <iostream>
#include <string>
using namespace std;
int main() {
string person;
cin >> person;
int year = 0;
int age = 0;
for(int i = 0; i < 2; i++)
{
year = year * 10 + (person[i] - '0');
}
if((person[7] - '0') % 2 == 1)
{
if (person[7] - '0' == 1)
{
age = 119 - year + 1;
cout << age << ' ' << 'M';
}
else
{
age = 19 - year + 1;
cout << age << ' ' << 'M';
}
}
else
{
if (person[7] - '0' == 2)
{
age = 119 - year + 1;
cout << age << ' ' << 'W';
}
else
{
age = 19 - year + 1;
cout << age << ' ' << 'W';
}
}
return 0;
}
분기문을 통해 나이와 성별을 찾을 수 있도록 했다.
6. 숫자만 추출
2023년 2월 5일
#include <iostream>
#include <string>
#include <cctype>
using namespace std;
int main() {
string input;
cin >> input;
int length = input.size();
int num = 0;
int count = 0;
for (int i = 0; i < length; i++)
{
if(isdigit(input[i]))
{
num = num * 10 + input[i] - '0';
}
}
cout << num << '\\n';
for(int i = 1; i <= num; i++)
{
if(num % i == 0)
{
count++;
}
}
cout << count;
return 0;
}
7. 영어단어 복구
2023년 2월 5일
#include <iostream>
#include <string>
using namespace std;
int main() {
string input;
getline(cin, input);
int length = input.size();
string result;
for (int i = 0; i < length; i++)
{
if (input[i] == ' ')
continue;
result += tolower(input[i]);
}
cout << result;
return 0;
}
#include <iostream>
#include <string>
using namespace std;
int main() {
char input[101] = {};
cin.getline(input, 101);
char result[101] = {};
int index = 0;
for (int i = 0; i < 101; i++)
{
if (input[i] == ' ')
continue;
if (input[i] >= 65 && input[i] <= 90)
result[index++] = input[i] + 32;
else
result[index++] = input[i];
}
cout << result;
return 0;
}
[C++] 공백이 포함된 문자열 입력받기(char array, string : getline)
string으로 문제를 푼 이후 배열을 이용해 푸는 횟수가 줄었다.
8. 올바른 괄호
2023년 2월 5일
#include <iostream>
#include <string>
using namespace std;
int main() {
char input[31];
cin >> input;
int check = 0;
bool result = false;
for (int i = 0; input[i] != '\\0'; i++)
{
if (input[i] == '(')
check++;
else
check--;
if (check < 0)
break;
}
if(check == 0)
cout << "YES";
else
cout << "NO";
return 0;
}
**stack**을 이용하지 않아도 풀 수 있다.
#include <iostream>
#include <string>
#include <stack>
using namespace std;
int main() {
char input[31];
cin >> input;
stack<char> store;
string result = "YES";
for (int i = 0; input[i] != '\\0'; i++)
{
if (input[i] == '(')
store.push(input[i]);
else if(!store.empty() && input[i] == ')' && store.top() == '(')
store.pop();
else
{
result = "NO";
break;
}
}
if (!store.empty())
result = "NO";
cout << result;
return 0;
}
스택을 이용했을 때의 코드이다.
스택에는 **(**만 넣어준다. else if를 보면 store이 비지 않아야 하고 input[i]가 )야 하며 스택에는 )와 짝을 이룰 (가 존재 해야 한다. **result**는 미리 YES를 넣어두어, 더 이상 팝 할게 없거나 1개 이상 남아있을 때 NO가 되도록 해준다.
9. 모두의 약수
2023년 2월 5일
#include <iostream>
using namespace std;
int main()
{
int N = 0;
cin >> N;
for (int i = 1; i <= N; i++)
{
int count = 0;
for (int j = 1; j <= i; j++)
{
if (i % j == 0)
count++;
}
cout << count << ' ';
}
}
단순히 문제만 읽었을 때 위 코드처럼 풀었지만 시간 초과로 인해 틀렸다. 코드를 까보면 이중for문이기 때문에 시간복잡도가 N2이 나온다. 게다가 입력된 최대 수까지 일일히 수를 나눠 약수를 구해야 한다.
#include <iostream>
using namespace std;
int main()
{
int arr[50001] = {};
int N = 0;
cin >> N;
for (int i = 1; i <= N; i++)
{
for (int j = i; j <= N; j = j+i)
{
arr[j]++;
}
}
for (int i = 1; i <= N; i++)
{
cout << arr[i] << ' ';
}
}
강의 내용을 따랐을 때 위 코드와 같다.
계속해서 나눠주는게 아닌, j에 배수를 더해주어 배수를 확인하는 것을 대신한다. 심지어 그 수도 입력한 N의 값이기 때문에 50000까지 구하지 않아도 된다.
<aside> ⚠️ 이렇게 생각하는 법을 배워야겠다.
</aside>
10. 자릿수의 합
2023년 2월 5일
#include <iostream>
#include <vector>
using namespace std;
int digit_sum(int x)
{
int sum = 0;
while (x > 0)
{
sum += x % 10;
x /= 10;
}
sum += x % 10;
return sum;
}
int main()
{
int N = 0;
cin >> N;
int arr[101] = {};
int max = 0;
int maxCount = 0;
for (int i = 0; i < N; i++)
{
cin >> arr[i];
int temp = digit_sum(arr[i]);
if (temp > max)
{
max = temp;
maxCount = i;
}
else if (temp == max)
{
if(arr[maxCount] < arr[i])
maxCount = i;
}
}
cout << arr[maxCount];
return 0;
}
함수를 만들어 푸는 문제였다. 프로그래머스에서 자주 출제되었던 문제 유형이라 크게 어렵지 않았다. 각 자릿수의 값을 더할 때에는 변수 2개를 사용하면 된다.
예를 들어 124라는 숫자의 각 자릿수 합을 구한다고 가정해보자.
10 나머지 값인 4를 저장 → 10으로 나누기 (= 12) → 다시 10 나머지 값인 2 저장 → 10으로 나누기 (= 1) → 반복문 탈출해서 나머지값 1 합산 ⇒ 4 + 2 + 1
마지막에 한 번 더 나머지 값을 더하는 이유는 마지막으로 10을 나눴을 때 1이 남는데 반복문만 통해서 합산을 하면 1은 더해지지 않은 채로 반복문이 끝나기 때문이다.
14. 뒤집은 소수
2023년 2월 5일
#include <iostream>
using namespace std;
int reverse(int x)
{
int rValue = 0;
while (x > 0)
{
int temp = x % 10;
rValue = rValue * 10 + temp;
x /= 10;
}
return rValue;
}
bool isPrime(int x)
{
if (x < 2)
return false;
for (int i = 2; i < x; i++)
{
if (x % i == 0)
return false;
}
return true;
}
int main()
{
int N = 0;
cin >> N;
for (int i = 0; i < N; i++)
{
int temp = 0;
cin >> temp;
temp = reverse(temp);
if (isPrime(temp))
cout << temp << ' ';
}
return 0;
}
숫자를 뒤집고 앞자리에 있는 0을 뺐을 때 1이 되는 수를 조심해야 한다. 1은 소수가 아니기 때문이다.
15. 소수의 개수(제한시간 1초)
#include <iostream>
using namespace std;
int main()
{
int N = 0;
cin >> N;
int i = 0;
int j = 0;
int count = 0;
int check = 0;
for (i = 2; i <= N; i++)
{
check = 1;
for (j = 2; j * j <= i; j++)
{
if (i % j == 0)
{
check = 0;
break;
}
}
if (check == 1)
count++;
}
cout << count;
return 0;
}
강의를 들은 후 다시 짜봤을 때 통과했다.
#include <iostream>
using namespace std;
int main()
{
int N = 0;
cin >> N;
int i = 0;
int j = 0;
int count = 0;
for (i = 2; i <= N; i++)
{
for (j = 2; j <= i; j++)
{
if (i % j == 0)
break;
}
if (i == j)
count++;
}
cout << count;
return 0;
}
처음에 혼자 풀었을 때의 코드이다.
디버깅하면 값은 잘 나오지만 시간초과가 나왔다.
#include <iostream>
using namespace std;
int main()
{
int N = 0;
cin >> N;
int i = 0;
int j = 0;
int count = 0;
for (i = 2; i <= N; i++)
{
for (j = 2; j * j <= i; j++)
{
if (i % j == 0)
break;
}
if (i == j)
count++;
}
cout << count;
return 0;
}
그래서 제곱을 하면 더 빨라지기 때문에 잘 실행될 줄 알았으나 아예 틀린 값이 나왔다. 하단에 있는 분기문 때문에 처음 2를 제외한 다른 숫자들은 분기문으로 들어가지 않았다.
'😈 알고리즘 > 🍃 인프런 #1' 카테고리의 다른 글
| 🙏 23, 24번 문제 (0) | 2023.02.18 |
|---|---|
| 🙏 21, 22번 문제 (0) | 2023.02.17 |
| 🙏 16, 17, 18, 19, 20번 문제 (0) | 2023.02.16 |
| 🙏 11, 12번 문제 (0) | 2023.02.15 |
| 🙏 1 - 4번 문제 (0) | 2023.02.13 |