작은문제를 풀어서 큰 문제를 푸는데 도움이 되자!문제가 원하는 정답을 찾기 위해 가장 먼저 완전탐색 접근 시도탐색하는 경우가 지나치게 많아서 안될 것 같을때이럴때 빠르게 탐색 하는 다이나믹 프로그래밍 시도 풀고 싶은 가짜 문제 정의 Dyi : 1~ i 번 원소에 대해서
묶음 단위로 값을 저장 하는 자료구조배열에 저장된 객체 하나 하나 = 원소각 원소는 인덱스를 부여받음생성할 때 원소 개수를 자유롭게 지정 가능인덱스를 이용해서 원소에 접근 가능Any = 제약이 없는 임의의 자료형Sequence = 시퀀스형 (리스트형,바이트배열형,문자열
어떠한 이벤트에서 자기 자심을 포함하고 다시 자기자신을 사용하는 경우0! = 1n>0 이면 n! = n \* (n-1)!직접재귀는 자신과 똑같은 함수를 호출하는 방식간접재귀는 a() 함수가 b()함수를 호출하고 다시 b()함수가 a()함수를 호출하는 구조최대 공약수 구
빅 오 : 상한 접근빅 오메가 : 하한 접근빅 세타 : 평균빅 오 표기법은 최악의 경우를 고려하기 때문에 프로그램이 실행되는 과정에서 소요되는 최악의 시간 까지 고려할 수 있다.그렇기 때문에 빅 오 표기법을 가장 많이 사용한다.최악의 경우가 발생하지 않길 바라며 시간
hashing 데이터를 저장할 위치(=인덱스)를 간단한 연산으로 구하는 것검색/ 추가/삭제 효율적으로 수행할 수 있음키와 해시값은 일반적으로 다대일 저장할 버킷이 중복되는 현상을 충돌 이라고 함충돌이 발생할 경우 (체인법/오픈주소법) 으로 대처 가능해시값이 같은 데이터
그래프(vertex, edge, node, arc)종류: Undirected, Directed, Weighted Graph표현방식: 인접행렬(Adjacency Matrix), 인접리스트(Adjacency List)사물을 정점(vertex) 또는 노드(node) 와 간선
정점들과 같은 레벨에 있는 노드들 (형제 노드들)을 먼저 순회함A-B-C-D-G-H-I-E-F-JHashMap 과 ArrayList로 표현 가능Queue를 이용 함visited / needVisit 두개의 Queue 를 만듬연결된 노드를 한 Hash Key 값에 Arr
Directed Acyclic Graph (DAG) 간선에 방향성이 있다사이클이 없다그래프 = 정점 + 간선Degree 차수 란 ? 정점에 연결되는 간선의 개수방향성 그래프에서 차수는 inDegree와 outdegree로 구별inDegree 자신에게 들어오는 차수 /
가중치 그래프에서 두개의 노드를 잇는 가장 짧은 경로를 찾는 문제 즉 가중치의 합이 가작 작은 경로 찾기 단일 출발 (single-source) 최단 경로 문제그래프 내 특정 노드에서 출발해서 그래프 내 모든 다른 노드에 도착하는 가장 짧은 경로단일 도착 (singl
전반적인 문제를 풀어낼 수 있는 전략최적의 해에 가까운 값을 구하기 위해 사용됨매 순간 최적의 해를 선택하는 전략각각의 현재 시점에서 최적을 선택하는 알고리즘EX.동전 문제
부분 수열과 부분 문자열의 차이점은 위와 같다.부분 수열 보다 조금 더 쉽고 최장 공통 부분 수열을 구하는데 사용됨우선 LCS라는 2차원 배열을 이용해서 두 문자열을 행과 열에 매칭과정문자열 A와 문자열 B의 한 글자 끼리 비교해본다두 문자가 다르다면 LCSi에 0을
다익스트라 알고리즘은 시작점 고정 → 모든 노드로 가는 최단 경로를 테이블로 관리한다.그렇게 때문에 1차원 테이블이 필요하다 플로이드-워셜 알고리즘은 모든 출발점에서 모든 도착점으로 가는 최단경로를 찾기 때문에 2차원 테이블이 필요하다.자신 → 자신으로 가는 경우에는
💡 다이나믹 프로그래밍 (DP) 에서 유명한 문제 어떤 배낭이 있고 최대 무게가 K 라고 했을 때배낭에 넣을 수 있는 N개의 물건이 각자 다른가치 V를 가지고 있고 물건마다 다른 무게 W가 있을 때,최대한 가치가 있는 물건들을 담을 수 있는 조합을 찾는 문제만약 n
최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법내림차순 -- 최대힙 오름차순 -- 최소힙 n개의 노드에 대한 완전이진트리를 구성! 부모 -> 왼쪽자식 -> 오른쪽 자식 순으로 구성됨 최대힙을 구성한다. 부모노드가 자식노드보다 큰 트리 아래 부터 루트 까지 순차