본문 바로가기

Algorithm272

[ 파이썬(python) ] 백준 2167 - 2차원 배열의 합 📌 백준 2167 - 2차원 배열의 합 문제 설명 💡 나의 풀이 시간 복잡도를 줄여주는 구간 합(prefix_sum)으로 구하면 쉽게 풀 수 있는 문제인데, 지금까지 1차원 배열의 구간합만 해봤어서 2차원 배열 일 때 어떻게 사용해야 하는지 방법을 잘 몰랐었다. 1차원 배열에서 누적 합을 어떻게 구했었는지 한번 살펴보자. 누적 합 -> 구간 합 순서로 살펴볼 것이다. 누적 합 구하기 누적합을 구현하는 방법은 2가지가 있다. append방법과 memoization방법인데, 기억이 잘 안 난다면 다음 코드를 살펴보자. arr = [10, 20, 30, 40, 50]은 고정이다. arr = [10, 20, 30, 40, 50] # append value = 0 append_sum = [0] for i in a.. 2021. 5. 10.
[ 파이썬(python) ] 백준 1406 - 에디터 📌 백준 1406 - 에디터 문제 설명 💡 나의 풀이 어제 응시했던 2021 카카오 인턴십 온라인 코딩 테스트에서도 비슷한 문제가 나왔다. 다만 거기서는 ctl + z기능도 포함되어있어서 조금 더 어려웠던것 같다. 나중에 해설이 나오면 어떤 방식으로 접근했는지 살펴봐야겠다. 이 문제는 어떻게 풀어야 할지 정말 많이 고민했는데, 결과적으로 stack 혹은 deque를 사용하면 쉽게 풀 수 있는 문제였다. 그리고 문제에서 시간 제한이 0.3초로 주어져있어서 O(N^2)으로는 풀 수 없다. 첫 시도에서 len(s)만큼 cursor를 선언해서 풀었지만 B 명령어의 예외처리를 어떻게 해줘야할지 모르겠다. 그리고 cursor를 사용해서 insert와 remove를 사용했는데 각각 시간복잡도가 O(N)이고 입력인 명.. 2021. 5. 10.
[ 파이썬(python) ] 백준 2693 - N번째 큰 수 📍 백준 2693 - N번째 큰 수 백준 2693 - N번째 큰 수 ⚡️ 나의 풀이 N번째 큰 값을 출력하는 문제인데, 출력 지문을 다시 보면 배열 A에서 3번째 큰 값을 출력한다고 정해져 있다. 테스트 케이스만큼 반복한다. 배열을 입력받는다. 정렬한다. 앞에서 혹은 뒤에서 3번째 수를 출력한다. import sys input = sys.stdin.readline T = int(input()) for i in range(T): arr = list(map(int, input().split())) arr.sort() print(arr[-3]) 2021. 5. 7.
[ 파이썬(python) ] 백준 10866 - 덱 📌 백준 10866 - 덱 문제 설명 💡 나의 풀이 백준 10828 - 스택과 백준 18258 - 큐와 같은 유형이면서 다른 자료구조인 덱 문제다. 이번에는 이전에 공부했던 내용인 단락평가를 이용해서 문제를 풀어봤는데 코드가 조금 간결해진것 같다. 단락평가를 이용하여 코드를 짧게 구현해보는 방법도 익혀두자. import sys from collections import deque input = sys.stdin.readline def push_front(x): stack.appendleft(x) def push_back(x): stack.append(x) def pop_front(): return stack and stack.popleft() or -1 def pop_back(): return stack.. 2021. 5. 5.
[ 파이썬(python) ] 백준 18258 - 큐 📌 백준 18258 - 큐 문제 설명 💡 나의 풀이 백준 10773 - 제로 와 비슷한 문제지만 front, back의 경우 그리고 pop에서 제일 앞에 있는 정수를 빼는 경우만 생각하면 된다. 제일 앞에 있는 값을 빼낼 때에는 deque를 사용하여 실행시간을 단축시키는 것 잊지 말자! from collections import deque import sys input = sys.stdin.readline n = int(input()) stack = deque([]) def push(x): stack.append(x) def pop(): if not stack: return -1 return stack.popleft() def size(): return len(stack) def empty(): if n.. 2021. 5. 4.

티스토리툴바