11232번: Shuffles (acmicpc.net) 주어진 수열이 최소 몇번의 shuffle로 이루어진 수열인지 구하는 문제 셔플방법은 수열에서 어떤 특정 지점에서 두 부분으로 나누고 두 부분을 순서를 유지한채 섞는 것이다. 1 2 3 4 5라면.. 1 2 3 4 5로 나누고 1 4 2 5 3 처럼 섞는 것 주어진 수열에서 어떤 특정 지점 k에서 나뉘었다고 한다면, 2개의 부분 수열 1,2,3,...,k k+1,k+2,...,n으로 나뉘고 이것이 섞일 것이다. 이렇게 섞인 수열에서 또 한번 나누면 최대 4개의 부분 수열 1,2,3,..,k1 k1,k1+1,...k k+1,k+2,..k2 k2+1,k2+2,...,n으로 구해진다. 여기서 또 한번 나누면 최대 8개의 부분 수열을 얻을 수 있다. ...
1. 그래프를 통한 전파 1) 정보의 전파 SNS에 의한 정보 전파 스페인의 15M 운동은 트위터를 통해 전국적으로 알려졌다 2) 행동의 전파 SNS에 의한 행동 전파 틀리면 펭귄 사진으로 프로필 사진을 바꿈 아이스 버킷 챌린지 3) 고장의 전파 small world effect의 예시라고 볼 수도 있다. 컴퓨터 네트워크 같은 경우 일부분만 고장나도 다른 부분에서 과부하가 걸려 금방 전체가 고장난다 4) 질병의 전파 사회에서 극히 일부만 질병에 걸려도 전체로 퍼지는 경우가 많다. 네트워크에서 전파과정은 다양하면서 복잡하다. 이것을 체계적으로 이해하고 분석하기 위해 그래프를 이용한 수학적으로 모형화할 필요가 있다. 2. 선형 임계치 모형(linear threshold mode..
18668번: Find the Vertex (acmicpc.net) 무방향 연결그래프가 주어지고, self-loop나 multiple edge가 없다. 정점의 번호가 1번부터 n번까지 되어있고, 시작정점 s번에서 다른 정점까지의 거리를 3으로 나눈 나머지가 배열로 주어진다. 여기서 s가 무엇인지 찾는 문제 n,m 제한이 50만이다보니, 하나하나 해보기는 어렵다. 일단 거리 배열에서 0인 값인 정점 번호가 일단 정답 후보가 될 것이다. 시작정점 s에서 거리가 3,6,9,... 3의 배수여도 0이기 때문에 정답이 아닌 정점이 있을 수도 있다. 또 하나 알 수 있는 점은, 시작정점 s라면 인접한 정점까지 거리는 무조건 1이다. 물론 위 그림과 같이 s에서 인접한 3개 정점과 똑같이 인접한 어떤 정점 A..
1. decision making 1) deductive 모든 사람은 죽는다. 소크라테스는 사람이다. 따라서 소크라테스는 죽는다 이미 정의된 혹은 증명된 사실들을 바탕으로 원하는 가설들을 증명하는 과정 참고로 7C2는 7개 중에서 2개를 선택하는 경우의 수인데 이 모든 경우의 수들이 노란색 동그라미들에 전부 대응시킬수 있어서 1+2+3+4+5+6=7C2가 성립 전제에 따라 바뀌는 결과 10진수에서는 1+1=2이지만, 2진수에서는 1+1=0 12진수에서는 1+15=4, 13진수에서는 1+5=-7(6이라 해도 되긴 하는데 1+5 = 6보다는 -7로 해서 다르게 할려고 쓴것 같음) 전제가 참이면 결론이 참이다 2) inductive 해가 동쪽에서 떠서 서쪽에서 뜨는 것은 수만년 전부터 많이 관찰..
24597번: Reversibly Cyclic Strings (acmicpc.net) 문자열 s의 cyclic substring이라는 것은 s를 rotate했을때 부분문자열 t를 말한다. 'fatcat'에서 'atf'는 fatcat에서 왼쪽으로 1칸 rotate하면 atcatf인데 여기에 부분문자열로 있다 만약 s의 모든 부분문자열 t에 대하여 t를 뒤집은 것이 s의 cyclic substring이라면 s를 'Internally Reversibly Cyclic'이라고 정의한다. 주어진 s가 Internally Reversibly Cyclic인지 판단하는 문제 어떤 부분 문자열 t가 s의 cyclic substring이라는 것을 어떻게 알 수 있을까? 한칸 한칸씩 roate해서 판단해봐야할까? fatc..
13531번: Secret Santa (acmicpc.net) n명의 사람이 모자에 이름을 쓰고, 한번 섞은 다음에 다시 가져가는데 적어도 1명 이상이 자기 자신 것을 그대로 가져갈 확률을 구하는 문제 https://deepdata.tistory.com/946 자기 것을 다시 갖지 않고 나눠주는 경우의 수 교란순열(완전순열) 배우기1. 문제 1947번: 선물 전달 (acmicpc.net) 1947번: 선물 전달 경우의 수를 1,000,000,000으로 나눈 나머지를 첫째 줄에 출력한다. www.acmicpc.net 2. 풀이 PS를 위한 수학 - 교란 순열(완전순열) - 와 이게 에러가deepdata.tistory.com 1 - n명의 사람이 모두 자기 자신 것을 가져가지 않는 확률 = 적어도 1명 이..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
