[BAEKJOON]백준 4256번 트리 - 트리(Tree) 자료구조, 분할 정복(Divide and Conquer)
백준 4256번 트리 백준 4256번 트리 설명 전위 순회는 가운데, 왼쪽, 오른쪽으로 가기 때문에 첫번째 값이 가운데 노드이므로 이 노드를 중위 순회에 적용하여 중위 순회를 가운데 노드 기준으로 왼쪽, 오른쪽으로 나누는 분할 정복 형태로 문제를 풉니다. 이렇게 트리를 만들고, 후위 순회로 찍어줍니다. 코드 import sys from typing import List input = sys.stdin.readline # 트리 구조체 선언 class TreeNode: def __init__(self, x, left=None, right=None): self.x = x self.left = left self.right = right class Solution: def tree(self, preorder: L..
[BAEKJOON]백준 10830번 행렬 제곱 - 분할 정복(Divide and Conquer) 알고리즘, 행렬 곱하기
백준 10830번 행렬 제곱 백준 10830번 행렬 제곱 divide and conquer로 제곱승, 제곱승x제곱승=4제곱승, 4제곱승x4제곱승=16제곱승 형태로 계산수를 줄인다. 곱한다음 1000으로 나눈 나머지나 1000으로 나눈 나머지 곱이나 같으므로, 받을 때, 곱할 때, 곱하고 나서 모두 1000으로 나눈 나머지로 바꿔준다. 안그럼 커짐. 행렬곱은 외워두는게 좋겠다.. 코드 import sys sys.setrecursionlimit(10**6) input = sys.stdin.readline def multiply_matrix(arr1, arr2): answer = [] for idx1 in range(len(arr1)): row = [] for idx2 in range(len(arr2[0]))..
[Algorithm]그리디(Greedy) 알고리즘, 분할 정복, 다이나믹 프로그래밍 이란? 비교 및 분석하기 - 알고리즘 문제를 풀기전에 알아야 하는 개념(배낭 문제, 동전 바꾸기, 피보나치 수열 등)
그리디 알고리즘 그리디 알고리즘이란 바로 눈앞의 이익만을 좇는 알고리즘을 말한다. 그리디 알고리즘은 최적화 문제를 대상으로 한다. 최적해를 찾을 수 있으면 그것을 목표로 삼고, 찾기 어려운 경우에는 주어진 시간 내에 그런대로 괜찮은 해를 찾는 것을 목표로 삼는다. 그리디 알고리즘이 잘 작동하는 문제들은 탐욕 선택 속성을 갖고 있는 최적 부분 구조인 문제들이다. 여기서 탐욕 선택 속성이란 앞의 선택이 이후 선택에 영향을 주지 않는 것을 말한다. 다시 말해 그리디 알고리즘은 선택을 다시 고려하지 않는다. 또한 최적 부분 구조란 문제의 최적 해결 방법이 부분 문제에 대한 최적 해결 방법으로 구성되는 경우를 말한다. 이렇게 탐욕 선택 속성과 최적 부분 구조의 2가지 조건을 만족하면 최적해를 찾을 수 있다. 하지..
[Leetcode] 리트코드 - 괄호를 삽입하는 여러 가지 방법(different-ways-to-add-parentheses) 파이썬(python) 풀이
문제 숫자와 연산자를 입력 받아 가능한 모든 조합의 결과를 출력하라. 입력 : "2 - 1 - 1" 출력 : [0, 2] 설명 ((2 - 1) - 1) = 0 (2 - (1 - 1)) = 2 입력 : "2 * 3 - 4 * 5" 출력 : [-34, -14, -10, -10, 10] 설명 (2 * (3 - (4 * 5))) = -34 ((2 * 3) - (4 * 5)) = -14 ((2 * (3 - 4)) * 5) = -10 (2 * ((3 - 4) * 5)) = -10 (((2 * 3) - 4) * 5) = 10 코드 """ fixme. https://leetcode.com/problems/different-ways-to-add-parentheses/ fixme. Q84. 괄호를 삽입하는 여러 가지 방법..