본문 바로가기

Algorithm

 (2139)
(C++) - 백준(BOJ) 13251번 : 조약돌 꺼내기 https://www.acmicpc.net/problem/13251 13251번: 조약돌 꺼내기 첫째 줄에 뽑은 조약돌이 모두 같은 색일 확률을 출력한다. 정답과의 절대/상대 오차는 10-9까지 허용한다. www.acmicpc.net 확률 문제였습니다. 풀이방법 m개의 색으로 이뤄진 조약돌들 중 k만큼 랜덤으로 골랐을 때 모두 같은 색일 확률을 구해야합니다. 3개의 색으로 이워진 조약돌들이 각 색마다 3, 5, 7개 있다면 n은 3 + 5 + 7인 15입니다. k가 지금 뽑아야하는 색의 조약돌의 개수이하라면 뽑을 수 있습니다. k를 3이라고 가정해보면 확률을 구하는 공식은 다음과 같습니다. 정답 : 3/15 * 2/14 * 1/14 + 5/15 * 4/14 *...* 1/11 + 7/15 * ... * ..
(C++) - 백준(BOJ) 5557번 : 1학년 https://www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net dp로 해결한 문제였습니다. 풀이방법 d[i][j] = +또는 -인 수식을 i개 뽑았을 때 j수를 만드는 경우의 수로 정의합니다. i를 n-2개 뽑았을 때 j가 마지막 카드에 도달했다면 경우의 수를 1늘려줍니다. Code #include #define ll long long using namespace std; ll n, num[101], d[101][101]; ll dp(int i, in..
(C++) - 백준(BOJ) 5568번 : 카드놓기 https://www.acmicpc.net/problem/5568 5568번: 카드 놓기 예제 1의 경우 상근이는 11, 12, 21, 112, 121, 122, 212를 만들 수 있다. www.acmicpc.net 순열문제였습니다. 풀이방법 1. 자기자신을 뽑지 않으면서 순서 상관있도록 뽑으면됩니다. 2. 카드를 뽑았으면 카드들을 나열한 뒤 set에 넣어줍니다. 3. set의 size를 출력합니다. Code #include using namespace std; int n,k; vector card; set cardSet; vector tmp; int ck[11]; void dfs(int depth){ if(depth == k){ string c; for(auto t : tmp) c += t; cardS..
(C++) - 백준(BOJ) 1256번 : 사전 https://www.acmicpc.net/problem/1256 1256번: 사전 첫째 줄에 N, M, K가 순서대로 주어진다. N과 M은 100보다 작거나 같은 자연수이고, K는 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net dp로 푼 문제였습니다. 풀이방법 1. d배열 : i개의 a와 j개의 z로 만들 수 있는 문자열의 개수로 정의합니다. 점화식으로 다음과 같이 표시됩니다. d[i][j] = min(d[i][j], d[i-1][j] + d[i][j-1]) 2. 최대한 'a'를 앞에 붙여줘야합니다. Code #include using namespace std; string word; //i개의 a와 j개의 z로 만들 수 있는 문자열의 개수 int d[101][101..
(C++) - 백준(BOJ) 11444번 : 피보나치 수 6 https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 행렬 곱셈을 이용해 log n만에 피보나치를 구하는 문제였습니다. 풀이방법 ​F(n) = F(n-1) + F(n-2) (n > 2) 를 행렬로 나타내면 다음과 같습니다. {\begin{pmatrix} F(n) \\ F(n-1) \end{pmatrix}} = {\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}} X {\begin{pmatrix} F(n-1) \\ F(n-2) \end{pmatrix}} 1. 행렬로 피보나치 수열을 연산하게 되면 l..
(C++) - 백준(BOJ) 6588번 : 골드바흐의 추측 https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 수학문제였습니다. 풀이방법 1. 에라토스테네스의 체를 이용해 i번째 수가 소수인 부분은 0 아닌 부분은 1로 ck배열에 저장합니다. 2. 답 출력 : i와 n-i가 모두 소수라면(ck배열에 해당 값이 0이라면) 정답을 출력합니다. * 수학적으로 100만 이하의 소수 두 개의 합으로 모든 짝수를 표현할 수 있습니다. 따라서 안되는 경우는 없습니다. 낚시입니다. Code #in..
(C++) - 백준(BOJ) 4358번 : 생태학 https://www.acmicpc.net/problem/4358 4358번: 생태학 프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어 www.acmicpc.net 자료구조 map을 사용해보는 문제였습니다. 풀이방법 1. map의 key를 종 value를 해당 종의 나무 개수로 하여 저장합니다. 2. 정답을 출력합니다. * printf("%.소수점 몇 쨰자리f) 로 출력 형식을 고정시킬 수 있습니다. Code #include using namespace std; map m; double totalCnt; string s; int main(){ wh..
(C++) - 백준(BOJ) 6416번 : 트리인가? https://www.acmicpc.net/problem/6416 6416번: 트리인가? 트리는 굉장히 잘 알려진 자료 구조이다. 트리를 만족하는 자료 구조는 비어 있거나(노드의 개수가 0개), 노드의 개수가 1개 이상이고 방향 간선이 존재하며 다음과 같은 조건을 만족해야 한다. www.acmicpc.net 트리의 성질을 이해해 구현하는 문제였습니다. 풀이방법 입력이 트리가 1개이며 연결 그래프임이 보장되므로 다음과 같은 2가지 성질에 주의해야합니다. 1. 트리는 정점의 개수 = 간선의 개수 + 1이어야 합니다. set을 이용해 정점을 저장하고 간선은 u와 v사이의 관계를 입력할 때마다 추가함으로써 구할 수 있습니다. 2. 트리는 사이클이 없어야합니다. 즉, 한 노드에서 출발해 그 노드로 돌아오는 경로는..

티스토리툴바