알고리즘/Baekjoon (202) 썸네일형 리스트형 차분 배열 [19551] [1. 문제 설명]https://www.acmicpc.net/problem/19951[2. 코드] 라빈-카프 [3033] [1. 문제 설명]https://www.acmicpc.net/problem/3033[2. 풀이 접근]완전 탐색으로 접근부분 문자열이 발생할 수 있는 대상은 아래와 같다.부분 문자열의 길이는 1 부터 L-1 까지길이 L-1 부터 발생 할 수 있는 모든 부분 문자열을 모두 확인하여 비교하는 방법라빈-카프 알고리즘 등을 이용하여 문자열 비교를 진행하더라도, O(L2) 의 시간 복잡도 발생이분 탐색으로 접근길이가 4인 부분 문자열이 2개 이상 존재한다고 했을 때,길이가 3인 부분 문자열의 존재는 굳이 확인하지 않아도 된다."ABCDE"FGH"ABCDE"XYZ=> ABCD 라는 중복 되는 부분 문자열이 있음을 바로 알 수 있다.즉, 중복 되는 부분 문자열이 있을 때, 그 보다 작은 길이의 부분 문자열의 중복 존재.. 포함-배제의 원리. [16565] [1. 문제 설명]https://www.acmicpc.net/problem/16565[2. 풀이 접근]여러 집합의 합집합의 원소 수를 셀 때,각 집합의 크기를 더한 뒤 겹치는 부분(교집합)을 빼거나 더하는 과정을 반복하여 정확한 전체 개수를 구하는 방법. 가령, 1이상 100 이하의 자연수 집합에서 2 또는 3의 배수의 개수를 구해야 할 때,2의 배수 개수를 구하고, 3의 배수를 구하여 서로 더하면,6의 배수가 중복되어 더해진다. (교집합이 되어버림) 따라서, 6의 배수 개수를 전체 결과에서 빼야 정확한 개수를 구할 수 있다.[3. 코드] 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. 소스코드] 컨벡스 헐. [1708] [1. 문제 설명]https://www.acmicpc.net/submit/1708/87944456[2. 풀이 접근]컨벡스 헐 알고리즘의 기본 문제[3. 코드] 네트워크 유량. [6086] [1. 문제 설명]https://www.acmicpc.net/problem/6086[2. 풀이 접근]동일한 edge 가 여러 번 주어질 수 있다.이 경우 해당 edge 의 용량을 그 만큼 늘려 주도록 한다. 그리고,,, [3. 코드] 아호코라식. [10256] [코드] 트라이. [5052] [1. 문제 설명]https://www.acmicpc.net/problem/5052[2. 풀이 접근]공통 된 접두어가 있는 경우 해당 목록은 일관성이 없다고 볼 수 있다.트라이를 이용하여, 공통된 접두어가 있는지 확인 할 수 있다.[3. 코드] 이전 1 2 3 4 ··· 21 다음