https://www.acmicpc.net/problem/13732 13732번: Falling Apples The input begins with a line containing integers R and C, designating the number of rows and columns of the grid, such that 1 ≤ R ≤ 50 000 and 1 ≤ C ≤ 10. The first line is followed by R additional lines, each designating a row of the grid, from to www.acmicpc.net 흔히 볼 수 있는 '중력' 문제이다. 그런데 그냥 아무생각없이 O(N^2)과 같은 시간복잡도로 구현하기 쉬운 유형이다. 큐를 이용..
분류 전체보기
문제 Algorithm 먼저 상자의 크기가 1일 경우를 살펴보자. 사과가 처음 떨어질 때 상자의 이동거리는 상자의 처음 위치와 사과의 위치의 차이이다. 이후로는 현재 사과의 위치와 다음 사과의 위치의 차이가 상자의 이 구간에서의 이동거리가 될 것이다. 모든 구간에서의 이동거리의 합이 답이 될 것이다. 하지만 상자의 크기가 1보다 클 경우에는 상자의 최소 이동거리를 이렇게 구할 수 없다. 먼저 상자의 좌우 각각을 기준으로 더 작은 값이 나오는 쪽을 총 이동거리에 더해간다. $t$시간에서 상자의 가장 왼쪽 부분의 위치, 가장 오른쪽 부분의 위치, 사과의 위치를 각각 $a_t,\ L_t,\ R_t$라 하자. 상자의 크기는 $M$이므로 항상 $R_t = L_t + M$의 관계가 성립한다. 상자의 처음 위치는 $..
https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 아주 기본적인 것들을 충실하게 물어본 문제입니다. 정렬을 하는데 조건이 2개 이상이면 이중 for 문이나 if 문을 사용해도 되지만, lambda 함수를 사용하여 깔끔하게 정리할 수 있습니다. 이 문제를 풀기 위해 알아야 하는 파이썬 기초 개념 set 자료형은 중복을 제거할 수 있으나, 순서가 없기 때문에 list(set(arr)) 형식으로 종종 사용된다. (정렬이 필요할 때) set ..
백준 6502 동혁피자 알고리즘 분류 : 수학, 구현, 기하학, 피타고라스 정리 링크 : https://www.acmicpc.net/problem/6502 6502번: 동혁 피자 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 숫자 세 개로 이루어져 있고, 순서대로 r, w, l이다. r은 식탁의 반지름이고, w와 l은 피자의 너비와 높이이다. (1 ≤ r ≤ 1000 www.acmicpc.net 문제분석 반지름이 r인 원 안에 너비가 w. 높이가 l인 피자가 놓여질 수 있는지 없는지를 판단하는 문제이다. 직사각형 모양의 피자가 원을 벗어나지 않고 놓이기 위해서는 피자의 대각선의 길이가 테이블의 지름의 길이를 초과해선 안된다. 이 때 직사각형의 대각선 길이 x는 (w^2 + x^2)..
문제 문제코드 x=int(input()) boo={} for i in range(x): a=input() if a in boo: boo[a]+=1 else: boo[a]=1 key=list(boo.keys()) value=max(list(boo.values())) t=[] for j in range(len(key)): if boo[key[j]]==value: t.append(key[j]) t.sort() print(t[0]) 문제 풀이 우선 책을 입력받고 boo라는 딕셔너리 안에 책이 없다면 key값을 만들어주고 value 값으로 1을 준다. 그런식으로 모두 받은 다음 value값중 가장 큰 값을 max함수로 찾아내고 max로 찾은 값과 매칭하여 책을 찾아낸다. 그중 사전순으로 정렬할때가장앞의 값을 출력..
문제 https://www.acmicpc.net/problem/6996 문제 해석 하나의 문자로 이루어진 알파벳들로 다른 문자를 만들 수 있는지 알아보는 문제이다. 문제 풀이 .첫 번째 문자열과 두 번째 문자열을 입력받는다. 두 개의 빈 리스트를 만들고 두 개의 문자열의 원소들을 각각의 리스트에 추가한다. 각각의 리스트 들을 sorted함수로 입력했을 때 일치하면 애너그램이고 일치하지 않으면 애너그램이 아니다. 문제 코드
https://www.acmicpc.net/problem/6996 6996번: 애너그램 첫째 줄에 테스트 케이스의 개수(
문제 링크 7785번: 회사에 있는 사람 첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 www.acmicpc.net 문제 문제 해석 이름과 출입 기록을 입력한다. 출입 기록이 enter일 경우 출근 상태, leave일 경우 퇴근 상태이다. 모든 입력이 끝났을 때 출입 기록이 enter인 사람의 이름을 사전 순의 역순으로 출력하면 되는 문제이다. 코드 #include #include #include #include #include #include #include using namespace std; map member; map ..
https://www.acmicpc.net/problem/1302 1302번: 베스트셀러 첫째 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. 이 값은 1,000보다 작거나 같은 자연수이다. 둘째부터 N개의 줄에 책의 제목이 입력으로 들어온다. 책의 제목의 길이는 50보다 작거나 같고 www.acmicpc.net 문제 김형택은 탑문고의 직원이다. 김형택은 계산대에서 계산을 하는 직원이다. 김형택은 그날 근무가 끝난 후에, 오늘 판매한 책의 제목을 보면서 가장 많이 팔린 책의 제목을 칠판에 써놓는 일도 같이 하고 있다. 오늘 하루 동안 팔린 책의 제목이 입력으로 들어왔을 때, 가장 많이 팔린 책의 제목을 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. ..
https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 0. 잡설 시뮬레이션 문제에 자신이 없어서 헤매다가, 좀 풀어보니 감이 좀 잡혔습니다. 시뮬레이션에서는 문제의 모듈화가 중요한 것 같습니다. 디버깅도 쉬워지고, 요새 코테에서 많이 사용하는 프로그래머스에서도 solve()모듈을 주니까 모듈화에 이점이 많은 것 같습니다. 또, 모듈화를 하면 중간중간 프린트를 찍어볼 때 어떤 모듈에서 생각대로 움직여주지 않는지 확인할수도 있겠죠!! 1. 접근 ..
1371번: 가장 많은 글자 (acmicpc.net) 1371번: 가장 많은 글자 첫째 줄부터 글의 문장이 주어진다. 글은 최대 50개의 줄로 이루어져 있고, 각 줄은 최대 50개의 글자로 이루어져 있다. 각 줄에는 공백과 알파벳 소문자만 있다. 문장에 알파벳은 적어도 하나 이 www.acmicpc.net 문제 영어에서는 어떤 글자가 다른 글자보다 많이 쓰인다. 예를 들어, 긴 글에서 약 12.31% 글자는 e이다. 어떤 글이 주어졌을 때, 가장 많이 나온 글자를 출력하는 프로그램을 작성하시오. 입력 첫째 줄부터 글의 문장이 주어진다. 글은 최대 50개의 줄로 이루어져 있고, 각 줄은 최대 50개의 글자로 이루어져 있다. 각 줄에는 공백과 알파벳 소문자만 있다. 문장에 알파벳은 적어도 하나 이상 있다. ..
https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 문제 KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다. 같은 양의 두 용액을 혼합한 용액의 ..
