Mee in the middle (MITM) 알고리즘
https://www.acmicpc.net/problem/1450 이 문제는 n이 30이고 무게가 10^9이다. 완탐으로 하기에는 담고 안 담고 2^30 -> 10억이라서 너무 큰 수이다. dp로 저장하기에는 상태값이 [30][10^9]라서 값이 너무 크다. 완탐이나 DP도 안될 때즉, n이 너무 클 때 반으로 쪼개서 각각 완탐을 하는 게 meet in the middle 알고리즘이다.  완전 탐색 (Brute-force): O(2ⁿ) → n ≤ 30일 때 너무 큼 ❌ Meet in the Middle: O(n * 2ⁿ/²) → n ≤ 30에서 현실적으로 가능 ✅ 이분탐색을 하는 것도 아니다.각각 완탐을 한 다음에 경우의 수를 더할 뿐이다. 2의 30승인 10억이 넘는데절반으로 나누면 O(2^(n/2))..

2025.01.31

최대 증가 부분 수열 (LIS : Longest Increasing Subsequence)
최대 증가 부분 수열최대로 긴 증가하는 부분 수열을 구하는 방법 다음의 수열이 있다.10, 20, 10, 30, 20, 50 다음의 4가지를 사용해 최대 증가 수열을 만들 수 있다. 10, 20, 10, 30, 20, 50  다음의 3가지를 사용해도 증가하는 수열을 만들 수 있지만 최대로 긴 부분수열은 아니다.10, 20, 10, 30, 20, 50   각자 자신의 위치에서 왼쪽을 바라보고그 중 자기보다 작은 수들 중에 가장 큰 cnt 값에 + 1을 해서 자신한테 적는다. 예시 코드시간 복잡도는 n^2 이니 주의.#include #include #include using namespace std;int result = 0;int n = 6; // 더미값int a[1001] = { 10, 20, 10, 3..

2025.01.26

2차원 배열 / 행렬의 90도 회전
회전으로 코드 축소하기문제에 따라 행렬에 방향으로 로직을 짜는 경우가 생긴다. 예시문제 : 12100 - 2048(Easy)https://www.acmicpc.net/problem/12100 보통 2방향이나 4방향의 로직을 중복해서 짤 필요는 없으므로한 쪽 방향으로 코드를 작성한 후, 2차원 컨테이너를 회전시켜서 적용하는 것이 간편하다. x축 y축 만 사용하는 경우 전치행렬만 만들면 되니 간단하지만4방향을 체크해야하는 경우 90도 회전시켜주는 코드가 필요하다. 시계 방향으로 90도 회전vector> rotated(width, vector(height));for (int y = 0; y  반시계 방향으로 90도 회전vector> rotated(width, vector(height));for (int y =..

2025.01.25

C++ 인풋이 소수점으로 주어질 때 정수 변환시 주의
https://www.acmicpc.net/problem/4781dp문제에서 인풋이 소수점 둘째 자리로 주어진다면 배열에 담기 위해서 정수형으로 변환해야한다.이 때 단순히 인풋값을 단순히 x 100 해서 사용하면 틀렸다고 나온다. 소수점을 연산해서 0.01 x 100 했더니 정수에 약간 모자르는 0.99999 등의 수가 나올 수 있는 것.부동소수점 연산의 한계이다. 때문에 x100을 곱하고 보정값 ( 주로 0.5f )를 더해줘서 변환하자.  float temp;cin >> temp;int p = (int)((temp * 100) + 0.5f); 혹은 . 을 기준으로 정수부와 소수부를 각각 정수형으로 받는 방법도 있다.

2025.01.24

에라토스테네스의 체
에라토스테네스의 체 2부터 시작해서 자기자신을 제외한 n의 배수를 전부 체크하고체크되지 않은 것들이 소수가 되는 알고리즘이다.vector v(n + 1);for (int i = 2; i prime;for (int i = 2; i  1은 소수가 아니라는점에 주의하자.  따라서 [0] 번 위치와 [1] 위치는 소수가 아니므로 [2] 위치부터 소수이다.  구하려는 수가 충분히 작은 경우에는 최적화를 할 수 있는데,예를들어 4를 검색할 때는 이미 2에서 제외된 로직을 다시 실행하는 꼴이 되므로n * n + n * i 꼴로 실행하면된다. 하지만 n의 제공이 int 범위를 넘는 경우가 많으므로 많은 경우에서는 쌩으로 구하는게 맞다.vector v(n + 1);for (int i = 2; i prime;for (..

2025.01.24

투 포인터 알고리즘
Line Sweeping 알고리즘라인을 탐색하면서 무언가를 하는 알고리즘사실 교차점이나 집합 등 까지 들어가면 고급 알고리즘이지만 코딩테스트에서는 정렬을 해놓고 순서대로 탐색 하는 정도만 나온다. 투 포인터선형 자료구조에서 두 개의 포인터를 사용하여 특정 조건을 만족하는 부분 배열 또는 원하는 값을 찾는 문제를 풀 때 주로 사용되는 알고리즘.'정렬된 배열' 에서 두 수의 합 찾기, 연속된 부분배열의 합 찾기에 사용된다. 예시 ) 많은 수의 숫자들이 있을 때,이 중 두개를 합친 값이 x인 순서쌍의 갯수 구하기 문제 이를 이중 for문으로 돌리면 시간초과한다. 왼쪽 포인터를 0번, 오른쪽 포인터를 맨 뒤로 두고이게 x라면 왼쪽을 한칸 뒤로 보내거나 오른쪽을 한칸 앞으로 보낸다. (*이는 문제마다 다르다. 두..

2025.01.24

이분 탐색 (이진 탐색)
이분 탐색정렬된 배열이나 리스트에서 매 루프마다 탐색 구간을 반으로 쪼개서 시간복잡도를 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