본문 바로가기
반응형

Computer Science/Algorithms13

[Leetcode] Longest substring without repeating characters 1. 개요 주어진 문자열에서 가장 긴 부분 문자열(연속된 문자로 이루어진 부분)의 길이를 반환합니다.부분 문자열은 중복되는 알파벳을 가지고 있지 않아야 합니다.예) abcdabefgabcda는 a를 2개 포함하므로 탈락입니다.cdabefg에는 중복되는 문자가 없고 가장 깁니다.따라서 정답은 7입니다. 2. 나의 풀이 가장 간단한 방법은 모든 부분 문자열을 구한 다음, 각 문자가 중복되지 않고 가장 긴 것을 찾는 것입니다.저는 전체 문자열에서 시작 문자 char를 선택한 다음,char로 시작하는 부분 문자열을 모두 구하는 방식으로 풀었습니다.class Solution: def lengthOfLongestSubstring(self, s: str) -> int: answer = 0 .. 2025. 9. 18.
[Leetcode] add two numbers 1. 개요 링크드 리스트 형태의 두 숫자를 더한 결과를 링크드 리스트로 반환합니다.예)L1: 3 -> 2 -> 1 (123)L2: 6 -> 5 -> 4 (456)123 + 456 = 579 이므로정답: 9 -> 7 -> 5 2. 나의 풀이 class Solution: # 클래스 안에 정의한 함수는 인스턴스 메서드로 취급되므로, 첫 번째 인자가 self여야 한다. def getNum(self, node: Optional[ListNode]): if node is None: return 0 num = node.val next = node.next i = 1 while next: num += (10 ** .. 2025. 9. 17.
[Leetcode] two-sum 1. 개요 숫자 배열 nums과 목표 숫자 target 하나가 주어집니다.숫자 배열에 있는 숫자 두 개를 더해서 목표 숫자를 만들고,각 숫자의 인덱스를 배열로 반환해야 합니다.예를 들어,[1, 2, 3] 과 5가 주어진 경우2 + 3 = 5 이므로, [1, 2]를 반환해야 합니다.문제의 정답은 반드시 존재합니다. 2. 단순 무식한 방법 이중 루프를 돌면서 리스트에서 두 개의 숫자를 골라 더해보는 방법이 있습니다.쉽고 간단한 대신 O(n^2)의 시간 복잡도를 가집니다.class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: for i, n in enumerate(nums): for j, m.. 2025. 9. 16.
다이나믹 프로그래밍 Dynamic Programming 1. divide and conquer와 dynamic programming의 차이 divide and conquer(분할정복)는 하나의 문제를 해결할 수 있을 정도의 작은 부분으로 분할하여 하나하나 정복해나가는 프로그래밍 기법을 말합니다. 작게 나눌수록 복잡해 보였던 문제는 단순화되고 보다 쉽게 해결책을 도출해낼 수 있게 됩니다. dynamic programming(동적계획법)은 문제를 작은 조각들로 분해하여 한꺼번에 해결한다는 점에서 분할정복과 유사해보입니다. 하지만 분명한 차이가 있습니다. 분할정복은 하나의 문제를 작은 문제들로 나누고, 그 작은 문제들을 해결한 결과를 합쳐나가는 방식으로 문제에 대한 최종 해를 구하는 것인 반면, 다이내믹 프로그래밍은 일련의 문제들을 해결하기 위해서 문제를 작은 조.. 2022. 12. 29.
선택정렬, 버블정렬, 삽입정렬 1. 개요 1) 선택정렬 가장 간단한 정렬방법입니다. 6 3 4 5 1 2 리스트 중에서 최소값을 찾아 맨 앞에 위치시킵니다. 1 6 3 4 5 2 그리고 나머지 원소 중에서 다시 최소값을 찾습니다. 1 2 6 3 4 5 이를 n번 반복하면 1 2 3 6 4 5 1 2 3 4 6 5 1 2 3 4 5 6 정렬된 리스트를 얻을 수 있습니다. 2) 버블정렬 오른쪽 끝에서부터 최소값(왼쪽에서 시작할 경우는 최대값)을 거품이 올라오듯 보글보글 불러오는 방법입니다. 인접한 두 개 원소를 비교해서 작은 값을 땡겨오고 또 옆에 있는 놈과 비교해서 땡겨오고 하다보면 최소값이 리스트 시작점에 쌓이게됩니다. 3) 삽입정렬 길이가 1인 정렬된 리스트에 원소를 하나씩 추가하여 정렬된 리스트의 길이가 n이 되면 종료합니다. 2.. 2021. 11. 9.
스택과 괄호의 값 문제 : https://www.acmicpc.net/problem/2504 1. 개요 주어진 괄호들이 규칙에 맞는지 확인, 계산하는 문제입니다. 2. 고난과 역경 1) check () 우선 괄호의 짝이 맞는지 확인하기 위해 왼쪽 괄호를 하나씩 읽어와 스택에 추가합니다. 오른쪽 괄호를 만났을 때 스택이 비어있거나, 꺼내온 값이 왼쪽 괄호가 아니라면 규칙에 어긋나므로 0을 리턴합니다. 처음 완성한 check() 에는 " ( ( [ " 와 같이 왼쪽 괄호만이 들어왔을 때 그냥 통과시켜버리는 문제가 있었습니다. check가 규칙에 맞지 않는 녀석들을 통과시켜버리는 바람에 EmptyStackException 이 발생했습니다. for 문이 종료되었을 때, 스택에 값이 남아있다면 0을 리턴하는 문장을 추가하여 문제를.. 2021. 11. 4.
반응형

티스토리툴바