본문 바로가기
728x90

파이썬13

백준 2217 - 로프 ( Python ) https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 예제풀이 n: 2 10 15 2개의 로프가 각각 10 15를 들 수 있음. 10인 로프는 10이 넘어가는 순간 끊어짐 예제의 최대 무게는 20이된다. n: 5 3 7 1 10 5 이런경우에는 줄을 5개를 쓰는 것이 불필요하다 1이 5개인 경우엔 고작 5까지밖에 못들지만 최대가 10이므로 하나를 쓰는게 더 나은 경우다 내림차순으로 정렬해보자 모든 경우의 수를 생각해보면 10 -> 10 7 .. 2022. 12. 1.
백준 1541 - 잃어버린 괄호 ( Python ) https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 키포인트 : -를 기준으로 하여 괄호를 치는 것이 가장 작은 수를 만들 수 있다. 처음에는 마이너스가 존재하는 경우 아닌 경우로 풀이하였는데 +기준으로 분리하여 더한다는 것이 공통된 부분이였고 -1을 하는 것이 논리적으로 바로 알아보기 힘든 점이 있어서 개선하였다. 1. - 기준으로 분리 2. 첫번째 요소를 제외하고 다 더함 3. 첫번째 요소를 + 기준으로 분리하여 다시 빼고 * -1 한 후.. 2022. 11. 27.
백준 11047 - 동전 0 (Python) 백준 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 예제 풀이 10 4200 1 5 10 50 100 500 1000 5000 10000 50000 10가지의 동전을 4200원의 최소 동전 개수를 구하려면 큰 숫자부터 값을 빼줘야 한다 4200 - 1000 = 3200 3200 - 1000 = 2200 2200 - 1000 = 1200 1200 - 200 = 200 200 - 100 = 100 100 - 100 = 0 총 6번 1.. 2022. 11. 25.
백준 11399 - ATM( Python ) https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 예제 풀이 n = 5 p = [ 3, 1, 4, 3, 2 ] 적게 기다리는 순으로 우선 오름 차순 정렬을 해줘야한다 sorted = [ 1, 2, 3, 3, 4 ] 1 1 + 2 = 3 1 + 2 + 3 = 6 1 + 2 + 3 + 3 = 9 1 + 2 + 3 + 3 + 4 = 13 => 1 + 3 + 6 + 9 + 13 = 32 즉, 1부터 이전 값을 계속 반복하며 더하는 문제이다. 2중 for문으로 해결이 가능하다 n = .. 2022. 11. 23.
정렬 알고리즘(선택정렬, 삽입정렬, 퀵정렬, 계수정렬) - python 선택정렬 가장 작은 것을 선택해서 맨 앞의 데이터와 바꾸는 것을 반복 시간복잡도 Ο(n²)으로 상당히 느린편이다 array = [...] for i in range(len(array)): min_index = i; #가장 작은 원소의 인덱스 for j in range(i+1, len(array)): if array[min_index] > array[j]: min_index = j array[i], array[min_index] = array[min_index], array[i] 삽입정렬 특정한 데이터를 적정한 위치에 삽입 데이터가 거의 정렬되어 있을 때 훨씬 효율적 첫번째 데이터는 정렬되어 있다고 판단하고 두번째 데이터 부터 시작한다 정렬이 이루어진 원소는 항상 오름차순을 유지한다. 시간복잡도는 Ο(n².. 2022. 10. 1.
파이썬 온라인 컴파일러 https://www.programiz.com/python-programming/online-compiler/ Online Python Compiler (Interpreter) www.programiz.com 파이참을 설치하기 싫고 단순 코딩테스트용으로 쓰기 적당하다. 다만 커서를 인식하는 줄이 조금은 멍청해서 줄수안에 커서를 정확히 클릭해야 인식함.. 처음에는 에러난 줄 맙소사 이건 import sys 를 아직 지원하지 않는다고 한다 역시 구관이 명관 학교에서 쓰던 온라인 컴파일러가 최고다.. https://www.onlinegdb.com/online_python_compiler 2022. 9. 1.
728x90
반응형

티스토리툴바