Computer Science
-
[자료구조 Java] 비선형 자료구조 ① 그래프Computer Science/Data Structure 2022. 10. 5. 17:03
비선형 자료구조란? : 일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조를 말하며 일반적으로 트리나 그래프를 의미 1. 그래프 : 정점과 간선으로 이루어진 자료 구조 - 어떠한 곳에서 어떠한 곳으로 무언가를 통해 간다고 할 때, '어떠한 곳'은 정점(Vertex)이고 '무언가'는 간선(Edge)가 됨 1-1. 관련 용어 - 방향 그래프, Directed Graph(Digraph): 간선에 방향성이 포함되어 있는 그래프 - 무방향 그래프, Undirected Graph: 간선에 방향성이 없는 그래프 - 인접 정점(adjacent vertext): 간선에 의해 직접 연결된 정점 - 정점의 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수(연결된 간선의 수) ▶︎ 무방향 그래프에 존재..
-
[자료구조 Java] 선형 자료 구조(연결 리스트, 배열, 스택, 큐)Computer Science/Data Structure 2022. 10. 5. 15:53
선형자료구조란? : 요소가 일렬로 나열되어 있는 자료 구조 1. 연결 리스트 : 데이터를 감싼 노드를 포인터로 연결해 공간적 효율성을 극대화 시킨 자료구조로, prev 포인터와 next 포인터로 앞과 뒤의 자료들을 연결시킨 것 1-1. 시간 복잡도 - 삽입/삭제 : O(1) - 탐색 : O(n) 1-2. 종류 1) 싱글 연결 리스트: next 포인터만 가짐 2) 이중 연결 리스트: prev, next 포인터를 둘 다 가짐 3) 원형 이중 연결 리스트: 마지막 노드의 next 포인터가 헤드 노드(맨 앞의 자료)를 가리킴 1-3. 주요 명령어 import java.util.LinkedList; import java.util.List; public class Example { public static void..
-
[자료구조 Java] 공간복잡도, 자료구조의 시간 복잡도Computer Science/Data Structure 2022. 10. 2. 13:57
[ 참고용: 시간복잡도 ] 출처: https://erinh.tistory.com/entry/자료구조-Java-시간복잡도-점근표기법-빅오표기법?category=1046468 공간복잡도란? : 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양 - 정적 변수로 선언된 것 외에, 동적인 재귀적 함수로 인해 공간을 계속해서 필요로 할 경우도 포함 - 시간복잡도와 마찬가지로 빅오표기법을 사용 - int 자료형 기준으로 배열 크기에 따른 메모리 사용량을 일반적으로 아래와 같음 int a[1000] : 4KB int a[1000000] : 4MB int a[2000][2000] : 16MB 자료구조에서의 시간 복잡도 1. 최악 시간 복잡도 자료구조 접근 탐색 삽입 삭제 배열 O(1) O(n) O(n) O(n) 스택..
-
[자료구조 Java] 시간복잡도 (점근표기법, 빅오표기법)Computer Science/Data Structure 2022. 10. 1. 14:34
시간복잡도란? : 문제를 해결하는 데 걸리는 시간과 입력의 함수 관계 ▶︎ 어떠한 알고리즘의 로직이 '얼마나 오랜 시간'이 걸리는지 나타날 때 사용되며 보통 Big-O 표기법으로 표현 📍점근 표기법 1) Big-O(빅오) : 상한 점근, 시간복잡도가 최악인 경우 2) Big-Ω(빅오메가) : 하한 점근, 시간복잡도가 최선인 경우 3) Big-Θ(빅세타): 상한, 하한의 평균(중간값) ▶︎ 빅오표기법의 경우, 프로그램 실행 과정에서 소요되는 최악의 시간까지 고려하기 때문에 효율적인 코드의 판단 척도로 사용 가능 // 시간복잡도 10n^2+n을 가지는 경우의 코드 for (int i = 0; i < 10; i++) { for (int j = 0; j < n; j++) { for ( int k = 0; k <..
-
[알고리즘] 카운팅 정렬 (Counting sort) - 자바 JavaComputer Science/Algorithm 2022. 8. 21. 21:38
[ 개념 ] 항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하여, 선형 시간에 정렬하는 효율적 알고리즘 - 정수나 정수로 표현할 수 있는 자료만 적용 가능 (각 항목의 발생 횟수를 기록하기 위해 정수 항목으로 인덱스가 되는 카운트들의 배열을 사용하기 때문) - 카운트를 위한 충분한 공간을 할당하려면 집합 내의 가장 큰 정수를 알아야 함 [ 과정 설명 (오름차순) ] 1) Data 배열에서의 최댓값을 최대 인덱스로 갖는 counts 배열 생성 후, data에 각 인덱스에 해당하는 숫자가 몇 번 등장하는지 누적 카운팅 2) 뒤에서 부터 탐색하며, data 배열의 값에 해당하는 count 배열 인덱스로 가서 값을 -1 해준 뒤, result 배열에 해당 값의 인덱스로 가서 dat..
-
[알고리즘] 이진 검색 (Binary search) - 자바 JavaComputer Science/Algorithm 2022. 8. 21. 20:40
📍 검색이란? - 저장되어 있는 자료 중에서 원하는 항목을 찾는 작업 - 목적하는 탐색 키(자료를 구별하여 인식할 수 있는 키)를 가진 항목을 찾는 것 [ 이진 검색이란? ] : 자료의 가운데에 있는 항목의 키 값과 비교하여 다음 검색의 위치를 결정하여 검색을 진행하는 방법 - 목적 키를 찾을 때까지 이진 검색을 순환적으로 반복 수행함으로써, 검색 범위를 반으로 감소시켜 보다 빠르게 검색 가능 - 이진 검색을 위해서는 자료가 반드시 정렬된 상태여야 함 [ 검색 과정 ] - 자료의 중앙에 있는 원소를 고르고 찾고자 하는 목표 값을 비교 - 목표 값이 중앙 원소의 값보다 작으면 자료의 왼쪽 반에 대해 새로 검색을 수행, 반대는 오른쪽 반에 대해 검색 수행 - 찾고자 하는 값을 찾을 때까지 반복 [ 코드 예시..
-
[알고리즘] 순차 검색 (Sequential search) - 자바 JavaComputer Science/Algorithm 2022. 8. 21. 20:05
📍 검색이란? - 저장되어 있는 자료 중에서 원하는 항목을 찾는 작업 - 목적하는 탐색 키(자료를 구별하여 인식할 수 있는 키)를 가진 항목을 찾는 것 [ 순차 검색이란? ] : 원하는 키 값을 갖고 있는 요소를 만날 때까지 맨 앞에서부터 순서대로 요소를 검색하는 알고리즘 (선형 검색) - 가장 간단하고 직관적이며, 배열/연결리스트 등 순차구조로 구현된 자료구조에서 검색시 유용 - 알고리즘이 단순하여 구현은 쉬우나 검색 대상수가 늘어날수록 시간이 급격히 증가하여 비효율적 [ 검색 과정 ] - 첫 번째 원소부터 순서대로 검색 대상과 키 값이 같은 원소가 있는지 비교 - 키 값이 동일한 원소를 찾으면 해당 원소의 인덱스 반환 - 자료구조의 마지막까지 대상을 찾지 못하면 검색 실패 - 정렬되어 있는 배열의 경..
-
[알고리즘] 퀵 정렬 (Quick sort) - 자바 JavaComputer Science/Algorithm 2022. 8. 14. 12:54
[ 개념 ] - 분할 정복(divide and conquer) 방법을 통해 주어진 배열 정렬 - 불안정 정렬, 비교 정렬 📍 분할 정복 (divide and conquer) : 문제를 작은 2개의 문제로 분리하고 각각을 해결한 후, 결과를 모아 원래의 문제를 해결하는 방법 [ 과정 설명 (오름차순) ] - 배열 가운데 하나의 원소를 고르며, 그 원소를 pivot 이라고 함(피벗을 기준으로 비균등하게 2개의 부분 배열로 분할) - 피벗을 기준으로 피벗 앞에는 피벗보다 작은 수가, 오른쪽에는 피벗보다 큰 수가 옮겨짐 - 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬(피벗을 다시 선택해 정렬을 반복) - 부분 리스트들이 더 이상 분할이 불가능할 때까지 반복 [초기 배열] 6 9 20 3 5 10 7 ..