welcome! welcome!

FIsher-Yates Shuffle 순서를 정하는 문제에 직면하였을 때, 원소들을 어떻게 무작위적으로 배치하는가 생각이 들었다. 산업공학과 학부 시절에 가장 흥미가 있었던 분야가 통계/실험계획법이었기에, 랜덤/샘플링 이라는 단어만 들어도 그냥 재밌을것 같다. 현실 문제 만약 n 명의 사람이 있다. n 명의 사람을 일렬로 세우는데 순서를 무작위적으로 바꾸기 위한 알고리즘을 제시하라. 편향된 알고리즘 제시 이 이야기를 시작하기 전에 우선 편향된 알고리즘을 보여주려고 한다. n 개의 원소를 무작위로 셔플하는 naive approach #include #include #include #include #include using namespace std; vector ans; set s; int main() { ..

link https://codeforces.com/contest/496/problem/D Problem - D - Codeforces codeforces.com 흥미로운 문제다 테니스게임은 set라는 개념이 있다. 하나의 set은 어떤 플레이어가 점수 t를 달성하면 끝나고, 어떤 플레이어가 s개의 set을 이기면 테니스 게임이 끝난다. 프로그래밍 문제는 이 부분에 대한 질문이다. 만약 어느 게임의 스코어 정보만 남아있을 때 s와 t를 찾아낼 수 있는지에 대한 문제다. 다음 예를 보자. 5 1 2 1 2 1 5개의 숫자정보 아래 숫자 5개는 score를 낸사람의 번호다. 이 때 s와 t를 추론하는 것이다. naive 한 접근법은 모든 s 가능성을 탐색하자. s : from 1 to n. 만약 5개의 점수가..

참고문헌 나무위키 https://namu.wiki/w/%EC%A4%91%EA%B5%AD%EC%9D%B8%EC%9D%98%20%EB%82%98%EB%A8%B8%EC%A7%80%20%EC%A0%95%EB%A6%AC 중국인의 나머지 정리 - 나무위키 나눗셈 정리에 의하여 m=q⋅lcm(a1,a2,⋯ ,an)+rm=q\cdot\text{lcm}\left(a_1,a_2,\cdots,a_n\right)+rm=q⋅lcm(a1​,a2​,⋯,an​)+r 을 만족하는 정수 q,rq,rq,r이 유일하게 존재한다 (0≤r≤lcm(a1,a2,⋯ ,an)0\leq r\leq\text{lcm}\left(a_1,a_2,\cdots,a_n\right)0≤r≤lcm(a1​,a2​,⋯,an​)). 그런데 aia_iai​가 mmm namu..

You are given a sequencea1,a2,…,ana1,a2,…,anconsisting ofnnnon-zero integers (i.e.ai≠0ai≠0). You have to calculate two following values: the number of pairs of indices(l,r)(l,r)(l≤r)(l≤r)such thatal⋅al+1…ar−1⋅aral⋅al+1…ar−1⋅aris negative; the number of pairs of indices(l,r)(l,r)(l≤r)(l≤r)such thatal⋅al+1…ar−1⋅aral⋅al+1…ar−1⋅aris positive; Print two integers — the number of subsegments with negat..

백준 2133 타일채우기 해설 흥미로운 문제이다. 정답을 미리 알거나 스포일링 당하는건 괴롭지만, ... 생각해나갈 때는 알쏭달쏭한 즐거운 문제였을 것이다.(구현문제보단 재밌는듯) 가로 길이 2 인 것을 만드는 경우의 수는 3가지이다. ( ||_ ),( _|| ), ( _ _ _ )이다. 임의의 길이 i를 만드는 데에는 i-2 길이를 만드는 경우의 수에 3가지 경우의 수를 조합하는 것이므로, f(i) = f(i-2)*2 이다. 그리고, 길이 4 이상부터 다음과 같은 형태를 만들 수 있다. 이러한 형태는 4, 6, 8, ... i 길이 만큼 만들 수 있고, 뒤집은 형태도 있기 때문에 각 길이마다 2가지의 경우의 수가 있다. 이를 종합하면 i를 만드는 경우의 수는 다음과 같다. f(i) = f(i-2)*2 ..

백준 14494 다이나믹이 뭐에요? 해설 n*n의 2차원 공간에서 오른쪽, 아래쪽, 우아래 대각 세 방법만 이용하여 이동한다고 하자. 이때 임의의 점 (x, y)에 도달 할 수 있는 경우의 수 f(x, y)는 f(x-1,y) + f(x, y-1) + f(x-1, y-1)이다. d배열을 1칸 크게 잡는다면 특별히 배열 range-exception 처리를 할 필요 없이 온전하게 연산에만 집중할 수 있다. #include #define MOD ((int)1e9+7) using namespace std; int d[(int)1e3+1][(int)1e3+1]; int main() { int n, m; cin >> n >> m; d[0][0] = 1; for (int i=1; i

백준 2037 문자메세지 해설 ABC, DEF, GHI, JKL, MNO, PQRS, TUV, WXYZ 가 각각 같은 번호를 눌러 입력해야하므로 이전에 동일한 번호를 눌렀다면 추가로 대기시간 W시간을 요구한다. 공백에 대해선 대기시간 W 이 필요하지 않다. BC, EF, HI .. 등에 대해선 여러번 눌러야하므로 P*required[알파벳]을 이용해 구할 수 있게 하였음. 입력 받는 것이 조금 까다로울 수 있다. ````C++ #include #include #include using namespace std; int a[26] = { 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 9, 9, 9, 9 }; int required[26..

백준 1463 1로 만들기 해설 Queue를 이용하여, 임의의 n 에서 1 까지의 이동하는 것을 구현하여서 최단경로 길이를 구할 수 있다. (BFS) 하지만 문제를 뒤집어서 생각해보면, n에서 1까지의 최단경로 길이는 다음 세개 중 하나이다. n/2 에서 1까지 가는 최단경로 길이 + 1 n/3 에서 1까지 가는 최단경로 길이 +1 n-1 에서 1까지 가는 최단경로 길이 + 1 아래는 memoization을 이용하여 문제를 해결한 소스코드이다. ````C++ #include #include #include using namespace std; int d[(int)1e6+1]; int go(int cur) { if ( cur = 0) return d[cur]; d[cur] = 1e9; if ( cur%2 ..