본문 바로가기

전체 글126

[백준/파이썬(Python), 자바(JAVA)] 회의실 배정1931 Silver1 💌문제 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 💌풀이 그리디 알고리즘 문제이다. 그리디 알고리즘이란, 최적의 솔루션을 찾기 위해 알고리즘의 각 단계에서 최적의 선택을 하는 수학적 최적화 기법이다. 솔루션을 반복적으로 구성하여 최적화 문제를 해결하는데 사용하며, 항상 현재 사용 가능한 최상의 값을 선택한다. 이러한 그리디 알고리즘은 구조가 단순한데, 개인적으로는 솔루션 떠올리는게 어려운 것 같다. 또한, 그리디는 간단하고 효율적이지만 항상 최적의 솔루션이 나오지는 않을 수 있다. 이럴 때는 DP등의 다른 알고리즘을 사용해야 한다. 아래 코드에 대한 설명.. 2023. 2. 10.
[백준/파이썬(Python), 자바(JAVA)] 동전0 11047 Silver 4 💌문제 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 💌풀이 그리디 알고리즘 문제이다. 그리디 알고리즘이란, 최적의 솔루션을 찾기 위해 알고리즘의 각 단계에서 최적의 선택을 하는 수학적 최적화 기법이다. 솔루션을 반복적으로 구성하여 최적화 문제를 해결하는데 사용하며, 항상 현재 사용 가능한 최상의 값을 선택한다. 이러한 그리디 알고리즘은 구조가 단순한데, 개인적으로는 솔루션 떠올.. 2023. 2. 9.
[백준/파이썬(Python),자바(JAVA)] 기타줄 1049 Silver 4 💌문제 https://www.acmicpc.net/problem/1049 1049번: 기타줄 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주 www.acmicpc.net 💌풀이 일단 먼저 6개가 들어있는 패키지의 가격대로 정렬한 리스트와 낱개로 살 때의 가격대로 정렬한 리스트를 만든다. 루프를 돌면서 만약에 n이 6보다 같거나 크면 패키지 가격으로 살 수 있기 때문에 n//6한 값만큼 패키지를 살 수 있으므로, 그렇게 연산해서 answer에 패키지 가격을 더해본다. 그리고, 낱개로 6개를 샀을 때의 가격도 계산해본다. 그 다음에 패키지가격으로 샀을 때,.. 2023. 2. 8.
[백준/파이썬(Python), 자바(JAVA)] 수리공 항승 1449(Silver 3) 💌문제 https://www.acmicpc.net/problem/1449 1449번: 수리공 항승 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 www.acmicpc.net 💌풀이 물이 새는 곳을 편의상 창문이라고 칭하겠다. 창문이 있는 위치는 제각각으로 들어오기 때문에, 연산하기 쉽도록 처음에 정렬을 하고 시작한다. 물을 막을 때 적어도 그 위치의 좌우 0.5만큼 간격을 줘야 한다고 했기 때문에, x-0.5와 x+0.5까지를 고려하며 계산해야 한다. 만약 테이프의 길이가 최대 1이라면, (x+0.5)-(x-0.5)=1이기 때문에 테이프는 창문.. 2023. 2. 7.
[백준/파이썬(Python)] 나무자르기 2805 🐱문제 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 🐱풀이 벌목 높이를 움직여서 필요 나무 길이를 채우는지 확인한다. 가장 짧은 길이 1을 start로 정하고, 나무 중에 가장 긴 길이를 end로 설정한다. 이진탐색이 끝날 때까지 while문을 돌린다. mid를 start와 end의 중간으로 두고, 모든 값에서 mid를 빼서 총 어느정도 길이의 벌목된 나무가 나오는지 확인한다. 만약 벌목된 나무가 목표.. 2023. 2. 6.
[백준/파이썬(Python)] 2252 줄세우기(Gold 3) 💜문제 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 💜코드 from collections import deque n,m=map(int,input().split()) num=[[] for _ in range(n+1)] visit=[0]*(n+1) for _ in range(m): a,b=map(int,input().split()) num[a].append(b) visit[b]+=1 def topolo.. 2023. 2. 5.

티스토리툴바