5. 자료구조와 알고리즘

1. 기본 자료구조

배열 (Array)

• 정의: 같은 타입의 데이터를 연속된 메모리 공간에 저장 (예: [10,[20][30]).
• 특징:
  • 인덱스(번호)로 즉시 접근 가능 (예: arr → 첫 번째 요소).
  • 크기가 고정되어 있어 추가/삭제가 어려움 (공간이 부족하면 새 배열 생성 필요).
• 사용 예시: 학생 점수 목록, 이미지 픽셀 데이터.

리스트 (Linked List)

• 정의: 노드로 구성된 구조. 각 노드는 데이터 + 다음 노드 주소를 가짐 (예: 1 → 3 → 5).
• 특징:
  • 크기가 유동적 (데이터 추가/삭제가 빠름).
  • 특정 위치 접근 시 처음부터 순회해야 해 느림 (예: 100번째 노드 접근 → 100번 이동).
• 사용 예시: 음악 재생 목록, 브라우저 방문 기록.

스택 (Stack)

• 정의: LIFO(Last In First Out) 구조. 마지막에 추가된 데이터가 먼저 제거됨.
• 주요 연산:
  • push(): 데이터 추가 (예: 접시 쌓기).
  • pop(): 가장 위의 데이터 제거 (예: 접시 꺼내기).
• 사용 예시: 뒤로 가기 기능, 함수 호출 스택.

큐 (Queue)

• 정의: FIFO(First In First Out) 구조. 먼저 추가된 데이터가 먼저 제거됨.
• 주요 연산:
  • enqueue(): 데이터 추가 (예: 줄 서기).
  • dequeue(): 가장 앞의 데이터 제거 (예: 줄에서 첫 번째 사람 처리).
• 사용 예시: 프린터 작업 대기열, 메시지 큐.

해시 테이블 (Hash Table)

• 정의: 키(key)-값(value) 쌍을 저장하는 구조 (예: 사전).
• 동작 원리:
  • 키를 해시 함수로 변환 → 인덱스 생성.
  • 해당 인덱스에 값 저장.
• 충돌 처리:
  • 체이닝: 같은 인덱스에 연결 리스트로 데이터 저장.
  • 개방 주소법: 다른 빈 인덱스 탐색.
• 사용 예시: 사용자 로그인 정보 캐싱, 데이터베이스 인덱싱

트리 (Tree)

• 정의: 계층적 구조 (예: 가계도).
• 이진 탐색 트리 (BST):
  • 왼쪽 자식 < 부모 < 오른쪽 자식.
  • 검색/삽입/삭제: 평균 O(log n).
• 사용 예시: 파일 시스템 계층, 데이터베이스 인덱스.

그래프 (Graph)

• 정의: 노드(정점) + 간선(연결선)으로 구성된 네트워크 (예: SNS 친구 관계).
• 종류:
  • 방향 그래프: 간선에 방향 있음 (예: 웹페이지 링크).
  • 무방향 그래프: 간선에 방향 없음 (예: 페이스북 친구).
• 사용 예시: 지도 최단 경로 탐색, 추천 시스템

2. 알고리즘

정렬 알고리즘

• 버블 정렬:
  • 인접한 두 요소를 비교해 교환.
  • 시간복잡도: O(n²) (비효율적).
  • 예시: [5, 3,[8] →[3][5][8]
• 퀵 정렬:
  • 피벗(pivot)을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할 → 재귀적 정렬.
  • 시간복잡도: 평균 O(n log n), 최악 O(n²).
  • 예시: 피벗 5 선택 → [3][5][8]

탐색 알고리즘

• 선형 탐색:
  • 처음부터 끝까지 순차적으로 검색.
  • 시간복잡도: O(n).
  • 예시: 책장에서 책 찾기.
• 이진 탐색:
  • 정렬된 데이터에서 중간값을 기준으로 범위를 절반씩 좁혀감.
  • 시간복잡도: O(log n).
  • 예시: 전화번호부에서 이름 찾기

캐싱 알고리즘

• LRU (Least Recently Used):
  • 가장 오래전에 사용된 데이터를 삭제.
  • 예시: 브라우저 캐시에서 자주 방문하지 않은 페이지 제거
• FIFO (First In First Out):
  • 가장 먼저 들어온 데이터를 삭제.
  • 예시: 슈퍼마켓 재고 관리 (먼저 들어온 상품 먼저 판매).

3. 시간복잡도 & 공간복잡도

• Big O 표기법: 입력 크기(n)에 따른 알고리즘의 효율성 표기.
  • O(1): 상수 시간 (예: 배열 접근).
  • O(n): 선형 시간 (예: 단일 반복문).
  • O(n²): 이중 반복문 (예: 버블 정렬).
  • O(log n): 로그 시간 (예: 이진 탐색)

4. 코딩 테스트 준비

• 연습 플랫폼:
  • LeetCode: 실제 기출 문제 풀이.
  • 프로그래머스: 한국형 코딩 테스트 연습.
• 전략:
  1. 유형 파악: 그리디, DP, 탐색 등 문제 유형 분류.
  2. 의사코드 작성: 코드 구현 전 논리 구조 설계.
  3. 테스트 케이스 생성: 예외 상황 (빈 입력, 큰 수) 직접 검증

6. 운영체제와 시스템

프로세스 vs 스레드

구분	프로세스	스레드
메모리	독립적 (Code, Data, Heap 등)	Stack만 독립, 나머지 공유
생성 비용	높음	낮음
동기화	필요 없음	필수 (공유 자원 관리)

 

• 예시:
  • 프로세스: 크롬 브라우저와 엑셀은 별도의 프로세스.
  • 스레드: 크롬 내에서 여러 탭은 스레드로 동작.

멀티스레딩

• 하나의 프로세스에서 여러 스레드가 병렬 처리.
• 장점: 자원 공유로 효율적.
• 단점: 데드락 발생 가능성 (예: 두 스레드가 서로의 자원을 무한 대기).

동기/비동기

• 동기: 작업 완료 후 다음 작업 실행 (예: 은행 창구에서 순차적 처리).
• 비동기: 작업 완료를 기다리지 않고 다음 작업 실행 (예: 배달 앱에서 주문과 동시에 결제).

데드락 (Deadlock)

• 조건: 상호 배제, 점유 대기, 비선점, 순환 대기.
• 해결법: 자원 할당 순서 강제, 타임아웃 설정.

메모리 구조

• 스택 (Stack):
  •  함수 호출, 지역 변수 저장 (LIFO).
  •  예시: main() → funcA() → funcB() 순서로 호출.
• 힙 (Heap):
  •  동적 메모리 할당 (예: new 연산자).
  •  예시: 객체 생성 시 힙에 저장.
• GC (Garbage Collection):
  •  더 이상 사용되지 않는 힙 메모리 자동 정리.
  • 예시: Java, Python에서 불필요한 객체 삭제.

파일 시스템 & 입출력

• 파일 시스템: 데이터를 파일/폴더로 관리 (예: Windows의 NTFS, Linux의 ext4).
• 입출력 (I/O):
  • 블로킹 I/O: 작업 완료 시까지 대기 (예: 파일 읽기).
  • 논블로킹 I/O: 작업 완료 여부와 관계없이 다음 작업 실행.

리눅스 기본 명령어

• ls: 디렉토리 내용 조회.
• cd: 디렉토리 이동.
• grep: 텍스트 검색 (예: grep "error" log.txt).
• chmod: 파일 권한 변경 (예: chmod 755 script.sh).

CI/CD

• CI (지속적 통합): 코드 변경 시 자동 빌드/테스트.
• CD (지속적 배포): 테스트 통과 시 자동 배포 (예: Jenkins, GitHub Actions).

실무 팁

• 배열 vs 연결 리스트:
  • 빠른 접근 필요 → 배열.
  • 빈번한 추가/삭제 → 연결 리스트.
• 캐싱 전략 선택:
  • LRU: 최근 데이터가 재사용될 가능성 높을 때.
  • FIFO: 데이터 사용 패턴이 예측 불가능할 때.
• 코딩 테스트: 의사코드 작성 → 코드 구현 → 테스트 단계를 꼭 거칠 것!