원조맛집

동적계획법이라는 이름은 전혀 연관성이 없으므로 생각하지 않는게 좋다 n = 10일때를 구하기 위해 n =9,8,7,6 일때를 먼저 구해서 더 큰 경우를 구하는 것 둘다 DP 테이블에 작은 문제의 답을 담아두는것은 동일함 메모이제이션을 이해할 수 있느 간단한 예시 DP에서 자주 나오는 수열 개념 (구현하는데 반복문, 재귀 둘 다 사용가능하다) 둘 중 재귀를 생각해보자 f(6)을 구하기 위해 하나하나 따져보면 f(4), f(3)과 같이 반복적으로 값이 사용되는 것을 볼 수 있다 이런 경우 작은 부분의 값을 미리 구해서 어딘가에 저장해두면 다음부터는 쓸모없는 연산을 줄일 수 있다 이렇게 답을 저장해두는 것을 캐싱이라고 하며 성능에서 엄청난 차이를 보인다 차이점 bottom-up(반복문) 방식은 다음 단계를 위..

이진탐색 : 절반씩 탐색범위를 줄여가는 것 절반씩 떨쳐내려면 정렬이 되어있어야 한다 선형탐색(완전탐색)이 O(N)인데 그럼 이진탐색보다 선형탐색이 더 유리한거 아니냐? 1번만 찾을 경우에는 선형탐색이 유리하고 (N x N => N^2) 여러번 찾을 경우에는 이진탐색이 유리하다 (NlogN[정렬] + NlogN[이진탐색xN번 반복] = NlogN) 파이썬에서의 이진탐색 라이브러리 left : 3보다 같거나 큰 숫자를 발견하면 해당 숫자 인덱스를 반환 ( >= 3이상) right : 3보다 큰 숫자를 발견하면 해당 숫자 인덱스를 반환 ( > 3초과) 파라메트릭 서치는 이진탐색과 똑같은데 다만 경계선을 찾는다는 느낌이라고 보면 됨 ppt 출처 및 강의 https://www.udemy.com/course/com..

재귀함수는 내부적으로 스택을 쓰므로 사실 스택 = 재귀이다 DFS는 완전탐색이라 모든 경우를 도는데 그 순서가 중요한 것이다 0 -> 1 -> 2 -> 3 -> 2 -> 4 -> 2 -> 1 -> 5 -> 6 -> 5 -> 1 -> 0 -> 7 ... 이 순서대로 감(깊이 우선 탐색) DFS를 코드로 나타내면 위와 같다 완전탐색이다 DFS와 탐색 순서가 다르다 0 -> 1 0 -> 2 1 -> 3 1 -> 4 2 -> 5 2 -> 6 ... 순서대로 탐색 큐를 사용한 BFS의 동작원리를 그림으로 나타내면 아래와 같다 BFS를 코드로 구현하면 다음과 같다 DFS & BFS 공통점 완전탐색, 무조건 답을 찾을 수 있지만 느리다 차이점 최단거리를 구하는 문제에서 BFS(너비우선탐색)은 목표 지점을 찾는 즉시 ..

그래프의 종류중에서 순환성 없는 무방향 그래프를 트리라고 함 (수학적, 이론상 트리) 트리의 개념 위 트리는 실제 전산학, 자료구조에서 많이 쓰이는 트리임(이론적 트리와 다름) 스택,큐 등등은 구현해주는 라이브러리가 대부분의 언어에서 있지만 그래프는 따로 없어 직접 구현해줘야함 1번째 방법 인접행렬 방향성이 있을 경우 행은 시작 index, 열은 도착 index 두 노드를 잇는 간선이 있을 경우에는 1 없으면 0 방향성이 없을 경우 무방향은 양방향과 같은 의미임 즉 간선이 연결되어 있으면 양쪽으로 출발과 도착이 가능하다는 의미 2번째 방법 인접리스트(연결리스트) 방향성이 있을 경우 행렬과의 차이 행렬은 연결이 없으면 0으로 자리를 차지했지만 리스트는 연결이 있는 부분만 공간을 차지함 엄밀히 따지면 연결리..

SNS에서 서로 연결되어 있는 상황이 그래프의 개념임 그래프는 Vertex(node, 한국말로 정점)와 이들을 연결하는 edge(한국말로 간선)으로 이루어져있음 방향 그래프는 방향대로만 이동 가능 전체 그래프 중에 한군데라도 순환 사이클이 있으면 순환 그래프라고 칭함 방향성이면서 비순환인 그래프를 DAG라고 함 이 때는 그래프가 3개가 아니라 1개임,그리고 이를 연결 요소라 부름 (연결요소가 3개인 그림)

모든 문제에 적용할 수 없다 초반에는 최악의 선택지로 보이지만 결국에는 더 나은 결과로 이어지는 선택지인 경우가 있는 문제에는 그리디를 적용할 수 없다 이 문제는 그리디 문제로 풀 수 있지만 이 문제는 그리디로 풀 수 없다 두 문제의 차이점은 숫자의 배수가 그 다음으로 큰 숫자가 될 수 있는지의 유무이다 10,50,100,500은 모두 작은 수의 배수로 구성이 가능하니 500을 가장 많이주고 그다음 100을 주는 방식이 가능하지만 400,500의 경우에는 배수가 안되고 그 말은 1200원처럼 400으로만 가능한 경우가 발생한다는 것이다 즉 그리디의 문제는 다음과 같다

완전탐색의 장단점 시간 복잡도를 꼭 체크해봐야함 대표적인 완전탐색 기법 브루트 포스(무차별 대입) 순열 permutations(배열, 몇개 뽑을지) 조합 순열과 조합의 차이 순열은 모든 경우의 수, 조합은 중복되는 경우(0 1 ==> 1 0)는 제외 자료출처, 강의 https://kmooc.udemy.com/course/comgong_codingtest/

import heapq numbers = [] #min-heap 파이썬은 min-heap이 기본사항이라 값 넣으면 자동으로 루트(최상단)에 최소값이 옴 heapq.heappush(numbers,숫자) // 자동으로 오름차순(정확히는 이진트리 형식)으로 정렬 됨 print(heapq.heappop(numbers)) // 루트 노드에 있는 가장 작은 값 제거 후 반환 # 출력예시: heaqp[1,2,3,4....] # max-heap 숫자를 넣을때 - 부호를 붙여주고 꺼내쓸때 -부호를 다시 붙여주면 max-heap 가능 counts = [] heapq.heappush(counts, -숫자) print(-heap.heappop(counts)) # 출력예시: heapq[6,5,4,3,...] 파이썬에서 우선순위..

맵 c++(Map) python(Dictionary) map 형식은 키와 밸류 쌍으로 이루어져있으며 대표적으로 JSON의 형식이다 (key : value) key는 중복될 수 없는 고유한 값이여야하지만 value는 중복이 가능하다 c++에서는 logN의 시간 복잡도를 가지고(정확히는 밑을 2로 가지는 log2 N ) python에서는 1의 시간 복잡도를 가진다(파이썬에서 유리하다) 집합 set 집합은 중복이 되지 않고(중복된 값을 넣을 수는 있지만 1개만 남는다) set 함수로 사용할 수 있다 c++에서는 logN의 복잡도 python 에서는 1의 복잡도를 가진다 python에서 s.pop()으로 제거시 무작위로 1개의 값이 제거된다, s.remove('원하는값')으로 원하는 값을 제거할 수 있다 집합과..

배열의 경우 탐색을 할 경우: arr[2] 는 arr[0]의 주소 + 2*(해당 타입의 바이트 수)를 의미하므로 1번의 계산으로 원하는 위치를 특정할 수 있다 이는 O(1)이 됨을 뜻한다 추가/삭제를 할 경우: 만약 arr[2] = 4를 넣고 싶다면 기존의 arr[2] ~ arr[6] 까지의 값들을 한칸씩 뒤로 미뤄야 한다 만약 맨 뒤에 넣고 싶다면 옮길 필요가 없으니 1번이면 되지만 맨 앞에 넣고 싶다면 모든 값을 한번씩 옮겨야하니 N이 된다 O(빅오) 에서는 최악의 상황을 가정하므로 이때는 O(N)이 됨을 뜻한다 링크드리스트의 경우 탐색을 할 경우: 링크드리스트에서는 99의 값의 위치를 찾으려고 해도 한번에 찾을 수 없다 99를 찾으려면 0의 위치를 찾아야 하고, 0을 찾으려면 5의 위치를 찾아야 한..