알고리즘44 병합 정렬 in python 고급 정렬 중 병합정렬에 대해 공부해보자. 병합정렬은 모든 리스트의 요소를 한개의 배열로 쪼개고 하나씩 위로 올리면서 정렬을 하는 방식이다. 그래서 리스트의 모든 요소가 한개의 배열로 쪼개질 때, log(n)이고 각 요소를 정렬할 때 n의 복잡도가 들면서 최종적으로 O(nlog(N))의 복잡도가 든다. log(n)은 만약 8개의 요소가 있으면 각각을 한개로 쪼개는데 3번 분류된다. 2^3. 2의 몇승으로 늘어나기 때문에 log를 붙인다. 이걸 코드로 짜면 #병합정렬 def merge_sort(array): if len(array) 2021. 11. 1. [백준 1018번] 체스판 다시 칠하기 in python 문제 지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다. 체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다. 보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8.. 2021. 10. 29. [백준 11729번] 하노이 탑 이동 순서 in python 문제 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다. 아래 그림은 원판이 5개인 경우의 예시이다. 입력 첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다. 출력 첫째 줄에 옮긴 횟수 K를 출력한다. 두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈.. 2021. 10. 29. [백준 2447번] 별 찍기 - 10 in python 문제 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다. *** * * *** N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 예를 들어 크기 27의 패턴은 예제 출력 1과 같다. 입력 첫째 줄에 N이 주어진다. N은 3의 거듭제곱이다. 즉 어떤 정수 k에 대해 N=3k이며, 이때 1 ≤ k < 8이다. 출력 첫째 줄부터 N번째 줄까지 별을 출력한다. 예제 입력 1 27 예제 출력 1 **************************.. 2021. 10. 28. int형 숫자를 0을 앞에 붙인 문자열로 변경 in python target=1 print(format(target,'02')) print('{0:03d}'.format(target)) 결과 : 01 001 개인적으로 밑에 것을 더 선호 2021. 10. 27. 문자열 내부 공백 제거 in python 문자열 처리를 하다보면 공백들이 들어간 문자열들을 볼 수 있다. 예를 들어, 1: " asdf asdf asdf asdf " 2: "asdf asdf asdf asdf" 이런 경우들이 있다. 이럴 땐, str.strip(), str.replace(), str.split()들을 써주면서 제거해주면 가볍게 해결이 된다. S=input() #' asdf asdf asdf ' print(S.split()) split()함수로 ['asdf', 'asdf', 'asdf']가 생성된다. 좌우 공백이 있는 문자열이 불편하다 싶으면, S=input() #' asdf asdf ' print(S.strip()) strip()함수를 써주면 'asdf asdf'가 나온다. 또한 아예 공백이 없는 문자열로 만들고 싶다? S=in.. 2021. 10. 26. 파이썬으로 입력받기 - input() or sys.stdin.readline() 보통 백준에서 알고리즘 공부를 하다보면 입력을 넣어줘야하는 코드를 작성해야한다. (프로그래머스에선 그런거 필요없는데....) 여튼 그래서 보통 input()을 쓰거나 a,b=map(int, input().split()) 을 써서 받은 string값을 정수인 int값으로 바꿔주었다. 그러다가 유용한게 있어서 적어놓는다. input대신 sys.stdin.readline()을 하면 시간초과를 줄여줄 수 있다. 안그래도 다른 언어에 비해 속도가 낮은 파이썬이라 시간초과가 많이 나는데 이 정보는 유용하다. import sys T=int(sys.stdin.readline())# strip은 문자열의 앞뒤에 있는 공백문자들을 제거해준다. for i in range(T): a,b=map(int, sys.stdin.re.. 2021. 10. 25. python 딕셔너리 - items, values, 정렬 가끔 dict이 헷갈릴 때가 있어 써놓는다. a={} for 문을 쓸 때, 키만 불러오고 싶다면 for key in a: 값만 꺼내오고 싶다면 for value in a.values(): 키와 값 둘다 불러오고 싶을 땐 for key, value in a.items(): https://wikidocs.net/16043 + dict을 정렬할 땐, key를 기준으로 정렬하고 싶다면 # 오름차순 정렬 sorted_a=sorted(a.items()) #내림차순 정렬 sorted_a_reverse=sorted(a.items(),reverse=True) 또는 value를 기준으로 정렬한다면, #오름차순 정렬 sorted_a=sorted(a.items(),key=lambda x:x[1]) #내림차순 정렬 sorted.. 2021. 9. 1. 이전 1 2 3 4 5 다음
