happindex

💡 대부분의 내용을 Do it! 알고리즘 코딩테스트 with JAVA 강의를 참고하여 정리하였습니다. DFS (Depth - First Search) DFS (깊이 우선 탐색)은 그래프 완전 탐색 기법 중 하나이다. 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른쪽 분기로 이동하여 다시 탐색한다. (최대 깊이까지 탐색한 후 다음으로 넘어간다!) 특징 재귀함수로 구현한다. 이때, stack overflow에 유의해야 한다. 스택 자료구조를 이용한다. 시간 복잡도 O(V + E) O(노드 수 + 엣지 수) 핵심 이론 노드 방문 여부를 체크할 배열이 필요하다. 한 번 방문한 노드는 다시 방문하면 안 되기 때문이다. 중복 방문 불가!! 그래프(데이터를 담는 자료구..

💡 대부분의 내용을 Do it! 알고리즘 코딩테스트 with JAVA 강의를 참고하여 정리하였습니다. 합 배열 구간 합 알고리즘을 활용하기 위해서는 먼저 합 배열을 구해야 한다. 배열 A가 있을 때, 배열 S를 합 배열이라고 하면, 다음과 같이 나타낼 수 있다. S[i] = A[0] + A[1] + A[2] ... + A[i-1] + A[i] 합 배열 공식은 다음과 같다. S[i] = S[i-1] + A[i] 구간 합 구간 합은 합 배열을 이용하여 시간복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘이다. 배열에서 특정 범위의 값들의 합을 구하고 싶을 때 합 배열을 이용하면 빠르게 구할 수 있다. i에서 j까지의 구간 합을 구할때, 공식은 다음과 같다. S[ j ] - S[ i-1 ]

💡 대부분의 내용을 Do it! 알고리즘 코딩테스트 with JAVA 강의를 참고하여 정리하였습니다. 배열 배열은 연속 공간에 값이 채워져 있는 형태의 자료구조이다. 배열의 특징 인덱스를 사용하여 값에 바로 접근이 가능하다. 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어렵다. (연속 공간에 값이 채워져 있는 형태이기 때문) 삽입 및 삭제를 원하는 인덱스 주변에 있는 값을 이동시켜야 한다. 배열의 크기는 선언 할 때 지정해야 하고, 한번 선언하면 크기를 늘리거나 줄일 수 없다. 리스트 리스트는 값과 포인터를 묶은 노드를 포인터로 연결한 자료구조이다. 리스트의 특징 인덱스가 없다. 따라서 값에 접근하려면 Head 포인터부터 순서대로 접근해야 한다. → 값에 접근하는 속도가 느리다. 포인터로 연..

💡 대부분의 내용을 Do it! 알고리즘 코딩테스트 with JAVA 강의를 참고하여 정리하였습니다. 시간 복잡도 알고리즘에서 시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 의미한다. 일반적으로 1초에 1억번의 연산을 할 수 있다. 문제에서 시간 제한이 2초라면, 2억 번 이하의 연산 횟수로 문제를 해결해야 한다! 연산 횟수는 1초에 1억번 연산하는 것을 기준으로 생각한다. 시간제한이 2초라면, 2억번 이하의 연선 횟수로 문제를 해결해야 한다! 시간 복잡도 활용 시간 복잡도를 계산하려먼 데이터의 개수와 제한 시간을 보면 된다. 🧐 [문제 1] N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. - 시간 제한 : 2초 - 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,..