728x90 ALGORITHM/BAEKJOON42 [BOJ/Python] 12865. 평범한 배낭 📌 문제 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 📌 문제 접근 방법 처음에는 가치가 큰 물건 별로 우선적으로 배낭에 넣는 방식으로 구현해보았으나 시간초과! 결국 구글링을 해보니 Knapsack Algorithm을 사용해야 하는 것이었다. 인덱스 에러가 나지 않도록 0번째 줄을 포함해서 2차원 배열을 생성한다. i 번째 물건을 가방에 넣었을 때 / 넣지 않았을 때의 최대 .. 2021. 10. 4. [BOJ/Python] 20437. 문자열 게임 2 📌 문제 https://www.acmicpc.net/problem/20437 20437번: 문자열 게임 2 첫 번째 문자열에서 3번에서 구한 문자열은 aqua, 4번에서 구한 문자열은 raquator이다. 두 번째 문자열에서는 어떤 문자가 5개 포함된 문자열을 찾을 수 없으므로 -1을 출력한다. www.acmicpc.net 📌 문제 접근 방법 defaultdict 진짜 편하다! alpha = defaultdict(list) : 이런 식으로 괄호 안에 값의 초기값 형태를 지정해주면 된다! 딕셔너리의 키가 없어도 바로 값을 저장할 수 있다. 📌 코드 import sys from collections import defaultdict ''' superaquatornado 2 ''' def string_game.. 2021. 8. 28. [BOJ/Python] 17298. 오큰수 📌 문제 https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 📌 문제 접근 방법 스택을 활용해서 풀이해보았다. 오큰수가 존재하지 않으면 -1을 입력하기 때문에 answer의 초기값을 -1로 설정했다. 스택에 값을 넣고 스택에 들어있는 값보다 큰 값이 들어오면 그 값보다 작은 값을 스택에서 모두 빼낸다. 예시로 수열 3 5 2 7 을 순회한다면, i = 0 / 수열의 해당 값 = 3 스택이 비어있으므로 3과 3의 인덱스를 각각 스택에 넣는다. 현재 answer.. 2021. 8. 28. [BOJ/Python] 1541. 잃어버린 괄호 📌 문제 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 📌 문제 접근 방법 처음엔 내가 직접 수식을 풀 듯이 괄호를 넣어주기 위해 따로 temp리스트에 저장해서 계산하는 코드를 구현했었는데, 생각해보니 더 간단하게 표현할 수 있었다. 어쨌든 최소가 되기 위해서는 -가 많아야 한다. 그래서 첫 번째 -가 나온 이후로는 부호를 따질 것 없이 모든 숫자를 다 마이너스 해주면 된다! (어차피 괄호를 삽입하면 모든 숫자를 다 마이너스할 수 있으므.. 2021. 8. 28. 이전 1 ··· 5 6 7 8 9 10 11 다음 728x90
