코테 필요 개념 간단 정리

재귀함수

• 자기자신을 재 참조
• 매개변수 달라짐

[주의사항]

• 종료 조건을 반드시 작성

순열

• 순서와 상관 있는 경우 사용 (순서가 다르면 다른 값으로 인정)
• 예시) 1,2,3 에서 3개 뽑기 -> 1,2,3/ 1,3,2 / 2,1,3 ..등 순서가 있음 총 6개
• C++ ) next_permutation
  : (from, to) 가 매개변수로 들어감 오름차순을 기반으로 만듦
  (1) 언제나 오름차순 정렬이 되어있어야됨
  (2) to 값은 초과하는 값을 사용해야함.
  (3) 공식) nPr = n! / (n-r) !
  ex. 3P2: 3개중에 2개 뽑는 경우의수 구하기

  => n! / ( n-r)! // 즉, 3*2*1/(3-2)! = 6개

조합

• 순서와 상관 없는 경우 사용( 순서가 달라도 값이 같으면 같은 값으로 인정)
• 예시) 1,2,3 중에 2개 뽑기 -> 1,2/ 1,3/ 2,3
• 꿀팁) 4개 이상은 재귀로 풀고 3개이하는 중첩 for문
• 공식) nCr = n!/r!(n-r)!
  ex. 5C3 : 5개중에 3개를 뽑아라

  => n!/r!(n-r)! // 즉, 54321 / 32121 = 10개

Split() 구현

• 문자열 분리하여 배열형태로 변경

string str = "apple, banana, orange, grape"; 
vector<string> fruets = split(str, ","); //str과 구분자를 함께 사용

중복 요소 제거

• 방법
  (1) map을 사용해서 key ,value로 넣어주기
  (2) unique 함수 사용 : 중복 배열 정렬 후 안되어있는 리터레이터 반환하기 때문에 sort와 함께 써야함

sort(v.begin(), v.end());

auto it = erase(unique(v.begin(), v.end()), v.end());