MODE::CREATIVE

https://www.acmicpc.net/problem/15649 문제 해석1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 사전순으로 출력알고리즘 분류백 트래킹풀이재귀함수와 불리언 배열을 이용해서 해결한다endl 을 사용하면 시간초과가 발생하니 주의코드#include using namespace std;static int N,M;static int arr[8];static bool check[8];void find(int len) { if (len == M) { for (int i=0; i > N >> M; find(0); return 0;}

https://www.acmicpc.net/problem/15650문제 해석사전순으로 증가하는 수열의 모든 경우를 출력하는 문제알고리즘 분류백 트래킹풀이재귀함수를 이용해서 해결한다코드#include using namespace std;static int N,M;static int arr[8];void find(int x, int len) { if (len == M) { for (int i=0; i > N >> M; find(0, 0); return 0;}

https://www.acmicpc.net/problem/15652 아래 문제의 변형이다.https://mode-creative.tistory.com/28 [백준][c++] 15650번: N과 M (2)https://www.acmicpc.net/problem/15650문제 해석사전순으로 증가하는 수열의 모든 경우를 출력하는 문제알고리즘 분류백 트래킹풀이재귀함수를 이용해서 해결한다코드#include using namespace std;static int N,M;stmode-creative.tistory.com  문제 해석사전순으로 증가하는 수열의 모든 경우를 출력하는 문제15650번 문제와 달라진점:증가 수열에서 중복된 숫자를 인정함알고리즘 분류백 트래킹풀이재귀함수를 이용해서 해결한다.코드#include ..

https://www.acmicpc.net/problem/1305문제해석문자열에서 가장 짧은 패턴의 길이를 찾는 문제KMP 알고리즘과 가장 짧은 패턴은 (문자열길이 -  LSP배열에서의 마지막 요소)라는 것을 알면 쉽게 풀 수 있다.풀이LPS 배열이란?LPS(Longest Prefix which is also Suffix) 배열은 주어진 문자열의 접두사(prefix)와 접미사(suffix)가 일치하는 가장 긴 부분 문자열의 길이를 저장한 배열입니다.참고: https://mode-creative.tistory.com/25 [알고리즘] KMP알고리즘 (문자열 검색 알고리즘)KMP 알고리즘 이란주어진 텍스트 문자열에서 특정 패턴 문자열이 등장하는 위치를 효율적으로 찾는 데 사용됩니다. KMP 알고리즘은 패턴 ..

KMP 알고리즘 이란주어진 텍스트 문자열에서 특정 패턴 문자열이 등장하는 위치를 효율적으로 찾는 데 사용됩니다. KMP 알고리즘은 패턴 매칭의 각 단계에서 이미 비교된 정보를 활용하여 불필요한 비교를 줄임으로써 검색 속도를 높이는 방식으로 작동합니다.KMP 알고리즘 구현 코드public class KMP { // KMP 알고리즘을 사용하여 패턴을 검색하는 메서드 public static void KMPSearch(String pattern, String text) { int M = pattern.length(); int N = text.length(); // 부분 일치 테이블을 생성합니다. int[] lps = new in..

숭실대학교 컴퓨터학부의 알고리즘 수업을 들으며 정리한 내용입니다.참고교재: 쉽게 배우는 알고리즘(문병로)선택 알고리즘 1.선형 시간 선택 알고리즘(QuickSelect)2.최악의 경우 선형 시간 선택 알고리즘 최악의 경우 선형 시간 선택 알고리즘앞서 주어진 리스트에서 k번째로 작은(또는 큰) 요소를 찾는 선택 알고리즘을 구현했습니다.하지만 최악의 경우, 선택한 기준 원소가 항상 최솟값이나 최댓값이 되어, 분할이 매우 불균형하게 이루어지면 재귀 호출이 깊어져 Θ(n²) 시간이 걸립니다. 이를 해결하기 위해서 Median of Medians 알고리즘을 적용해 Θ(n)의 시간 복잡도를 보장할 수 있습니다. Median of Medians 알고리즘 단계그룹화:주어진 배열을 5개씩의 그룹으로 나눕니다. 마지막 ..