1. 왜 문자열의 hashing이 필요한가? https://deepdata.tistory.com/960 문자열 해싱(hashing) 기본 개념 배우기String Hashing - Algorithms for Competitive Programming (cp-algorithms.com) String Hashing - Algorithms for Competitive Programming String Hashing Hashing algorithms are helpful in solving a lot of problems. We want to solve the problem of comparing stringdeepdata.tistory.com 두 문자열 S1, S2가 서로 같은지 다른지 비교하고 싶을 때가 있..
1. 왜 확률적 전파 모형이 필요한가? 코로나19가 전파되는 과정을 모형화하고 싶은데 의사결정 기반의 선형 임계치 모형은 적절한 모형일까? 그렇지 않다. 누구도 코로나19에 걸리려고 의사결정을 한것이 아니다. 확률적으로 코로나19에 감염되기 때문에 확률에 기반한 전파 모형이 적절하다. 2. 독립적 전파 모형(independent cascade model) 방향성이 있고 가중치가 있는 weighted directed graph를 생각하자. u에서 v로의 weighted link (u,v)의 가중치는 P(u,v)로 u가 감염되었을 때 v를 감염시킬 확률이다. 당연하지만 시작점인 u가 감염되지 않았을 때는 의미 없다. node u가 감염될때마다 v를 감염시킬 확률 P(u,v)에 의해 다음 v를 감염시킨다...
python에서는 trie가 class로 구현된 경우가 많아 꺼렸는데... 배열로 구현하는 법을 익혀서 기록해보기 https://deepdata.tistory.com/659 문자열 자료구조 Trie 알고리즘 기본기 배우기1. 문자열 단어 저장 'hello', 'hi', 'hey' 등을 저장하고자 할때, 생각할 수 있는 방법중 하나는 dictionary에 저장하는 것이다 d = {'hello':1, 'hi':1, 'hey':1} 단어를 key값으로 저장해두면, 특정 단어를 찾고자deepdata.tistory.com https://blog.encrypted.gg/1059 [실전 알고리즘] 0x1F강 - 트라이안녕하세요, 드디어 마지막 강이라니 가슴이 웅장해집니다. 마지막인만큼 난이도도 끝판왕일 수 있지만 개..
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..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
