2024 Study Plan/자료구조&알고리즘4 [자료구조와 알고리즘 with Python] 1. 스택 1 - 1 스택이란?스택(Stack)은 마지막에 들어간 자료가 가장 먼저 나오는 구조이다.예) 설거지를 한 그릇을 설거지통에 넣어놓으면 요리사가 맨 위에 놓인 접시를 가져가 음식을 담아 손님들에게 제공예) 웹 브라우저의 뒤로가기, 네이버 홈페이지 -> 뉴스 -> 스포츠 뉴스에서 뒤돌아가면 뉴스 -> 네이버 스택은 예시들처럼 후입선출(Last In First Out) 형태의 자료구조이다.설거지통에서 맨 윗 부분을 상단(stack top)이라고 하고 스택에 저장되는 데이터를 요소라고 한다.스택은 요소의 삽입과 삭제가 상단에서만 이루어진다. 스택의 연산push(item): item이라는 요소를 맨 위에 넣음pop(): 스택의 맨 위의 요소를 꺼내 returnis_empty(): 스택이 비어있으면 True, 아.. 2024. 12. 9. [알고리즘] Greedy Algorithm, 그리디(탐욕) 알고리즘 1. 그리디(탐욕) 알고리즘의 정의 미래를 고려하지 않고 오직 현재 시점에서 가장 좋은 선택예) 잔돈 반환 프로그램 - 사용할 수 있는 가장 큰 동전부터 최대 사용 가능한 양만큼 쓰고 밑으로 차근차근 내려가며 동전의 개수를 최소로 사용하게 하는 방법, 6800원이 들어왔다면 5000원 한 장을 낼 때 뒤에 어떤 돈들이 쓰일 지 고려하지 않음 2. 그리디 알고리즘의 특징 이 알고리즘은 항상 최적을 보장하지 못함, 현재의 최적 해가 전체의 최적 해를 보장하지 않음예) 마시멜로를 참으면 10분 뒤에 두 개를 먹을 수 있지만, 그리디 알고리즘에 따르면 하나를 먹는게 최선임 따라서 항상 최적 해를 찾아야 하기 때문에 최적 해가 보장되는 조건에서만 그리디 알고리즘을 사용해야함 조건1 - 현재의 선택이 미래에 영향을.. 2024. 6. 4. [자료구조&알고리즘] 0-2. 알고리즘 시간복잡도 알고리즘 시간복잡도 자료구조, 알고리즘의 시간복잡도 (Time Complexity) algorithm arrayMax(A,n): currentMax = A[0] for i = 1 to n-1 do: if currentMax < A[i]: currentMax = A[i] return currentMax A = [ _ , _ , _ , _ , _ , _ ] n : input size arrayMax가 기본 연산을 몇번 하는지 찾기 1. 모든 입력에 대해 기본연산 횟수를 더한 후 평균 (현실적으로 불가능, 고려해야할 것이 많음) 2. 가장 안좋은 입력 (worst case input) 에 대한 기본 연산 횟수를 측정 : worst case time complexity (정확하지 않지만 어떤 입력에 대해서도 w.. 2024. 1. 9. [자료구조&알고리즘] 0-1. 자료구조와 알고리즘 자료구조 자료 : 데이터(data) 자료구조 : 데이터를 저장하기 위한 저장공간(memory) + 읽기, 쓰기, 삽입, 삭제, 탐색 등의 연산 알고리즘 : 입력된 데이터를 통해 문제를 푸는 과정 (유한한 횟수의 연산들을 반복해 정답을 출력) 자료구조 예 : 1. 변수(variable) a = 5 (a라는 저장 공간에 값 5를 쓰는 쓰기연산), print(a) (a에 들어있는 값을 읽어와 출력하는 읽기연산) ※ a라는 변수가 있으면 a에 5라는 값이 실제로 저장되는 것이 아니라 5가 저장되어 있는 주소가 a에 저장됨 (5가 들어있는 객체의 주소) 2. 배열(array) 리스트(list) A = [3,-1,5,7] A[0]은 3이 들어있는 객체를 가리키고 A[1]은 -1이 들어있는 객체를 가리키는 방식으로 .. 2024. 1. 9. 이전 1 다음
