분류 전체보기 (34) 썸네일형 리스트형 python - 스택(Stack) 자료구조 1. 스택의 개념스택(Stack): 선형 자료구조, LIFO(Last In, First Out) 방식으로 작동.가장 나중에 삽입된 데이터가 가장 먼저 제거됨. (예: 접시 쌓기)2. 스택의 특징LIFO 구조 : 마지막 들어간 데이터가 가장 먼저 나옴.주요 연산 :push: 데이터를 스택의 맨 위에 추가.pop: 스택의 맨 위 데이터를 제거하고 반환.peek (또는 top): 스택의 맨 위 데이터를 제거하지 않고 확인.is_empty: 스택이 비어 있는지 확인.실제 구현 :리스트를 사용하여 스택을 구현하거나, collections.deque를 사용하여 더 효율적인 스택을 구현할 수 있다.3. 스택의 구현 방법(1) 리스트를 이용한 스택Python의 리스트는 기본적으로 스택처럼 사용할 수 있음.# 스택 구현.. python - 시간복잡도(Time Complexity)와 예제 시간복잡도(Time Complexity)시간복잡도는 알고리즘의 실행 시간이 입력 크기(input size, n)에 따라 어떻게 변화하는지를 평가하는 척도입니다.빅오 표기법(Big-O Notation)을 사용해 최악의 경우를 기준으로 표현하며, 알고리즘의 효율성을 비교하는 데 활용됩니다.1. 빅오 표기법(Big-O Notation)입력 크기 증가에 따른 실행 시간의 상한(최악의 경우)을 수학적으로 간단히 표현합니다.빅오 표기법설명예시O(1)상수 시간 (입력 크기에 무관)배열 첫 요소 접근, 변수 선언O(log n)로그 시간 (입력 크기의 로그에 비례)이진 탐색O(n)선형 시간 (입력 크기에 비례)배열 순회, 선형 탐색O(n log n)로그 선형 시간퀵 정렬, 병합 정렬O(n²)이차 시간 (중첩 반복문)버블.. 파트7. 탐욕법 - [Greedy] 실습문제3 (단속카메라 42884번) python def solution(routes): answer = 0 q = 10 routes.sort(key=lambda x: x[0], reverse=True) for i in routes: if q>=i[0]: if i[0]1트만에 정답이라고 떠서 매우 좋아하고 있었다.그리고 gpt한테 코드 어떤지 물어봤는데 ...구리다는 팩폭을 당해 코드를 구글링과 함께 수정해보았다. gpt의 피드백비효율적인 정렬 기준 - 진입지점이 아니라 진출 지점을 기준으로 정렬하기차량의 경로가 겹치는 부분을 정확히 판단하려면 차량이 고속도로를 떠나는 지점을 기준으로 카메라를 배치하는 것이 합리적이다.조건문의 복잡성if i[0] gpt의 코드def solution(routes): .. 파트7. 탐욕법 - [Greedy] 실습문제2 (회의실 배정 211123번) python def solution(arr): answer = 0 end=0 arr.sort(key=lambda x:(x[1],x[0])) for s, e in arr: if end 파트7. 탐욕법 - [Greedy] 실습문제1 (예산 12982번) python def solution(d, budget): answer = 0 d.sort() for i in d: if budget>=i: budget=budget-i answer+=1 else: break return answer입력받은 신청 금액들을 정렬해준다예산이 신청 금액보다 크다면 예산에서 신청 금액을 빼주고, answer을 1 증가시킨다.끝 python - 탐욕법, 그리디 알고리즘 (Greedy Algorithm) 그리디 알고리즘 (Greedy Algorithm)개념그리디 알고리즘은 현재 시점에서 가장 최선의 선택(최적해)을 반복적으로 수행하여 문제를 해결하는 방법입니다.이 방법은 특정 조건에서만 전체 문제의 최적해를 보장합니다.1. 그리디 알고리즘의 특징탐욕적 선택 속성:각 단계에서의 최선의 선택이 전체 문제의 최적해를 보장해야 합니다.최적 부분 구조:문제의 최적해는 부분 문제들의 최적해로 구성될 수 있어야 합니다.간단하고 빠름:일반적으로 시간 복잡도가 낮으며, 직관적인 풀이가 가능합니다.최적해 보장 여부:모든 문제에서 그리디 알고리즘이 최적해를 보장하지는 않습니다. 문제의 성질을 반드시 확인해야 합니다.2. 그리디 알고리즘의 동작 과정문제를 여러 단계로 나눔.각 단계에서 현재 상황에서 최적이라고 판단되는 선택을.. 파트6. 정렬과 탐색 - [Sorting] 실습문제4 (가장 큰 수 42746번) python 많은 수정 과정을 거친 문제이다...우선 가장 처음 짠 코드!def solution(numbers): answer = sorted(list(map(str,numbers)), reverse=True) return ''.join(answer)정수를 map 함수 통해 string으로 바꿔주고, 정렬한다.이때, 내림차순 정렬을 위해 reversed 옵션을 True로 설정한다.리스트로 되어있는 answer을 공백 없이 join해주며 리턴한다. 처음에 map함수에 list를 안 붙였더니 출력값이 이상했다. map object at 0x00605c0과 같은...검색해보니 map 함수의 수행결과는 map object이기 때문에 반복문이나 리스트 변환 등을 통해 실제 값을 접근하거나 출력해야 한다.아무튼 채점.. 파트6. 정렬과 탐색 - [Sorting] 실습문제1 (A로 B만들기 120886번) python def solution(before, after): answer = 0 if sorted(list(before))==sorted(list(after)): answer=1 print(before, after) return answer입력값들을 전부 리스트로 바꿔준다이후 정렬 함수를 사용하여 정렬하고, 비교한다. 이 때 두 값이 같으면 순서를 바꿨을 때 같은 값이 나올 수 있으므로 answer을 1로 바꿔준다. 이전 1 2 3 4 5 다음
