url : https://www.acmicpc.net/problem/11401 11401번: 이항 계수 3 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 내일 좀 더 자세하게 정리할 예정... 수학적 지식 +1 코드 #include using namespace std; const int MOD = 1000000007; // 빠른 거듭제곱 함수 long long pow(long long base, int exponent) { long long result = 1; while (exponent > 0) { if (exponent % 2 == 1) result = ..
url : https://www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 이항 계수 2 문제이다. N이 1000 이하인 이항 계수에 10007로 나눈 나머지를 구하는 문제이다. 수학적 지식을 이용해야 빡센 시간 복잡도를 통과할 수 있다. 이항 계수 계산 이항 계수는 팩토리얼 계산을 베이스로 한다. N이 커질수록 직접 N!, K!, (N-K)!를 구하여 나누는 것은 매우 큰 수가 되기 때문에, 어떤 타입이던 오버플로우가 발생한다. 참고로 13!부터 int 타입 범위를 초과하고, 21!부터 long long 타입 범위를 초과한다. ..
url : https://www.acmicpc.net/problem/11050 11050번: 이항 계수 1 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 10, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 이항 계수 2 문제를 풀지 못해 이항 계수 1 문제를 풀었다. 이항 계수 2는 더 큰 팩토리얼(1000!)를 다룬다. 내일 다시 이항 계수 2 문제를 도전해볼 생각이다. 코드 #include using namespace std; int n, k, p1, p2; long long answer = 1; int main(){ cin.tie(0); ios_base::sync_with_stdio(false); cout.tie(0); // 1. 입력받기 cin >> n >..
url: https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 요즘 백준 문제집에서 단기간 성장이라는 문제집의 문제를 풀고 있다. (https://www.acmicpc.net/workbook/view/4349) 위 문제는 문제집의 두 번째 문제이다. 아주 쉬운 단순 구현 문제인 줄 알았지만, 시간초과가 빡세기 때문에 좀 더 빠른 방법으로 코드를 짜야한다. 위 문제집의 1번 문제도 그렇고, 역시 단기간 성장에는 적당한 난이도의 고난이 ..
url : https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 배낭 문제(무게, 가치 고려)라 평범한 그리디 알고리즘이라고 생각했으나, 0/1 배낭문제이므로 dp이다. 0/1 배낭문제 각 아이템을 배낭에 넣거나(1) 넣지 않는(0) 둘 중 하나의 선택만 가능하다. 특징 1. 부분최적구조(그리디)가 아닌 dp 이다. 그리디 : 물건의 무게와 가치를 고려하여 현재 상황에서 가장 좋아보이..
url : https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 구현 문제이다. 16%에서 시간초과가 계속해서 발생하였다. 16% TC 시간초과 문제의 입력으로 주어진 문자열이 매우 길 수 있고(10만 문자) 연산 횟수가 10만 번이기 때문에 시간초과가 발생할 수 있다. 내 경우에는 split 함수에서 매번 구분자(delimeter)를 찾고 문자를 split 하는 과정에서 시간초과가 발생했다. split 함수 구현시 find, erase를 이용하지않고, stringstream과 getline을 이용하니 시..
메리 크리스마스 🎄😊 url : https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱 www.acmicpc.net 위 문제가 dfs인 이유 완전탐색이고, 숫자가 주어지고 그 숫자를 모두 더하거나, 빼거나, 곱하거나, 나누어서 최대합과 최소합을 만드는 문제이기 때문이다. (처음위치~끝위치) (비슷한 문제로는 전에 풀었던 프로그래머스: 타겟 넘버 가 있다.) 처음에 dp로 생각했었으나, 위 문제는 같은 부분문제가 여러 번 ..
url : https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 일반적인 bfs 문제에서 조건이 추가된 문제이다. 벽을 한 개 이하로 부실 수 있는데, 벽을 부순 수를 visited 배열에 추가하여 최단거리를 계산하면 된다. 벽 부순 상태를 저장하는 이유 벽을 부순 상태에서 도달했을 때와, 벽을 부수지 않고 도달했을 때 각각 다른 결과를 불러올 수 있기 때문이다. 아래 예시는 질문게시판에 올라온 예시인데 이해하기 쉬워 가져왔..
