본문 바로가기

PS/백준

[백준 12015번] 가장 긴 증가하는 부분 수열 2 (파이썬/python) 2021. 6. 16. https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net LIS 문제는 종만북에서 보고 까먹을라 하니까 만나서 복습하는 좋은 기회가 됐다. DP를 사용하지만 거기에 추가로 탐색절차에 이진탐색(lower bound)를 추가한다. https://namu.wiki/w/%EC%B5%9C%EC%9E%A5%20%EC%A6%9D%EA%B0%80%20%EB%B6%80%EB%B6%84%20%EC%88%98%EC%97%B4 생각보다 나무위키에 정리가 잘 돼있다 ㅋㅋㅋ 저..
[백준 12865번] 평범한 배낭 (파이썬/python) 2021. 6. 16. 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 https://suri78.tistory.com/2 [백준알고리즘] 12865번: 평범한 배낭 -Python [백준알고리즘] 12865번: 평범한 배낭 -Python https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무..
[백준 2110번 ] 공유기 설치 (파이썬/python) 2021. 6. 15. https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 공유기 사이의 거리를 mid 값으로 준 후에 산출된 공유기의 갯수에 따라 start 나 end의 값을 증가시키거나 감소시키며 이분탐색한다. 목표 공유기 갯수인 c개보다 같거나 많이 설치했을때 가장 인접한 공유기 사이의 거리가 최대가 되도록 하면된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 ..
[백준 11279번] 최대 힙 (파이썬/python) 2021. 6. 15. https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net 파이썬의 heapq 라는 자료구조를 이용해 우선순위 큐 최대힙을 사용하면 되는 문제였다. https://velog.io/@janeljs/python-for-coding-test-6 코딩테스트를 위한 파이썬 문법 (6) (heapq, heap sort, min heap) 힙 정렬(heap sort) 힙 정렬은 max heap이나 min heap 트리를 이용한 정렬 방식으로 내림차..
[백준 2606번] 바이러스 (파이썬/python) 2021. 6. 15. https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 기초적인 bfs/dfs 문제. 둘 중 뭘 써도 상관 없는데 나는 파이썬 큐 자료구조를 이용해보고싶어서 bfs로 풀었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 import sys from collections import deque input = sys.stdin.readlin..
[백준 11399번] ATM (파이썬/python) 2021. 6. 15. https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 그리디~ 하게 걸리는 시간을 오름차순으로 정렬한 후에 앞에서 부터 문제 조건에 맞게 시간을 합해주면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 import sys from collections import deque input = sys.stdin.readline n = int(input()) arr = list(map(int, input().split())) arr = sorted(ar..
[백준 11866번] 요세푸스 문제 0 (파이썬/python) 2021. 6. 15. https://www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net 큐를 이용해서 빼고 넣기를 반복하다가 k번째 차례가 오면 빼고 넣지않기를 하면되는 문제. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 import sys from collections import deque input = sys.stdin.readline n, k = map(int, input().split()) q = deque(range(1, n + 1)) result = "" print(result) Colored by Color..
[백준 1541번] 잃어버린 괄호 (파이썬/python) 2021. 6. 15. https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 그리디 알고리즘으로 접근하면 좋은 문제 최소값을 출력해야하기 때문에 +연산을 먼저 다 진행해준다. 그 후 -연산을 수행하면 깔끔하게 최소값으로 출력된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 import sys input sys.stdin.readline str1 = input() # - 단위로 쪼개줌 str1 = str1..
[백준 9663번] N-Queen (파이썬/python) 2021. 6. 15. https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 와 이거 빡샜다.. 이거 혼자 못 풀고 다른 블로그 참고했음 근데 거기 코드 하나 빠진거있음!!!! pop()을 안 넣었음!! https://geonlee.tistory.com/40 [BOJ] 👸 N-Queens / 파이썬 👸 N-Queens 문제 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성..

티스토리툴바