한다 공부

2579번: 계단 오르기 (acmicpc.net) 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 동적 계획법 (dynamic programming) 이란 무엇일까? 바로 현재 값을 구할 때, 과거에 구한 값을 활용하는 알고리즘이다. 예를 들어 내가 한 노드에 있는데 이 노드로 올 수 있는 길은 두 갈래 라고 하자. 왼쪽 노드에서 와야 최단 경로인지, 오른쪽 노드에서 와야 최단 경로인지 구해야한다. 출발지에서 왼쪽 노드까지 가는 최소 비용의 합을 dp 배열에 저장한다. 위 그래프에서는 3의 비용으로 왼쪽 노드까지 갈 수 ..

15649번: N과 M (1) (acmicpc.net) 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 백트래킹이란? 브루트 포스와 같이 완전 탐색을 하는 알고리즘이 있는데, 여기서 조건에 해당되지 않는 경우를 가지치기 하여 경우의 수를 줄여나가는 방법을 백트래킹이라고 한다. 백트래킹을 이용하면 탐색 시간이 줄어든다. 백트래킹에서는 주로 재귀함수를 이용한다. 이때, 재귀함수의 종료조건이 중요하다. 백트래킹은 주로 N의 값이 20보다 작을 때 이용한다. 위 N과 M (1)의 문제를 예로 들어보자. n=4, m=..

16563번: 어려운 소인수분해 (acmicpc.net) 16563번: 어려운 소인수분해 첫째 줄에는 자연수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 자연수 ki (2 ≤ ki ≤ 5,000,000, 1 ≤ i ≤ N)가 N개 주어진다. www.acmicpc.net 일반 에라토스테네스의 체는 bool 배열을 만들어서 소수면 true, 아니면 false를 저장한다. 그런데 이 문제에서는 소인수들을 찾아야하므로 bool 배열 대신 int 배열을 만들어서, 어떤 수로 인해 소수가 아니게 되었는지를 저장한다. 예를 들어 8의 경우, 8은 2의 곱으로 인해 소수가 아니게 되었다. >> 2 출력 8/prime[k] = 8/2 =4 가 된다. 4는 2의 곱으로 인해 소수가 아니게 되었다..

2436번: 공약수 (acmicpc.net) 2436번: 공약수 첫째 줄에 두 개의 자연수가 빈칸을 사이에 두고 주어진다. 첫 번째 수는 어떤 두 개의 자연수의 최대공약수이고, 두 번째 수는 그 자연수들의 최소공배수이다. 입력되는 두 자연수는 2 이상 100,0 www.acmicpc.net 유클리드 호제법을 이용했다. 최대공약수를 G, 최소공배수 L이라 하자 G*L = A*B 이다. (수학적 공식이라고 한다.) A = G*a, B=G*a이라고 하면 (이때 a, b는 서로소이다. 왜냐하면 최대공약수 G로 공통부분을 끄집어 냈으므로) G*L = G*a*G*b가 되고 약분하면 L/G=a*b가 된다. L G가 주어지니 이를 이용해서 A+B, 즉 a+b가 최소가 되는 a b를 찾고 a b에 G를 구해 최종적으로 ..

5639번: 이진 검색 트리 (acmicpc.net) 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 예전에 올린 이진 탐색 트리 코드를 일부 수정했다. c언어로 구현했던 것을 c++로 구현하니 신경써야하는 부분이 있었다. 엔터 입력시 입력을 종료해야하는 부분이 까다로웠다. 그래서 getline을 이용해 문자열로 받은 다음, stoi를 이용해 문자열을 정수로 변환했고 엔터 입력시 반복문을 빠져나오게 했다. 4358번 생태학 문제를 풀 때 비슷한 방법을 이용했다. #include #include #..

https://www.acmicpc.net/problem/1448 1448번: 삼각형 만들기 첫째 줄에 빨대의 개수 N이 주어진다. N은 3보다 크거나 같고, 1,000,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 빨대의 길이가 한 줄에 하나씩 주어진다. 빨대의 길이는 1,000,000보다 www.acmicpc.net 삼각형 만들기 삼각형을 만드는 조건 : 가장 긴 변의 길이가 나머지 두 변의 길이의 합보다 작으면 된다. a < b < c 일 때 c < a+b 이면 성립한다. 최대 길이의 삼각형을 만들면 되므로 가장 큰 길이인 빨대 3개를 골라주면 된다. 삼각형이 만들어지지 않을 수도 있다. 그러면 가장 큰 길이인 빨대를 버리고 나머지 중에 제일 큰 3개의 빨대를 골라서 비교해보면 된다...

2108번: 통계학 (acmicpc.net) 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 1. 산술평균의 경우 반올림값을 유의한다 2. 중간값의 경우, 입력 갯수가 홀수이므로 어렵지 않다 3. 최빈값의 경우, pair에 넣어서 빈도수를 비교하고 재정렬한다 4. 범위의 경우 차의 절댓값을 이용한다 최빈값이 까다롭지만 pair를 이용한다면 비교하기 수월하다. 이 문제는 함수를 많이 만드는 바람에 return을 자꾸 깜빡해서 런타임 에러가 많이 났었다 ㅠ #include #include #include #include #in..

정답은 map으로 저장하고 학생의 답은 vector로 저장했다. 정답을 o[a]=0 o[b]=1 o[c]=2 으로 저장하고 학생의 답을 x[0]=a, x[1]=c, x[2]=b 로 저장을 했으니 정답의 맵의 key에 vector의 요소를 넣어주고 value의 크기를 비교해주면 된다. #include #include #include using namespace std; int main() { map o; vector x; int n, temp; cin >> n; temp = n; //정답 map으로 저장 string s; while (temp--) { cin >> s; o[s] = n - temp; } //학생의 답 vector로 저장 temp = n; while (temp--) { cin >> s; x...

1. 테두리가 성립하는 모든 경우의 수를 구한다. 2. 해당 테두리로 사각형을 만들었을 때, 입력한 안쪽 벽돌의 갯수가, 만들어진 사각형의 내부 갯수와 같은지 확인한다. 테두리를 구하는 방법은, 가로길이 * 2 + 세로길이 *2 를 한 다음 겹치는 모서리 4개를 빼줘도 된다. 나는 가로길이 *2 + (세로길이-2) * 2 를 했다. i = 가로 j = 세로 인데, 가로의 범위와 세로의 범위는 주석에 적어뒀다. #include using namespace std; int main() { int r, b; cin >> r >> b; int l, w; //i의 범위 // 세로 길이가 가장 짧은게 3이다. // 이 경우 가로와 겹치지 않은 세로 벽돌은 2개 뿐임. //따라서 2개를 빼주고 위와 아래 2개가 있으..

브루트 포스란 무엇인가? 모든 경우의 수를 다 해보는 것이다. 이런 단순한 방법이 때로는 가장 합리적인 방법일 수도 있다. #include #include using namespace std; vector num; //삼각수를 벡터에 push_back void calc() { int sum = 0; int k = 1; while (sum < 1000) { sum += k; num.push_back(sum); k++; } } //세 삼각수의 합이 입력한 수이면 true 리턴 bool check(int n) { bool c = false; for (int i = 0; i < num.size(); i++) { for (int j = 0; j < num.size(); j++) { for (int k = 0; k..