'Python' 카테고리의 글 목록 (3 Page)

본문 바로가기

Python74

[그리디 알고리즘5] 백준 4796번 캠핑 파이썬 백준 4796번 캠핑 📜 문제 등산가 김강산은 가족들과 함께 캠핑을 떠났다. 하지만, 캠핑장에는 다음과 같은 경고문이 쓰여 있었다. 캠핑장은 연속하는 20일 중 10일동안만 사용할 수 있습니다. 강산이는 이제 막 28일 휴가를 시작했다. 이번 휴가 기간 동안 강산이는 캠핑장을 며칠동안 사용할 수 있을까? 강산이는 조금 더 일반화해서 문제를 풀려고 한다. 캠핑장을 연속하는 P일 중, L일동안만 사용할 수 있다. 강산이는 이제 막 V일짜리 휴가를 시작했다. 강산이가 캠핑장을 최대 며칠동안 사용할 수 있을까? (1 < L < P < V) 🚩 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, L, P, V를 순서대로 포함하고 있다. 모든 입력 정수는 int범위이.. 2021. 7. 15.

[그리디 알고리즘4] 백준 1202 보석 도둑 파이썬 우선순위 큐 heapq 백준 1439 보석 도둑 📜 문제 세계적인 도둑 상덕이는 보석점을 털기로 결심했다. 상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다. 상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오. 🚩 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci ≤ 100,000,000) 모든 숫자는 양의 정수이다. 🌞 출력.. 2021. 7. 15.

[그리디 알고리즘3] 백준 1439 뒤집기 파이썬 백준 1439 뒤집기 📜 문제 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다. 예를 들어 S=0001100 일 때, 전체를 뒤집으면 1110011이 된다. 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다. 하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다. 문자열 S가 주어졌을 때, 다솜이가 해야하는 행동의 최소 횟수를 출력하시오... 2021. 7. 14.

[그리디 알고리즘2] 백준 1080 행렬 파이썬 백준 1080 행렬 문제 0과 1로만 이루어진 행렬 A와 행렬 B가 있다. 이때, 행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값을 구하는 프로그램을 작성하시오. 행렬을 변환하는 연산은 어떤 3*3크기의 부분 행렬에 있는 모든 원소를 뒤집는 것이다. (0 -> 1, 1 -> 0) 입력 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. 출력 첫째 줄에 문제의 정답을 출력한다. 만약 A를 B로 바꿀 수 없다면 -1을 출력한다. 여기서 뽀인트는 3*3 크기 단위로 모든 원소를 반대로 뒤집는다는 것 ! 그래서 각각의 배열들을 비교했을 때 전체를 비교할 필요가 없이 3.. 2021. 7. 14.

[ 그리디 알고리즘 1 ] 백준 1774 수 묶기 파이썬 백준 1744번 수 묶기 처음에는 너무 쉽게 풀은 줄 알았으나 생각할수록 예외가 많아지는 문제였다. 실패를 여러번 한 케이스 n = int(input()) plus=[] minus=[] zero=0 for i in range(n): x = int(input()) if x>0: plus.append(x) if x1 and plus[i+1]>1: answer += plus[i]*plus[i+1] used.append(i+1) else: answer += plus[i] used2=[] for i in range(len(minus)): if i in used2: continue elif i==len(minus)-1: if zero>0: answer+= 0 else: answer += minus[i] else: .. 2021. 7. 14.

[Python] 백준 1946번 이해하기 백준 1946번 신입사원 문제 이번 주는 GREEDY 알고리즘을 공부하고 있다. 모르더라도 문제 풀이를 읽으며 이해가 가능했는데 요 문제는 뭔가 문제 자체를 이해하기도 어려웠고 풀이하는 것도 어려웠다. (T_T) 그래서 혹시나 요 문제 이해가 잘 안되는 분들을 위해 풀이를 정리해보고자 한다. 백준 1946번 문제 풀이 문제 풀이 : 헷갈렸던 점은 바로 ! 입력되는 저 숫자들은 성적이 아니고 순위입니다. 이 문제를 풀며 다시 한번 문제를 제대로 잘 읽어야하는 중요성을 느꼈습니다. 그 다음 헷갈리는 것은 신입사원으로 뽑는 기준입니다. 기준은 한 지원자의 서류, 면접 성적이 다른 어떠한 지원자보다 최소 1개라도 높으면 채용이 됩니다. 즉, A의 서류순위, 면접 순위가 B 보다 둘 다 낮으면 A는 100% 떨어.. 2021. 7. 7.

[Python] 탐욕법, Greedy 알고리즘 GREEDY 알고리즘 Greedy 알고리즘이란 ? 현재 상황에서 지금 당장 최선인 것, 좋은 것만을 고르는 알고리즘이다. 또한 탐욕 법이라고도 불립니다. Greedy 알고리즘은 '정당성' 분석이 매우 중요합니다. - 단순히 가장 좋아보이는 것을 반복저긍로 선택해도 최적의 답을 구할 수 있는지 검토가 필요합니다. 일반적인 상황에서 Greedy 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많습니다. 왜냐하면 탐욕법은 당장의 좋은 것을 선택하기 때문입니다. 하지만 코딩테스트의 Greedy 문제는 대개 탐욕법으로 얻은 답(해)이 최적의 답이 되는 상황이 주어집니다. 그리디 알고리즘의 대표문제 : 그리디 알고리즘은 대표적으로 k 원의 돈을 건네야할 때 n개의 잔돈 가짓수(500원, 100원, 50원..) .. 2021. 7. 6.

[Python3] 최신버전 Reduce 사용법 lambda 표현법 Python .reduce() from functools import reduce Python3 이후, fuction ---> functools 로 변경되었습니다. 매서드 풀이 기본형 reduce(집계함수, 순회 가능한 데이터, 초기값) 기본적으로 위와 같습니다. 보통 누적 덧셈으로 reduce를 처음 접하고 이후 다양한 함수들을 연습해보면 좋습니다 ! 반환값 : 설정한 함수의 return 값 예제 1. 누적 덧셈 from functools import reduce arr = [1,2,3,4,5,6,7,8,9,10] SUM1 = reduce(lambda x,y : x+y, arr) SUM2 = reduce(lambda x,y : x+y, arr, 0) print(SUM1) print(SUM2) 풀이 : .. 2021. 7. 5.

[Python 파이썬] 해시 (Hash) 해싱 (Hashing) 알고리즘 예제로 알아보기 파이썬 코딩테스트에 출제 빈도가 높은 파이썬 '해시' 에 대해 알아보기 해시 / 해싱 / Hash / Hashing - 데이터를 빠르게 넣거나 or 가져올 때 사용하는 기법 : 해시로 풀어야하는 코딩 테스트의 경우 *** (아래 예제 有) -> 리스트로 풀게되면 효율성 테스트 실패 ! - 최솟값 or 최댓값을 찾을 때 (전체 자료를 모두 검색하는 경우) 효율이 떨어짐 - 파이썬의 딕셔너리가 해시 테이블로 구현되어 있음 해시관련 알고리즘을 접한 후에, 해시의 유용함에 대해 알게 되었습니다. 먼저 프로그래머스 level2 의 해시 대표문제 '전화번호 목록' 을 보겠습니다. 먼저 해시를 사용하지않은 코드, 그리고 해시를 사용한 코드의 실행 시간을 비교해 보겠습니다. 파이썬 실행시간 계산 / 측정 방법 http.. 2021. 7. 4.

[Python] 함수 실행 경과 시간 계산하기 time() time_process() 코딩테스트를 풀면서 문득 제가 실행하는 코드의 경과 시간이 궁금해졌습니다. 그래서 찾아본 함수 실행하면 시간이 얼마나 걸리는지 알려주는 time 매서드! 1. TIme.time() 1. 시간 계산하고 싶은 함수 준비 def Fn(x,y): print(x + y) Fn(1,2) 2. import time 그리고 시작하는 부분과 시간 계산을 끝내고 싶은 부분에 변수(아무 이름이나 ok) 를 담아 마지막에 print(end - start)를 해주면 됩니다. import time start = time.time() def Fn(x,y): print(x + y) Fn(1,2) end = time.time() print(end-start) * start - end 를 a , b로 바꿔보기 import time a .. 2021. 7. 4.

[Python] 소수 찾기 알고리즘 파이썬으로 소수 찾기 알고리즘 소수 찾기는 무언~가 어려운 느낌이 들어서 코딩테스트 연습할 때 항상 가장 마지막까지 남겨두곤 했다. 계속 이러면 더 못할테니 오늘 날잡고 아예 파헤쳐보자 !!! 👩‍💻 소수란 ? 1과 자기 자신만으로 나누어 딱 떨어지는 1보다 큰 양의 정수 ex) 2 -> 어떤 수로 2를 나누어 딱 떨어지는 수는 1,2 -> 2는 소수 ex) 4 -> 어떤 수로 4로 나누어 딱 떨어지는 수는 (= 4를 나눌 수 있는 수) 1,2,4 => 1,4 본인 자신을 제외하고 2도 있기 때문에 4는 소수가 아님 문제 : n 이 주어지고 1부터 n 까지의 소수의 개수를 구해보기 ex) n=10이라면 소수는 = [2,3,5,7] 4개가 나온다 ! 1. 완전 탐색 - 시간 복잡도 O(N) 이중 for문으.. 2021. 6. 30.

[Python] 파이썬 함수 def / Function / global 키워드 / 람다표현식 함수를 쓰는 이유 : 똑같은 코드를 반복적으로 쓸 때 'function'을 만들어 놓고 필요할 때마다 씀으로써 효율적이고 코드의 길이도 줄일 수 있다. Python, 파이썬의 두 가지 함수 종류 1. 내장 함수 : 파이썬이 기본적으로 제공하는 함수 es) input(), print() 2. 사용자 정의 함수 : 개발자가 직접 정의하여 사용할 수 있는 함수 함수 용어 1. 매개변수 : 함수 내부에서 사용할 변수 2. 반환 값 : 함수에서 처리 된 결과를 반환 def 함수명 (매개변수) : 실행할 소스코드 return 반환값 def = define 매개변수와 반환값은 Optional 예제 파이썬의 Global 키워드 global 키워드로 변수를 지정하면 해당 함수에서는 지역 변수를 만들지 않고 함수 바깥에 .. 2021. 6. 25.

[프로그래머스] 모의고사 파이썬 python 모의고사 문제 설명 수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ... 2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ... 3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ... 1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution .. 2021. 6. 23.

[프로그래머스] python 2016년 2016년 문제 설명 2016년 1월 1일은 금요일입니다. 2016년 a월 b일은 무슨 요일일까요? 두 수 a ,b를 입력받아 2016년 a월 b일이 무슨 요일인지 리턴하는 함수, solution을 완성하세요. 요일의 이름은 일요일부터 토요일까지 각각 SUN,MON,TUE,WED,THU,FRI,SAT 입니다. 예를 들어 a=5, b=24라면 5월 24일은 화요일이므로 문자열 "TUE"를 반환하세요. 제한 조건 2016년은 윤년입니다. 2016년 a월 b일은 실제로 있는 날입니다. (13월 26일이나 2월 45일같은 날짜는 주어지지 않습니다) 입출력 예 abresult 5 24 "TUE" 나의 코드 def solution(a, b): day = ['MON','TUE','WED','THU','FRI','SA.. 2021. 6. 22.

[프로그래머스] 파이썬 문자열 다루기 기본 python 문자열 다루기 기본 문제 설명 문자열 s의 길이가 4 혹은 6이고, 숫자로만 구성돼있는지 확인해주는 함수, solution을 완성하세요. 예를 들어 s가 "a234"이면 False를 리턴하고 "1234"라면 True를 리턴하면 됩니다. 제한 사항 s는 길이 1 이상, 길이 8 이하인 문자열입니다. 입출력 예 sreturn "a234" false "1234" true 실패 1 def solution(s): if len(s)==6 or len(s) ==4: if (s.isdigit() ==True) : return True else: return False 드디어 성공 ! def solution(s): if len(s)==6 or len(s) ==4: if (s.isdigit() ==True) : retur.. 2021. 6. 21.

이전 1 2 3 4 5 다음

티스토리툴바