tose33

c++로 풀었던 백준 문제를 파이썬으로 변환하다가 메모리 초과가 났다. 이유가 뭔지 찾아봤는데 이유는 다음과 같았다. 1. c++도 그렇지만 파이썬도 재귀함수를 호출하면 함수가 끝나지 않은채 함수가 또 호출되기 때문에 스택 메모리에 메모리가 계속 쌓이게 된다. 2. 그런데 나는 지금까지 c++에서 재귀 함수의 사용으로 메모리 초과를 경험한 적이 없다. (적어도 내 기억에는) 3. 이유는 바로 꼬리 재귀 (Tail Recursion) 때문 이었다. 꼬리 재귀 꼬리 재귀란 재귀 함수의 호출이 끝난 후 아무 연산을 하지 않고 바로 반환하는 재귀이다. 예를들어 다음과 같은 깊이 우선 탐색을 구현한 재귀 함수는 void dfs(int r, int c, int cnt, int dir, vector &v) { if(..

노트용, 계속 추가 ... 빠른 입력 import sys n = int(sys.stdin.readline()) 클래스 # 클래스 생성 class Node: # 생성자 def __init__(self, root, left, right): self.root = root self.left = left self.right = right Dictionary 순회하며 출력 map = {} for key, val in map.items(): print(key, val) Dictionary get 함수 c++에서는 key값이 없으면 0을 반환하지만 파이썬에서는 그냥 에러를 발생시킨다. get 함수를 사용하면 에러를 발생시키지 않고 none 값을 반환함으로서 예외처리를 할 수 있다. m = {} m[0] = 1 if m..

계속 추가 join 함수 문자열 이을때 사용. '구분자'.join(리스트) 형식 리스트를 받아 구분자로 구분된 문자열로 이어붙여서 리턴해준다. stdin.readLine() 입력이 많아서 입력속도 개선이 필요할때 사용. permutations 함수 순열 함수인데, c++이랑 다른점은 모든 순열이 담긴 리스트를 리턴해준다 permutations(리스트, 리스트에서 뽑을 숫자의 갯수)

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net bfs를 이용해서 풀었다. 큐를 다음과 같이 queue q 로 int형 한 쌍이 들어가도록 pair로 선언하고 { 정점, 이전정점 } 을 기록해서 각 정점이 어떤 정점에서 이동되었는지 기록한다. 이렇게 기록하면 이전 정점이 현재 정점의 부모가된다. 다른 분들 코드를 봤는데 큐를 페어로 선언 하지 않아도 된다. 생각해보면 그냥 이전 정점이 현재 정점의 부모이다.. python 파이썬으로 풀어봤는데 아무리 봐도 시간초과가 날 코드가 아닌데 계속 시간초과가 나서 검..