여가생활 개발일지

[C++] 백트래킹 정답 찾으면 다른 경우 안보기

단일 해 탐색 가지치기백트래킹에서 정답을 찾았으면 다음 경우를 볼 필요 없이 탐색을 종료하고 싶을 때가 있다.아래와 같이 성공하면 true를 반환하여 for문의 다음 idx를 하지 않으면 된다. bool dfs(int depth) { // 정답 찾음 if(depth == n) return true; for(int i = 0; i  ※ exit(0)를 하는 방법도 있지만 선호하지 않음

[C++] 냅색 방향 + 반복문 위치

조합 완전 냅색물건을 하나씩 작은 무게부터 넣어봄 → 정방향순서가 달라도 같음같은 물건 중복 가능// 1번 상황for(int i = 0; i 조합 0-1 냅색물건을 하나씩 큰 무게부터 넣어봄 → 역방향순서가 달라도 같음같은 물건 중복 불가// 2번 상황for(int i = 0; i = weight[j]; j--) dp[j] = max(dp[j], dp[j - weight[i]] + price[i]);}순열 완전 냅색작은 무게부터 가능한 모든 물건을 넣어봄 → 정방향순서 다르면 다름같은 물건 중복 가능// 3번 상황for (int i = 0; i = 0) dp[i] = max(dp[i], dp[i - weight[j]] + price[j]); }} Tip. 냅색 문제를..

[C++] 팀을 2개로 나누는 조합

절반만 탐색해야 하는 이유 팀을 조합으로 선택할 때 절반만 탐색하면 된다. A팀과 B팀의 팀원이 그대로 교환된 경우가 중복되기 때문이다. 아래 예시는 두 예시의 원소 조합이 같고, 팀 명만 바뀌었다. A팀{ 1, 2 } + B팀{ 3, 4 } A팀{ 3, 4 } + B팀{ 1, 2 } 1번 노드를 고정하기 한 팀에 1번 노드를 고정하면 경우의 수를 절반으로 줄일 수 있다. 이진트리로 생각해 보면 루트에서는 1번 노드를 A팀에 사용할지 B팀에 사용할지로 결정할 수 있다. 하지만 둘 중에 어느 팀이든 1번 노드를 가져가야 하고, 위의 예시처럼 원소 조합이 같은 경우는 탐색하지 않아도 된다. 이렇게 A팀에서 1번 노드를 사용하지 않는 경우를 안 봐도 된다면 루트에서부터 경우의 수가 절반이 된다. int n; ..

[C++] 냅색 정리

1차원 냅색 코드 서로 다른 물건을 1번씩만 사용해서 배낭에 최대 가치를 담기 점화식은 물건을 넣었을 때 가치가 크다면 갱신 dp[현재 무게] = 최대 가치 int w[100], p[100]; int dp[100001] = {0,}; for(int i = 0; i = w[i]; j--) // 가치 dp[j] = max(dp[j], dp[j - w[i]] + p[i]); } for문 순서 2중 for문의 순서가 중요하다. 옳은 방법 → 조합을 위해서는 물건의 개수를 바깥 for문에 사용해야 한다. 하나의 물건씩 넣어본다고 생각하자. 틀린 방법 → 물건의 가치를 바깥 for문에 쓴다면 순열이 된다. 만약 하나의 가방에 여러 물건을 넣어보면 ..

[C++] 다익스트라 응용

무의미한 간선 없애기 다익스트라로 순회를 하다 보면 가중치가 큰 간선이 우선순위 큐의 밑에 쌓인다. 이것이 결과에는 무관하지만, 모든 연산을 끝나는 시간에 영향을 미친다. 한 간선에 연결된 다른 노드의 수만큼 무의미한 for문을 수행한다. 우선순위 큐에서 꺼낸 노드의 가중치와 현재 가중치를 비교한다. struct edge { int x; int d; }; struct cmp { bool operator()(edge& a, edge& b) { return a.d > b.d; } }; int dist[20001]; vector edges[20001]; void dijkstra(int sx) { priority_queue pq; pq.push({ sx, 0 }); dist[sx] = 0; while (!pq...

[C++] 소수점 자릿수로 출력하기

cout.precision(10); // 10자리 cout

[C++] DFS + DP

정의 모든 경우의 수를 찾아야 하는데 중복된 계산이 존재할 때 함께 사용한다. 현재 노드에서 진행할 수 있는 모든 경우의 수를 DFS로 탐색하고 결과를 DP 배열에 저장해 놓는다. 모든 탐색이 완료된 노드를 재방문한 경우 메모이제이션할 수 있다. 하지만 탐색이 완료되지 않았음에도 불구하고 노드를 재방문한다면 사이클이 존재한다. 사이클이 없는 DFS ex. 목적지까지 도달하는 모든 경우의 수를 세기 bool visited[51][51]; int dp[51][51]; int dfs(int x, int y) { if(baseCondition) return 0; if(dp[x][y] != -1) // 메모이제이션 return dp[x][y]; if(!visited[x][y]) { visited[x][y] = t..

[C++] 정수 나눗셈을 한 줄로 올림하기

정의 나눗셈한 값을 올림 해야 할 때 간단하게 한 줄로 처리하는 법을 알아봅시다 나눈 결과 올림하기 a를 b로 나눈 결과를 올림 b는 나눌 때 몫으로 1이다 a에 몫-1(b-1)만큼을 더하고 나누면 올림이 된다 한 줄로 올림하기 int div_up(int a, int b) { return (a+b-1)/b; } if문을 활용한 올림하기 int div_up2(int a, int b) { if(a % b != 0) return a/b+1; return a/b; }

[C++] 1차원 배열(벡터), 2차원 배열(벡터) 초기화

정의 배열을 STL을 사용하여 초기화하기 for문으로도 할 수 있지만 간단하게 한줄로 가능 배열 (memset) #include 0 또는 -1로만 초기화 가능 // 1차원 배열 int arr[101]; memset(arr, 0, sizeof(arr)); // 2차원 배열 int arr[101][101]; memset(arr, 0, sizeof(arr)); 배열 (fill) #include // 1차원 배열 int arr[10]; // 0부터 n-1까지 2로 초기화 fill(arr, arr + n, 2); // 2부터 4까지 1로 초기화 fill(arr + 2, arr + 5, 1); // 결과: 2 2 1 1 1 2 2 2 // 2차원 배열 int arr[101][101]; // 전체를 -0로 초기화 f..

[C++] 배열을 다른 배열로 복사

정의 배열의 원소를 다른 배열로 STL을 사용하여 복사하기 for문으로도 옮길 수 있지만 간단하게 한줄로 가능 배열 (memcpy) #include // 1차원 배열 int src[101]; // 복사 해줌 int dest[101]; // 복사 받음 memcpy(dest, src, sizeof(dest)); // 2차원 배열 int src[101][101]; // 복사 해줌 int dest[101][101]; // 복사 받음 memcpy(dest, src, sizeof(dest)); 배열 (copy) #include // 1차원 배열 int src[101]; // 복사 해줌 int dest[101]; // 복사 받음 copy(src, src + sizeof(dest), dest); // 2차원 배열 in..

[C++] 행렬 덧셈, 행렬 곱셈, 행렬 회전

정의 행렬 덧셈 결과 구하기 행렬 곱셈 결과 구하기 행렬 회전하기 행렬 덧셈 int A[101][101]; // 행렬1 int B[101][101]; // 행렬2 int ans[101][101] = {0,}; // 결과 저장 void add_matrix() { for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) ans[i][j] = A[i][j] + B[i][j]; } } 행렬 곱셈 int A[101][101]; // 행렬1 int B[101][101]; // 행렬2 int ans[101][101] = {0,}; // 결과 저장 // (A_row, A_col), (B_row, B_col) void mul_matrix() { for(int i = 0; i <..

[C++] 비트마스킹

정의 비트마스킹이란 컴퓨터의 연산 방식인 이진수의 표현을 자료구조 사용하는 기법이다 수행시간이 빠름 메모리 사용량이 적음 비트마스킹 연산 설명 코드 1 뜻 비트를 왼쪽으로 n만큼 이동(2^n) (1 > idx) & 1) idx++; 예시 100111의 가까운 꺼져있는 비트의 순번은 3 11 뜻 가장 가까이 켜져있는 비트의 순번 (= 가장 가까이 켜져 있는 비트 전의 0의 개수) __builtin_ctz(n) 예시 100100의 가까운 켜져있는 비트의 순번 2 12 뜻 켜져있는 비트수 세기 __builtin_popcount(n) 예시 10111의 켜져 있는 비트 수는 4