백준 문제풀이(파이썬)

명령에 따라 pop하거나 reverse하는 문제이다. 새로운 배열을 하나 더 만들어서 거꾸로 넣어주는 식으로 R명령을 수행하고, pop()을 사용하여 D 명령을 수행하려고 했지만, 입력의 수와 코드의 간결성을 생각하면 딱히 좋은 풀이는 아닌 것 같다. 내가 사용한 방법은 front라는 변수를 선언하여 앞부분의 인덱스를 넣어주는 방법이다. 만약 R명령이 들어와서 뒤집는 경우에는 front에 -1을 넣어 마지막 원소를 가리키게하고, D명령을 수행할 때는 front가 가리키는 값을 pop해주는 식이다. 그렇게 하면, 보조 리스트를 계속하여 생성하거나, 뒤에 append하는 등의 시간 초과 요인에 대해 걱정할 필요가 없다. ##함수 선언 부분 ##변수 선언 부분 command = [] index_2 = 0 fr..

자신보다 오른쪽에 있는 수 중에서 자신보다 크고 가장 자신과 가까이 있는 수를 찾는 문제이다. 2중 for문을 써서 문제를 풀 수는 있지만, 범위가 1,000,000까지이기 때문에, 시간초과가 뜰 것이다. 자신의 오른쪽을 탐색할 때, 자신보다 큰 경우가 나오면 반복을 멈추고 그 값을 넣어주면 되고, 자신보다 작은 수가 나오면, 그 값들을 스택에 저장한 뒤에 큰 수가 나오면 pop해서 큰 수를 ans에 저장하면 되겠다. 하지만 스택에 값을 push하기엔 그 값들에 따른 ans값에 저장을 해줄 수가 없기 때문에, 스택에 자신보다 작은 수가 아닌 그 수의 인덱스를 push하고 인덱스를 pop해주면 된다. ##함수 선언 부분 ##변수 선언 부분 A = [] stack = [] ans = [] top = -1 #..

옷의 종류와 개수에 따라 입을 수 있는 경우의 수를 구하는 문제이다. 알고리즘적인 문제이기보다 경우의 수를 구하는 수학 문제라고 생각하면 된다. 예를 들어, A유형의 옷이 2벌, B유형의 옷이 3벌 C유형의 옷이 1벌있다고 가정하자. 만약 A, B, C를 모두 입는 경우라면 2X3X1 = 6일 것이다. 하지만, 각각 따로 입는 경우도 있기 때문에 무작정 곱하면 안된다. A의 옷이 각각 A1,A2라고 하면 여기에 A의 옷을 입지 않는 AX를 추가하고, B와 C도 모두 각각 BX, CX를 추가하여 곱해주면, 각 옷을 입지 않는 경우도 포함한 경우가 나올 것이다. 물론 모두 입지 않은 알몸의 경우도 포함되기 때문에 1을 빼주는 것을 주의해야한다. ##함수 선언 부분## ##변수 선언 부분## ##메인 함수 부..

어떤 수로 나누었을 때 모두 나머지가 같게 되는 수를 찾는 문제이다. A를 M으로 나누었을 때 나머지를 R이라고 하면, A = M * a + R B = M * b + R C = M * c + R 위의 식이 성립한다. R을 없애기 위해 각 식을 빼보면, A - B = M(a-b) B - C = M(b-c) 위 처럼 M은 각 수의 차의 공약수이다. 각 수들의 차를 먼저 구하고 그 수들의 최대공약수를 구한 뒤에 1을 제외한 약수들을 출력해주면 된다. ##함수 선언 부분## from math import gcd ##변수 선언 부분## A = [] B = [] min = 0 min_i = 0 tmp = 0 divisor = [] ##메인 함수 부분## if __name__ == "__main__": N = int..

도시로 이동하는 동안 비용의 최솟값을 구하는 문제이다. 그리디 알고리즘의 기본적인 특성을 가지고 풀면 된다. 각 도시로 이동할 때의 최소 비용은 (기름 가격이 싼 도시의 기름 가격 * 다음 도시로 이동할 때까지의 거리의 합)이다. 그러므로 매번 도시를 이동할 때마다 가격이 싼 도시에서 기름을 최대한 넣어주면 될 것이다. 그러므로 처음부터 시작해서 기름 가격이 쌀 때마다 최솟값으로 갱신해주고 거리를 곱해서 합을 구해주면 된다. ##변수 선언 부분## road = [] price = [] road_sum = 0 sum = 0 ##메인 함수 부분## if __name__ == "__main__": N = int(input()) road = [int(x) for x in input().split()] price..

괄호를 넣어 식의 답을 최소로 만드는 문제이다. 풀이는 생각보다 간단하다. 식이 55-50+40이라하면, -를 기준으로 뒤의 값들은 그 다음 -가 나올 때 까지 모두 더해주면 된다. 다른 식들도 -를 기준으로 더해주기만 하면 되기 때문에, 나는 수를 더해주는 함수를 만들고, 첫번째 시행일 때는 sum에 더해주고, 두번째 시행부터는 -가 나오기 때문에 빼주는 식으로 코드를 짰다. 그러다보니 코드도 길고 복잡했다. ##함수 선언 부분## def Plus_calculation(e): #덧셈 식을 계산해주는 함수 num = [] sum_num = 0 length = 0 for i in range(len(e)): #받은 배열의 길이만큼 if e[i] != '+': #+가 아닐 때는 num.append(e[i]) ..

문제를 풀기 전에 이번 단계의 주제인 그리디 알고리즘에 대해 알아보자. Greedy Algorithm이란 문제를 해결하는 과정에서 그 순간마다 최적이라고 생각되는 결정을 하여 최종 해답에 도달하는 문제 해결 방식이다. 위 그림은 가장 큰 수를 찾는 문제인데, 매 순간순간마다 큰 값을 찾아나가면 엉뚱한 결과가 나온다. 다시말해, 그리디 알고리즘이 항상 전체 문제해결에서 최적의 해답을 찾지는 못한다는 것이다. 그렇다면 왜 이 알고리즘을 사용할까? 그리디 알고리즘은의 가장 큰 장점은 계산 속도에 있다. DP는 모든 경우를 탐색하지만 계산 속도가 느리고 그리디는 모든 경우를 탐색하지는 못하지만 계산 속도가 무척 빠르다. 그래서 DP와 그리디는 상호 보완하는 개념으로 알려져 있다. 또한 그리디 알고리즘은 Gree..

가치합의 최댓값을 구하는 문제이다. 흔히 배낭 문제라고 하는데, 밑은 이 배낭 문제의 알고리즘을 잘 설명해놓은 글이므로 참고해서 어떻게 구현할 지 생각해보면 좋을 것 같다. (출처:huiyu's blog) https://huiyu.tistory.com/entry/DP-01-Knapsack%EB%B0%B0%EB%82%AD-%EB%AC%B8%EC%A0%9C [DP] 0/1 Knapsack(배낭) 문제 배낭문제(Knapsack Problem)란, 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제를 말 huiyu.tistory.com 예제 입력 1을 보면 4개의 물건과 최대 무게와 각 물건의 가치를 입력..