본문 바로가기

백준4

백준 2839 파이썬 - 설탕 배달 - 동적 계획법 백준 2839 파이썬 https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net N킬로그램의 설탕이 주어졌을 때, 설탕을 담기 위해 3키로그램과 5키로그램 봉지로 가장 적은 양의 봉지를 만들어 내는 방법을 구하는 문제이다. 이 문제는 계산 횟수를 줄이기 위해 이전에 계산했던 값을 기억해뒀다가 재사용하는 메모이제이션을 활용하는 것이 적당하다고 판단했습니다. 3 ~ N킬로그램까지 작은 숫자부터... 각각 가장 적은 양의 봉지를 저장해두면... 해당 값보다 3, 5 큰 .. 2021. 10. 5.
[백준 11724 연결 요소의 개수] 파이썬 BFS 너비 우선 탐색 풀이 연결 요소의 개수 문제 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주�� www.acmicpc.net 뱡향 없은 양방향 그래프가 주어졌을 때 연결 요소를 구하는 문제입니다. 문제 풀이 연결 요소를 구하는 것은 즉 몇개의 구역으로 나누어져 있는지 구하는 문제입니다. 그래프를 위와 같이 표현했을때 2개의 영역으로 이루어져 있습니다. DFS, BFS 모두 사용해서 풀수 있는 문제입니다. 너비 우선 탐색 BFS로 문제를 풀어보겠습니다. 1. 그래프 연결 정보용 행렬 생성 2. BFS.. 2020. 9. 28.
[백준 1012 유기농 배추] 파이썬 BFS 너비 우선 탐색 풀이 유기농 배추 문제 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 � www.acmicpc.net 2차원 배열의 유기농 배추밭이 주어지고 0(땅) 과 1(배추 심어져 있는 땅)로 데이터가 구분됩니다. 배추흰 지렁이를 배추에 서식하게 하면 사방면으로 이동이 가능하여 다른 배추를 해충으로부터 보호가 가능하다. 필요한 배추흰 지렁이의 마리수를 구하는 문제입니다. 입력 받는 정보로 아래와 같이 배추 밭을 2차원 배열 형태로 만들어 주어야 합니다. 문제 풀이 4방면으로 이동이 가능하므로 각 영역당 한마리의 배추흰 지렁이를 배치하면 해결할 수 있습니다. 즉, .. 2020. 9. 28.
[백준 10026 적록색약] 파이썬 BFS 너비 우선 탐색 풀이 적록색약 문제 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net RGB 3가지 문자로 이루어진 N * N 보드판이 주어질때 일반사람과 적록색약인 사람이 보는 구역의 수를 각각 구하는 문제입니다. 적록색약은 R과 G를 하나의 색으로 보입니다. 즉, 아래와 같이 구역이 나뉘게 됩니다. 문제 풀이 2차원 배열의 영역을 구하는 문제로 BFS 너비 우선 탐색 알고리즘을 사용해서 풀면 될것으로 판단했습니다. 단, 2가지 경우가 발생하기 때문에 2가지 버전의 배열을 만들어주고 탐색하는 방식을 선택했습니다. N의 최대 .. 2020. 9. 27.