본문 바로가기

분류 전체보기

[백준 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이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성..
[백준 2798번 ] 블랙잭 (파이썬/python) 2021. 6. 15. https://www.acmicpc.net/problem/2798 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net 문제대로 구현하면 된다. n의 범위가 최대 100 까지만 가능하기때문에 3중 for문으로 n^3 의 시간복잡도를 가져도 최대 1000000번밖에 탐색 안한다. 충분히 O(N^3) 의 완전탐색으로 풀 수 있는 문제 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 import sys input = sys.stdin.readline n, ..
[백준 1002번] 터렛 (파이썬/python) 2021. 6. 15. https://www.acmicpc.net/problem/1002 1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다. www.acmicpc.net 터렛이 닿을 수 있는 거리는 중심점을 기준으로 r 만큼의 반지름을 가진 원과 같다. 따라서 두 원이 두 점에서 만날때 / 한점에서 접할떄 / 만나지 않을때를 고려해서 식을 써주면 된다. 접할떄 같은 경우 내접, 외접 두가지 케이스가 있고 만나지 않을때도 서로 의 밖에서 만나지 않는경우 혹은 큰 원 안에 작은 원이 쏙 들어가있어서 만나지 않는 경우가 있다. 잘 고려해야함! 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18..
[백준 15650번] N과 M (2) 2021. 6. 15. https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 말그대로 조합을 구하라는 문제였다. combinations 함수로 풀어도됐지만 조합 구현하는 방법을 아는건 중요하다 생각하기 때문에 직접 구현도 해보고 combinations 로도 풀어보았다. 혹시 몰라 c++로 조합과 순열 구현한 풀이도 한번 첨부해봄.. 알고리즘 공부 할때 c++로 시작했기때문에 ㅎㅎ.. https://foameraserblue.tistory.com/62?category=48..

티스토리툴바