이분 탐색 (이진 탐색)
이분 탐색정렬된 배열이나 리스트에서 매 루프마다 탐색 구간을 반으로 쪼개서 시간복잡도를 logN으로 탐색하는 알고리즘.정렬 되어있다는게 중요하다! 정렬이 안되어있다면 별도로 정렬 후 로직을 실행하자. 예시 1) 주어진 배열에서 특정 값이 존재한다면 인덱스를 반환하는 함수#include #include #include using namespace std;int GetIndex(const vector& arr, int target){ int left = 0; int right = arr.size() - 1; while (left arr = { 1, 2, 3, 5, 10, 21, 22, 24 }; sort(arr.begin(), arr.end()); // 반드시 정렬해야함 int ..

2025.01.18

비트 마스크, 비트 마스킹, 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

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

모듈러 연산의 분배법칙
예시문제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