Python

[python] 백준 - 1743. 음식물 피하기

🤔문제 해결 S1 | BFS 이번에는 2차원리스트를 활용하지 않고 set()을 활용하여 문제를 해결했다. 각각의 좌표가 주어져 있으므로 쓰레기를 하나 선택해 상하좌우 BFS탐색을 한다. 주변의 쓰레기를 선택할 때마다 visited 에 add 해준다. 또 count + 1 을 해줘서 쓰레기 더미의 크기를 answer 에 담는다. 💨 set() 을 쓰는 이유 if tmp in set() : 이렇게 tmp가 set()에 있는지 없는지 확인할 때 시간복잡도가 O(1) 이다. 하지만 if tmp in list : list의 경우 O(n) 이다. 💻소스 코드 import sys from collections import deque def bfs(x, y): q = deque() q.append((x, y)) cnt..

[python] 이진 탐색 트리 (binary Search tree) - 4. 삭제

📗 이진 트리 (binary Search tree) - 삭제 노드 삭제 노드를 하나 삭제해보자. 노드를 삭제하는 경우는 3가지가 있다. 자식 노드가 없은 경우, 자식 노드가 하나인 경우, 자식노드가 둘인경우로 나눌 수 있다. 🔵 자식 노드가 없는 경우 자식 노드가 없는 경우는 그냥 삭제하면 된다. 🔵 자식 노드가 하나인 경우 자식 노드가 하나인 경우는 삭제할 노드를 삭제하고, 그 자식 노드를 할아버지 노드에 붙이면 된다. 🔵 자식 노드가 둘인 경우 자식 노드가 둘인 경우는 삭제할 노드를 삭제하고, 그 노드의 오른쪽 자식의 가장 왼쪽 자손을 가져와서 삭제한 노드의 부모 노드에 붙여준다. 🔵 전체 코드 # 노드 만들기 # A(val) # / \ # B(left) C(right) class Node: def ..

[python] 백준 - 11052. 카드 구매하기 / 16194. 카드 구매하기 2

🤔문제 해결 S1 | 다이나믹 프로그래밍 dp 리스트를 만든다. dp[i]: 카드 i장을 구매하기 위한 지불 금액의 최솟값 dp[0] = float('inf') (파이썬에서의 최댓값) dp[i-j] + dp[j]: 카드를 j장 구매하기 위한 최솟값과 카드를 i-j장 구매하기 위한 최솟값의 합 ex) dp[2] + dp[3]: 카드를 2장 구매하고 3장구매할 때의 최솟값 dp[i-j] + dp[j] 와 dp[i] 의 값을 비교하여 더 작은 값을 dp에 저장 테스트케이스 1번 예시 dp[0] = float('inf') dp[1] = 1 dp[2] = 5 | dp[2] = min(dp[2], dp[1]+dp[1]) | dp[2] = 2 dp[3] = 6 | dp[3] = min(dp[3], dp[2]+dp[1..

[python] 이진 탐색 트리 (binary Search tree) - 3. 순회

📗 이진 트리 (binary Search tree) - 순회 트리 순회 트리 순회는 트리에 저장된 값을 모두 확인할 때 사용한다. 순회 방법에 따라 값을 확인하는 순서가 다르다.순회의 종류로는 전위 순회 (preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)이 있다. 🔵 전위 순회 (preorder traversal) 💨 완성되어 있는 트리를 다른 서버에 리스트 형태로 보내서 그 서버에서 다시 트리를 구성할 때 사용 노드 > 왼쪽 서브트리 > 오른쪽 서브트리 순으로 순회한다. 구현 방법은 다음과 같다. 노드 방문 왼쪽 서브트리 방문 오른쪽 서브트리 방문 전위 순회 결과: F, B, A, D, C, E, G, I, H def p..

[python] 백준 - 1722. 순열의 순서

🤔문제 해결 S1 | 수학, 조합론 순열을 보면 itertools의 permutation이 생각난다. 하지만 이 문제에서는 N이 20까지 이므로 20!을 구하는것은 불가능. 먼저 소문제1일 때의 경우를 살펴보자. N = 5, K = 35 일 때(5개의 숫자, 35번째 순열) N = 5 이므로 5! = 120이다. 120 / N 으로 나누면 24가 되는데, 이는 각각의 앞자리 5개가 가지는 경우의 수이다. 앞자리가 1이면 1 ~ 24번째, 앞자리가 2이면 25 ~ 48번째, 앞자리가 3이면 49 ~ 72번째 ... 이다. K = 35이면 25~48이므로 앞자리가 2라는 것을 알 수 있다. 다음 스텝으로 넘어가면 n = 4, k = 35 - 24 = 11이다. 즉, 맨 2 이전의 숫자인 1이 맨 앞자리에 오..

[python] 백준 - 2240. 자두나무

🤔문제 해결 S1 | 다이나믹프로그래밍 1. 답은 X초에 Y번 움직여서 먹은 최대의 자두 갯수! 변수가 2개이니 2차원 리스트를 만든다. 다른 분들의 답을 보면 자두(사람 헷갈림)의 위치까지 저장하여 3차원으로 만든다. 하지만 이동 횟수에 따라 자두(사람)의 위치는 저절로 정해진다. 홀수번 움직이면 2번 나무에, 짝수번 움직이면 1번 나무에 있다. 2. 행을 초(0~자두갯수) 열을 움직일 수 있는 횟수(0~W) 만큼 2차원 리스트를 만든다. dp의 0번째 행은 0초때, 0번째 열은 움직이지 않았을 때 3. %중요% (1) 받아 먹는 조건: a. i초에 자두가 1번에서 떨어지고 이동 횟수가 짝수(j % 2 == 0, 1번 나무에 위치)하면 b. i초에 자두가 2번에서 떨어지고 이동 횟수가 홀수(j % 2 ..