알고리즘/백준 알고리즘
[BOJ] 1034 램프
문제 링크 www.acmicpc.net/problem/1034 모든 알고리즘 문제는 C++로 구현되어 있습니다. 이 문제를 풀기 위해 나는 먼저 주어진 2차원 배열의 열을 2진수로 바꿔서 생각했다. 예제로 주어진 배열에서 보면 첫 번째 열은 위에서부터 0, 1, 1이므로 011(2), 두 번째 열은 위에서부터 1, 0, 0이므로 100(2)와 같이 바꿔보면 특정 열의 스위치를 누르는 것은 그 열의 수와 bit 1이 n개인 수(2^n - 1)와 XOR 연산을 하는 것이라고 생각할 수 있다. 행과 열이 최대 50개까지 늘어날 수 있으므로 각각의 열을 나타내는 수는 long long 형으로 설정했다. 이렇게 생각을 해보면 이 문제는 임의의 열들을 골라 bit 1이 n개인 수(2^n - 1)와 K번 XOR 연산..
[BOJ] 1030 프랙탈 평면
문제 링크 www.acmicpc.net/problem/1030 모든 알고리즘 문제는 C++로 구현되어 있습니다. 이 문제는 재귀를 이용한 분할정복으로 해결할 수 있다. 주어진 n과 s를 이용하여 미리 전체 평면의 한 변의 길이를 구해두고, 이중 for문을 이용하여 행 [r1, r2], 열 [c1, c2] 범위의 점들을 하나씩 판정하여 출력해준다. int len = 1; while (s--) len *= n; for (i = r1; i = border * (n - k) / 2 && y > s >> n >> ..
[BOJ] 1027 고층 건물
문제 링크 www.acmicpc.net/problem/1027 모든 알고리즘 문제는 C++로 구현되어 있습니다. 고층 건물 A에서 왼쪽, 오른쪽으로 건물들을 보면서 기울기와 최대 높이를 측정하고, 이를 통해 이 건물에서 최대 몇 개의 다른 건물을 볼 수 있는지 구한다. 먼저 왼쪽으로 보면서 그리고 건물 B가 건물 A보다 높은지, 낮은지에 따라 처리를 해주고, 그 다음 오른쪽으로 보면서 건물 B가 건물 A보다 높은지, 낮은지에 따라 처리를 해준다. 기울기는 (A의 높이 - B의 높이) / (A 좌표 - B 좌표)로 구할 수 있다. 왼쪽으로 볼 때와 오른쪽으로 볼 때 각각 maxHeight에 지금까지 본 건물들 중 가장 높은 건물의 높이를 저장해둔다. 다음에 볼 건물의 높이가 maxHeight보다 낮고, m..