본문 바로가기

알고리즘/백준

 (23)
백준 1920 - 수 찾기 문제https://www.acmicpc.net/problem/1920   풀이# 백준 / 실버4 / 수 찾기# 이진탐색 알고리즘# 반드시 찾는 list가 정렬된 상태여야 한다.def binary_search(target,list1): start = 0 end = len(list1)-1 while start target: end = mid - 1 else: start = mid + 1 return 0N = int(input())list1 = list(map(int,input().split()))M = int(input())list2 = list(map(int,input().split()))list..
백준 11651 - 좌표 정렬하기 2 문제https://www.acmicpc.net/problem/11651  풀이# 백준 / 실버5 / 좌표 정렬하기 2n = int(input())dot = []for _ in range(n): dot.append(list(map(int,input().split()))) dot.sort(key=lambda x : (x[1],x[0]))for i in dot: print(f'{i[0]} {i[1]}') sort의 key=lambda만 잘 기억하면 쉽게 풀 수 있다.
백준 2485 - 가로수 문제https://www.acmicpc.net/problem/2485   풀이# 백준/실버4/가로수# 유클리드 호제법# a,b가 있을 때, a를 b로 나눈값을 b, 기존의 b를 a로 바꾸면서# b가 0이 될때까지 반복한다.def gcd(a,b): while b > 0: a,b = b,a % b return an = int(input())data = []# 입력값for _ in range(n): data.append(int(input()))# 가로수 사이의 격차를 저장diff = []for i in range(1,len(data)): diff.append(data[i] - data[i-1])# 격차 간의 최대공약수를 구한다g = diff[0]for j in rang..
백준 1246 - 온라인 판매 문제경래는 닭을 기르는데 올 겨울 달걀 풍년으로 함박 웃음을 짓고 있다. 그리고 이 달걀을 영양란으로 둔갑하여 옥션에 판매하려한다.경래는 총 N개의 달걀이 있고, 그의 잠재적인 고객은 총 M명이다. 그리고 각각의 i번째 고객은 각자 달걀 하나를 Pi 가격 이하로 살 수 있다고 밝혔다.경래는 영양란이라 속인 죄책감에 한 고객에게 두 개 이상의 달걀은 팔지 않기로 하였다. 하지만 위의 규칙 하에 수익은 최대로 올리고 싶기에 얼마로 팔지 고민하고 있다. 즉, A가격에 달걀을 판다고 하면 Pi가 A가격보다 크거나 같은 모든 고객은 달걀을 산다는 뜻이다. (물론 달걀 총 수량을 초과하여 팔 수 는 없다)문제는 이러한 경래를 도와 최대 수익을 올릴 수 있는 달걀의 가장 낮은 가격을 책정하는 것이다.입력첫째 줄에 정..
백준 16439 - 치킨치킨치킨 문제N명의 고리 회원들은 치킨을 주문하고자 합니다.치킨은 총 M가지 종류가 있고 회원마다 특정 치킨의 선호도가 있습니다. 한 사람의 만족도는 시킨 치킨 중에서 선호도가 가장 큰 값으로 결정됩니다. 진수는 회원들의 만족도의 합이 최대가 되도록 치킨을 주문하고자 합니다.시키는 치킨의 종류가 많아질수록 치킨을 튀기는 데에 걸리는 시간도 길어지기 때문에 최대 세 가지 종류의 치킨만 시키고자 합니다.진수를 도와 가능한 만족도의 합의 최댓값을 구해주세요.입력첫 번째 줄에 고리 회원의 수 N (1 ≤ N ≤ 30) 과 치킨 종류의 수 M (3 ≤ M ≤ 30) 이 주어집니다.두 번째 줄부터 N개의 줄에 각 회원의 치킨 선호도가 주어집니다.i+1번째 줄에는 i번째 회원의 선호도 ai,1, ai,2, ..., ai,M ..
백준 1268 - 임시 반장 정하기 문제오민식 선생님은 올해 형택초등학교 6학년 1반 담임을 맡게 되었다. 오민식 선생님은 우선 임시로 반장을 정하고 학생들이 서로 친숙해진 후에 정식으로 선거를 통해 반장을 선출하려고 한다. 그는 자기반 학생 중에서 1학년부터 5학년까지 지내오면서 한번이라도 같은 반이었던 사람이 가장 많은 학생을 임시 반장으로 정하려 한다.그래서 오민식 선생님은 각 학생들이 1학년부터 5학년까지 몇 반에 속했었는지를 나타내는 표를 만들었다. 예를 들어 학생 수가 5명일 때의 표를 살펴보자.                                                                        1학년               2학년               3학년               4학년   ..
백준 2870 - 수학숙제 문제상근이는 수학시간에 딴 짓을 하다가 선생님께 걸렸다. 선생님은 상근이에게 이번 주말동안 반성하라며 엄청난 숙제를 내주었다.선생님이 상근이에게 준 종이에는 숫자와 알파벳 소문자로 되어있는 글자가 N줄있다. 상근이는 여기서 숫자를 모두 찾은 뒤, 이 숫자를 비내림차순으로 정리해야한다. 숫자의 앞에 0이 있는 경우에는 정리하면서 생략할 수 있다.글자를 살펴보다가 숫자가 나오는 경우에는, 가능한 가장 큰 숫자를 찾아야 한다. 즉, 모든 숫자의 앞과 뒤에 문자가 있거나, 줄의 시작 또는 끝이어야 한다.예를 들어, 01a2b3456cde478에서 숫자를 찾으면 1, 2, 3456, 478이다.선생님이 준 종이의 내용이 주어졌을 때, 상근이의 숙제를 대신하는 프로그램을 작성하시오.입력첫째 줄에 종이의 줄의 개수 ..
백준 28292 - 개미 수열 문제대구소프트웨어마이스터고등학교에 다니고 있는 changwook987은 베르나르 베르베르의 소설 『개미』를 읽다가 흥미로운 수열을 보았다. 1,11,12,1121 ... 이 수열은 소설 『개미』에서 나와 개미 수열이라고 부르기도 하고 읽고 말하기 수열이라고 하기도 한다.이 수열의 규칙은 이렇다.첫 번째 항은 1이다.이전 항의 이웃한 같은 숫자들을 묶는다.이전 항이 1121일 경우 (1,1), (2), (1)묶인 숫자들의 숫자와 개수를 붙여 쓴다.묶인 숫자들이 (1,1), (2), (1) 일경우 122111이 된다.2, 3을 반복한다.이 개미 수열을 관찰하다 보면 수가 빠르게 길어지지만, 수를 이루는 숫자가 커지기는 쉽지 않다는 것을 알 수 있다.그렇다면 이 수열의 N번째 항의 자릿수 중에서 가장 큰 수는..

티스토리툴바