CS지식/자료구조
-
Java 자료 구조 - 배열CS지식/자료구조 2023. 12. 20. 12:49
배열 자료구조는 크게 메모리 공간 기반의 연속(Contiguous)방식과 포인터 기반의 연결(Link)방식으로 나누니다. 배열은 이 중 연속 방식의 가장 기본이 되는 자료형이다. 배열의 값은 집합으로 구성되며, 하나 이상의 인덱스 또는 키로 식별한다. 추상 자료형(Abstrac Data Type, 이하 ADT)의 실제 구현은 대 부분 배열 또는 연결 리스트를 기반으로 한다. 스택은 연결리스트로 구현하고 큐는 배열로 구현하는 식이다. 물론 반대의 경우도 충분히 가능하다. C언어를 기준으로(C는 자료구조의 가장 기본적인 형태를 소개하기에 가장 적합한 언어이다.)배열 설명을 보면, 배열은 크기를 지정하고 해당 크기만큼의 연속된 메모리 공간을 할당받는 작업을 수행하는 자료형을 말한다. 크기가 고정되어 있으며, ..
-
시간의 복잡도 - 빅오 (Big-O)2CS지식/자료구조 2023. 12. 19. 12:23
빅오 (Big-O) 빅오를 계산하는 실용적인 방법 한눈에 빅오를 계산할 수 있으면 가장 좋지만 사실 웬만큼 알고리즘에 익숙하더라도 헷갈릴 때가 많다. 팩토리얼(n!) 계산 같은 게 그런 예다. 다음은 팩토리얼을 재귀로 구현한 코드이다. public int factorial(int n){ if( n>= 1){ return n * factorial(n-1); }else{ return 1; } } 얼핏 봐서는 팩토리얼 계산이고 재귀도 있고 하니 시간 복잡도는 O(n!) 쯤 될거 같다. 하지만 자세히 살펴보면 재귀는 n, n-1, n - 2, ... 순으로 한 번씩만 구하면 되기 때문에 시간의 복잡도는 O(n)에 불과하다. 자칫 헷갈리기 쉬운 부분이다. 그렇다면 어떻게 하면 정확하게 계산할 수 있을까? 다음과 ..
-
시간의 복잡도-빅오(Big-O)1CS지식/자료구조 2023. 12. 19. 09:47
빅오 (Big-O)1 알고리즘은 궁극적으로 컴퓨터로 구현되므로, 컴퓨터의 빠른 처리 능력을 감안하면 아무리 복잡한 알고리즘도 입력의 크기가 작으면 금방 끝나버린다. 그러므로 관심의 대상이 되는 것은 입력의 크기가 충분히 클 때다. 충분히 큰 입력에서는 알고리즘의 효율성에 따라 수행 시간이 크게 차이가 날 수 있기 때문이다. 파일 크기에 따른 소요시간 간단한 예를 들어보자. 디스크에 저장된 파일을 다른 지역에 살고 있는 친구에게 보낸다고 가정해보자 여기서 교통비 드 물리적인 비용은 전혀 고려하지 않고 단순히 시간만 따진다고 해보자. 이때 파일 크기가 작다면, 즉 n이 작다면 O(n)의 시간이 걸리는 온라인 전송이 빠르다. 하지만 파일이 아주 크다면 비행기를 통해 물리적으로 배달하는 게 더 빠를 수 있다. ..