본문 바로가기

Algorithm44

[백준] 11723. 집합 / 비트 연산 https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 풀이 2진수의 각 자리를 1~20까지의 존재 여부를 담는 배열로서 사용한다. 수가 존재하면 1, 그렇지 않으면 0인 것이다. 예를 들어, 집합 S = {1, 3}이라고 한다면 2진수 첫번째 자리와 세번째 자리 숫자는 1이고 나머지 자리는 0일 것이다. add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다. s |= (1 2022. 11. 30.
소수(Prime Number) 판별 방법 세 가지 소수(Prime Number) "소수는 1과 자기 자신만으로 나누어 떨어지는 1보다 큰 양의 정수" 즉, 소수는 1과 자기 자신만을 약수로 갖고있다. 만약 1 보다 크고 자기 자신보다 작은 자연수를 약수로 갖게 된다면 이는 합성수라고 한다. 이제부터 어떤 수 N에 대하여 소수인지 판별하는 세 가지 방법을 정리하겠다. 방법 1. " N 보다 작은 자연수들로 일일히 나누어 본다 " 2 부터 N-1 까지의 모든 자연수들로 나누어보았을 때 나누어 떨어지는 수가 없다면(즉, 1과 N 이외에 약수가 없다면) 그 수(N)는 소수에 해당할 것이다. public class PrimalityTest { public static void main(String[] args) throws IOException { Buffere.. 2022. 10. 20.
[백준] 2753. 윤년 / 파이썬 (python) https://www.acmicpc.net/problem/2753 2753번: 윤년 연도가 주어졌을 때, 윤년이면 1, 아니면 0을 출력하는 프로그램을 작성하시오. 윤년은 연도가 4의 배수이면서, 100의 배수가 아닐 때 또는 400의 배수일 때이다. 예를 들어, 2012년은 4의 배수이면서 www.acmicpc.net 문제 풀이 간단한 문제이지만 배울 점이 있었다. 여러 개의 조건문을 작성해야 할 때 간략히 표현하는 방법에 대해서이다. 이 문제에서 윤년이 되기 위한 세 개의 조건이 있다. 아래와 같이 여러 줄에 걸쳐 표현할 수도 있지만, n = int(input()) if n % 4 == 0: if n % 100 != 0 or n % 400 == 0: print(1) else: print(0) else.. 2022. 7. 10.
[백준] 2437. 저울 / 파이썬 (python) https://www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net 문제 풀이 문제를 관통하는 키워드는 '누적합'이다. 예를 들어, 아래와 같이 주어졌다고 가정해보자. 4 1 2 4 5 가장 작은 추 하나만 가지고 있는 상태에서 하나씩 추가로 가지게 된다고 생각하면 1만 가지고 있을 때는 측정 가능범위 [0, 1] 2가 추가되면 [0, 1] + [2, 3] = [0, 3] 4가 추가되면 [0, 3] + [4, 7] = [0, 7] 5가 추가되면 [0, 7] + [5, 12].. 2022. 7. 9.

티스토리툴바