목록C,C++ (125)
오답노트
이분탐색(이진탐색)이란? 상대방이 속으로 생각한 숫자를 찾는 '업다운' 게임의 규칙은 다음과 같다. 상대방은 제한된 범위 안에서 숫자를 생각하고 또 다른 사람은 숫자를 부르며 그 숫자보다 생각한 수가 크면 업, 작으면 다운으로 상대방이 생각한 수를 맞추는 게임이다. 이분탐색은 '업다운' 게임과 같이 배열의 가장 중간의 값을 선택하고 그 수가 우리가 찾는 수보다 크면 중간 위치 부터 마지막 위치까지, 작으면 처음 위치부터 중간 위치까지를 반복하여 탐색 범위를 좁혀가며 원하는 수를 찾는 방법이다. 하지만 이를 위해서는 무조건 배열의 오름차순 정렬이 선행되어야 한다. 그리고 이런 이분탐색을 친절하게도 STL에서 제공한다. algorithm.h 를 코드에 추가하면 아래 함수들을 사용할 수 있다. 1. binar..
https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net - 문제파악 배열에는 중복 가능한 N개의 요소가 주어진다. 그 이후에 입력되는 숫자들이 배열에 몇개가 있는지 출력하라. - 나의 접근 배열에서 찾고싶은 정수가 있다면 처음 나타는 인덱스와 마지막에 나타나는 인덱스를 빼면 된다는 발상까지는 성공했으나 구현이 쉽지 않았다. 그런데 STL에 함수가 있었다... 이분탐색 힘들게 구현하지 말고 STL을 활용하자... - 정..
https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net - 문제 파악 N 개의 배열을 주어지고 이 안에서 주어지는 M개의 정수가 있는지 판별하라. 주어지는 정수가 존재한다면 1, 아니면 0을 주어지는 정수에 따라 각각 출력하라. - 정답 이분탐색 입문 문제 시작 인덱스와 종료 인덱스 그리고 중간 인덱스를 각각 초기화 시킨 다음 중간 인덱스의 값과 확인하고 싶은 값의 크기에 따라 시작 인덱스 또는 종료 인..
https://www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net - 문제파악 이항계수 n,k 의 값을 10007로 나눈 나머지로 출력하라 - 나의 접근 이항 계수 1에서 나머지와 for문을 살짝 바꿔줬는데 해도해도 안되더라.. - 정답 점화식을 활용해 메모이제이션을 해야한다.이항 계수의 성질중 하나는 다음과 같다. nCk = (n-1)Ck + (n-1)C(k-1) 참고로 위 공식은 파스칼의 삼각형과 같다. 위 공식을 점화식으로 메모이제이션을 실시한다. 초항인 k 가 0일때 그리고 k가 n 일때는 값이 1이다. #include "b..
https://www.acmicpc.net/problem/11050 11050번: 이항 계수 1 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 10, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net - 문제파악 n 과 k 의 이항계수를 출력하라 - 정답 #include "bits/stdc++.h" using namespace std; int main() { int n, k; cin >> n >> k; if (!k || n == k) { cout
https://www.acmicpc.net/problem/4796 4796번: 캠핑 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, L, P, V를 순서대로 포함하고 있다. 모든 입력 정수는 int범위이다. 마지막 줄에는 0이 3개 주어진다. www.acmicpc.net - 문제 파악 연속되는 P일중 캠핑은 L일만 할 수 있다. 이 때 휴가가 V일이라면 캠핑 가능한 최대 일 수를 출력하라. - 정답 #include "bits/stdc++.h" using namespace std; int main() { int cnt = 1; while (1) { int a, b, c; cin >> a >> b >> c; if (!a && !b && !c) break; int..
https://www.acmicpc.net/problem/6064 6064번: 카잉 달력 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. www.acmicpc.net - 문제 파악 각 각 M진수 N진수가 주어지고 입력으로 주어지는 각각의 나머지를 만족하는 자연수 출력, 출력할 수 없으면 -1 출력 - 나의 시도 https://www.acmicpc.net/problem/1476 (날짜 계산) 과 같이 접근 하지만 그러면 시간초과 - 정답 1. M진수 먼저 생각했을 때, 입력으로 주어지는 M진수에 대한 나머지를 만족하는 자연수를 구하는 점화식을 구한다. 2. 1번으로..
https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net - 문제파악 정수 N에 대해서 소인수분해한 결과를 출력하라 - 정답 #include "bits/stdc++.h" using namespace std; int main() { int n; cin>>n; vector vec; for(int i = 2; i*i
https://www.acmicpc.net/problem/7795 7795번: 먹을 것인가 먹힐 것인가 심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 www.acmicpc.net - 문제 파악 수열 A와 B가 주어진다 수열 A의 원소와 수열 B의 원소를 비교했을 때, 수열 A가 큰 쌍의 개수를 출력하라 - 정답 #include "bits/stdc++.h" using namespace std; int arrA[20005]; int arrB[20005]; int main() { cin.tie(0); cout.tie(0); i..
https://www.acmicpc.net/problem/5648 5648번: 역원소 정렬 모든 원소가 양의 정수인 집합이 있을 때, 원소를 거꾸로 뒤집고 그 원소를 오름차순으로 정렬하는 프로그램을 작성하세요. 단, 원소를 뒤집었을 때 0이 앞에 선행되는 경우는 0을 생략해야합니 www.acmicpc.net - 문제 파악 N 개의 정수가 입력된다. 이 정수를 뒤집은 수를 오름차순으로 정렬하여 출력하라 - 정답 정수를 모두 문자열로 받아 reverse 함수를 이용해 뒤집고 문자열을 다시 unsigned long long 으로 변환 해주었다. 문자열에서 숫자로 바꾸는 함수들 stoi : string -> int stoul : string -> unsigned long stoull : string -> uns..