삽입/삭제: O(N)탐색: O(1)→ 삽입/삭제: 삽입이나 삭제시 나머지 배열 요소의 위치를 바꾸어주어야 한다.→ 탐색: 임의 접근방식으로 한번에 원하는 위치에 접근할 수 있다.※ 시간 복잡도는 최악의 경우를 기준으로 계산한다.※ 임의 접근 방식은 배열의 시작 주소에서
1. 완전탐색 특징 장점: 반드시 답을 찾아낸다. 단점: 오래 걸린다. ※ trade-off 관계: 자원 ↔ 시간 2. 브루트 포스 Brute-force (무차별 대입) ex) 비밀번호 숫자 4자리: 모든 경우의 수를 다 넣는다. 가장 확실한 방법으로 많이 쓰임 암호
매 순간마다 최선의 경우만을 골라간다다른 경우는 고려 X, 나중은 생각 X (이것때문에 답이 아닐 수도 있다.)모든 경우를 다 보지 않으니 완전탐색보다 빠르다.어떤 경우가 최선인지 찾는 게 포인트규칙성을 찾아야하는 상황도 있다.greedy로 문제인지 판별하기 정말 어렵
지도, 내비게이션SNS, 메신져 → 계정 간 관계도VCS (Version Control System)Vertex(=node): 정점, Edge: 간선무방향 그래프(=양방향 그래프): 방향이 없다, 방향 그래프: 방향이 있다순환그래프(Cyclic), 비순환그래프(Acyc
완전탐색인 선형탐색보다 효율적이다.이미 정렬이 되어있다는 가정하에 탐색이 필요없는 절반범위를 제외 및 탐색을 하는 것을 반복한다.→ 탐색 전에 반드시 정렬되어 있어야 함!→ 살펴보는 범위를 절반씩 줄여가며 탐색※ 시간복잡도→ 정렬 O(NlogN) + 이진탐색 O(log
하나도 다이나믹하지 않다. 그냥 멋있어 보인다고 붙인 이름이다. 1\. 문제를 쪼개서 작은 문제의 답을 구하고, 그걸로 더 큰 문제의 답을 하는 것을 반복 2\. 분할정복과 비슷한 느낌Top-down : 재귀, 메모이제이션 MemoizationBottom-up