jungle stack sort recursion depth range sys 백준 2493 python algorithm

파이썬 알고리즘 2주차 : 탑

정글일지 7

1.개발 진행 및 완료상황

  • 2주차 파이썬 알고리즘 공부
  • 스택 문제 1회독 완료
  1. 업무, 개발 중 발생한 이슈/고민 또는 이를 해결한 내용
  • 백준 문제 2493번을 파이썬으로 풀었다. 스택과 관련된 문제로 스택(파이썬에선 list지만)을 정방향으로 볼지(왼쪽부터), 반대방향으로 볼지(오른쪽)에 관련된 문제였다. 주목한 원소가 다음 원소와의 크기 비교를 통해 스택에서 pop을 할지 push를 할지 관련된 문제였는데, 경우에 따른 분류가 힘들었다.
  • 위와 같이 정렬한 자료구조를 역순으로 바라보는 문제가 많았는데 정렬을 뒤바꾸는 것과 읽는 방향을 바꾸는 방법이 있었다. 때에 따라 사용하기 위해 둘 다 알아놓아야겠다. 밑의 첫번째는 오름차순 정렬, 두번째는 내림차순 정렬이다.

list.sort() list.sort(reverse=True)

  • 전 주에 배운 재귀를 이용해 문제풀이를 시도했으나 binary search나 분할정복, 스택 문제에서 재귀를 사용하면 시간 초과로 오답처리 되었다. recursion Error의 경우 python이 정한 최대 재귀 깊이를 초과하면 나오는 문제이다. 아래와 같은 설정을 위에 두면 깊이를 한정지을 수 있어 해결할 수 있다. 물론 나의 경우는 재귀로 푸는 문제가 아니였기에 이후에도 시간 초과가 해결되지 않아 푸는 방식을 아예 바꿨다. 문제가 요구하는 문제풀이 방식을 이용해야 겠다.

import sys sys.setrecursionlimit(1000000)

  • 여전히 입력값을 받아 처리하는 과정이 부드럽지 않다. 확실하게 정리하여 불필요한 부분에서 시간소모를 줄여야겠다.

  • 새로 배운 내용

  • range: 아래 박스에서 첫번째는 10부터 1까지 역순으로 적용된다(10이 출발지여서 10은 포함되었고 0은 도착지라 포함되지 않음). 두번째는 0~9까지를 거꾸로 뒤집은 것이여서 9,8,…,1,0 으로 진행된다.

for i in range(10,0,-1): for i in reversed(range(10)):

  • sys.stdin.readline() : 반복문으로 여러 줄을 입력받을시 input으로 인해 시간초과되는 것을 방지할 수 있다. 아래 코드는 순서대로 한줄에서 1개의 정수 입력받기, 한줄에서 정해진 갯수의 정수 입력받기, 한줄에서 임의의 갯수의 정수 입력받기, 첫줄에서 줄의 갯수를 정해준 후 여러줄의 정수 입력받기, 첫줄에서 줄의 갯수를 정해준 후 문자열 입력받기 이다. 사실 각 줄마다 첫번째 숫자는 갯수를 의미하는 등 다양한 경우가 있지만 우선 list를 이용하고 이후 pop이나 다른 방식으로 추출하여 사용하는게 지금까지는 좋은 방법인것 같다.

import sys N = int(sys.stdin.readline()) A,B = map(int,sys.stdin.readline().split()) data = list(map(int,sys.stdin.readline().split())) data = [] n = int(sys.stdin.readline()) for i in range(n): data.append(list(map(int,sys.stdin.readline().split()))) import sys n = int(sys.stdin.readline()) data = [sys.stdin.readline().strip() for i in range(n)]

  1. 참고할 만한 레퍼런스들
  • 자료구조와 함께 배우는 알고리즘 입문 파이썬편(BohYoh Shibata 지음, 강민 옮김, 이지스 퍼블리싱)
  • https://dojang.io/mod/page/view.php?id=1271
  • https://velog.io/@yeseolee/Python-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%9E%85%EB%A0%A5-%EC%A0%95%EB%A6%ACsys.stdin.readline

  • 특이사항

  • 푹 쉬고 나니 오늘까지도 집중이 잘 됐다. 또한 매일 팀원들과 하루를 정리하는 시간을 가지니 이해가 안되는 문제에 불필요하게 시간을 소모하는 일도 줄었고, 내가 설명을 해주면서 더욱 명확하게 이해되는 경우도 많았다.

  • 회고

  • 아마 화요일 전에는 문제 1회독이 끝날듯 하다. 시간 낭비하지 말고 철저한 복습으로 분할정복, 스택 난이도 상 문제들을 내것으로 만들어야 겠다.
  • 이미 자주 사용하면서도 여전히 헷갈려하는 코드들이 있다. remove,pop,count,index 등등은 잘 적어놨다가 개발일지에 꼭 써야겠다.
  • CSAPP 좀 읽자.
  • TO-DO-LIST
  1. 큐, 우선순위 큐 문제풀이
  2. CSAPP 읽기
CATALOG
    log