알고리즘 공부20 [python] 1931번 - 회의실 배정 문제 파이썬 풀이 최대 회의 수를 구하기 위해서는 회의시간이 짧은 즉 가장 빨리 끝나는 회의를 배정하면 된다. 계속해서 짧은 회의를 배정하여 사용할 수 있는 회의의 수를 늘리는 것이다. 따라서 회의가 끝나는 시간을 기준으로 살펴본다. 회의가 끝나는 시간이 현재 시간과 가장 가까운 회의를 배정하면된다. import sys input = sys.stdin.readline N = int(input().rstrip()) time_list = [] for i in range(N) : time_list.append(list(map(int, input().rstrip().split()))) time_list.sort(key=lambda x: (x[1], x[0])) count = 0 last_time = 0 for .. 2021. 11. 23. 그리디 알고리즘 내용 정리 그리디 알고리즘 그리디 알고리즘이란? 탐욕(그리디) 알고리즘이란 현재 상황에서 가장 최선의(좋은) 선택을 고르는 알고리즘을 의미한다. 그리디 알고리즘은 현재 상황의 가장 좋은 결과를 선택하는 것으로 최종 결과에 대한 최적의 해를 구하는 것과는 다르다. 위와 같은 예시에서 가장 합이 큰 경로를 찾는다고 할 때 최종적으로 가장 최적의 해는 노란색 루트를 따라 111을 구하는 경로이다. 그러나 그리디 알고리즘은 루트에서 가장 최적의 해인 20으로, 20에서 가장 최적의 해인 41로 가는 파란색 루트를 따라간다. 현재의 상황에서 가장 큰 수를 따라 최종적으로 62의 값을 얻게 된다. 이렇게 그리디 알고리즘이 최종적으로 가장 최적의 해를 구하는 것은 아니다. 그리디 알고리즘의 조건 그렇다면 그리디 알고리즘을 사용.. 2021. 11. 23. [python] 1541번 - 잃어버린 괄호 문제 파이썬 문제 풀이 괄호를 이용하여 최소의 결과를 얻어내는 문제이다. 가장 작은 값을 얻기 위한 방법을 간단하게 생각하면 가장 큰 값을 빼주면 된다. 즉 마이너스 연산을 만나면 가장 큰 값을 빼주면 된다. 가장 큰 값을 빼주기위해 마이너스를 만나게 되면 다음 마이너스까지 있는 플러스 연산들을 모두 괄호로 묶어 가장 큰 수를 만들어주면 된다. eval함수를 이용한 코드 : 틀림 import sys input = sys.stdin.readline inputExp = input().rstrip().split("-") resultExp = 0 for index, i in enumerate(inputExp) : if index == 0 : resultExp += eval(i) else : resultExp -.. 2021. 11. 23. [python구현] 정렬 알고리즘 - 선택, 삽입, 버블, 병합, 퀵 정렬 정렬 선택 정렬 선택 정렬 알고리즘 주어진 리스트 중에 최솟값을 찾는다. 찾은 값을 맨 앞에 위치한 값과 교체한다. 정렬된 앞부분을 제외한 리스트를 같은 방법으로 교체한다. 선택 정렬 파이썬 구현 def selectionSort(x) : length = len(x) for i in range(length-1) : minIndex = i for j in range(i+1,length) : if x[minIndex] >x[j] : minIndex = j x[i], x[minIndex] = x[minIndex], x[i] return x 선택 정렬 시간 복잡도 모든 인덱스 접근 루프문(i for문) : O(n) 최솟값 찾기 루프문 (j for문) : O(n) 총 O(n^2) 버블 정렬 버블 정렬 알고리즘 인접.. 2021. 8. 30. 이전 1 2 3 4 5 다음
