전체 글
(Python) 백준 14500번: 테트로미노
출처 : https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누 www.acmicpc.net 정말 가능한 모든 경우에 대해서 브루트 포스하게 풀었다. # Code N, M = map(int, input().split..
![[자료구조] 힙(Heap)이란? 최대힙(Max Heap)과 최소힙(Min Heap)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FGKsdz%2FbtqCy37TvSH%2F8Ch1KjiQTmEE46C8kRohqK%2Fimg.png)
[자료구조] 힙(Heap)이란? 최대힙(Max Heap)과 최소힙(Min Heap)
힙(Heap) 최대 힙(Max Heap) 최소 힙(Min Heap) 1. 최대 힙(Max Heap) 최대 트리(Max Tree)는 각 노드의 키(Key)값이 (자식 노드가 있다면) 그 자식의 키(Key)값보다 작지 않은(=크거나 같은) 트리이다. 최대 힙(Max Heap)은 최대 트리(Max Tree)이면서 완전 이진 트리(Complete Binary Tree)이다. 2. 최소 힙(Min Heap) 최소 트리(Min Tree)는 각 노드의 키(Key)값이 (자식 노드가 있다면) 그 자식의 키(Key)값보다 크지 않은(=작거나 같은) 트리이다. 최소 힙(Min Heap)은 최소 트리(Min Tree)이면서 완전 이진 트리(Complete Binary Tree)이다. + 정리) 최대 힙(Max Heap) :..
(Python) [2019카카오공채] 후보키
출처 : https://programmers.co.kr/learn/courses/30/lessons/42890# 코딩테스트 연습 - 후보키 | 프로그래머스 [["100","ryan","music","2"],["200","apeach","math","2"],["300","tube","computer","3"],["400","con","computer","4"],["500","muzi","music","3"],["600","apeach","music","2"]] 2 programmers.co.kr # code from itertools import chain, combinations def powerset(iterable): "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2)..
(Python) 백준 13458번: 시험 감독
출처 : https://www.acmicpc.net/problem/13458 13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net (Python) 백준 13458번: 시험 감독¶출처 : https://www.acmicpc.net/problem/13458 In [19]: if __name__ == '__main__': N = int(input()) #시험장 개수 room = map(int, input().split()) # 응시 인원 수 B, C ..
(Python) 순열, 조합, 중복순열, 중복조합 쉽게 구현하기
(Python) 순열, 조합 쉽게 만들기¶결론부터 말하자면, 라이브러리에서 불러온 함수와 직접 구현한 함수가 속도차이 10배정도를 보였다. (라이브러리가 훨씬 빠름) 파이썬 documentation에서 어떻게 구현했는지 나중에 차차 확인해봐야 할 것 같다. 1. itertools를 이용하여 순열, 조합 구현하기¶ 1.1 순열(=permutations) 반복 가능한 객체(=길이가 n인)에 대해서 중복을 허용하지 않고 r개를 뽑아서 나열한다. 뽑힌 순서대로 나열하기 때문에 순서가 의미가 있다. (즉, 같은 값이 뽑히더라도 순서가 다르면 다른 경우의 수로 취급한다.) permutations(반복 가능한 객체, r) In [1]: from itertools import permutations for i in p..
(Python) 백준 12100번: 2048 (Easy)
출처 : https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다. www.acmicpc.net (Python) 백준 12100번: 2048 (Easy)¶ 출처 : https://www.acmicpc.net/problem/12100 알고리즘 분류: 브루트 포스 In [68]: import copy In [69]: ## 가장 큰 값 업데이트하기 def find_max..
(Python) 백준 15684번: 사다리 조작
출처 : https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선이 같은 위치를 갖는다. 아래 그림은 N = 5, H = 6 인 경우의 그림이고, 가로선은 없다. 초록선은 세로선을 나타내고, 초록선과 점선이 교차하는 점은 가로선을 놓을 수 있는 점이다. 가로선은 인접한 두 세로선을 연결해야 한다. 단, 두 가로선이 연속하거나 서로 www.acmicpc.net 알고리즘 분류: 브루트 포스 Python으로 제출했으나 시간초과. PyPy3로 제출해서 통과 이 문제는 시간 단축을 위해 ..
[Python/기타] 파이썬 시간 복잡도(Time Complexity)
1. 파이썬 시간 복잡도 관련 문서 출처 : https://wiki.python.org/moin/TimeComplexity TimeComplexity - Python Wiki This page documents the time-complexity (aka "Big O" or "Big Oh") of various operations in current CPython. Other Python implementations (or older or still-under development versions of CPython) may have slightly different performance characteristics. Howe wiki.python.org 2. Complexity of Python Ope..
(Python) 백준 1931번: 회의실 배정
출처 : https://www.acmicpc.net/problem/1931 1931번: 회의실배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 알고리즘 분류: 그리디 알고리즘 시간이 들쭉날쭉 나오는데 그 원인을 알고싶어서 시작했다. 입력을 어떻게 받아야 시간이 단축되는걸까? import sys N = int(input()) meeting = [] for i in range(N): start,end = map(int,sys.stdin.readline().split()) meeting.append((start,end)) meeting = sorted(meeting, key=lambda time : time[0]) meeting = sorted(mee..
티스토리 코드 예쁘게 삽입하기 - Color Scripter
필자는 Squared 스킨을 애용하고 있다. 다만 이 스킨을 사용할 경우, 코드블럭을 사용할 때 불필요한 테두리가 생기는데 맘에 들지 않아서 다른 방법을 찾고 있던 와중에 Color Scripter를 알게 됐다. 주소 : https://colorscripter.com/ Color Scripter Simple & Flexible Syntax HighLighter colorscripter.com 위처럼 Color Scripter에 들어가서 코드를 옮기면 언어와 스타일에 맞춰서 코드가 꾸며진다. 세부설정에서 줄번호 복사를 체크 해제 할 경우, 블로그에 옮겼을 때 왼쪽 번호들이 제거된채로 포스팅이 된다. Color Scripter에서 HTML로 복사를 선택하여 복사한다. 티스토리 글쓰기에서 Html 모드로 전환..
(Python) 백준 14501번: 퇴사
출처 : https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net (Python) 백준 14501번: 퇴사¶출처 : https://www.acmicpc.net/problem/14501 알고리즘 분류: 브루트 포스 다이나믹 프로그래밍 In [1]: def dfs(t, p): global maxv if t == N+1: if maxv
(Python) 백준 11559번: Puyo Puyo
출처 : https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 현재 주어진 상황에서 몇연쇄가 되는지 출력하라. (하나도 터지지 않는다면 0을 출력하면 된다.) www.acmicpc.net (Python) 백준 11559번: Puyo Puyo¶출처 : https://www.acmicpc.net/problem/11559 알고리즘 분류 BFS DFS 시뮬레이션 In [1]: from collections import deque In [2]: def bfs(x, y, color): same_color = set() queue = deque() queue.append((x,y)) while queue: node = queue.popleft() if node in sa..
(Python) 백준 2979번: 트럭 주차
출처 : https://www.acmicpc.net/problem/2979 2979번: 트럭 주차 문제 상근이는 트럭을 총 세 대 가지고 있다. 오늘은 트럭을 주차하는데 비용이 얼마나 필요한지 알아보려고 한다. 상근이가 이용하는 주차장은 주차하는 트럭의 수에 따라서 주차 요금을 할인해 준다. 트럭을 한 대 주차할 때는 1분에 한 대당 A원을 내야 한다. 두 대를 주차할 때는 1분에 한 대당 B원, 세 대를 주차할 때는 1분에 한 대당 C원을 내야 한다. A, B, C가 주어지고, 상근이의 트럭이 주차장에 주차된 시간이 주어졌을 때, 주차 요금으로 얼마 www.acmicpc.net (Python) 백준 2979번: 트럭주차¶출처 : https://www.acmicpc.net/problem/2979 알고리즘..
(Python) 백준 2161번: 카드 1
출처 : https://www.acmicpc.net/problem/2161 2161번: 카드1 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다. 예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리 www.acmicpc.net (Python) 백준 2161번: 카드1¶출처 : https://www.acmicpc.net/problem/2161 알고리즘 분류..
(Python) 백준 5532번: 방학 숙제
출처 : https://www.acmicpc.net/problem/5532 5532번: 방학 숙제 문제 상근이는 초등학교에 다닐 때, 방학 숙제를 남들보다 먼저 미리 하고 남은 기간을 놀았다. 방학 숙제는 수학과 국어 문제 풀기이다. 방학은 총 L일이다. 수학은 총 B페이지, 국어는 총 A페이지를 풀어야 한다. 상근이는 하루에 국어를 최대 C페이지, 수학을 최대 D페이지 풀 수 있다. 상근이가 겨울 방학동안 숙제를 하지 않고 놀 수 있는 최대 날의 수를 구하는 프로그램을 작성하시오. 입력 한 줄에 하나씩 총 다섯 줄에 걸쳐 L, A, B, C, D가 www.acmicpc.net (Python) 백준 5532번 : 방학 숙제¶출처 : https://www.acmicpc.net/problem/5532 알고리..