Tori의 개발 공부

문제 파이썬 풀이 최대 회의 수를 구하기 위해서는 회의시간이 짧은 즉 가장 빨리 끝나는 회의를 배정하면 된다. 계속해서 짧은 회의를 배정하여 사용할 수 있는 회의의 수를 늘리는 것이다. 따라서 회의가 끝나는 시간을 기준으로 살펴본다. 회의가 끝나는 시간이 현재 시간과 가장 가까운 회의를 배정하면된다. 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 ..

그리디 알고리즘 그리디 알고리즘이란? 탐욕(그리디) 알고리즘이란 현재 상황에서 가장 최선의(좋은) 선택을 고르는 알고리즘을 의미한다. 그리디 알고리즘은 현재 상황의 가장 좋은 결과를 선택하는 것으로 최종 결과에 대한 최적의 해를 구하는 것과는 다르다. 위와 같은 예시에서 가장 합이 큰 경로를 찾는다고 할 때 최종적으로 가장 최적의 해는 노란색 루트를 따라 111을 구하는 경로이다. 그러나 그리디 알고리즘은 루트에서 가장 최적의 해인 20으로, 20에서 가장 최적의 해인 41로 가는 파란색 루트를 따라간다. 현재의 상황에서 가장 큰 수를 따라 최종적으로 62의 값을 얻게 된다. 이렇게 그리디 알고리즘이 최종적으로 가장 최적의 해를 구하는 것은 아니다. 그리디 알고리즘의 조건 그렇다면 그리디 알고리즘을 사용..

문제 파이썬 문제 풀이 괄호를 이용하여 최소의 결과를 얻어내는 문제이다. 가장 작은 값을 얻기 위한 방법을 간단하게 생각하면 가장 큰 값을 빼주면 된다. 즉 마이너스 연산을 만나면 가장 큰 값을 빼주면 된다. 가장 큰 값을 빼주기위해 마이너스를 만나게 되면 다음 마이너스까지 있는 플러스 연산들을 모두 괄호로 묶어 가장 큰 수를 만들어주면 된다. 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 -..

분할 정복 알고리즘 이란? 분할 정복 알고리즘(Divide and conquer algorithm)은 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이나 알고리즘이다. 일반적으로 재귀 함수로 구현한다. 설계 단계 Divide (분할) : 문제가 분할이 가능한 경우, 원래 문제를 분할하여 더 작은 하위 문제들로 분할한다. Conquer (정복) : 나누어진 문제가 여전히 분할이 가능하다면, 다시 Divide 수행하고 그렇지 않다면 문제를 해결한다. Combine (합치기): Conquer한 문제들을 통합하여 원래 큰 문제의 답을 얻는다. 장단점 장점 문제를 나눔으로써 어려운 문제를 쉽게 해결할 수 있다. 단점 재귀 함수를 호출한다는 점에서 함수 호출로 인한 오버헤드 발생, 스택에 ..