알고리즘/[Python] 백준
(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..
(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 알고리..
(Python) 백준 15685번 : 드래곤 커브
출처 : https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커브의 시작 점, d는 시작 방향, g는 세대이다. (0 ≤ x, y ≤ 100, 0 ≤ d ≤ 3, 0 ≤ g ≤ 10) 입력으로 주어지는 드래곤 커브는 격자 밖으로 벗어나지 않는다. 드래곤 커브는 서로 겹칠 수 있다. 방향은 0, 1, 2, www.acmicpc.net (Python) 백준 15685번 : 드래곤 커브¶출처 : https://www.acmicpc.net/problem/156..
(Python) 백준 1120번 : 문자열
출처 : https://www.acmicpc.net/problem/1120 1120번: 문자열 길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다. 두 문자열 A와 B가 주어진다. 이때, A의 길이는 B의 길이보다 작거나 같다. 이제 A의 길이가 B의 길이와 같아질 때 까지 다음과 같은 연산을 할 수 있다. A의 앞에 아무 알파벳이나 추가한다. A의 뒤에 아무 알파벳이나 추가한다. 이때, A와 B의 길이가 같으 www.acmicpc.net (Python) 백준 1120번 : 문자열¶출처 : https://www.acmicpc.net/problem/1120 알고리즘 분..
(Python) 백준 14890번 : 경사로
출처 : https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net (Python) 백준 14890번 : 경사로¶출처 : https://www.acmicpc.net/problem/14890 알고리즘 분류 시뮬레이션 In [1]: def row_fc(x): # board 에서 특정 행,row(=x) array = set() # 경사로 업데이트 해줘야할 좌표들 모음 for y in range(N-1): ## 현재 원소와 그 다음 원소값이 동일 if board[x][y] == boa..