비트마스킹 모음.zip

1094 막대기https://www.acmicpc.net/problem/1094 단순한 비트마스킹 문제이다. 64인 막대기를 계속해서 반으로 잘르고, 모든 막대기의 합이 X가 되도록 구현하는 문제이다.이 문제의 핵심은 막대기가 모두 2의 지수라는 점이다.예를 들어, 막대기가 나올 수 있는 총 종류는 {64, 32, 16, 8, 4, 2, 1} 뿐이다.다시 말해 구하고자하는 X는 위 막대 종류로 만들 수 있다는 것이다. 결국 구하고자하는 것은 X의 이진수 중 1비트의 개수를 의미한다. 예를 들어, 23는 10111로 나타낼 수 있고, 총 필요가 막대기는 4종류로 {1, 2, 4, 16}이다. 2961 도영이가 만든 맛있는 음식https://www.acmicpc.net/problem/2961 완전탐색 + ..

• format_list_bulleted 📊알고리즘/BOJ
• · 2025. 7. 2.

구현 모음.zip

15683 - 감시https://www.acmicpc.net/problem/15683 해결 방안- 모든 CCTV의 방향을 돌리면서, 모든 경우의 수를 다 구해야 한다. CCTV - 모든 방향 - 보이는 시야 체크 - 사각 지대 계산 CCTV의 종류는 총 5개이고, 최대 4개의 시야각 종류가 존재한다.따라서, 4방향에 대해서 각각의 시야삭 종류를 모두 구해야 한다. 12100 - 2048 (Easy) https://www.acmicpc.net/problem/12100 해결 방안 먼저 백트래킹을 이용하여 모든 방향에 대해 브루트포스를 진행했다.처음 문제를 해결한 거 같았는데 4%와 11% 지옥에 빠졌다. 문제의 원인은 이미 한 번 합쳐진 블록에 대해서 중복적으로 합쳤기 때문이다.예를 들어, { 2 0 2 4..

• format_list_bulleted 📊알고리즘/BOJ
• · 2025. 7. 1.

[수학] 분할정복을 이용한 거듭제곱

수학적 정의를 이용하여 거듭제곱을 하는 방법이다.기존 거듭제곱의 경우, 모두 곱하기 때문에 O(N)의 시간이 걸리지만,분할정복을 이용하면 O(LogN)에 결과 도출이 가능하다. 그냥 단순하게 2, 3등분하여 한방에 구한다는 뜻이다. 재귀함수와 반복문 두 가지 방법으로 구현이 가능하다. 반복문의 경우 코드를 먼저 보자.void powFunc(int a, int b) { int res = 1; while(b) { if (b % 2 != 0) { res *= a; } a *= a; b /= 2; } cout - 2, 3 등분으로 나누기 위해 b가 1이상일 동안 이루어진다.- 만약 홀수인 경우, (위 식 그림에서) 마지막에 C가 추가적으로 곱해지기 때문에, 초기에 곱한다.- 짝수의 경우, 마지..

• format_list_bulleted 📊알고리즘/이론
• · 2024. 5. 1.

[알고리즘] 방향그래프

방향그래프 - 모든 간선이 방향간선 방향그래프의 속성 - 모든 간선은 한 방향으로만 - G가 단순(간선이 많지 않음) : M v인 방향경로가 존재하면, "u는v에 도달한다" , "v는 u로부터 도달 가능하다" 강연결성 어느 두 정점 u, v 간에 u에서 v 도달가능 이고 v에서u 로 도달가능이면 강연결 강연결 검사 알고리즘 1. 임의 정점 v 선택 2. v에서 DFS 실행 3. 간선들 방향을 역행시킨 그래프 G'을 얻음 4. G'에서 v에서부터 DFS 수행 -> O(n+m) 강연결 요소 - 최대한 모든 정점을 도달할 수 있는 부그래프 a->f로 간다고 하면, a로 다시 올 수 없음. 이행적폐쇄 다음 성질을 만족. 1. G'은 G와 동일한 정점들로 구성 2. G의 u에서 v(v!=u)로의 경로가 존재하면 ..

• format_list_bulleted 🏫CS/알고리즘
• · 2023. 11. 21.