Baekjoon

[C++] 1919번 : 애너그램 만들기

https://www.acmicpc.net/problem/1919 1919번: 애너그램 만들기 두 영어 단어가 철자의 순서를 뒤바꾸어 같아질 수 있을 때, 그러한 두 단어를 서로 애너그램 관계에 있다고 한다. 예를 들면 occurs 라는 영어 단어와 succor 는 서로 애너그램 관계에 있는데, occurs www.acmicpc.net 풀이 11328번 Strfry 문제와 상당히 유사한 문제이다. 이 때 배열을 굳이 2개나 사용하지 않아도 1개로 해결할 수 있는 모범 풀이가 존재해 이번 문제도 한 가지 배열로 풀어봐야겠다고 다짐했으나.. 시간을 투자하여도 내 풀이에는 반례가 존재했다. 모범 답안을 보면 1개의 배열로 풀 수는 있으나 2차원 배열이기 때문에 1차원 배열 2개를 사용하는 것과 같다. 내 코드..

[C++] 백준 3273번 : 두 수의 합

https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 풀이 문제를 보고 2중 for문으로 풀면 되는 것 아닌가? 하셨을 수도 있겠어요. 하지만, 시간 제한이 1초이기 때문에 O(N^2) 풀이로는 시간초과가 발생할 것입니다. (주어진 N의 최대값은 10만이고 1초는 대략 3-5억번의 연산을 수행하기 때문에 당연히 초과) 시간복잡도를 줄이기 위해서는 공간복잡도를 희생해보는 건 어떨지 고민해봅시다. ..

[C++] 1475번 : 방 번호

https://www.acmicpc.net/problem/1475 1475번: 방 번호 첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 한 세트에는 0번부터 9번까지 숫자가 하나씩 들어있다. -> 대놓고 배열을 사용하여 풀라고 한다. 문제에서 신경써줘야 하는 부분은 '6은 9를 뒤집어서 이용할 수 있고, 9는 6을 뒤집어서 이용' 이다. 일단 단순하게 방번호가 9999인 경우 2set가 필요함을 알 수 있다. 그렇다면 99999의 경우는? 당연히 3set일 것이다. 이에 따라 홀수/짝수 경우를 나눠 홀수 -> 2로 나누고 + 1 , 짝수 -> 2로 나누기 연산을 수행해서 최댓값을 구하고자 하였으나, 66699 라는 반례가 ..

[C++] 2577번: 숫자의 개수

https://www.acmicpc.net/problem/2577 2577번: 숫자의 개수 첫째 줄에 A, 둘째 줄에 B, 셋째 줄에 C가 주어진다. A, B, C는 모두 100보다 크거나 같고, 1,000보다 작은 자연수이다. www.acmicpc.net 풀이 문제에서 A,B,C는 1000보다 작다고 주어졌습니다! 1000^3은 10억으로 int의 범위 21억보다 작으니 int로 다뤄도 무방합니다~ 아이디어 자체는 정말 쉽습니다! 10으로 계속 나누는데 그 과정에서 나머지를 따로 count해주는 것입니다 내 코드 #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int A, B, C; cin >> A >> B ..

[C++] 10808번: 알파벳 개수

https://www.acmicpc.net/problem/10808 10808번: 알파벳 개수 단어에 포함되어 있는 a의 개수, b의 개수, …, z의 개수를 공백으로 구분해서 출력한다. www.acmicpc.net 풀이 문자열의 원리를 이해하고 있으면 쉽게 풀 수 있는 문제이다. 나의 코드 #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); string s; vector v(26); cin >> s; for (char c : s) { int num = c - 97; v[num]++; } for (int a : v) { cout s; for (char a = 'a'; a

[C++]백준 10804번: 카드 역배치

https://www.acmicpc.net/problem/10804 10804번: 카드 역배치 1부터 20까지 오름차순으로 놓인 카드들에 대해, 입력으로 주어진 10개의 구간 순서대로 뒤집는 작업을 했을 때 마지막 카드들의 배치를 한 줄에 출력한다. www.acmicpc.net 폐구간 내의 원소들을 reverse하는 간단한 문제이다. reverse method 대신 reverse 해야하는 범위가 n일 때 반복문의 범위를 n/2로 잡고 swap하여도 된다.(사실 이것이 reverse의 원리) 내 정답코드 #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int arr[21]; for (int i = 1; i < 2..

[C++]백준 10093번: 숫자

https://www.acmicpc.net/problem/10093 10093번: 숫자 두 양의 정수가 주어졌을 때, 두 수 사이에 있는 정수를 모두 출력하는 프로그램을 작성하시오. www.acmicpc.net 풀이 : subtask라는 재밌는 장치가 존재하였다. c/c++이라면 10^15로 범위 제한인 것을 보자마자 long long 자료형을 사용해야한다는 것을 생각해내야한다. (int는 약 21억까지의 수를 다루니 그보다 10^15는 그 보다 훨씬 큰 수이다) +long long 조차 감당이 안될 큰 수라면 string으로 다뤄야한다. (Python을 쓰자..) 위 사실만 알면 쉽게 풀리는 문제이다. 내 정답코드 #include using namespace std; int main() { ios::s..

[C++]백준 2309번: 일곱 난쟁이

https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 풀이 : 문제를 딱 보고 경우의 수가 생각났다. 조합으로 생각하면 9개의 data에서 7개의 요소를 선택하는 경우니 최악의 경우 9C2를 만족한다고 생각했다. 7개의 합으로 판단하는 것 보다 전체의 합에서 100을 만족시키게끔 배열의 요소를 빼는 풀이를 생각했다. 다만, break문을 잘못 써서 오답이 발생하였다.. break 문은 가장 가까운 loop를 탈출한다!! (정말 바보같다.) 질문 게시판에 나와..

[C] 백준 10829번 : 이진수 변환

https://www.acmicpc.net/problem/10829 10829번: 이진수 변환 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 100,000,000,000,000) www.acmicpc.net #define _CRT_SECURE_NO_WARNINGS #include long long recursion(long long N) { long long temp; if (N == 0) return 0; else { temp = N % 2; N /= 2; recursion(N); printf("%lld", temp); } } int main() { long long N; scanf("%lld", &N); recursion(N); } 우선 문제에서 제시된 자연수 N의 범위가 대략 21억의 값의 범위..

[C] 백준 2750번 : 수 정렬하기

https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net #define _CRT_SECURE_NO_WARNINGS #include int main() { int N = 0, temp = 0; int arr[1000] = { 0, }; scanf("%d", &N); for (int i = 0; i < N; i++) { scanf("%d", &arr[i]); } for (int i = 0; i < N; i++) {//시간복잡도가 O(n^2)인 버블정렬 for (i..