본문 바로가기
반응형

알고리즘211

[알고리즘] Maximum Subarray + 배열에서 부분 최대합을 구하는 방법 어느 순간 1100 명께서 저의 글을 읽어 주셨습니다. 정말 부족한 글이지만 잘 쓰도록 하겠습니다. 포인트 배열에서 부분합을 구하는 방법은 정말 다양하게 있을 수 있습니다. 먼저 LeetCode 문제를 풀어보고 이어서 다른 것들도 써보는 시간이면 좋겠습니다. 저는 다이나믹 프로그래밍으로 해결을 하였습니다. O(n) 즉, 배열을 전부 순회를 하는 경우 답을 구할 수 있다는 뜻입니다. 값을 계속 저장을 해나가면서 만약 더하려고 하는 값이 0 이하일 경우 0으로 초기화한 후 계속해서 더해나가는 것입니다. python class Solution: def maxSubArray(self, nums: List[int]) -> int: result = 0 presum = 0 # DP 를 이용한 방법 for index .. 2021. 5. 17.
[알고리즘] 길 찾기 게임 포인트 전위, 후위 그리고 node 구성을 알 수 있는가? 입니다. 🧶문서는 항상 수정될 수 있습니다. 비판은 환영합니다. python import sys sys.setrecursionlimit(10 ** 6) class Node: def __init__(self, id, x, y): self.id = id self.x = x self.y = y self.left = None self.right = None def __str__(self): # 클래스를 표현 할때, 사용 return "Node {} {} {} {} {}".format(self.id, self.x, self.y, self.left.id, self.right.id) def preorder(pre: list, node: Node) -> Non.. 2021. 5. 7.
[알고리즘] 불량 사용자 포인트 불량 사용자의 경우의 수를 찾는 프로그램을 만들어야 합니다. 전체적으로 데이터가 있고 불량 사용자가 있는 경우들을 표시합니다. 각각의 경우를 계산하여 구하고자 하는 경우를 찾아야 합니다. 🧶문서는 항상 수정될 수 있습니다. 비판은 환영합니다. python from collections import defaultdict from itertools import product def check(string1: str, string2: str) -> bool: if len(string1) != len(string2): # 길이가 다르면 False return False for i in range(len(string1)): if string1[i] == "*": # * 이 나오면 통과 continue if.. 2021. 5. 6.
[알고리즘] 방금그곡 포인트 방법에 따라서 접근 방법이 달라질 수 있을 것 같습니다. 저는 시간에 따라서 기존에 갖고 있는 scale note를 이어 붙인 뒤 조건에 맞으면 vc에 넣어서 정렬하여 원하는 값을 출력할 수 있도록 문제를 해결하였습니다. 🧶문서는 항상 수정될 수 있습니다. 비판은 환영합니다. python def other_char(string:str) -> str: # 중복되지 않는 스케일로 변환 return string.replace('C#', 'c').replace('D#', 'd').replace('F#', 'f').replace('G#', 'g').replace('A#', 'a') def solution(m: str, musicinfos: list) -> str: m = other_char(m) vc = .. 2021. 5. 5.
반응형

티스토리툴바