자료구와 알고리즘

자료구조

자료구조의 정의

• 데이터를 저장하고 관리하는 방식

메모리 구조

• 각 메모리는 주소값을 가지고 있음
• 메모리에 데이터를 저장하고 주소값을 통해 해당 값을 찾을 수 있음

 

알고리즘의 정의

• 어떠한 문제를 해결하기 위해 정해진 일련의 절차나 방법

알고리즘 평가 기준

• 시간 복잡도
• 공간 복잡도
• 구현 복잡도
• 시간복잡도와 공간복잡도는 상관관계에 있음 ⇒ 시간 복잡도가 줄어들면 공간 복잡도가 증가하고 그 반대로 공간 복잡도가 줄어들면 시간 복잡도가 늘어남

시간 복잡도

• 빅오 표기법으로 표현
• 실행 시간을 표시
• 빅오를 통해 가장 높은 차수만 가져와 표현

• Best Case, Average Case, Worst Case 가 존재
• 알고리즘의 시간 복잡도를 말할 때는 보통 Average Case를 말함 ⇒ 하지만 Average Case는 구하기 어려운 경우가 많아 가장 많이 비슷한 Worst Case를 칭함
• 제약 조건이 존재할 때 자세히 보고 시간 복잡도를 선택 할 수 있어야함
• ex) 10^8 일 경우 제한이 1 ~ 10^5 일 때 n^2 이면 10^10이 되기 때문에 시간 제약 조건이 넘어감
• 기준에 따라 N이 달라짐
• ex) 두 수를 더해서 원하는 숫자를 찾을 때 더하는 것보다 수의 list가 많으면 그만큼 시간이 오래 걸리기 때문에 수의 list가 n이 됨

풀이 방법

1. 문제를 파악 (시간복잡도 파악)
2. 직좐적으로 생각하기
   1. 보통 완전 탐색으로 시작
   2. 문세 상황을 단순화 하여 생각(간단하게)
   3. 문제 상황을 극한화 하여 생각(복잡하게)
3. 자료구조와 알고리즘 활용
   1. 문제파악에서 파악한 내용을 토대로 어떤 자료구조를 사용하는게 적합한지 결정
   2. 대놓고 특정 자료구조와 알고리즘을 묻는 문제도 많음
   3. 자료구조에 따라 선택할 수 있는 알고리즘을 문제에 적용
4. 메모리 사용
   1. 시간복잡도를 줄이기 위해 메모리를 사용하는 방법
   2. 대표적으로 해시 테이블
5. 단계별로 코드 설계
   1. 직관적 생각 한것 설계
   2. 자료구조와 알고리즘 활용 설계
   3. 메모리 사용 설계

 

 

출처 : https://www.inflearn.com/course/코딩테스트-입문-파이썬/