비트 마스크, 비트 마스킹, 2진법으로 바꾸기
~ 연산자 (Ones' Complement)결과값은 수에 +1하고 -를 붙인 것과 같다.~(3) 은 -4이다. 비트 연산 활용하기k 번째 비트 끄기mask &= ~(1 k 번째 비트 켜기mask  |= (1 k 번째 비트가 켜졌는지 체크mask & (1 k 번째 비트 XOR 연산mask ^= (1 최하위 켜져있는 비트인덱스 k 찾기k = ( mask & -mask )크기가 n인 집합의 모든 비트 켜기mask = (1   비트 마스크는 모든 조합을 만들어낼 수 있다.n이 정해져있다면 Combi로 풀어도 되고몇 개를 뽑아야되는지 정해져 있지 않은 경우에는 비트마스크로 푸는게 더 효율적.물론 비트마스크도 몇개가 마스킹 되어있는지 연산제외는 가능하지만.for (int i = 1; i   int 기준 30~31개..

2025.01.12

C++ std::rotate 벡터 회전하기
원판, 기어 등 원형 데이터 기반 문제가 나오는 경우인덱스를 마킹해서 모듈러 연산으로 풀거나std::rotate 를 사용하여 푸는 방법이 있다. std::rotate 헤더에 선언되어있다.배열, 벡터, 리스트 등에서 사용할 수 있다. 인자로는 시작점, 새로운 시작점, 끝점을 받는다. 왼쪽으로 n만큼 회전 새로운 시작점(2번째 인자)을 begin에서 + n 해주자.std::rotate(vec.begin(), vec.begin() + n, vec.end()); std::vector vec = {1, 2, 3, 4, 5}; std::rotate(vec.begin(), vec.begin() + 2, vec.end());// 이전 : 1 2 3 4 5// 변경 : 3 4 5 1 2 오른쪽으로 n만큼 회전새로운 시작..

2025.01.11

그리디 알고리즘
그리디 예시 : 지폐문제가장 흔한 그리디 문제인 지폐문제 10000원 5장5000원 5장1000원 5장100원 5장 이 있을 때 12100을 내기위해 가장 적은 갯수의 돈을 내는 최적해는?-> 가장 큰 지폐부터 순서대로 계산하면 된다. 그런데 8000원 5장5000원 5장1000원 5장100원 5장  인 경우에 가장 큰것부터하면8000원 1개1000원 4개100원 1개  라서5000원 2개1000원 2개100원 1개의 경우의 수보다 크다. 따라서 언제나 큰게 최적해는 아니다. 증명해당 명제에 대해 탐욕 선택 충족이 되는 해를 찾아야한다. 그렇다면 그 선택이 해당 명제에 최적이라는 건 어떻게 알 수 있을 까?증명을 통해서 확인하면 된다.  직접 증명 명제 : n은 짝수다 직접 증명 : n % 2 는 0이다..

2025.01.11

큰 수의 덧셈 연산 (string 뒤집기)
https://www.acmicpc.net/problem/15353  방법 1string도 벡터처럼 다룬다.처음부터 뒤집어서 저장하고 출력할때 반대로 뒤집어서 출력한다!#include #include #include #include using namespace std;// int main(void)void Code::main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); string a, b; cin >> a >> b; string ret; int sum = 0; while (a.size() || b.size() || sum) { if (a.size()) {..

2025.01.10

완전 이진 트리
https://www.acmicpc.net/problem/9934 자식 노드의 인덱스부모 노드의 인덱스를 i라고 할 때,1. 왼쪽 자식의 인덱스 : 2i + 12. 오른쪽 자식의 인덱스 : 2i + 2 부모 노드의 인덱스자식 노드의 인덱스를 i라고 할 때1. 부모의 인덱스 : ⌊(i - 1) / 2⌋ 소수점은 버린다. 높이가 k개 일 때 노드의 개수2^(k + 1) - 1 완전 이진트리의 노드가 n 개일 때 높이h=⌊log2​(n)⌋

2025.01.09

유니티 타임라인 루트모션 제거하기 Unity Timeline remove Rootmotion
타임라인의 강제 루트모션 애니메이터와 타임라인의 애니메이션을 블렌딩 할 때 가장 문제점이루트모션이 강제로 사용된다는 점이다. 처음부터 루트모션이 없는 애니메이션을 사용하면 좋겠지만 에셋을 사용한다거나 하면제거하는건 불가능한 상황이 많다. 해결법playable Track은 위에서부터 순차 평가되기 때문에애니메이터를 하나 두고, 0,0,0으로 강제 위치를 조정하는 애니메이션 트랙을 두어서 해결하였다. 주의 : FootIKFootIK를 사용하지 않는 경우이렇게 두개의 애니메이션 트랙을 동시에 겹칠경우 FootIK가 이상하게 동작할 수 있다.애니메이션을 넣는 일반 트랙에도 FootIK를 끄고위치 조정을 위해 만든 두 번째 애니메이션 트랙의 FootIK도 체크해제하자.

2025.01.08

모듈러 연산의 분배법칙
예시문제https://www.acmicpc.net/problem/1629 모듈러 연산의 분배법칙모듈러 연산이 그대로 분배법칙이 성립한다는 것은 아니다.'모듈러 연산은 결과값에 한번 더 모듈러를 취해주면 분배법칙이 성립한다'. 0. a ≡ b mod n과 b ≡ c mod n 은 a ≡ c mod n 을 의미 1. [(a mod n)+(b mod n)] mod n = (a+b) mod n 2. [(a mod n)-(b mod n)] mod n = (a-b) mod n 3. [(a mod n)*(b mod n)] mod n = (a*b) mod n 1. (a + b) % n 은 (a % n) + (b % n) 을 다시 %n 한 것과 같다. 2. (a - b) % n 은 (a % n) - (b % n) 을 다..

2025.01.08

순열 / 조합
순열과 조합어떤 수를 순서에 관계있이 뽑는다면 -> 순열어떤 수를 순서와 관계없이 뽑는다면 -> 조합 C++에서는 순열을 위해 헤더에서 next_permutation 함수를  제공한다 next_permutation은 오름차순으로 순열을 만든다. prev_permutation은 내림차순인자는 시작과 끝 이터레이터이다.next_permutation(v.begin(), v.end()); vector v = {1, 2, 3}do{ for(int i : a) cout  위 결과는1 2 31 3 22 1 32 3 13 1 23 2 1로 나온다.그러나 오름차순 정렬되어있지 않다면{2, 1, 3} 으로 넘기면 2 1 32 3 13 1 23 2 1로 출력된다. 다음의 수를 추출하는 것 뿐.따라서 순열 사용 전에 반드시 ..

2025.01.07