[1주차] 인프런 워밍업 클럽 스터디 3기 - CS전공지식 발자국

자료구조

• 데이터를 저장하는 구조이며, 어떤 자료구조를 선택하느냐에 따라 데이터 처리 방식이 달라진다.

• 변수: 가장 단순한 자료구조로, 저장된 데이터를 찾으려면 변수명을 사용.

• 배열: 데이터를 연속된 메모리 공간에 저장하며, 인덱스를 통해 빠르게 접근 가능.

  • 유지보수 측면에서 데이터를 배열에 저장하는 것이 일반적으로 유리함.

  • 단, 데이터 삽입/삭제 시 오버헤드가 발생하여 성능 저하 가능.

• 연결리스트: 노드(데이터 + 포인터)로 이루어져 있으며, 각 노드가 다음 노드를 가리키는 방식.

  • 첫 번째 노드만 알면 전체 리스트를 탐색 가능.

  • 데이터 삽입/삭제가 용이(기존 데이터 이동 없이 포인터만 변경).

  • 하지만 특정 위치에 접근하는 속도는 배열보다 느림.

• 배열 vs 연결리스트

  • 배열: 빠른 검색(O(1)) & 고정된 크기의 연속된 메모리 할당

  • 연결리스트: 빠른 삽입/삭제(O(1)) & 동적 메모리 할당

시간 복잡도 & 알고리즘 성능

• 알고리즘은 코드 실행 성능을 결정하며, 반복문이 많아질수록 실행시간이 증가.

• 성능을 평가하는 기준:

  1. 메모리를 줄이는 알고리즘

  2. 메모리를 많이 사용하지만 속도가 빠른 알고리즘

• 시간 복잡도 (Big-O 표기법)

  • 입력 크기(n)에 따라 계산량이 어떻게 증가하는지를 나타냄.

  • 빅오(O): 최악의 경우

  • 빅세타(Θ): 평균적인 경우

  • 빅오메가(Ω): 최선의 경우

  • 일반적으로 빅오(O)를 많이 사용.

• 빅오 표기법 예시

  • O(1): 상수 시간 - 입력 크기와 상관없이 일정한 시간 소요 (예: 배열에서 인덱스로 접근)

  • O(n): 선형 시간 - 입력 크기에 비례해 실행 시간 증가 (예: 배열을 순회)

  • O(n²): 제곱 시간 - 중첩 반복문 (예: 버블 정렬)

  • O(log n): 로그 시간 - 이진 탐색

자료구조 선택

• 배열: 빠른 조회(O(1)), 삽입/삭제가 비효율적(O(n))

• 연결리스트: 삽입/삭제가 효율적(O(1)), 조회가 비효율적(O(n))

• 메모리 구조가 중요한 경우 운영체제 공부가 필요.

추상 자료형 (ADT, Abstract Data Type)

• 자료구조에서 제공하는 기능을 정의한 것.

• 예시:

  • 연결리스트의 모든 원소 출력

  • 모든 데이터 제거

  • 특정 인덱스에 데이터 삽입

정리: 적절한 자료구조를 선택하고, 알고리즘을 통해 데이터를 효과적으로 처리해야 한다. 성능 평가를 위해 Big-O를 사용하며, 특정 작업에 맞는 자료구조를 골라야 한다.