- 백준 2839번 설탕배달
상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.
상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.
상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오
num = int(input())
count = 0
while num >= 0:
if num % 5 == 0:
count += int(num // 5)
print(count)
break
num -= 3
count += 1
else:
print(-1)무개 변수N을 받은 후 ,봉지 수 변수 count도 있어야해서 count변수를 생성했다.
최대한 적게 반복해야해서 먼저 while 으로 반복하고 만약 5로 나누어 떨어지는지 확인 해보는데, 나머지가 0이면 3은 필요가 없으므로 count를 출력하고 멈추지만 만약 나머지가 생긴다면 -3을 계속하면서 count를 하나씩 올린다. num이 0이면 위의 조건처럼 -1을 출력한다.
2.백준 10546번 배부를 마라토너
문제
마라토너라면 국적과 나이를 불문하고 누구나 참가하고 싶어하는 백준 마라톤 대회가 열린다. 42.195km를 달리는 이 마라톤은 모두가 참가하고 싶어했던 만큼 매년 모두가 완주해왔다. 단, 한 명만 빼고!
모두가 참가하고 싶어서 안달인데 이런 백준 마라톤 대회에 참가해 놓고 완주하지 못한 배부른 참가자 한 명은 누굴까?
입력
첫째 줄에는 참가자 수 N이 주어진다. (1 ≤ N ≤ 105)
N개의 줄에는 참가자의 이름이 주어진다.
추가적으로 주어지는 N-1개의 줄에는 완주한 참가자의 이름이 쓰여져 있다.
참가자들의 이름은 길이가 1보다 크거나 같고, 20보다 작거나 같은 문자열이고, 알파벳 소문자로만 이루어져 있다.
참가자들 중엔 동명이인이 있을 수도 있다.
출력
마라톤을 완주하지 못한 참가자의 이름을 출력한다.
import sys
input= sys.stdin.readline
N = int(input())
li = dict()
for _ in range(N):
name = input().rstrip()
if name not in li.keys():
li[name] = 1
else:
li[name] += 1
for _ in range(N-1):
name = input().rstrip()
if name in li.keys():
li[name] += 1
for key, values in li.items():
if values %2 == 1:
print(key)
break이 문제는 많은 사람들이 딕셔너리를 통해 key:value 형식을 이름:완주할 시+1 로 활용해서 풀었다.
먼저 참가자의 수를 입력한 후 딕셔너리를 만든 후 for문으로 출전자 이름을 선언한다. 동명이인 일시 value값을 1 더해서 구분한다.
두번째 for문에서 무조건 한 명은 완주를 못한다고 했기에 range(N-1)을 설정해주고 이들에게만 value값을 +1해준다. 그럼 다음 for문에서 완주한 이들의 나머지는 무조건 0이 될것이다. 이런 방식으로 완주를 못한 사람을 찾아냈다.
3.1697번 숨바꼭질
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 (2*X)의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
-입력
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
-출력
수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
이 문제는 넓이 우선 탐색이라는 원리로 풀어야 했다.
넓이 우선 탐색(BFS)란
루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법
-시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.
-즉, 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것이다.
-사용하는 경우: 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다. Ex) 지구상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Ash와 Vanessa 사이에 존재하는 경로를 찾는 경우
-깊이 우선 탐색의 경우 - 모든 친구 관계를 다 살펴봐야 할지도 모른다.
-너비 우선 탐색의 경우 - Ash와 가까운 관계부터 탐색
-너비 우선 탐색(BFS)이 깊이 우선 탐색(DFS)보다 좀 더 복잡하다.
동생이 이동할 수 있는 위치를 모두 뽑아낸 후 그 뽑아낸 위치에서 이동할 수 있는 모든 위치를 뽑아내서 가장 짧은 위치를 알아내야 한다.
import sys
from collections import deque
input = sys.stdin.readline()
def bfs():
q = deque()
q.append(n)
while q:
x = q.popleft()
if x == k:
print(dist[x])
break
for j in (x-1,x+1,x*2):
if 0<= j <= MAX and not dist[j]:
dist[j] = dist[x] +1
q.append(j)
MAX = 100000
n,k = map(int,input.split())
dist = [0] * (MAX+1)
bfs()
함수 bfs 안에 deque라는 것이 있는데 이는 데크라고 하며, 쉽게 말해 양방향 큐라고 생각해면 된다.
while 문 안의 popleft는 deque안의 메서드로 데크의 왼쪽 끝 엘리먼트를 가져오는 동시에 데크에서 삭제한다.
수빈이의 현재위치를 x 라고 하는데 이는 deque배열에서 제일 왼쪽 것만 사용하겠다는 뜻이다.
x==k즉 위치가 같다면 코드를 끝낸다는 것이다.
for문에서는 현 위치x에서 갈 수 있는 모든 공간을 계산하는데 MAX를 걸어 100000을 넘기지 않게했다.
4.백준 2023 신기한 소수 찾기
이 문제는 깊이 우선 탐색이라는 개념이 사용되었다.
깊이 우선 탐색이란
-루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법
-미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다.
즉, 넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것이다.
-사용하는 경우: 모든 노드를 방문 하고자 하는 경우에 이 방법을 선택한다.
-깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단하다.
-단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리다.
n=int(input())
def isPrime(a):
if(a<2):
return False
for i in range(2,int(a**0.5)+1):
if(a%i==0):
return False
return True
def dfs(num):
if len(str(num))==n:
print(num)
else:
for i in range(10):
temp=num*10+i
if isPrime(temp):
dfs(temp)
dfs(2)
dfs(3)
dfs(5)
dfs(7)isPrime에서는 소수를 구하는 함수를 썼다.
그리고 dfs함수에서 if문은 자리수를 구하고,else에서 다시 for 을 써서 자리수를 늘리는데 else속의 if문으로 늘린 수가 소수일때만 출력하게했다.
