알고리즘

주어진 함수에서 엄밀한 점근적 상한을 나타내는 점근적 표기법숫자는 다 빼기 가장 증가율이 높은 수식만 남기기 f(n) = 4텍스트f(n) = 2n+3f(n) = 3n2 + n + 5f(n) = 4n + log(n) + 3시간복잡도 : O(1)공간복잡도 : O(1)시간

배열은 연속된 메모리 영역에 저장된 데이터로, 조회가 O(1), 추가 및 삭제가 O(n) 복잡도를 가지고 있다. 즉 조회는 빠르고 추가 및 삭제는 느리다. 자바에서 배열은 만들 때 크기를 정해야 하며, 추가 및 삭제 기능은 없다. 다른 자료구조를 구현하는데 사용하는 가

어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 것 두 인접한 데이터를 비교해서 앞에 있는 데이터가 뒤어 있는 데이터보다 크면 자리를 바꾸는 정렬 알고리즘 시간복잡도 : O(n2) 다음과 같은 순서를 반복하면서 정렬하는 알고리즘 1\. 주어진 데이터 중 최

함수 안에서 동일한 함수를 호출하는 형태여러 알고리즘 작성시 사용된다. 시간복잡도 : O(N) (n - 1번의 반복문을 호출하는 것 이기 때문에) 함수는 내부적으로 스택처럼 관리된다. 숫자가 들어있는 배열이 주어졌을 때 배열의 합을 리턴하는 코드를 작성하시오.

입력 크기가 작은 부분 문제들을 해결한 후 해당 부분 문제의 값을 활용하여 보다 큰 크기의 부분 문제를 해결하고 최종적으로는 전체 문제를 해결하는 알고리즘 상향식 접근법으로 가장 최하위 답을 구한 후 이를 저장하고 해당 결과값을 이용해서 상위 문제를 풀어가는 방식Mem

탐색은 여러 데이터 중에서 원하는 데이터를 찾아내는 것을 의미한다.데이터가 담겨있는 리스트를 앞에서부터 하나씩 비교해서 원하는 데이터를 찾는 방법이다.시간복잡도 : O(N)탐색할 자료를 둘로 나누어 해당 데이터가 있을만한 곳을 탐색하는 방법 시간복잡도 : O(logN)

대표적인 그래프 탐색 알고리즘 정점들과 같은 레벨에 이는 노드들을 먼저 탐색하는 방식 시간 복잡도 노드 수 : V간선 수 : E = O(V + E)

정점의 자식들을 먼저 탐색하는 방식 한 노드의 자식을 타고 끝까지 순회한 후 다시 돌아와서 다른 형제들의 자식을 타고 내려가며 순회한다.needVisit 스택과, visited 큐를 사용한다.시간복잡도 : 노드 수 : V간선 수 : E = O(V+E)

최적의 해에 가까운 값을 구하기 위해 사용된다.여러 경우 중 하나를 결정해야할 때마다, 매순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행해서 최종적인 값을 구하는 방식이다. 지불해야 하는 값이 4720원 일 때 1원,50원,100원,500원 동전으로 동전의 수가

두 노드를 잇는 가장 짧은 경로를 찾는 문제다.가중치 그래프 (Weighted Graph)에서 간선(Edge)의 가중치 합이 최소가 되도록 하는 경로를 찾는 것이 목적이다. 그래프 내의 특정 노드 u에서 출발하여 그래프 내의 모든 다른 노드에 도착하는 짧은 경로를 찾는

백 트래킹 또는 퇴각 검색이라고 부른다. 제약 조건 만족 문제에서 해를 찾기 위한 전략이다. 해를 찾기 위해 후보군에 제약 조건을 저진적으로 체크하다가, 해당 후보군이 제약 조건을 만족할 수 없다고 판단되는 즉시 backtrack(다시는 이 후보군을 체크하지 않을 것을

문제를 해결하기 위해 확인해야 하는 모든 경우를 전부 탐색하는 방법이다.그 중에서도 백 트래킹을 통해야 하는 상황을 해결할 때 유용하다. 모든 코테문제에서 기본적으로 접근해 봐야 한다. 장점 : 부분점수를 얻기좋다.단점 : 전부 탐색하기에 시간 복잡도가 일반적으로 높다