Posts

백준 1924번 바로가기 나의 풀이 # 입력 import sys from datetime import datetime x, y = map(int, sys.stdin.readline().split()) days = ['MON', 'TUE', 'WED', 'THU', 'FRI', 'SAT', 'SUN'] # 처리 today = datetime(2007, 1, 1) target = datetime(2007, x, y) dday = (target-today).days print(days[dday%7]) CODE REVIEW 간만에 숨돌리기 용으로 푼 간단한 수학 문제. 아니 구현 문제. 참고로 2007년에는 1, 3, 5, 7, 8, 10, 12월은 31일까지, 4, 6, 9, 11월은 30일까지, 2월은 28일까지 있다.라는 문제조건이 있긴 하지만 범용적으로 쓰는 datetime 모듈을 활용해서 풀어내었다. 이전에 짭군돌이 만들었을 때에 dday 구했던 기억이 난다. month = [31, 28, 31, 30 ... ]로 해서 month 인덱싱으로 풀 수도 있겠지만 웬만하면 datetime 씁시다 ㅎㅎ

요즘은 실제 개발보다는 알고리즘 공부에 더 힘을 실었었다. 백준이랑 프로그래머스 문제 풀이를 틈틈히 했는데, 브론즈 문제도 힘들어했던 내가 실버를 풀고 골드V 문제들도 몇 개는 풀 수 있는 실력이 되어 매우 뿌듯하다. 그러다보니 최근에 ML 공부에 소홀해진 것 같아서 간만에 Kaggle에 들어가서 dataset 하나 붙들고 열심히 풀어보았다. Kaggle은 일종의 ‘ML(머신러닝) 분야의 백준` 느낌인데, 다양한 데이터셋을 제공하고 Competition을 통해 경쟁을 붙이는 특징을 가진다. 여기에서는 0.0001단위의 개선도 중요하기에 특정 데이터를 분석하기 위한 좋은 모델들이 개발되고, 그 과정에서 머신러닝 생태계가 더욱 확장된다. ...

백준 11279번 바로가기 나의 풀이 # 입력 import heapq n,*l = open(0) heap = [] # 처리 for x in l: if (x:=(-int(x))) == 0: try: print(-heapq.heappop(heap)) except: print(0) else: heapq.heappush(heap,x) CODE REVIEW python에서 제공하는 heapq - 힙 큐 알고리즘을 이용. 참고로 heapq 모듈의 documentation에 등장하는 관련 method는 다음과 같다 삽입: heapq.heappush(heap, item) 삭제: heapq.heappop(item) 만일 힙이 비어있으면 IndexError 발생. 문제는 heapq 모듈은 최솟값, 즉 min heap만 다룰 수 있다는 점인데, 이를 해결하기 위해 입력 받는 x의 부호를 (-)로 바꾸어 반전시켜서 heapq을 이용했다.

백준 11286번 바로가기 나의 풀이 # 입력 import sys import heapq n = int(sys.stdin.readline().strip()) heap = [] # 처리 for x in sys.stdin: if (x := (int(x))) == 0: try: print(heapq.heappop(heap)[1]) except: print(0) else: heapq.heappush(heap, (abs(x), x)) CODE REVIEW 11279번 - 최대 힙 & 1927번 - 최소 힙과 매우 유사한 문제. heapq로 절댓값 힙을 구현하기 위해서 heapq.heappush() 해줄 때에 (x의 절댓값, x)을 함께 넣어주었다. 정렬은 x의 절댓값으로 되고, 출력은 heappop()했을 때에 index 1인 요소를 출력해주면 된다.

백준 1927번 바로가기 첫 번째 시도 # 입력 import sys read = sys.stdin.readline n = int(read().strip()) arr = [] # 처리 for _ in range(n): x = int(read().strip()) if x == 0: try: print(arr.pop()) except: print(0) else: arr.append(x) arr.sort(reverse=True) 최종 제출 # 입력 import heapq n,*l = open(0) heap = [] # 처리 for x in l: if (x:=int(x)) == 0: try: print(heapq.heappop(heap)) except: print(0) else: heapq.heappush(heap,x) CODE REVIEW 자료구조와 우선순위 큐의 구현 방법에 따른 시간 복잡도는 링크 참조! 우선순위 큐를 구현하는 방법에는 여러가지가 있는데, 배열이나 연결 리스트를 이용할 경우 시간 복잡도가 (삽입,삭제) = (O(1),O(n)) 혹은 (O(n),O(1))로 나타난다. 삽입, 삭제를 모두 구현해야하는 이 문제에서는 O(n)의 시간복잡도는 시간초과 에러를 발생시킬 수 밖에 없다. 게다가 매번 x가 들어올 때마다 arr을 새로 정렬하니까 시간이 많이 걸릴 수 밖에.. 삽입할 때 오름차순을 헤치지 않는 알맞은 자리에 집어넣어야 시간을 절약할 수 있다. 따라서 삽입, 삭제 모두 시간복잡도가 O(logn)인 힙(heap)을 이용해서 우선순위 큐(priority queue)를 구현해보자. 힙(heap)을 스스로 구현하려다가 귀찮아서(…) 그냥 python에서 제공하는 heapq - 힙 큐 알고리즘을 이용했다. heapq 모듈의 documentation에 따르면… 삽입: heapq.heappush(heap, item) 삭제: heapq.heappop(item) 만일 힙이 비어있으면 IndexError 발생. heapq라는 매우 유용한 python 내장 모듈이 있음을 기억해두고, 최댓값/최솟값을 다루는 문제가 있다면 유용하게 써먹자!!