알고리즘
(Python) 백준 15686번: 치킨 배달
출처 : https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다. 이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 www.acmicpc.net # Code from itertools import combinations ## 맵크기(N), 치킨집 최대 선택가능개수(M)..
(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..
(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) 백준 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..
(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..