백준

[python] 백준 - 2504. 괄호의 값

🤔문제 해결 S2 | 스택, 자료구조, 구현, 재귀 괄호문제는 항상 스택으로 풀었다. 먼저 올바른 괄호인지 체크하자! 그 다음 스택을 이용해 괄호 짝을 맞추면서 ()일 때 2, []일 때 3을 계산해준다. 만약 스택의 마지막에 숫자가 있다면 곱해준다. 만약 스택에 숫자가 연속으로 나열되면 더해준다. 💻소스 코드 def is_right(s): stack = [] for ss in s: if ss == '(': stack.append(ss) elif ss == ')': if stack and stack[-1] == '(': stack.pop() else: return False elif ss == '[': stack.append(ss) elif ss == ']': if stack and stack[-1] =..

[python] 백준 - 1890. 점프

🤔문제 해결 S2 | DP DFS로 해봤지만 역시나 시간초과!! 시간복잡도가 O(N^2) 인 DP로 풀어봤다. dp에는 현재 위치까지 올 수 있는 경우의 수를 담아서 해결함. 💻소스 코드 N = int(input()) field = [list(map(int, input().split())) for _ in range(N)] answer = 0 dp = [[0] * N for _ in range(N)] # i,j까지 올 수 있는 경우의 수를 저장 dp[0][0] = 1 for i in range(N): for j in range(N): if i == N - 1 and j == N - 1: # 끝에 도달했을 때 print(dp[i][j]) break cur_cnt = field[i][j] # 오른쪽으로 가기..

[python] 백준 - 1780. 종이의 개수

🤔문제 해결 S2 | 분할정복 첫번째에 있는 코드가 더 정답인거 같다( 둘다 통과했지만 ) 첫번째 코드는 항상 9개의 조각으로 잘라서 진행한다. - 이게 문제랑 더 맞는거 같다. 하지만 두번째 코드는 (처음 풀어서 통과하고 다시보니 이상함) 9개의 조각이 아니다. 종이가 들어오면 3x3으로 다 잘라버린다. 그래도 통과한다. 이게 되네?? 내가 문제를 잘 이해하지 못한건지... 내가 짠 코드를 이해하지 못한건지 잘 모르겠다. 💻소스 코드 from itertools import chain # 2차원 리스트를 1차원리스트로 바꿔주는 친구 def bt(paper): global a, b, c nn = len(paper) if len(set(chain.from_iterable(paper))) == 1: if pa..

[python] 백준 - 11279. 최대 힙

🤔문제 해결 S2 | 자료구조, 우선순위 큐 최대힙 자료구조를 활용하는 문제 하지만 귀찮으므로 힙큐 모듈을 사용했다. 💻소스 코드 import sys import heapq N = int(input()) numbers = [] for i in range(N): number = int(sys.stdin.readline()) if number: heapq.heappush(numbers, -number) else: if numbers: print(abs(heapq.heappop(numbers))) else: print(0) 📕문제 확인 출처: BACKJOON ONLINE JUDGE 링크: https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1≤..

[python] 백준 - 10819. 차이를 최대로

🤔문제 해결 S2 | 완전탐색 뭔가 특별한 방법이 있는거 같아서 열심히 짜봤지만 숫자가 겨우 8개 이하이므로 순열을 사용해서 해결(문제유형도 완전탐색) 경우의 수를 전부 구함 💻소스 코드 from itertools import permutations n = int(input()) numbers = list(map(int, input().split())) result = [] for permu in permutations(numbers, n): tmp = 0 for i in range(n - 1): tmp += abs(permu[i] - permu[i + 1]) result.append(tmp) print(max(result)) 📕문제 확인 출처: BACKJOON ONLINE JUDGE 링크: https:..

[python] 백준 - 1541. 잃어버린 괄호

🤔문제 해결 S2 | 수학, 그리디 요번 구현 문제의 핵심은 최초로 마이너스가 나온순간 뒤의 모든 숫자는 음수로 진행할 수 있다!! 💻소스 코드 c = input() answer = 0 c += '*' # 문제의 핵심!! 마이너스가 최초로 한번 나오는 순간 뒤의 모든 숫자들은 마이너스로 취급한다.!!! number = '' operator = '+' for i in range(len(c)): if c[i].isdigit(): number += c[i] else: if operator == '+': answer += int(number) else: answer -= int(number) if c[i] == '-': operator = '-' number = '' print(answer) 📕문제 확인 출처:..