시간 복잡도, 빅오표기법, 공간복잡도, 누적합, 구현

[fkdl0048]

재귀함수

• 재귀에 대한 이해는 BF에 대한 이해를 했을 때 된 것 같다.
  • 반복문으로 가능하면 반복문으로

순열

• 순서와 상관있게 뽑는다면 순열이고, 순서와 상관없이 뽑는다면 조합이다.
  • 123을 조합으로 뽑는다면 123이고, 순열로 뽑는다면 123, 132, 213, 231, 312, 321이다.
  • 123에서 두개를 뽑는다면 조합은 12, 13, 23이고, 순열은 12, 13, 21, 23, 31, 32이다.
• C++에서는 next_permutation을 사용하면 쉽게 구할 수 있다. (오름차순)
  • 해당 함수는 현재 주어진 배열의 다음 순열을 구하는 함수이기 때문에 반복해서 사용하여 모든 순열을 구하고 싶다면 정렬을 해야한다.
• 공식이 있다. nPr = n! / (n-r)!
  • 3개중에 1개를 뽑는다면 3! / 2! = 3이다.

조합

• 조합은 순서와 상관 없이가 중요하다. "몇명을 뽑는지"
• 마찬가지로 공식이 있다. nCr = n! / r!(n-r)!
  • 3개중에 1개를 뽑는다면 3! / 1! * 2! = 3이다.

스플릿

• C++은 만들어서 사용해야 한다.
  • 사용할 때 다시 볼것

메모리, 포인터

• 이미 잘 아는 내용

unipue

• 유니크를 목적에 맞게 사용하려면 마찬가지로 정렬 후 사용 그리고 삭제

1주차

누적합

누적합에 관한 내용, 배열을 써서 쉽게 품.

개수를 세는 문제

대부분의 개수를 세는 문제는 배열이나 맵을 사용하여 풀 수 있다.

시간

시간은 이상과 미만이다.

알파벳 문제

대부분 알파벳 문제는 아스키 코드를 사용하여 풀 수 있다.

경우의 수

경우의 수는 곱하기

짝짓기, 폭발

스택을 생각하자.

곱셈 오버플로우

long long을 쓰고, 제곱연산을 생각

배수