본문 바로가기

Algorithm705

[탐색/BFS] 백준 1926 그림 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 2. 문제 풀이 1로 이어진 그림의 개수와, 그림의 최대 크기를 구하는 BFS 문제입니다. 2022.02.23 - [Algorithm] - [탐색/BFS] 백준 1012 유기농 배추 - Python [탐색/BFS] 백준 1012 유기농 배추 - Python [ Contents ] 1. 문제 (링크 참조) 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 .. 2023. 6. 30.
[탐색/BFS] 백준 5014 스타트링크 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 2. 문제 풀이 1층부터 F층까지 있는 건물에서 엘리베이터를 타고 S층에서 G층으로 가는 문제입니다. 엘리베이터는 U층만큼 오르며, D층만큼 내려갑니다. G층으로 가기위해 필요한 최소 버튼 횟수를 구해야 합니다. (G층에 갈 수 없을 시, use the stairs를 출력합니다.) 2022.02.24 - [Algorithm] - [탐색/BFS] 백준 1697 숨바꼭질 - Python [탐색/BFS] 백준 1697 숨바꼭질 - .. 2023. 6. 30.
[탐색/BFS] 백준 24444 알고리즘 수업 - 너비 우선 탐색 1 - Python [ Contents ] 1. 문제 (링크 참조) 24444번: 알고리즘 수업 - 너비 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방 www.acmicpc.net 2. 문제 풀이 너비 우선 탐색(BFS)을 사용하는 기본 예제입니다. 2022.02.23 - [Algorithm] - [Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자 [Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자 BFS는 가까운 주변부터 탐색하는 알고리즘입니다. 큐를 이용한 BFS 구현방법과 코드를.. 2023. 6. 30.
[구현/수학] 백준 10810 공 넣기 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) https://www.acmicpc.net/problem/10810 10810번: 공 넣기 도현이는 바구니를 총 N개 가지고 있고, 각각의 바구니에는 1번부터 N번까지 번호가 매겨져 있다. 또, 1번부터 N번까지 번호가 적혀있는 공을 매우 많이 가지고 있다. 가장 처음 바구니에는 공이 www.acmicpc.net 2. 문제 풀이 N개의 바구니가 있고, M번 덮어쓰기 작업을 실시합니다. i부터 j까지의 바구니에 k를 덮어쓰기 하며, 마지막에 남는 바구니 결과를 출력합니다. 3. 코드 N, M = map(int, input().split()) lst = [0]*N for _ in range(M): i, j, k = map(int, input().split()).. 2023. 6. 7.
[구현/수학] 백준 28061 레몬 따기 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 28061번: 레몬 따기 성우는 숲에서 레몬을 따와야 한다. 숲은 하나의 수직선으로 표현할 수 있고, 여기에는 레몬 나무 \(N\)그루가 \(x=1\)부터 \(x=N\)까지 일정한 간격으로 자라 있다. 성우는 현재 \(x=0\)에 있으며, 집은 www.acmicpc.net 2. 문제 풀이 x = 1부터 x = N까지 레몬나무 N그루가 있으며, 각 나무마다의 레몬 개수가 주어집니다. 성우는 딱 1개의 레몬나무에서만 채집할 수 있으며, 채집 후에는 도착지(x = N)까지 1씩 이동할 때마다 1개씩 잃게 됩니다. 이때, 최대로 채집할 수 있는 레몬의 개수를 구합니다. 3. 코드 import sys input = sys.stdin.readline # 입력 N = .. 2023. 6. 2.
[구현/수학] 백준 28135 Since 1973 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 28135번: Since 1973 $N$이 주어진다. $(1 \leq N \leq 1\, 000\, 000)$ www.acmicpc.net 2. 문제 풀이 N이 처음으로 등장하는 때를 구하는 문제입니다. 예를 들어 N이 15이면, '15'0, '15''15' 등 다양한 수가 나올 수 있으나 처음으로 등장하는 때는... 당연히 15입니다. 따라서 N이 나오는 때를 구하면 됩니다. 다만, 50이 들어가면 그 수를 한 번 더 셉니다. 이를 고려하여 N이 처음으로 나오는 때를 구합니다. 3. 코드 import sys input = sys.stdin.readline # 입력 N = int(input()) # 50이 들어가면 +1 res = 0 for i in ran.. 2023. 6. 1.
[구현/수학] 백준 6840 Who is in the middle? - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 6840번: Who is in the middle? In the story Goldilocks and the Three Bears, each bear had a bowl of porridge to eat while sitting at his/her favourite chair. What the story didn’t tell us is that Goldilocks moved the bowls around on the table, so the bowls were not at the right seats www.acmicpc.net 2. 문제 풀이 세 수를 입력받아 중간값을 구하는 문제입니다. 3. 코드 import sys import math input = .. 2023. 6. 1.
[구현/수학] 백준 27961 고양이는 많을수록 좋다 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 27961번: 고양이는 많을수록 좋다 올바른 행동 순서가 될 수 있는 하나의 예시는 아래와 같으며, $4$번보다 더 작은 행동 횟수로 $6$마리의 고양이를 마도카의 집에 들이는 것은 불가능하다. 초기 상태($0$마리) $\rightarrow$ 생성 www.acmicpc.net 2. 문제 풀이 생성마법: +1 복제마법: 1 ~ 2배 마법을 최소로 사용해서 고양이를 N마리로 만들어야 합니다. 보통 이런 문제는 DP를 사용하지만, 이 문제는 당연히 복제마법의 효율이 좋습니다. 사실상 생성마법 ∈ 복제마법인 셈이죠. 맨 처음에만 생성마법으로 +1을 시키고, 그 다음에는 복제마법만 쓰면 됩니다. 3. 코드 import sys import math input = sy.. 2023. 5. 7.
[구현/수학] 백준 27960 사격 내기 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 27960번: 사격 내기 A, B, C는 올해에도 예비군 훈련을 받으러 간다. 이번 예비군 훈련 과정 중에는 영점 사격이 있으며, 10개의 과녁 각각에 점수를 매겨 맞춘 과녁 점수의 총합을 측정한다. 과녁을 맞혔을 때, 과녁별 www.acmicpc.net 2. 문제 풀이 A와 B의 사격점수가 주어집니다. 과녁은 1 / 2 / 4 / 8 / 16 / 32 / 64 / 128 / 256 / 512 배점이며, 각 과녁마다 1번씩만 쏴서 맞추면 해당 점수를 획득합니다. C는 A와 B 중 한 명만 맞힌 과녁은 맞췄으나, 둘 다 맞히거나 못 맞힌 과녁은 안 맞혔다고 합니다. C의 과녁점수를 구해야 합니다. True True False True False True Fa.. 2023. 5. 6.