우대비의 블로그

1722번: 순열의 순서 (acmicpc.net) 3개의 수를 이용해 임의의 순열을 만들고 정렬을 하면{1, 2, 3}{1, 3, 2}{2, 1, 3}{2, 3, 1}{3, 1, 2}{3, 2, 1}이처럼 정렬을 할  수 있습니다.이 문제는 2,1,3이 몇번째에 있는지, 5번째에 위치한 순열은 무엇인지 물어보는 문제입니다. 경우의 수1부터 N까지의 수를 임의로 배열한 순열은 N!개가 있습니다.N * (N - 1) * (N - 2) * .... ... ... * 2 * 1 1 ~ 4까지의 수를 임의로 배열한 순열은 1 * 2 * 3 * 4 = 24개해당 경우의 수를 이용하면 문제를 쉽게 풀 수 있습니다. N = 4, K = 3이라고 할때3번째에 위치한 순열을 찾는 방법1이 1번째에 올 경우의 수 = 6 (..

13251번: 조약돌 꺼내기 (acmicpc.net)  M개의 색, M개의 색을 가진 조약돌이 몇개인지, 랜덤하게 뽑을 수 K를 입력받습니다.이때 K개의 조약돌이 모두 같은 색일 확률을 구하면 됩니다. 2개의 랜덤한 조약돌을 뽑을때의 경우의 수는 이렇습니다. 총 18개 중 5개의 조약돌이 있는 색을 2번 뽑을 확률 -> 5 / 18 * 4 / 17 즉A개의 조약돌을 가진 색을 2번 뽑을 확률 -> (A개 / 조약돌 총갯수) * (A - 1개 / 조약돌 총갯수 - 1)이러한 점화식을 바탕으로 코드를 만들면 쉽게 풀 수 있습니다.  정답 코드#include #include using namespace std;static int D[1001]; double Total = 0;int M, K;// 색상 A 수..

1010번: 다리 놓기 (acmicpc.net) 서쪽, 동쪽에 각각 N개, M개의 사이트가 주어지고 (N M개의 사이트중 N개를 선택하라는 것이고 모든 경우의 수를 구하라는 것은 이항계수 구하는 공식을 이용하라는 의미입니다.  이항계수 구하기N개의 수 중 K개를 선택하는 경우의 수를 구하는 방법은 점화식을 구하는 것에서 부터 시작합니다. 5개중 3개를 선택하는 경우의 수 점화식의 경우D[5][3] = D[4][2] + D[4][3]5개중 3개를 선택하는 경우flrjtwjrjt.tistory.com 정답 코드#include #include #include using namespace std;static int D[1001][1001]; int array[5][5] = { {1, 0, 0, 0, 0}, //..

2775번: 부녀회장이 될테야 (acmicpc.net) 이항계수 구하기N개의 수 중 K개를 선택하는 경우의 수를 구하는 방법은 점화식을 구하는 것에서 부터 시작합니다. 5개중 3개를 선택하는 경우의 수 점화식의 경우D[5][3] = D[4][2] + D[4][3]5개중 3개를 선택하는 경우flrjtwjrjt.tistory.com이항계수 구하기와 굉장히 비슷한 문제 문제 핵심“a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다”"0층부터 있고 각층에는 1호부터 있으며, 0층의 i호에는 i명이 산다." 0층 i호에는 i명이 살고 있고, 모든 호의 1호에는 1명이 살고있다는것을 도출할 수 있음{1, 0, 0, 0} // 3층{1, 0, 0, 0} ..

백준 11050번: 이항 계수 1 (acmicpc.net)백준 11051번: 이항 계수 2 (acmicpc.net) 이항계수 구하기N개의 수 중 K개를 선택하는 경우의 수를 구하는 방법은 점화식을 구하는 것에서 부터 시작합니다. 5개중 3개를 선택하는 경우의 수 점화식의 경우D[5][3] = D[4][2] + D[4][3]5개중 3개를 선택하는 경우flrjtwjrjt.tistory.com 11050 문제와 11051 문제는 같은 문제이지만 다른 속도를 요구하는 차이가 있습니다.11051을 해결할 수 있으면 11050도 해결할 수 있기에 같은 코드로 해결했습니다. 11050#include #include #include using namespace std;static int N, K;static int D..

11438번: LCA 2첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정www.acmicpc.net   11437 LCA (최소 공통 조상) [Gold III]11437번: LCA첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개flrjtwjrjt.tistory.comLCA2는 LCA와 똑같은 문제지만 보다 빠른 속도를 요구하고있습니다.이 문제를 해결하기 위해서는 최소 공통 조상을 찾는 함수의 '두 노드의 깊이를 맞추는 ..

11437번: LCA첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정www.acmicpc.net 문제 풀이 법1. 연결된 노드 데이터를 BFS를 통해 트리로 만들고 깊이를 저장한다2. 두 노드의 공통 조상을 찾기 위해 두 노드의 깊이를 맞춘 후 부모 노드로 올라가며 같은 노드가 나오는지 찾는다#include #include #include using namespace std;vector> tree;vector depth;vector parent;vector visited;int executeLCA(int a, int b);void BFS(int i);int..

11505번: 구간 곱 구하기첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄www.acmicpc.net 세그먼트 트리세그먼트 트리(Segment Tree) 구간 쿼리와 수정이 빈번하게 일어나는 상황에서 유용하게 사용할 수 있는 자료구조입니다. 배열의 특정 구간에 대한 정보를 빠르게 구하거나 업데이트할 때 사용되며flrjtwjrjt.tistory.com#include #include #include using namespace std;vector tree;static..

10868번: 최솟값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 www.acmicpc.net 세그먼트 트리 세그먼트 트리(Segment Tree) 구간 쿼리와 수정이 빈번하게 일어나는 상황에서 유용하게 사용할 수 있는 자료구조입니다. 배열의 특정 구간에 대한 정보를 빠르게 구하거나 업데이트할 때 사용되며 flrjtwjrjt.tistory.com #include #include #include using namespace std; vector tree; void SetTree(int i); int GetMin(int s,..

2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 세그먼트 트리 세그먼트 트리(Segment Tree) 구간 쿼리와 수정이 빈번하게 일어나는 상황에서 유용하게 사용할 수 있는 자료구조입니다. 배열의 특정 구간에 대한 정보를 빠르게 구하거나 업데이트할 때 사용되며 flrjtwjrjt.tistory.com #include #include #include using namespace std; static vector tree; long getSum(int s..