Study in SSAFY/면접을 위한 CS 전공지식 노트

[자료구조] 5.2. 선형 자료 구조

본 포스팅은 [면접을 위한 CS 전공지식 노트]의 내용을 참고하여 작성하였습니다. 5.2. 선형 자료 구조 선형 자료 구조란 요소가 일렬로 나열되어 있는 자료 구조를 말한다. 1) 연결 리스트 연결 리스트는 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료구조이다. 삽입과 삭제에 O(1), 탐색에 O(n)이 걸린다. 위와 같이 prev 포인터와 next 포인터로 앞과 뒤를 연결한 것이 연결 리스트이다. 연결 리스트는 다음과 같이 3가지 연결 리스트가 존재한다. 싱글 연결 리스트: next 포인터만 가진다. 이중 연결 리스트: next 포인터와 prev 포인터를 가진다. 원형 이중 연결 리스트: 마지막 노드의 next 포인터가 헤드 노드를 가리키는 이중 연결 리스트. 2) 배열 배열..

[자료구조] 5.1. 복잡도

본 포스팅은 [면접을 위한 CS 전공지식 노트]의 내용을 참고하여 작성하였습니다. 5.1. 복잡도 복잡도는 시간 복잡도와 공간 복잡도로 나뉜다. 1) 시간 복잡도 문제를 해결하는 데 걸리는 시간과 입력의 함수 관계. 알고리즘의 로직이 얼마나 오랜 시간 걸리는지. 빅오 표기법*으로 나타냄. (빅오 표기법*: 가장 영향을 많이 끼치는 항의 상수 인자와 나머지 항을 없앤 것. 예를 들어 10n^2+n의 시간이면 O(n^2)로 표기한다.) 필요한 이유: 효율적인 코드로 개선하는 데 쓰이는 척도. 2) 공간 복잡도 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양. 정적 변수는 물론이고 재귀함수로 인해 동적인 공간을 계속해서 필요할 경우도 포함. int a[1005]; 위와 같은 코드를 예시로 들면, a 배열..