그래프

그래프 관련 정리한 내 벨로그 링크

트리

트리 관련 정리한 내 벨로그 링크

추가로 알게 된 내용

1. String은 불변 클래스 : 관련 링크 : https://domean.tistory.com/276

   1. 문자열이 수정되면 새로운 공간을 할당
   2. 변수에 저장한 문자열이 많은 경우, String을 사용하면 메모리 관리가 비효율적

2. 시간복잡도는 프로세스(cpu)의 성능, 공간복잡도는 메모리(ram)의 성능에 좌우

3. 리스트에서 잘못된 설명

   1. ArrayList
   • 내부적으로 배열을 사용하여 데이터를 저장한다.
   • 데이터가 순차적으로 저장되며, 인덱스로 접근할 수 있다.
   • 이 때문에 ArrayList에서 데이터를 삭제하면 그 다음 인덱스에 있던 데이터가 앞으로 당겨진다.
   • 따라서 "먼저 들어온 데이터가 제일 먼저 나간다"는 것은 삭제된 데이터가 있더라도 해당 위치에 null 또는 다른 값이 들어있는 채로 남아있게 된다.

   b. LinkedList

   • 각 데이터는 이전 데이터와 다음 데이터의 참조를 가지고 있다.
   • 따라서 데이터를 추가하거나 삭제할 때 이전 데이터와 다음 데이터의 참조만 변경되므로, "먼저 들어온 데이터가 제일 먼저 나간다"는 규칙이 일반적으로 유지

   따라서 "모든 리스트는 먼저 들어온 데이터가 제일 먼저 나간다"는 설명은 ArrayList와 같은 배열 기반 리스트에서는 정확하지 않을 수 있다.

4. LinkedList도 인덱스가 있긴 함

   1. LinkedList도 각 요소에 인덱스가 있다. 하지만 ArrayList와는 다르게 LinkedList의 인덱스로 직접적인 접근은 성능상의 이유로 권장되지 않는다.
   2. LinkedList는 각 요소가 다음 요소와 이전 요소에 대한 참조만을 가지고 있기 때문에, 원하는 위치로 바로 접근하려면 처음부터 순차적으로 찾아가야 합니다. 반면에 ArrayList는 내부적으로 배열을 사용하고 인덱스로 직접 접근이 가능하기 때문에 빠른 접근이 가능합니다.

5. Arrays.sort(배열명);으로 배열을 정렬할 수 있다.

   1. Arrays.sort(배열명)을 사용하면 배열 안의 값을 정렬할 수 있다. 이 메서드는 배열의 값을 오름차순으로 정렬합니다. 만약 내림차순으로 정렬하려면 정렬 전에 Arrays.sort(배열명, Collections.reverseOrder())와 같이 사용할 수 있습니다.

6. 빅오의 실행 시간이 짧은 것부터 오래 걸리는 것까지 나열

   1. O(1) - 상수 시간(Constant Time): 입력 크기와 상관없이 항상 일정한 시간이 소요됩니다.
   2. O(log n) - 로그 시간(Logarithmic Time): 입력의 크기에 대해 로그의 형태로 증가하는 시간이 소요됩니다.
   3. O(n) - 선형 시간(Linear Time): 입력 크기에 비례하여 시간이 선형으로 증가합니다.
   4. O(n log n) - 선형 로그 시간(Linearithmic Time): n과 log n의 곱만큼 시간이 증가합니다.
   5. O(n^2) - 이차 시간(Quadratic Time): 입력 크기의 제곱에 비례하여 시간이 증가합니다.
   6. O(n^k) - 다항 시간(Polynomial Time): 입력 크기의 k 제곱에 비례하는 시간이 소요됩니다 (k는 상수).
   7. O(2^n) - 지수 시간(Exponential Time): 입력 크기에 대해 지수적으로 시간이 증가합니다.
   8. O(n!) - 팩토리얼 시간(Factorial Time): 입력 크기의 팩토리얼에 비례하는 시간이 소요됩니다.

회고 (●'◡'●)

이모티콘은 회고 쓰려고 이것저것 버튼 누르다 귀여워서 넣어본다 이번에 스터디랑 강사님이 알려주는 범위가 비슷해서 확실히 스터디가 도움된 듯 그리고 스터디를 하니 뭔가 더 잘 설명하기 위해 더 깊게 들어가는 것 같아서 좋다 쉬운코드 강의가 굉장히 도움이 많이 되는 듯

쉬운 코드 유투브 강의 하루에 1~2개씩 들으며 CS지식을 쌓을 예정 화이팅