CF486B 문제 풀이 - 행렬 OR 연산 검증
문제 분석
본 문제는 두 개의 n×m 이진 행렬 A와 B가 주어졌을 때, B 행렬이 특정 규칙에 따라 A 행렬로부터 생성되었는지 확인하는 문제이다.
생성 규칙: B[i][j]는 A 행렬의 i번째 행 전체와 j번째 열 전체에 대해 OR 연산을 수행한 결과값이다.
OR 연산의 특성을 먼저 파악해야 한다:
0|0 = 0
0|1 = 1
1|0 = 1
1|1 = 1
핵심 관찰
OR 연산의 특성을 통해 두 가지 ...
6월 17일 01:34에 게시됨
Codeforces 라운드 187 문제 해설
A. 상자 탑 쌓기
같은 크기의 상자만 존재하므로 각 상자가 견딜 수 있는 최대 상자 수를 계산하면 된다. 이 값을 c로 표기하면, 최대 스택 높이는 c+1이 된다. 전체 상자 수 n을 나누어 최소한의 스택 수를 계산한다.
코드 보기
<!-- 깊은 어둠을 바라보는 자, 어둠도 그를 바라보리라 -->
#include <bits/stdc++.h>
using namespace std;
int main() {
...
6월 15일 17:04에 게시됨
C++ STL 알고리즘 완전 정복
1. 비수정 시퀀스 알고리즘
이 알고리즘들은 컨테이너의 요소를 변경하지 않고 조작합니다.
1.1 find 및 find_if
find(begin, end, value): value와 첫 번째로 일치하는 요소를 찾아 반복자를 반환합니다 (찾지 못하면 end 반환).
find_if(begin, end, predicate): 조건자를 만족하는 첫 번째 요소를 찾습니다.
find_end(begin, end, sub_begin, sub_end): 서브시퀀스 ...
6월 15일 00:03에 게시됨
코딩 면접 문제 풀이 모음
두 수의 합 구하기
정수 배열이 주어졌을 때, 지정된 합계가 되는 두 개의 요소를 찾는 문제를 해결해 보겠습니다. 먼저 기본 접근법의 시간 복잡도를 분석한 후, O(n) 알고리즘으로 개선하겠습니다.
def solve():
data = [11, 7, 45, 67, 134, 5, 83, 55, 106, 33, 57, 82, 6, 24, 87, 61, 3, 39, 6, 26]
target = 13
result, a, b = find_pair(data, targe ...
6월 13일 22:41에 게시됨
ABC363 문제 풀이
A - 값의 범위
주어진 값 r이 어느 범위에 속하는지 확인하고, 그 범위의 상한에서 r을 뺀 값을 출력하면 된다.
100 미만이면 100-r, 200 미만이면 200-r, 300 미만이면 300-r을 출력한다.
코드 확인하기
#include<bits/stdc++.h>
using namespace std;
int main() {
int r;
cin >> r;
if(r < 100) {
cout << 100 - r;
...
6월 13일 16:20에 게시됨
AtCoder 초보자 대회 450 (ABC450)
A - 3,2,1,GO
값을 입력받은 후 1부터 입력값까지 반복하여 출력합니다.
코드 보기
#include<bits/stdc++.h>
using namespace std;
int n;
int main(){
cin >> n;
for(int i = n; i > 1; --i)
cout << i << ',';
cout << 1;
return 0;
}
B - Split Ticketing
a, b, c를 모두 반복하며 조건을 검사합니다. 조 ...
6월 12일 19:32에 게시됨
행렬 곱셈과 고속 지수 연산
행렬의 기초
기본 개념
행렬은 행과 열로 구성되는 2차원 배열이다. n×m 행렬은 n개의 행과 m개의 열을 가진 구조를 의미한다.
두 행렬을 곱할 때는 첫 번째 행렬의 열 개수와 두 번째 행렬의 행 개수가 반드시 일치해야 한다. 예를 들어, 2×3 행렬과 3×4 행렬을 곱하면 결과는 2×4 행렬이 된다.
[A_{a \times n} \times B_{n \times m} = C_{a \times m}]
행렬 곱셈의 ...
6월 11일 19:01에 게시됨
동적 계획법을 활용한 상태 머신 기반 문제 해결 전략
동적 계획법(Dynamic Programming)에서 상태 머신(State Machine) 개념을 도입하면 복잡한 의사결정 과정을 간결한 상태 전이 방정식으로 변환할 수 있습니다. 각 단계에서의 선택지를 상태로 정의하고, 이전 상태로부터 현재 상태로 도달하는 최적 경로를 계산하는 세 가지 사례를 살펴봅니다.
1. 인접한 항목을 선택할 수 없는 경우 (도둑 문제)
연속된 상점을 ...
6월 10일 16:04에 게시됨
Xorshift 기반 난수 배열 생성과 선형 시간 선택 알고리즘 활용
알고리즘 대회에서 자주 등장하는 난수 배열 생성 방식과 std::nth_element를 활용한 효율적인 문제 해결 기법을 살펴본다. 특히 대용량 데이터에서 순위 기반 쿼리를 처리하는 방법이 핵심이다.
Xorshift RNG 구현
다음은 경량 의사난수 생성기(Pseudo-Random Number Generator)의 한 종류인 xorshift 계열 구현이다. 세 개의 상태 변수를 이용하며, 비트 연산으로 빠르 ...
6월 8일 21:35에 게시됨
그래프 순회 알고리즘: 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)
너비 우선 탐색 (Breadth-First Search, BFS)
너비 우선 탐색은 시작 정점으로부터 가까운 노드를 우선적으로 탐색하는 알고리즘으로, 이진 트리의 레벨 순회(Level-order traversal) 방식과 유사합니다. 탐색 과정에서 큐(Queue)를 사용하여 정점을 관리하고, 방문 여부를 기록하기 위한 불리언 배열을 사용합니다.
시작 정점을 큐에 넣고 방문 처리한 뒤, 큐가 ...
6월 8일 16:40에 게시됨