코딩대장경

섬의 개수라는 문제와 로직이 거의 동일한 문제다. '섬의 개수' 문제와 살짝 응용이 필요한 '단지 번호 붙이기' 문제 2개를 풀고 나면 DFS의 기본을 마스터했다고 말할 수 있을 것이다. dx와 dy에 상하좌우 정보를 미리 담아 활용하는 방식이 인상적이고 한 번에 생각하기 힘든 방식인 것 같다. 그리고 리스트는 주소 값만 전달한다는 점을 이용해서 dfs의 어느 곳에서든지 land라는 리스트에 접근할 수 있게 코드를 짰다. import sys inputs_len = int(sys.stdin.readline()[:-1]) inputs = [list(sys.stdin.readline()[:-1]) for _ in range(inputs_len)] dx = [0,0,1,-1] dy = [1,-1,0,0] m =..

헤시 맵은 파이썬의 딕셔너리를 생각하면 된다. Key와 Value로 이루어져 있으며 값에 대한 접근, 삽입, 삭제 등이 O(1)로 매우 빠르다는 장점이 있다. 해시 맵의 원리 1. Key값을 입력으로 받아 해시를 출력하는 해시함수를 돌리게 된다. 2. 해당 해시에 값을 저장한다. 3. 해시가 충돌하면(서로다른 Key가 동일한 해시를 출력) 개별 체이닝 or 오픈 어드레스 방식으로 해결한다. 3-1 개별 체이닝: 해시가 충돌하면 값의 뒷 부분에 Linked List를 이용해 값을 붙인다. (이 경우 키 값은 다르니 매칭되는 key를 찾아 return하면 된다) 3-2 오픈 어드레스: 해시가 충돌하면 비어있는 다른 해시에 값을 저장한다. (파이썬의 딕셔너리는 이 방식) 4. 공간의 3/4(java)이 채워지..

중복 되지 않는 가장 긴 문자열을 찾는 문제. 문자열을 n번 순회하고 해당 문자열의 길이를 하나씩 늘려가며 검사하는 로직 통과는 했지만 상당히 낮은 속도를 보여줬다. from collections import Counter as ct class Solution: def lengthOfLongestSubstring(self, s: str) -> int: set_s = list(set(s)) if len(set_s) == 0: return 0 elif len(set_s) == 1: return 1 max_result = len(set_s) result = 2 for i in range(len(s)): if i + result > len(s): break flag = 0 t1 = ct(s[i:i + resul..

랜덤 값을 1~100 으로 100명에게 하나씩 주어진다. 이때 동일한 값을 가질 확률은 6.3% 일때 50%, 15.6% 일때 99%에 해당한다. 전체의 6.3% 즉 7명의 수를 비교했을 때 동일한 값을 가질 확률은 50%, 15.6%인 16명의 수를 비교했을 때 동일한 값을 가질 확률은 99%라는 소리다. 언뜻보면 50명이 모여야 50%가 될 것 같지만 생각보다 굉장히 낮은 수치여서 기록한다.

내가 푼 코드 제공받은 리스트 중에 가장 작은 값을 비교하여 새로운 노드에 값을 계속 추가해줬다. 근데 런타임이 아주 길게 나오며 아슬아슬하게 통과한 것 같다. class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next from typing import List, Optional class Solution: def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]: for i in range(len(lists)-1,-1,-1): if not lists[i]: del lists[i] if len(lists) == 0: return d..

중복된 문자를 제거하고 사전적 순서가 가장 적은 순으로 나열하라는 문제다. 이 문제는 직접 풀긴 했지만 속도가 100ms 정도로 하위 5%에 속하는 속도를 보여서 문제를 풀긴했지만 아주 찝찝하기 그지 없었다. stack문제인데 대체 어디서 스택을 써야하는지 감도 오지 않는다. class Solution: def removeDuplicateLetters(self, s: str) -> str: temp_s = sorted(list(set(s))) t1 = 0 temp_i = 0 result = [] while temp_s: t2 = temp_s[t1] for i in range(temp_i,len(s)): if s[i] == t2: flag = 0 for j in temp_s: if j not in s[i:..

토요일에 배웠던 Linked List가 어려워서 관련 문제를 하나 풀어보았다. https://leetcode.com/problems/reverse-linked-list-ii/ Reverse Linked List II - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 위 그림을 예제로 개념을 설명하겠다. 1. 2번부터 4번까지 순서를 바꿔준다. 2. 1 ->4, 2->5로 가리키는 주소를 바꿔준다 어렵지 않게 풀지 알았는데 구현하는데에 1시간 정도 걸려서 문제를 ..

토요일 새벽에 문제를 풀어서 강의를 적용하지 않은 방식과 적용한 방식 2가지를 소개하겠다. 간단하게 요약하자면 괄호가 제대로 닫히는지 확인하는 로직을 짜라는 문제다. 그리고 그것을 VPS라고 부른다. 이 문제를 보고 처음에 든 생각은 '입력 값은 무조건 짝수여야만 하겠구나'였다. 하지만 올바르지 않은 VPS도 짝수개 일 수 있다. 예제를 보며 10분간 멍때리다 보니 답이 생각났다. 왼쪽 괄호(Opener)와 오른쪽 괄호(Closer)의 갯수를 카운트하면 답이 나온다 Closer의 수 가 Opener 의 수보다 많아 질때 VPS가 되지 못 한다. (왼쪽부터 계산했을 때) ( ) ) ( ( ) 이 시점에서 뒤에있는 문자열은 체크할 필요없이 "NO"를 출력하면 된다. 만약에 끝까지 오른쪽 괄호가 왼쪽 괄호보다..

두 정렬 리스트의 병합 https://leetcode.com/problems/merge-two-sorted-lists/ Merge Two Sorted Lists - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com linked list.. 개념은 익숙하나 처음 들어보는 자료구조다. 노드 관련해서는 많이 취약한 편이라 이번 자료구조는 풀기 어려웠다. 어찌저찌 통과는 했지만 답안을 보니 내가 푼것은 편법이였다. 두 배열의 값을 모두 꺼내 sort시킨 후 다시 노드로 만..

이 문제는 Easy라고 나와 있지만 영어로 되어있어서 나는 문제를 이해하는 곳 부터 막혔다. 간단히 말해서 2n개의 숫자 input이 주어지고 n개의 쌍으로 만들어 각 쌍의 최소값이 가장 크게 만들어 모두 더한 것이 output이다. (간단하지 않다.) 처음에는 어떻게 두개의 값을 쌍으로 만들어서 더할까 고민을 많이 했다. 조합 문제인가 했지만 아니였고 아무리 생각해도 두개의 값을 묶는 방법은 떠오르지 않아 답안을 보게 됐다. 문제는 간단했다. 두개의 쌍을 만들 필요없이 정렬을 한 후 순서대로 2개의 값을 묶으면 최솟값을 가장 크게 만들 수 있다. 앞으로는 문제가 막힐때에 수학적으로 접근해보는것도 나쁘지 않은 방법 같다.