![]()
Think 나 왜 이렇게 재귀만 나오면 머리가 멈출까?...... 책 풀이만으로는 이해가 안되어서 영상 찾아봤다 https://www.youtube.com/watch?v=0snEunUacZY 코드에서 len(path)와 len(digits)의 값이 같을 때 깊이 탐색을 멈추고 백트래킹을 한다는 말이 이해가 안 갔는데 이번에도~ 영상 속 그림을 보고 한방에 이해 됐다 digit이 두개니까 지금 탐색중인 path의 길이가 두개이면 끝까지 갔다는 얘기 -> 백트래킹! 지금까지 따라온 경로 = 문자열 하나 인 path를 결과 배열에 저장하고 return 으로 한꺼풀 빠져나온다. Solution class Solution(object): def letterCombinations(self, digits): """ ..
https://leetcode.com/problems/jewels-and-stones/ Jewels and Stones - 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 Think 오늘 푼 것 중에 제일 할 만 했던 것 같다^^..! 문제도 귀여웠음 보석찾기 해시테이블에 존재하는 키 값을 찾을 때 딕셔너리 자료형의 무슨 메서드가 있는지부터 고민했는데 단순히 in 연산자로 해결..~ 파이썬에 더 익숙해지는 과정이 필요할 듯 Solution class Solutio..
https://leetcode.com/problems/design-circular-queue/ Design Circular Queue - 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 Think 왜 시작을 못하겠지? 경험이 부족함을 느꼈다 앞부분을 참고해서 적고나니 뒷부분은 얼추 구현해볼 수 있었다 공부하자!! 그리고 파이썬은 모든 내장 변수에 self를 붙여야 하는 점이 너무 불편하고 가독성도 안 좋은 것 같다 하지만 어쩌겠어 내가 고른 길인걸~~ 사람은 적응..
![]()
https://leetcode.com/problems/implement-stack-using-queues/ Implement Stack using Queues - 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 Think 뭘로 뭘 구현해라..라는 문제 형식 자체가 낯설어서 읽어보는 것만으로 공부였던 문제 뭘 써서 구현해야 할 지도 몰랐다 ㅋㅋㅋㅋ...~ 게다가 deque도 모르고~ 그리고 리트코드에서 적어둔 코멘트들 읽으면서 풀 것.. 문제 좀 읽어라 Soluti..
https://leetcode.com/problems/remove-duplicate-letters/ Remove Duplicate Letters - 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 Think 재귀는 많이 연습해야 겠다.. 함수 만들어서 재귀로 푸는 거에 쫄지 말기. 스택으로 푸는 법도 다시 풀어보기. Solution 1. 재귀 class Solution(object): def removeDuplicateLetters(self, s): """ :ty..
![]()
Think 역순 연결 리스트 2번째 문제. 전에 봤던 206. 역순 연결 리스트도 완벽히 이해하지 못한 상황이라 206번을 설명해주는 영상을 찾아 보고 왔다. 이해가 훨씬 잘 됐다! 반복과 재귀 두 방법 모두.. 그림이 역시 짱이다 https://www.youtube.com/watch?v=G0_I-ZF0S38 206번 풀이했던 내용을 바탕으로 이번 문제는 스스로 풀어보자 반복이 재귀방법보다 공간복잡도도 더 낮고 시간도 짧다. 반복으로 풀어보자 . . . 절반밖에 못풀었다^^! 영상을 찾아봤다! 같은 채널에서 올린 영상이 있었고 이해가 역시 잘 됨... https://www.youtube.com/watch?v=RF_M9tX4Eag 이 문제에서는 주어진 연결리스트의 맨 앞 head노드를 가리키는 root노드..
![]()
Think 혼자 풀기 실패 풀이 설명을 읽는데 이해가 안됨 리트 코드 solution탭을 살펴봤는데 아래 그림 보고 설명 바로 이해함!! Solution 투 포인터 사용 class Solution(object): def trap(self, height): """ :type height: List[int] :rtype: int """ #빈 인풋값이 들어왔을 경우를 처리 if not height : print(0) left = 0 right = len(height) - 1 #포인터 0부터 시작 left_max, right_max = height[left], height[right] volume = 0 while left < right : #서로 만나기 전까지 실행 #왼, 오 최댓값을 현재값과 비교해 갱신 l..
시간복잡도 정리 Dynamic 최단경로 : n^3 0-1배낭 : min(2^n, nW) 최적이진탐색트리OBST : n^3 Backtracking 그래프 색칠 노드의 수 : m^n Branch and Bound 0-1배낭 : 2^n 방법 핵심 정리 Dynamic: 작은 부분들부터 계산해서 Bottom-up으로 올라가며 작은 부분들의 결과를 이용해 다음 단계 결과를 계한하는 것. 의존적. 한번 계산한 값은 바뀌지 않음 principle of optimality 최적성원칙을 만족해야 함 - 큰 문제의 최적해는 최적의 작은 문제 해들로 구성되어야 함 최적화 문제 Backtracking : state space tree를 사용해 bound를 만족하는 노드에 대해 promising유망함을 점검하고 유망한 노드만 그..
Chap13 그래프의 응용 1. 스패닝 트리 (신장트리) 원래 그래프의 노드는 모두 포함. 간선은 최소로, 연결그래프를 유지하며 노드수-1개로 줄인 트리. 사이클 없음. 종류 깊이 우선 스패닝 트리 : dfs로 방문한 간선들로 만듦 너비 우선 스패닝 트리 : bfs로 방문한 간선들로 만듦 2. 최소 스패닝 트리 간선의 가중치(비용) 합을 최소로 하는 스패닝 트리 구하는 방법 종류 Kruskal 알고리즘(간선 수 e) 모든 엣지들 중 비용이 최소인 엣지들부터 추가해가며 사이클이 만들어지지 않도록 추가여부를 선택함 엣지를 크기순으로 정렬해두고 써도 되지만 min heap을 만들어 사용하면 더 효율적. 이 경우 heap구성시간 O(e) + 최소 엣지 탐색 시간 O(loge) = O(e+loge)소요. Prim..
Chap12 그래프, 그래프 탐색 1. 그래프의 개념 그래프 G1의 노드 V(G1) = {0,1,2,3,4} 그래프 G1의 간선 E(G1) = {(0,1) ..} ()는 무방향. {..} 는 방향이 있는 간선. G1은 방향그래프. 분리된 그래프 : 모든 루트가 연결되어있지 않고 분리되어있지만 하나의 그래프임. 연결된 그래프 용어 정리 완전 그래프 : 간선 수가 최대. 모든 각 노드에 모든 노드로의 간선이 존재. 완전그래프인 방향그래프에 n개의 노드가 있으면 간선의 수는 n(n-1), 무방향이면 n(n-1)/2 인접 : 두 노드를 직접 연결하는 간선이 존재하면 두 노드는 인접하다고 함 부속 : 두 노드를 직접 연결하는 간선이 존재하면 그 간선에 양쪽 노드가 부속된다고 함. 부분 그래프 : 그래프의 간선들과..
Chap11 검색(탐색) 선형 검색 앞에서부터 하나씩 찾아봄 이진 검색 절반씩 잘라서 중간값을 탐색해나가는 방법 해시 탐색 해시테이블(크기 = 버킷*슬롯) 버킷 : 해시될 키 값의 범위. 해시함수에 들어갔다 나온 값이 같으면(동의어) 같은 버킷에 저장됨 슬롯 : 같은 버킷에 저장될 수 있는 키 값 개수 충돌 : 동의어가 나타나서 다른 값이 같은 버킷에 저장되는 경우 오버플로우 : 충돌로 저장하려는 값의 슬롯이 이미 꽉 찬 경우 오버플로우가 일어남 식별자밀도=적재밀도 : 같은 말. 테이블 크기에 비해 저장된 데이터 수 비율을 의미.(키값=식별자=데이터) 해시 함수 : 계산이 편해야 하고 충돌을 최소화할 수록 좋음. mid-square : 식별자를 제곱해서 가운데 부분 값을 사용함 division : 나머지..
Chap10 정렬 선택 정렬 첫번째 자리에 올 값, 두번째 자리에 올 값.. 순서로 탐색해서 발견 시 해당 위치의 값과 자리 교환 비교 n(n-1)/2 회 교환 n-1 회 => O(n^2) 버블 정렬 맨 첫 값부터 바로 옆 값과 비교해 교환할지 말지 결정. 끝까지 가면 마지막 값부터 정렬 완료됨. 반복 비교 n(n-1)/2 회 교환 n(n-1)/2 회 (최악 : 비교할 때마다 교환) => O(n^2) 개선 - 중간 단계에서 정렬 완료된 경우. 현 단계에서 데이터 이동이 일어나지 않으면 다음 단계들을 수행하지 않고 종료 삽입 정렬 앞에서부터 현재 값을 앞쪽이 이미 정렬되어있는 값들 사이의 알맞은 위치에 삽입함(삽입하는 과정은 현재 위치에서 바로 앞 값과 비교해서 교환 결정하며 앞쪽으로 보냄. 계속 비교 교..
Chap8 트리 트리 삽입삭제가 편함 이진검색의 장점을 이용해 빠른 검색 가능 루트의 레벨 = 1 차수 : 노드의 부속트리 개수. 리프노드는 차수가 0임 부모, 자식, 조상, 자손 관계 등.. 트리 저장(구현)방법 n-링크표현법 모든 노드에 무조건 n개의 링크를 두고 각 자식노드의 링크를 저장함(남는 공간 있음) 왼쪽자식노드-오늘쪽형제노드 표현법 모든 노드에 링크 두개씩. - 효율적 왼쪽링크에는 첫번째 자식노드, 오른쪽 링크에는 자신의 형제노드를 연결함 차수가 n인 어떤 트리라도 이 방법을 이용하면 이진트리형태로 저장해 낭비되는 공간을 줄일 수 있음(간선을 다시 그리고 시계방향으로 45도 정도 돌림) 이진트리 자식노드의 수가 2개 이하(0~2개)인 트리 자식노드에 순서가 있음 - 똑같이 자식노드가 1개라..
3. Branch&Bound 분기한정법 State Space Tree활용 최적해 구하기에 적용 가능. Backtracking보다는 최적해를 구하기 위해 모든 해의 한계값(직접x)을 계산해 고려함. 각 노드에 대한 한계값bound을 계산함. 해당 노드는 bound보다 큰 값을 가질 확률이 없음. bound값이 지금까지의 최적해보다 좋은가?로 최적해 값을 업데이트하고 노드의 promising여부를 판단함. promising하지 않은 노드의 자식노드는 탐색하지 않음. 0-1 Knapsack 문제 state space tree : 왼쪽으로 가면 현재 아이템을 담지 않는 걸로, 오른쪽으로 가면 현재 아이템을 담는 걸로 함. 루트에서 리프노드까지의 모든 경로가 해답후보임 최적해를 찾는 문제이므로 전체를 다 탐색하기..
2. BackTracking 백트래킹(되추적) 막히면 왔던 길을 되돌아가서 다시 찾는다 최적화 문제와 결정 문제(yes/no) 해결 우리가 해줄 것은 해가 만족해야 하는 조건bound정하기! State Space Tree 활용으로 promising여부 확인(bound) n-Queens문제 n개의 Queen을 한 체스판에 가로세로대각선 방향으로 위치가 겹치지 않도록 배치하는 문제. State Space Tree 상태공간트리 : 문제해결의 중간 사태를 각 노드로 나타낸 트리 루트에서 리프노드까지의 모든 경로가 해답의 후보이며 그 중 답이 되는 경로를 Answer States라 함 답이 나올 가능성이 전혀 없는 노드를 유망하지 않은non-promising 노드, 그렇지 않은 노드를 유망한promising 노드..
