파티션 부분은 진짜 예술임 볼때마다 곱씹어 볼것
quicksort 부분도 역시 아름답게 처리됨!
https://gist.github.com/DongguemYoo/52db37550863a361148559dd0dc8cd09
2020년 6월 28일 일요일
[코드잇 divide and Conquer] 퀵소트 python
[코드잇 ] 합병 정렬 구현하기
# 합병 정렬
def merge_sort(my_list):
result = []
result = merge(my_list[0:int(len(my_list) / 2)], my_list[int(len(my_list) / 2):int(len(my_list))])
return result
# 코드를 입력하세요.
# 테스트
print(merge_sort([1, 3, 5, 7, 9, 11, 13, 11]))
print(merge_sort([28, 13, 9, 30, 1, 48, 5, 7, 15]))
print(merge_sort([2, 5, 6, 7, 1, 2, 4, 7, 10, 11, 4, 15, 13, 1, 6, 4]))
나는 실수로 merge를 재귀함수로 구현해놓아서 음...
일단
## 배울점
def merge_sort(my_list):
# base case
if len(my_list) < 2:
return my_list
# my_list를 반씩 나눈다(divide)
left_half = my_list[:len(my_list)//2] # 왼쪽 반
right_half = my_list[len(my_list)//2:] # 오른쪽 반
# merge_sort 함수를 재귀적으로 호출하여 부분 문제 해결(conquer)하고,
# merge 함수로 정렬된 두 리스트를 합쳐(combine)준다
return merge(merge_sort(left_half), merge_sort(right_half))
## 배울점리스트를 오른쪽 반 왼쪽 반으로 나누는 것 몰랏음
2020년 6월 27일 토요일
[코드잇,divide and Conquer] merge함수 Python
합병 정렬 알고리즘 중 사용되는 merge 함수를 작성해 보세요.
merge 함수는 정렬된 두 리스트 list1과 list2를 받아서, 하나의 정렬된 리스트를 리턴합니다.
풀이
실제 코드잇 풀이는 훨씬 심플하다
###다른부분(배울점)
컴파인 쪽에서 코드잇은 엄청 깔끔하게 처리하엿다
# list1과 list2를 돌면서 merged_list에 추가
while i < len(list1) and j < len(list2):
if list1[i] > list2[j]:
merged_list.append(list2[j])
j += 1
else:
merged_list.append(list1[i])
i += 1
###다른부분(배울점)
와우... 계속 인덱스를 증가시켜서 제일 앞쪽에 것을 merged_list에 추가해주었다.
2020년 6월 24일 수요일
[python] 리스트 뒤집기 재귀함수
# 파라미터 some_list를 거꾸로 뒤집는 함수
def flip(some_list):
if len(some_list)==0 or len(some_list) ==1:
return some_list
return some_list[-1:] + flip(some_list[:-1])
# 테스트
some_list = [1, 2, 3, 4, 5, 6, 7, 8, 9]
some_list = flip(some_list)
print(some_list)
설명
배운점
some_list[-1:] == 마지막에 있는 인자 하나some_list[:-1] == 마지막걸 뺀 인자 모두
2020년 6월 23일 화요일
[파이썬] 리스트 슬라이싱
my_list = [7, 5, 2, 3, 6]
print(my_list[1:4]) # => [5, 2, 3]
print(my_list[:4]) # => [7, 5, 2, 3]
print(my_list[1:]) # => [5, 2, 3, 6]
print(my_list[:]) # => [7, 5, 2, 3, 6]
print(my_list[::2]) # => [7, 2, 6]
[파이썬] 리스트를 복사하는 방법
def get_every_other(my_list):
every_other = my_list[::2] # 여기에 2를 바꾸면 결과값이 달라진다
return every_other
mylist = [1,2,3,4,5,6]
print(get_every_other(mylist))
시작 인덱스 부터 시작해서 결과값이 나온다
결과 : [1, 3, 5]
def get_every_other(my_list):
every_other = my_list[::-2] # 심지어 마이너스도 가능
return every_other
mylist = [1,2,3,4,5,6]
print(get_every_other(mylist))마이너스는 마지막 인덱스 부터 시작해서 결과값이 나온다결과 : [6, 4, 2]
2020년 6월 21일 일요일
[정올] 1291 구구단
#하...문제이해가 이렇게 중요하단것을 다시한번 깨닫게 해주는 문제였다...
일단. Error가 나면 출력하는게 아닌것이랑
처음값과 끝값이 주어지면 순차적으로 출력한다는것...
일단 너무 막코딩으로 해결을 한거같아서...다른사람의 정답을 보긴해야겠다..
1291 : 구구단
- 제한시간
- 1000 ms
- 메모리제한
- 64 MB
- 해결횟수
- 2534 회
- 시도횟수
- 12685 회
문제
원하는 구구단의 범위를 입력받아 해당 구간의 구구단을 출력하는 프로그램을 작성하시오.
<처리조건>
(1) 구간의 처음과 끝을 입력받는다.
(2) 입력된 구간은 반드시 처음 입력 값이 끝의 입력 값보다 작아야 하는 것은 아니다.
즉 입력된 구간의 범위는 증가하거나 감소하는 순서 그대로 출력되어야 한다.
입력형식
구구단의 시작 범위 s,와 끝 범위 e를 입력받는다.(s와 e는 2부터 9사이의 정수)
하나의 결과가 출력되면 프로그램을 종료한다.
출력형식
시작 범위와 끝 범위사이의 구구단을 출력하되 모든 값과 부호 사이는 공백으로 구분하여 아래 출력 예와 같이 줄을 맞추어 출력해야 한다.
구구단 사이는 3개의 공백으로 구분한다.
데이터의 크기가 주어진 범위를 벗어날 경우는 "INPUT ERROR!"를 출력하고 s와 e를 다시 입력받는다.
입력 예4 3 | 출력 예4 * 1 = 4 3 * 1 = 3 4 * 2 = 8 3 * 2 = 6 4 * 3 = 12 3 * 3 = 9 4 * 4 = 16 3 * 4 = 12 4 * 5 = 20 3 * 5 = 15 4 * 6 = 24 3 * 6 = 18 4 * 7 = 28 3 * 7 = 21 4 * 8 = 32 3 * 8 = 24 4 * 9 = 36 3 * 9 = 27 |
정답 및 풀이
파이썬 구구단(string 포맷을 정렬하는 방법)
string 포맷을 정렬하는 방법
def gugudan(n):
strFormat = '%-1s * %-1s = %+2s'
s = ''
for i in range(1,10):
s =''
for j in range(0,len(n)):
s += strFormat %(str(n[j]),str(i),str( int(n[j])*i))+" "
print(s)
while(True):
data = input().split()
result =[]
for j in range(0, len(data)):
if int(data[j]) <2 or int(data[j])>9:
print('INPUT ERROR!')
else:
result.append(data[j])
gugudan(result)
파이썬 소수점 자리 표시
f = 49
g = 0.2683
print(str(f)+' * '+str(format(g,".6f"))+' = '+ str(format(f*g,".6f")))
format(아이템,".2f") =
아이템을 소수점2째자리까지 표현
[프로그래머스] 가장큰수
쉬운줄알았는데 쉽게 안되넹...
문제 설명
0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.
예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.
0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.
제한 사항
- numbers의 길이는 1 이상 100,000 이하입니다.
- numbers의 원소는 0 이상 1,000 이하입니다.
- 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.
입출력 예
| numbers | return |
|---|---|
| [6, 10, 2] | 6210 |
| [3, 30, 34, 5, 9] | 9534330 |
추가 주석
대기업 다닌애들한테 문제 풀어보라고 부탁을 해봤습니다.
결론부터 말씀드리자면 대기업 다니는 애들도 왜 1~6 테케 실패하는지 모르겠다고 하네요. 제 최고 점수는 7~11 맞은게 최고 점수이고 아래 코드는 최신 버전이고 테케 11 과 10 실패하는 버전입니다. 일단은 Google, Microsoft 다닌애들한테도 풀어보라고 부탁하였고 개들도 못푸는 문제이면 프로그래머스가 정말 어려운 문제를 만들었거나 아니면 문제 자체에 문제가 있거나.
대기업 다니는애들이 이문제에 대에 지적한 부분은
- 일단 가장 문제있는 문제에 대에서 지적하자면 테케 11 경우
0000
경우0
을 리턴을 해야합니다. - 문제에 테케가 부족합니다.
- 모든 경우의 수를 프로그래머가 생각을 해야합니다.
- 마지막은 다 동의 하실거라 생각하네요. 자기가 무슨 테케를 틀렸는지 안말해준다는점
비록 영문이지만 적어도 테케 어디서 틀렸는지 말해주고 무슨 테케에서 fail 이 떴는지 나오는 사이트입니다. 또 미국 대기업들이 콘테스트 같은걸 할때 가장 많이 사용하는 사이트입니다. https://leetcode.com/explore/ 0% 숫자가 있는게 무료버전입니다 나머지는 유로이고요. 돈내고 굳이 푸실 필요까지는 없을거에요.
작성하고있던 코드는 더이상 시도는 무의미한거 같에서 포기하고. 다른분들이 필요할만한 Comparator 만 가져다 쓰세요. Comparator String 속성상 o1 이 항상 큰 숫자입니다 따라서 항상 o1 이 더 큰수를 지니고 있을거에요.
2020년 6월 16일 화요일
팔린드롬 python
def is_palindrome(word):
n = int(len(word)/2)
for i in range(0,n+1):
if word[i]!=word[len(word)-i-1]:
return False
return True
# 코드를 입력하세요.
# 테스트
print(is_palindrome("racecar"))
print(is_palindrome("stars"))
print(is_palindrome("토마토"))
print(is_palindrome("kayak"))
print(is_palindrome("hello"))
백준 파이썬 기본예제
두 수를 입력받아서 더한값을 리턴하시오
a, b = map(int, input().split())
print(a+b)
두 수를 입력받아 다양한 출력을 하시오
a, b = map(int, input().split())
print(a+b,a-b,a*b,a//b,a%b)백준 10951번문제
두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트 케이스로 이루어져 있다.
각 테스트 케이스는 한 줄로 이루어져 있으며, 각 줄에 A와 B가 주어진다. (0 < A, B < 10)
출력
각 테스트 케이스마다 A+B를 출력한다.
while True:
a = input().split()
print(int(a[0])+int(a[1]))이렇게하면 틀린다while True:
try:
a = input().split()
print(int(a[0]) + int(a[1]))
except:
break이렇게 해야함
python 피보나치 수열
n = int(input())
a,b = 0,1
while n>0:
a,b = b ,a+b
n -=1
print(a)
입력 받은 n 값에 따라 해당하는 index의 피보나치 수열을 리턴한다
2020년 6월 11일 목요일
2020년 6월 10일 수요일
2020년 6월 8일 월요일
토글을 구현하는 방법
1단계
onoff = True
if onoff == True:
onoff = False
else:
onoff = True2단계
onoff = False if onoff else True3단계
onoff ^= True와우...미쳣다 실화냐;;
onoff = True
onoff ^= True
print(onoff)
onoff = False
onoff ^= True
print(onoff)
False
True[코딩테스트] 타일 장식물.python
문제 설명
대구 달성공원에 놀러 온 지수는 최근에 새로 만든 타일 장식물을 보게 되었다. 타일 장식물은 정사각형 타일을 붙여 만든 형태였는데, 한 변이 1인 정사각형 타일부터 시작하여 마치 앵무조개의 나선 모양처럼 점점 큰 타일을 붙인 형태였다. 타일 장식물의 일부를 그리면 다음과 같다.
그림에서 타일에 적힌 수는 각 타일의 한 변의 길이를 나타낸다. 타일 장식물을 구성하는 정사각형 타일 한 변의 길이를 안쪽 타일부터 시작하여 차례로 적으면 다음과 같다.
[1, 1, 2, 3, 5, 8, .]
지수는 문득 이러한 타일들로 구성되는 큰 직사각형의 둘레가 궁금해졌다. 예를 들어, 처음 다섯 개의 타일이 구성하는 직사각형(위에서 빨간색으로 표시한 직사각형)의 둘레는 26이다.
타일의 개수 N이 주어질 때, N개의 타일로 구성된 직사각형의 둘레를 return 하도록 solution 함수를 작성하시오.
제한 사항
- N은 1 이상 80 이하인 자연수이다.
입출력 예
| N | return |
|---|---|
| 5 | 26 |
| 6 | 42 |
정답 및 풀이
2020년 6월 7일 일요일
[코딩테스트] 추석트래픽 python
문제 설명
추석 트래픽
이번 추석에도 시스템 장애가 없는 명절을 보내고 싶은 어피치는 서버를 증설해야 할지 고민이다. 장애 대비용 서버 증설 여부를 결정하기 위해 작년 추석 기간인 9월 15일 로그 데이터를 분석한 후 초당 최대 처리량을 계산해보기로 했다. 초당 최대 처리량은 요청의 응답 완료 여부에 관계없이 임의 시간부터 1초(=1,000밀리초)간 처리하는 요청의 최대 개수를 의미한다.
입력 형식
solution함수에 전달되는lines배열은 N(1 ≦ N ≦ 2,000)개의 로그 문자열로 되어 있으며, 각 로그 문자열마다 요청에 대한 응답완료시간 S와 처리시간 T가 공백으로 구분되어 있다.- 응답완료시간 S는 작년 추석인 2016년 9월 15일만 포함하여 고정 길이
2016-09-15 hh:mm:ss.sss형식으로 되어 있다. - 처리시간 T는
0.1s,0.312s,2s와 같이 최대 소수점 셋째 자리까지 기록하며 뒤에는 초 단위를 의미하는s로 끝난다. - 예를 들어, 로그 문자열
2016-09-15 03:10:33.020 0.011s은2016년 9월 15일 오전 3시 10분 **33.010초**
부터2016년 9월 15일 오전 3시 10분 **33.020초**
까지**0.011초**
동안 처리된 요청을 의미한다. (처리시간은 시작시간과 끝시간을 포함) - 서버에는 타임아웃이 3초로 적용되어 있기 때문에 처리시간은 0.001 ≦ T ≦ 3.000이다.
lines배열은 응답완료시간 S를 기준으로 오름차순 정렬되어 있다.
출력 형식
solution함수에서는 로그 데이터lines배열에 대해 초당 최대 처리량을 리턴한다.
입출력 예제
예제1
입력: [
2016-09-15 01:00:04.001 2.0s
,2016-09-15 01:00:07.000 2s
]출력: 1
예제2
입력: [
2016-09-15 01:00:04.002 2.0s
,2016-09-15 01:00:07.000 2s
]출력: 2
설명: 처리시간은 시작시간과 끝시간을 포함하므로
첫 번째 로그는01:00:02.003 ~ 01:00:04.002에서 2초 동안 처리되었으며,
두 번째 로그는01:00:05.001 ~ 01:00:07.000에서 2초 동안 처리된다.
따라서, 첫 번째 로그가 끝나는 시점과 두 번째 로그가 시작하는 시점의 구간인01:00:04.002 ~ 01:00:05.0011초 동안 최대 2개가 된다.
예제3
입력: [
2016-09-15 20:59:57.421 0.351s
,2016-09-15 20:59:58.233 1.181s
,2016-09-15 20:59:58.299 0.8s
,2016-09-15 20:59:58.688 1.041s
,2016-09-15 20:59:59.591 1.412s
,2016-09-15 21:00:00.464 1.466s
,2016-09-15 21:00:00.741 1.581s
,2016-09-15 21:00:00.748 2.31s
,2016-09-15 21:00:00.966 0.381s
,2016-09-15 21:00:02.066 2.62s
]출력: 7
설명: 아래 타임라인 그림에서 빨간색으로 표시된 1초 각 구간의 처리량을 구해보면
(1)은 4개,(2)는 7개,(3)는 2개임을 알 수 있다. 따라서 초당 최대 처리량은 7이 되며, 동일한 최대 처리량을 갖는 1초 구간은 여러 개 존재할 수 있으므로 이 문제에서는 구간이 아닌 개수만 출력한다.
정답 및 풀이
피드 구독하기:
글 (Atom)