알고리즘

시간복잡도란? 어떤 알고리즘이 입력 크기 N에 따라 얼마나 많은 연산을 수행하는지를 수학적으로 표현한 것임 즉 -> 입력이 커지면 , 이 코드가 얼마나 느려질까를 예측하는 기준 예시 : N번 반복하니까 -> 시간복잡도는 O(N) N * N번 반복하니까 -> 시간복잡도는 O(N²) O(..)식으로 쓰는 이유 이건 빅오(Big-O)표기법이라고 부르는데...

보통 n번째의 피보나치 수를 구하라고 나옴 근데 n번째의 기준이 인덱스처럼 봐서 0번째부터 n번째임 재귀 호출부분을 어케 짜야할지 고민해보자 이런느낌으로 밑에서 구해두면 f(n)값이 숫자가 되니까 더하면 될듯 이제 코드로 짜보자 일단 0이랑 1번째는 고정이니까 i

n!을 구하기 factorial 재귀함수를 만들어준다 재귀함수니까 종류조건을 만들어줘야함(필수) 종류 조건: n ==0 일때 return 1;을 해줌 궁금했던 점 -> 왜 return 0;이 안될까 더이상 재귀호출도 없는데 재귀 호출 마지막에서 factorial(0)

투 포인터 알고리즘(Two Pointer Algorithm) 정렬 + 연속 구간 처리 같은 문제에서 자주 쓰이는 알고리즘임 투 포인터란? 두 개의 포인터를 사용해서 배열을 탐색하는 알고리즘 C 문법* 이거랑 다른거임 가리키다의 의미 보통 왼쪽 포인터(l), 오른쪽 포인터(r)를 써서 배열에서 구간, 쌍, 조건을 만족하는 범위를 찾을 때 씀 투 포인터가...

라이브러리 정리 ![](https://velog.velcdn.com/images/mgh0115/post/21502eba-c481-4574-8494-280d6cda4686/image.p

알고리즘 아이디어 2부터 n까지 모든 수를 소수라고 가정 (배열 prime = [True] * (n+1)) 2부터 시작해서 아직 소수로 남아있는 수(i)의 배수들을 모두 지움(False로 변경) 끝까지 반복하면 남아 있는 모두 소수임 시간 복잡도 일반적인 소수 판별

최대 공약수 = 유클리드 호제법 최소 공배수 = 숫자 A,B이고 최대 공약수 G, 최소 공배수 L이면 A * B = G * L 최소 공배수 = (A*B) / G 아이디어(최대공약수) A , B가 있으면 A가 B(오른쪽)보다 커야함 A - B를 해주고 49 21일때