알고리즘 (419) 썸네일형 리스트형 파스칼 삼각형 [1. 개요]파스칼의 삼각형은 이항계수, 조합(Combination) 과 본질적으로 그 의미가 같다. 특히, 경우의 수를 계산해야 할 때 그 수식 계산을 직접 구현해야하는 경우가 번거로울 수 있다.특히, mod 연산을 해야하는 경우라면 난이도가 더 올라가게 됨.페르마 소정리를 적용해야 하기에..그러나, 이러한 계산을 파스칼의 삼각형을 구하듯 계산하면 그 난이도가 조금 더 쉬워진다.단순 덧셈 연산만 존재하기에 mod 연산의 분배법칙이 조금 더 수월하게 된다. 따라서, 파스칼 삼각형을 이용하여 이항계수를 계산하도록 하는 편이 조금 더 나을지도 모르겠다.(n, k) 에서 n 이 너무 커지면 적용하기 어려울지도,n 에 해당하는 배열을 할당 할 수 없음. (이 경우는 직접 계산하는 방식으로 접근해야 함.)예제 .. mo`s [13547] [1. 문제 설명]https://www.acmicpc.net/problem/13547[2. 풀이 접근]쿼리의 순서가 결과에 영향을 주지 않음 => 오프라인-알고리즘그 중, mo`s 알고리즘을 이용하여 문제를 해결하도록 한다. 코드 주석 참조. 시간복잡도..[3. 코드] 스프러그-그런디 [16895] [1. 문제 설명]https://www.acmicpc.net/problem/16895[2. 풀이 접근]최초 상태에서 필패하는지 먼저 확인 한다.필패 하면, 이기기 위해 첫턴에 할 수 있는 경우의 수는 존재하지 않는다.이길 수 있는 상황이라면,n 번째 돌무더기를 제외하고, 그런디 수를 계산한다.n 번째 돌무더기에서, 위에서 계산한 그런디 수로 만들게 끔 돌을 가져갈 수 있는지 확인한다.Value ^ Value = 0, 이므로 첫번째 턴에서 돌을 가져가서 전체 그러딘 수를 0으로 만들면,다음턴에 상대는 필패하게 된다.하나이상 제거가 반드시 발생하기 때문에, 아무것도 하지 않는 경우는 발생할 수 없다.그러나, 아무것도 하지 않는 경우는 이미 고려되었기 때문에,if (v == 0) return 0;아래 조건문에.. 슬라이딩 윈도우. [12891] [1. 개요]https://www.acmicpc.net/problem/12891[2. 문제 풀이]동적 계획법의 개념이 일부 포함되어 있음[3. 소스코드] [Queue] ITES [1. 문제설명] [2. 코드] [Stack] BRACKETS2 [1. 문제 설명] [2. 코드] [연결리스트] JOSEPHUS [1. 문제 설명]https://algospot.com/judge/problem/read/JOSEPHUS[2. 풀이 접근] [3. 코드] [부분 합] CHRISTMAS [1. 문제 설명]https://www.algospot.com/judge/problem/read/CHRISTMAS[2. 풀이 접근] [3. 코드] 컨벡스 헐. [1708] [1. 문제 설명]https://www.acmicpc.net/submit/1708/87944456[2. 풀이 접근]컨벡스 헐 알고리즘의 기본 문제[3. 코드] Convex hull (볼록 껍질) [1. 개요]컨벡스 헐(이하 볼록 껍질) 이란?평면 위 N개의 점이 주어졌을 때,M 개의 점을 이용하여, 나머지 모든 점을 내부에 포함하게 만드는 도형.즉, 모든 점을 포함하는 볼록 다각형 중, 면적이 최소인 다각형을 말한다.[2. 알고리즘 - 개요]컨벡스 헐을 구하는 알고리즘은 아래와 같은 것들 있다.Graham scan (그라함 스캔)Jarvis marchDivide & Conquer여기서 가장 유명한 알고리즘이 그라함 스캔이라고 한다.그라함 스캔의 동작 방식은 아래와 같다.주어진 점을 y 순으로 정렬한다. (y 가 같은 경우는 x 순으로 정렬)정렬 된 점 중 첫번째 점을 기준으로 반시계 방향으로 나머지 점들을 정렬한다.정렬 된 점 들 중, 처음 2 개의 점을 스택에 푸쉬한다.그 다음 점이, 스택의.. 이전 1 2 3 4 5 ··· 42 다음