CS03 - 자료구조와 알고리즘 개념 && LinkedList

Bash Communication

지난 시간에 셸 스크립트에 대해 학습했다. bash 커뮤니케이션이는 return 값이 존재한다! C언어로 예를 들면, 0는 시스템의 정상종료, 그외 정수 값은 비정상종료를 의미한다. $? 은 최근 실행한 함수의 return 값을 가진 변수를 출력해준다.

 

$?

자료구조와 알고리즘

알고리즘은 2가지 특성을 가진다.

1. input, output이 있어야 한다.

2. 유한시간 안에 실행되어야 한다.

 

자료구조는 데이터를 담는 방식이다. 적절한 자료구조를 사용하는 것이 가장 중요하다. 배열+리스트가 90%, 해시맵까지 포함하면 99% 비율로 많이 사용된다. 하지만 트리 등의 구조도 꼭 알아두자!

알고리즘 성능표기

- 점근적 표기법 : 알고리즘에서 input이 커지면서(x > N, 임의의 큰 수: N) 나타나는 성장률을 상수계수와 중요하지 않은 항목을 제거한 것을 점근 표기법이라고 한다. 빅오, 빅오메가, 빅세타 표기법이 있다.

 

- 빅오 표기법(big-O notation) : 성능의 상한선을 의미한다. 적어도 이 시간보다는 적게 걸림을 의미한다.

- 빅오메가 표기법(big-Ω notation) : 성능의 하한선을 의미한다. 이 시간보다는 더 적게 걸릴 수 없음을 의미한다.

- 빅세타 표기법(big-Θ notation) : 중간값을 의미하며 빅오와 빅오메가의 사이에 존재하는 값이다. 점근적으로 근접한 한계이다.

 

일반적으로 O(1), O(n), O(nlogn)까지를 빠른 알고리즘이라고 하고, O(n^2)까지도 사용하기도 한다. 웹에서 웹스케일이 커짐에 따라 빠른 알고리즘이 더 필요하게 된다. 

 

참고자료

Call by ~sth~

call by reference : 참조값 자체가 넘어간다. (주소)

call by address(pointer) : 포인터 주소를 받아 넘긴다. C에서 사용되는 듯 하다. (주소)

call by value : 값을 받아 넘긴다.

pass by value : 함수 호출 시에 매개변수의 값을 복사하여 전달한다. 

 

이렇게 call by reference, call by value로 자바에서의 값을 설명하지만 사실 자바에서는 pass by value 하나뿐이라고 한다. 스펙문서에 나와있다고 한다. 스펙문서를 읽으라고 해서 들어가 봤더니 버전별로 800쪽이 넘는다😂 스펙문서가 존재함을 알고있자..ㅎㅎㅎ 버전별로 업데이트 되어 추가된 항목들만 따로 정리되어 있는 부분도 있는 것 같으니 그 부분이라도 읽어보면 좋을 듯 싶다.

LinkedList

ADT(Abstract Data Type, 추상자료형)이란 자료와 그 연산을 명기한 것으로 구현 방법을 명시하지는 않는다. 인터페이스라고 이해했는데 List<String> names = new ArrayList<>(); 이렇게 작성이 가능한 것은 List라는 ADT를 ArrayList가 구현하고 있기 때문이다. 다양한 객체를 구현하고 있는 인터페이스로 묶어 관리할 수 있는 장점이 있다.

 

- 단일 링크드 리스트 : next에 어떤 객체가 연결되는지 알 수 있다. 큐 구조의 설계가 가능하다.

- 더블 링크드 리스트 : prev와 next에 어떤 객체가 연결되는지 알 수 있다. 데큐 구조의 설계가 가능하다.

- 선형 링크드 리스트 : head, tail이 존재하여 처음과 끝이 있다.

- 서큘러 링크드 리스트 : head와 tail 즉, 처음과 끝이 존재하지 않고 맞물려 있다. 시작과 끝이 중요하지 않고, 현재의 Node를 알면 다음을 진행하는 리스트, 혹은 처음과 끝이 중요한 것이 아니라 반복되는 리스트를 사용할 때 유용한 듯 싶다. head에 더미노드(센티넬)을 설정하면 더 쉽게 구현이 가능하다고 한다.

 

추가

- 큐(queue) : 뒤에서 넣고 앞에서부터 빼는 작업이 가능한 자료구조이다.

- 데큐(deque) : 앞, 뒤에서 넣고 빼는 작업이 가능한 자료구조이다.

- 우선순위  큐(priority queue) : 우선순위별로 자료를 빼는 작업이 가능한 자료구조이다. 배열, 링크드 리스트, 힙으로 구현이 가능하다고 한다. 배열과 링크드 리스트로 구현하면 추가, 삭제에 시간이 오래걸려 대부분 heap방식으로 구현되어 있다고 한다. heap이란 완전 이진트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다. 부모와 자식을 비교하여 우선순위가 높을수록 위쪽에 위치하게 된다.