[BOJ/백준] 2437번 저울 문제 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓을 수 있고, 다른 쪽에는 무게를 측정하려는 물건만 올려놓을 수 있다. 무게가 양의 정수인 N개의 저울추가 주어질 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값을 구하는 프로그램을 작성하시오. 예를 들어, 무게가 각각 3, 1, 6, 2, 7, 30, 1인 7개의 저울추가 주어졌을 때, 이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값은 21이다. 입력 첫 째 줄에는 저울추의 개수를 나타내는 양의 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 둘째 줄에는 저울추의 무게를 나타내는..

2021. 2. 9.

알고리즘

[BOJ/백준] 1647번 도시 분할 계획 문제 동물원에서 막 탈출한 원숭이 한 마리가 세상 구경을 하고 있다. 그러다가 평화로운 마을에 가게 되었는데, 그곳에서는 알 수 없는 일이 벌어지고 있었다. 마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 각 길마다 길을 유지하는데 드는 유지비가 있다. 마을의 이장은 마을을 두 개의 분리된 마을로 분할할 계획을 가지고 있다. 마을이 너무 커서 혼자서는 관리할 수 없기 때문이다. 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 한다. 각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 한다는 뜻이다. 마을에는 집이 하나 이상 있어야 한다. 그렇게 마을의 이장은 계획을 세우다가 마을 안..

2021. 2. 8.

알고리즘

[이코테] 팀 결성 문제 학교에서 학생들에게 0번부터 N번까지의 번호를 부여했다. 처음에는 모든 학생이 서로 다른팀으로 구분되어, 총N+1개의 팀이 존재한다. 이 때 선생님은 '팀 합치기' 연산과 '같은 팀 여부 확인' 연산을 사용할 수 있다. '팀 합치기' 연산은 두 팀을 합치는 연산이다. '같은 팀 여부 확인' 연산은 특정한 두 학생이 같은 팀에 속하는지를 확인하는 연산이다. 선생님이 M개의 연산을 수행할 수 있을 때, '같은 팀 여부 확인' 연산에 대한 연산 결과를 출력하는 프로그램을 작성하시오. 입력 조건 첫째 줄에 N,M이 주어진다. M은 입력으로 주어지는 연산의 개수이다.(1

2021. 2. 8.

알고리즘

[BOJ/백준] 1929번 소수 구하기 문제 M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 M과 N이 빈칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. 출력 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다. 풀이 a,b = map(int,input().split()) #두개의 값을 띄어쓰기로 구분지어서 입력 def prime(num): #소수 찾는 함수 if num == 1: #1이면 False return False elif num ==2: #2부터는 True return True for i in range(2,int(num**0.5)+1): #에라토스테네스의 체를 안다면 제곱근을 이용해서 푸는것이 시간 단축에 좋음 if..

2021. 2. 5.

알고리즘

[BOJ/백준] 11653번 소인수분해 문제 정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오. 입력 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. 출력 N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다. 풀이 a = int(input()) # 입력 값 선언 i = 2 # 1은 무조건 나누어 지기 때문에 2부터 순회 while a != 1: # 입력 값이 나누어 질 때 마다 1에 가까워 지기 때문에 1이 된다면 종료 if a % i == 0: # 입력 값이 나누어진다면 나누어진 값으로 a를 초기화 a //= i print(i) # i값이 나누어진 소인수 이기 때문에 출력 else: i += 1 # 나누어 지지 않는다면 i를 1씩 증가 코드 풀이 주석으로 대체

2021. 2. 5.

알고리즘

[BOJ/백준] 1978번 소수 찾기 문제 주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오. 입력 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. 출력 주어진 수들 중 소수의 개수를 출력한다. 풀이 n = int(input()) #입력받을 개수 arr = list(map(int,input().split()))#소수인지 판별할 배열 입력 def prime(num): #소수 판별 함수 if num == 1: return False elif num == 2: return True for i in range(2,num): if num % i == 0: return False return True cnt = 0 for i in arr: if p..

2021. 2. 5.

알고리즘