Problem Solving
-
[PS]좌표 정렬하기Problem Solving 2020. 12. 10. 22:57
단어 정렬하기와 비슷한 문제. 좌표가 입력되고 해당 좌표를 x좌표의 오름차순으로 정렬하고, x좌표가 같은 경우 다음은 y좌표로 정렬하여 출력해야 하는 문제이다. import math def mergesort(entries): if isinstance(entries,list) and len(entries) > 1 : pivot = math.floor(len(entries)/2)-1 first = mergesort(entries[:pivot+1]) second = mergesort(entries[pivot+1:]) return merge(first,second) else: return entries def merge(first,second): unit=[] if not isinstance(first,list..
-
[PS] 수 찾기Problem Solving 2020. 12. 5. 01:03
수열을 입력받고, 찾아야 하는 수들이 포함된 배열을 추가로 입력받아 수열 내에 수들이 포함되어 있는 지에 대한 여부를 1 또는 0으로 출력해야 하는 문제이다. n = int(input()) entries = input().split() m = int(input()) tofind = input().split() result =[0]*m for i in entries: for b in range(0,m): if int(i) == int(tofind[b]): result[b] = 1 for u in result: print(u) 우선 입력받은 수열을 반복문으로 전체 순회하고, 하나의 요소를 찾아야할 수열 중에 하나와 일치하는 지를 반복문으로 순회하여 판별하는 방식으로 진행. 결과는 당연히 시간 초과! impo..
-
[PS]수 정렬하기 3Problem Solving 2020. 12. 3. 20:24
수 정렬하기 2와 같은 문제이나 이번엔 메모리 제한이 8MB로 정해진 문제이다. 전에 사용했던 합병 정렬을 제출했으나 역시나 될리가 없었다. 질문 검색을 해본 결과 가장 많은 사람들이 사용하는 것이 계수 정렬이었다. 그래서 계수 정렬을 알아봤는데,꽤나 빠른 알고리즘이었다 n 시간 복잡도를 가지면서도, 아주 간결한 코드였다.다음은 내가 작성한 코드. 열심히 짠 코드였지만,역시나 메모리 초과. 이번엔 누적합을 제외한 코드를 제출해봤지만 역시나 실패였다. 지푸라기라도 잡아보자는 심정으로 파이썬으로 제출해봤다. 그런데 이게 왠걸?? 맞았다.이번으로 알게 된 교훈은 pypy는 빠르지만 메모리 소모가 크다는 것!
-
[PS] 단어 정렬하기Problem Solving 2020. 12. 2. 19:51
무작위로 입력된 소문자 영단어를 길이 순으로 정렬하되 같은 길이면 사전순으로 나열해야하는 문제이다. 단, 길이가 같으면 한 번만 출력해야 한다. import time import math def mergesort(entries): if isinstance(entries,list) and len(entries) > 1 : pivot = math.floor(len(entries)/2)-1 first = mergesort(entries[:pivot+1]) second = mergesort(entries[pivot+1:]) return merge(first,second) else: return entries def merge(first,second): unit=[] if not isinstance(first,l..
-
[PS] 백준 - 수 정렬하기 2Problem Solving 2020. 11. 19. 21:03
입력된 갯수만큼 수를 입력하고,해당 수열을 오름차순으로 정렬해야하는 문제이다. a = int(input()) entries=[] for x in range(0,a): entries.extend([int(input())]) entries.sort() for x in entries: print(x)멍청하게도, 그냥 아싸리 파이썬의 정렬함수를 이용하여 제출했으나결과는 제한 시간 2초를 넘겨 통과하지 못했다. 제한 시간이 2초밖에 안되는 만큼, 가장 빠른 정렬을 이용할 필요가 있다고 생각했고,퀵 정렬을 이용하기로 하였다. def quicksort(entry): if len(entry) entry[1]: temp = en..