hyejun CSlog

정수론이란?각종 수의 성질을 다룬다.약수 배수 최대공약수 최소공배수 소수 판결최대공약수소인수분해 이용 - 두 수 중 작은 수 기준으로 돌리면서 가장 큰 공통 약수 구하기구현 까다로움, 시간복잡도 O(n)유클리드 호제법: 시간복잡도 O(log(n))기본 원리A와 B의 최대공약수 = A-B 와 B의 최대공약수A = a*GB = b*G(a와 b는 서로소)A - B = a*G-b*G = (a-b)*G(a-b)와 b 또한 서로소 -> A-B 와 B의 최대공약수도 G이미 gcd⁡(a,b)=1 이므로, 어떤 정수 x,y 가 존재해서 ax+by=1을 만족시킨다. 그럼 (a−b)x+by=1도 만족. 어떤 정수 조합으로 1을 만들 수 있으니까 gcd(a−b,b)=1 이 된다.GCD(A,B) = GCD(A-B,B) -> A..

스택(Stack)LIFO(last in first out)자료의 맨 끝 위치에서만 모든 연산이 이루어진다.모든 연산에 대한 시간복잡도는 O(1)연산이 이루어지는 위치 : top, 삽입: push, 삭제: pop std::stackpush(element): top에 원소 추가pop(): top에 있는 원소 삭제top(): top에 있는 원소 반환empty(): 스택이 비어있는지 확인(비어있으면 true)size(): 스택 사이즈 반환* 파이썬은 ?따로 Stack 자료구조 제공 x. 이미 리스트에 모두 구현돼있다.list()stack = list()일 때...stack.append(element): top에 원소 추가stack.pop(): top에 있는 원소를 반환하고 삭제stack[-1]: top에 있는 ..

dynamic programming: 큰 문제를 부분문제로 쪼개어 푸는데, 여러 번 나오는 부분문제를 기억해서 최적화하는 기법 메모이제이션피보나치 수열: 단지 이미 계산한 값을 들고있는 것으로 호출의 양을 엄청나게 줄이는 것을 알 수 있다.dp - 메모이제이션 : 여러 번 나오는 부분 문제를 기억한다.사용법값을 저장해둘 테이블 만들기테이블을 식별할 수 있는 값으로 초기화해두기;내가 지금 풀어야 하는 문제의 답이 테이블에 존재하면 사용하기dp - 분할정복 : 문제를 바로 해결 가능하면 해결함. 지금 바로 해결 불가하면 문제를 잘게 쪼갠 후 조립문제 정의부분문제 정의내가 정의한 부분문제로 주어진 문제를 해결 가능한지 보이기내가 정의한 부분문제를 해결 가능한지 보이기

그래프: 정점의 집합과 간선의 집합으로 정의되는 이산수학의 추상적 구조정점: 어떠한 상태 or 위치 표현간선: 정점 사이의 관계나 연결성 표현ex) 지하철 노선도그래프의 종류모든 간선이 방향이 정해져 있지 않은 그래프하나의 간선으로 양방향으로 이동 가능방향이 정해져 있는 간선이 있는 그래프양방향 간선도 사실 방향이 있는 간선 두 개로 나눠서 생각해볼 수 있음간선에 가중치가 있는 그래프가중치: 간선 이용하는 비용일상예시: 지도 상의 여러 위치를 정점으로, 정점들 사이의 경로를 간선으로 잡으면 경로의 소요시간을 가중치로 모델링 가능같은 집합의 두 정점이 간선으로 이어지지 않게끔 정점들을 두 집합으로 나눌 수 있는 그래프초록색 정점들을 하나의 집합으로 묶고 회색 정점들을 하나의 집합으로 묶을 수 있다.판별법정..

1. 재귀함수함수 안에서 함수 호출 가능. 자기 자신도 호출 가능 >> 재귀함수void f(int x){ // x=3 cout 위는 재귀함수의 예시. 실행과정을 따라가보면 이상한 점 발견 ! x= 3에서 시작한다고 가정재귀적으로 f(3)이 호출된 후 f(2)가 호출된 후 f(1)이 호출된 후,,, 함수가 종료되지 않음!따라서 재귀함수는 종료조건 또는 기저조건을 설정하는 것이 중요void f(int x){ // x=3 cout xvoid f(int x){ if(x두 예시를 합친 예시와 호출과정을 시각화한 그림. 재귀호출이 몇 번 중첩돼 있는지를 재귀깊이라 부르기도 한다.void f(int x){ cout   백트래킹재귀적으로 모든 경우의 수를 탐색하는 문제. 일반적으로 모든 경우의 수를 구하거나 이에 대해..

1. bruteforce(무차별 대입공격)모든 경우에 대하여 조건에 맞는지 검사하는 방법더보기다음 연립방정식에서 x와 y의 값을 계산하시오.   ax+by=c dx+ey=f 각 칸에는 -999 이상 999 이하의 정수만 입력할 수 있다.식정리: ax + by = c , dx + ey = f , x = (c-by)/a로 구해두고 d(c-by)/a+ey = f , d(c-by) + ae , y = af y(ae-bd) = af-dc , y = (af-dc)/(ae-bd) 로 구할 수 있나?! --> 오류발생 !!y = (af-dc)/(ae-bd) 에서 ae-bd=0이라면 0으로 나누는 오류 발생, 이를 케어해줬다 해도 나누는 연산으로 인해 각종 억까 발생가능x와 y의 범위가 [-999,999]인 정수이므로 ..

prefix sum(누적합)배열에서 각 위치까지의 합을 미리 계산하는 기법f(i) = 구간 [1,i]의 원소를 합친 값알아볼 것우리가 원하는 것을 구할 수 있는가이걸 구하는 것은 효율적인가f(1)부터 f(n)까지 모두 구했다고 가정 -> 문제에서 요구하는 구간[i,j]에 속하는 원소들의 합을 구해야 함.f(j)-f(i-1)로 구할 수 있음f(1)부터 f(n)까지 구하려면 1+2+...+n번 연산해야돼서 나이브(별 다른 처리를 하지 않다)하게 구하면 O(N^2) but 최적화를 통해 O(N)으로 만들기f(i)=구간 [1,i]의 원소의 합 ---> f(i-1)=구간 [1,i-1]의 원소 합.f(i-1)을 안다면 f(i)=f(i-1)+A[i]로 O(1)만에 구할 수 있다.f(1)=A[1]이므로 이도 O(1)이..

제곱시간 미만 정렬합병정렬(merge sort) void merge(vector&arr, int start, int mid, int end){ int leftIdx=start; int rightIdx=mid+1; vector sorted; while (leftIdx & arr, int start, int end){ if (start >= end) return; int mid = (start + end) /2; mergeSort(arr, start, mid); mergeSort(arr, mid+1, end0; merge(arr, start, mid, end); } void solve(){ vector arr={2, -33, 24, 4, 54, 1, 2453, -34..

1. 제곱정렬정렬 알고리즘원소들을 번호순이나 사전순서와 같이 일정한 순서대로 열거하는 알고리즘아래 정렬 알고리즘들은 O(n^2)에 대해 동작1.1 버블정렬(Bubble Sort)void bubblesort(int A[],int N){ bool swapped = true; while(swapped){ swapped = false; for(int i=1; i첫번째 실행에 가장 큰 원소 정렬i번째 실행에는 i번째로 가장 큰 원소 정렬최악의 경우 N-1번째 실행에 N-1번째로 가장 큰 원소 정렬. 가장 작은 원소 또한 맨 앞에 위치 --> 바깥쪽 while문이 최대 N-1번 실행 -- 시작 배열이 역순으로 정렬되어 있을 때 해당안쪽반복문에 대한 최악의 경우: 바깥쪽 반복문의 모든 i번째 실행에서 i번째..

1. 알고리즘이란?수학과 computer science에서유한열수학적으로 엄격한 지침특정 종류의 문제 해결 or 연산수행에 사용2. C++int a; a=3 / int b=5; / int c=a+b;자료형1. 정수형: int, long long, unsigned int, unsigned long long 2. 실수형: float, double, long double (float보다 double이, double보다 long double이 더 정확(저장값과 실제값의 오차가 더 작음) 3. 문자 및 문자열#include #include int main(){ char a='a';//char은 작은따옴표로 감싸기 std::string hello="ICPC Sinchon 25W";//string은 큰 따옴표로..