백준3 [백준] 1717. 집합의 표현 (+파이썬 코드) Question. 백준 1717. 집합의 표현 Answer. union-find 알고리즘을 구현하는 문제이다. 즉, union 함수랑 find_parent 함수를 구현할 수 있냐를 묻는 문제. sol 1) union-find 알고리즘을 구현하고, 같은 서로소 집합에 있는지 아닌지 확인해주는 함수를 구현해 풀었다. import sys sys.setrecursionlimit(1000000) # maximum recursion depth exceed (한도 안 늘리면 runtime error 발생) input = sys.stdin.readline def find_parent(parent, x): if parent[x] != x: parent[x] = find_parent(parent, parent[x]) re.. 2021. 2. 15. [백준] 2748. 피보나치 수 2 - 문제 풀이 (+파이썬 코드) Question. 백준 2748. 피보나치 수 2 Answer. 사실 이 문제는 파이썬에서는 "백준 2747. 피보나치 수" 문제와 동일하다. 파이썬은 int, long 구분을 할 필요가 없고, 숫자가 아무리 커져도 다 담을 수 있기 때문에 2747번에 pass한 코드를 그대로 제출하면 된다. 그러나 cpp, java의 경우 long long 등으로 선언해, 피보나치 수의 값이 int 범위를 넘어갈 경우에도 해당 값을 담을 수 있도록 해야 pass 한다. 아래 파이썬 코드는 [백준] 2747. 피보나치 수 - 문제 풀이 (+파이썬 코드)과 동일하다. sol 1) recursion with memoization # recursion with memoization # time complexity : O(N).. 2021. 2. 5. [백준] 2747. 피보나치 수 - 문제 풀이 (+파이썬 코드) Question. 백준 2747. 피보나치 수 피보나치 수열을 구현하는 문제이다. 예전에는 면접 질문으로도 자주 나왔다고 하는데, 요즘은 쉬워서 잘 안 나오는 것 같다. 다만, '피보나치 수를 구현하는 모든 방법은?', '피보나치 수를 각각 반복법, 재귀로 구현해보면?' 이런 식으로 물어볼 수는 있겠다. Answer. 피보나치 수열을 구현하는 방식은 크게 3가지가 있는데, 1) 재귀 2) recursion with memoization 3) for문 이용해 구현 하지만 이 문제는 1)의 방식대로 재귀로 풀면 '시간초과'가 난다. O(N)에 풀어야 하는 문제이기 때문에, 재귀로 풀 경우, memoization을 해야 한다. sol 1) recursion with memoization 재귀로 구현하되 mem.. 2021. 2. 5. 이전 1 다음 728x90
