그리디 알고리즘
그리디 예시 : 지폐문제가장 흔한 그리디 문제인 지폐문제 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

백준 input 테스트 파일 설정하기 (C++)
프로젝트 설정백준은 프로그래머스와 달리 입출력을 직접 받는 형태로 문제가 출제되기 때문에input을 별도로 넣어주는 프로젝트를 직접 만들어야 한다. 프로젝트 구조인풋을 넣을 input.txt 텍스트 파일을 만들고기본이 되는 Main.cpp 와 코드부 래퍼클래스인 Code.cpp로 구성했다. Main.cpp#define _CRT_SECURE_NO_WARNINGS#include #include "Code.h"int main(void){ freopen("input.txt", "r", stdin); Code code; code.main();} Code.h#pragma onceclass Code{public: int main();}; Code.cpp#include "Code.h"#includ..

2025.01.06

백준 입출력 최적화
인풋 최적화텍스트 파일에서 많은 인풋을 불러올 경우 입출력 최적화 코드를 별도로 작성하지 않으면 시간초과가 발생한다. 시작 시 다음의 코드 사용할 것ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); 1. ios::sync_with_stdio(false)C++ 표준 입출력(cin, cout, cerr)과 C 표준 입출력(scanf, printf)은 기본적으로 동기화되어 있다.해당 코드를 설정하면 C++ 표준 입출력과 C 표준 입출력의 동기화를 해제한다. 동기화 해제를 통해 C++ 표준 입출력이 독립적으로 작동하게 되어 불필요한 동기화 작업을 피할 수 있게 되어 성능이 향상된다.특히나 C++ 표준 입출력(cin, cout)만 사용하는 경우 성능 향상이 크다. 그러나..

2024.12.02