본문 바로가기

2017/112

기술면접 list- 알고리즘(정렬) 정렬 알고리즘- 왜 정렬을 해야할까?탐색을 빠르게 하기 위해서- 같은 시간복잡도를 갖고 있더라도 요소에 따라 달라짐. 버블 정렬(Bubble sort) (평균 및 최악 : O(n^2))- 인접한 두 원소를 검사하며 정렬하는 방법- 시간복잡도 O(n^2)- 코드는 단순하지만, 정말 비효율적이라 거의 쓰이지 않음. 다만 이미 정렬된 데이터에 대해서 검사하는데는 O(N)으로 간단하게 알 수 있음.- 1번째부터 n번째까지 swap을 통해 정렬. 1번째부터 n-1번째 까지 swap. ...O(N + N-1 + N-2 + ... +1) => O(N(N+1)/2) => O(N^2) 선택 정렬(Selection sort) (평균 및 최악 : O(n^2)- 선형 탐색을 하며 가장 작은 원소를 배열의 맨 앞으로 보낸다. .. 2017. 11. 14.
기술면접 list- 자료구조 자료구조 배열(Array)- 정적으로 필요한 만큼만 원소를 저장할 수 있는 공간이 할당됨. 각 원소의 주소는 연속적으로 할당됨. - index를 통해 O(1)에 접근 가능. - 삽입, 삭제는 O(N)- 지정된 개수를 초과하는 경우 배열의 크기를 재할당한 후 복사해야함 리스트- 노드(Node)들의 연결로 이루어진 자료구조- 크기 제한이 없다(heap 용량이 충분하다면).- 다음 노드에 대한 참조를 통해 원소를 접근(O(N))- 노드의 삽입, 삭제에 강점을 가짐(O(1)) ArrayList- 동적으로 크기가 조정되는 배열- 배열이 가득 차는 경우 알아서 그 크기를 2배로 할당하고 복사를 수행- 재할당에 걸리는 시간은 O(N)이지만, 자주 일어나는 일이 아니기 때문에 접근시간은 O(1) 스택(Stack)- L.. 2017. 11. 14.