Algorithm/개념정리
-
[이진 탐색] 개념정리Algorithm/개념정리 2021. 11. 18. 10:25
순차 탐색 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 '보통 정렬되지 않은 리스트'에서 데이터를 찾아야 할 때 사용함 리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 원소(데이터)를 찾을 수 있다는 장점 시간 복잡도: O(N) → 데이터의 개수가 N개일 때 최대 N번의 비교 연산이 필요함 이진 탐색 : 반으로 쪼개면서 탐색하기 조건: 배열 내부의 데이터가 정렬되어 있어야 함 → 데이터가 무작위일 때는 사용할 수 없지만, 이미 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있음 특징: 탐색 범위를 좁혀가며 데이터 탐색 가능함 이진 탐색은 위치를 나타내는 변수 3개를 사용함(탐색하고자 하는 범위의 시작점, 끝점, 중간점) 찾으려는 데이터와..
-
[정렬] 개념정리 글 모음 - List<T>, 사용자 정의 객체, 배열Algorithm/개념정리 2021. 9. 30. 11:17
List 정렬 2021.08.18 - [Algorithm/유형별 문제 풀기] - [정렬] 문제 이름 : 위에서 아래로 - List 정렬, Collections 2021.09.16 - [Algorithm/유형별 문제 풀기] - [정렬] 문제 이름 : 성적이 낮은 순서로 학생 출력하기 - 객체 정렬, List, Collection 사용자 정의 객체 정렬 2021.07.30 - [Algorithm/HackerRank] - [Greedy] 문제 이름 : University Career Fair - 사용자 정의 클래스 객체 정렬 배열 정렬 2021.09.30 - [Algorithm/유형별 문제 풀기] - [배열 정렬] 문제 이름 : 두 배열의 원소 교체
-
[정렬] 개념정리1 - 삽입 정렬, 선택 정렬, 퀵 정렬, 계수 정렬Algorithm/개념정리 2021. 8. 18. 10:01
개념 → 정렬 : 데이터를 특정한 기준에 따라 오름차순 or 내림차순으로 나열하는 것 → 자료 탐색에 있어서 필수적임! → 정렬 알고리즘으로 데이터를 정렬하면 이진 탐색이 가능해짐(정렬은 이진 탐색의 전처리 과정이기도 함) 추가) 오름차순으로 정렬된 데이터들을 내림차순 정렬할 경우 : 리스트 뒤집는 연산은 O(N)의 복잡도로 간단히 수행 가능함 분류 *정렬 알고리즘 선택 기준 → 모든 경우에 최적인 정렬 알고리즘은 없음 → 각 응용분야에 적합한 정렬 방법을 사용해야 함 ex) 레코드 수의 많고 적음, 레코드 크기의 크고 작음, key의 특성(문자, 정수, 실수 등), 메모리 내부/외부 정렬 *정렬 알고리즘의 평가 기준 → 비교 횟수의 많고 적음, 이동 횟수의 많고 적음 *정렬 알고리즘 분류 [1] 단순하..
-
[DFS/BFS] 개념정리3 - DFS과 BFSAlgorithm/개념정리 2021. 7. 17. 14:29
그래프 탐색이란? → 하나의 정점을 시작으로 다수의 정점을 방문하는 것 DFS(Depth First Search) 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 이 알고리즘은 특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색하는 알고리즘임 사용 자료구조 : 스택 동작 과정 : 탐색 시작 노드를 스택에 삽입하고 방문 처리함 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면, 그 인접 노드를 스택에 넣고 방문처리 함 방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼냄 2번의 과정을 더 이상 수행할 수 없을 때까지 반복함 —> 방문 처리 : 스택에 한 번 삽입되어 처리된 노드가 다시 삽입되지 않..