https://codeforces.com/contest/1688/problem/A https://codeforces.com/contest/1688/problem/A codeforces.com 단순하게 패턴을 파악하면 되는 문제이다. 주어진 $x$와 AND 연산, XOR 연산에서 모두 0을 초과하는 값을 내는 최소의 양의 정수를 찾아야 한다. 그러면 AND 연산과 XOR 연산에서 각각 0을 초과할 수 있되 가장 작은 수를 만들 수 있는 패턴을 파악해보자. AND 연산 $x$의 이진수를 표현했을 때, 1로 표시되는 자릿수 중 가장 작은 자릿수에서 1 XOR 연산 $x$의 이진수를 표현했을 때, 0으로 표시되는 자릿수 중 가장 작은 자릿수에서 1 $x$의 이진수를 표현했을 때, 1로 표시되는 자릿수 중에서 0..

https://codeforces.com/problemset/problem/1688/C https://codeforces.com/problemset/problem/1688/C codeforces.com 문제 풀이방법도 어려웠지만, 문제 이해도 힘들었다...흑흑 최초의 문자로부터 시작해서 순서가 존재하는 시퀀스 $t$를 홀수 원소를 짝수 원수로 교체(replace)한다. 이렇게 교체한 후 final string인 $s$을 만든다. input data에서 $t$는 shuffle되어 제시된다. 처음에는 Brute Force하게 최초의 문자를 정하고, t 배열도 정렬해야하나 싶었다. 하지만 힌트에 의하면 그렇게 일일이 시도할 필요가 없다고 한다. Hint 1. You do not need to know anyt..

https://www.acmicpc.net/problem/21610 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net 알고리즘도 중요하지만 복잡한 구현 과정에서 실수하지 않는 것도 중요한 것 같다. 그래서 틈틈이 2차원 배열에서 원소들을 이동하는 문제를 풀어보았다. 가장 먼저 순서대로 주어진 일을 수행해야 한다. 이를 제대로 파악하기 위해 나는 함수별로 주어진 일을 나누었다. - move → 구름의 이동 및 구름의 물의 양 증가 - copy_bug → 물복사 버그 - make_cloud → 구름 생성 여기..

https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 이전에는 실버 단계도 어려워서 못 풀었던 문제였는데 이제는 쉽게 느껴지는 문제였다. 대신 메모리를 잘 할당해야한다는 주의를 얻었다. 2 by n이면 충분했으나 까먹고 습관적으로 n by n 배열을 할당해 최초 시도 시에는 메모리 초과가 떴기 때문이다. 그래서 메모리 할당을 제대로 다시 해주니 정상적으로 통과가 된다. 하지만 이는 부수적인 거고, 핵심은 아니다. 핵심은 어떻게 스티커의 점..

https://www.acmicpc.net/problem/1275 1275번: 커피숍2 첫째 줄에 수의 개수 N과 턴의 개수 Q가 주어진다.(1 ≤ N, Q ≤ 100,000) 둘째 줄에는 처음 배열에 들어가 있는 정수 N개가 주어진다. 세 번째 줄에서 Q+2번째 줄까지는 x y a b의 형식으로 x~y까지의 합 www.acmicpc.net 백준 2042번: 구간 합 구하기와 유사한 문제이다. 그러나 여기서 중요한 점은 조건의 함정이다. 문제를 보면 $x y$이면 $swap(x, y)$을 해줘야한다는 점이 이 문제 풀이의 핵심 포인트이다. 그리고 까다롭게 입출력에 대한 동기화를 해제하여야만 시간 초과가 되지 않고 통과된다. #include #include #include using namespace st..

이전에 틀렸다가 이제서야 세그먼트 트리를 복습하고 성공한 문제이다. 그 때는 세그먼트 트리가 너무 어려운 개념이었는데 이제는 쉽게 이해된다. 세그먼트 트리는 저장된 자료를 트리 형식으로 저장하여 빠르게 구간합을 쿼리할 수 있도록 한다. 여기서 세그먼트 트리는 크게 3가지의 기능이 필요하다. 💚 세그먼트 트리 만들기 배열을 통해 트리를 구현한다. 인덱스 1부터 트리를 노드 간의 합으로 구성한다. 만약 구간 합이 아니라 구간의 최댓값, 최솟값 등 다양하게 응용 가능하다. 여기서 중요한 점은 트리 배열의 크기다. 단순히 리프 노드 뿐만 아니라 구간합을 표현하는 중간 노드들도 배열의 노드로 차지 하기 때문이다. 배열의 원소가 N이라면, N이 2의 제곱수라면 Full Binary Tree가 되므로 노드의 개수는 ..