알고리즘 문제풀이/백준20

• 

  [백준 12851] 숨바꼭질 2 파이썬 https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net from collections import deque N,K = map(int,input().split()) MAX = 100000+1 def bfs(N,K): visited = [0]*(MAX) visited[N] = 1 time = 0 min_time = MAX cnt= 0 q = deque([[N,time]]) while q: x,t = q.popleft.. 알고리즘 문제풀이/백준 2021. 5. 13.

• [백준 18405] 경쟁적 전염 www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net from collections import deque N,K = map(int,input().split()) mat = [list(map(int,input().split())) for i in range(N)] S,X,Y = map(int,input().split()) dx=[0,0,1,-1] dy=[1,-1,0,0] start = [] # 바이러스 종류, x,y좌표 for i i.. 알고리즘 문제풀이/백준 2021. 5. 12.

• [백준 1034] 램프 www.acmicpc.net/problem/1034 1034번: 램프 첫째 줄에 N과 M이 주어진다. N은 행의 개수이고, M은 열의 개수이다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 램프의 상태가 주어진다. 1이 켜져있는 상태이고, 0이 꺼져 www.acmicpc.net from collections import defaultdict N,M = map(int,input().split()) lamp = [] for _ in range(N): lamp.append(input()) K = int(input()) d = {} for i in lamp: if d.get(i): d[i][0]+=1 else: #존재 안하면 "01" : [총 개수, 0의 수 ] cnt = i.coun.. 알고리즘 문제풀이/백준 2021. 5. 12.

• [백준 1027] 고층 건물 www.acmicpc.net/problem/1027 1027번: 고층 건물 세준시에는 고층 빌딩이 많다. 세준시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다. i번째 빌딩 (1부터 시작) www.acmicpc.net N = int(input()) bd= list(map(int,input().split())) def left_view(i): line = 10000000000 view = 0 cur_idx = i-1 while cur_idx >= 0: dx = i-cur_idx dy = bd[i] - bd[cur_idx] dydx = dy/dx if dydx < line: view+=1 line = dydx cur_idx-=1.. 알고리즘 문제풀이/백준 2021. 5. 12.

• [백준 1004] 어린왕자 www.acmicpc.net/problem/1004 1004번: 어린 왕자 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 첫째 줄에 출발점 (x1, y1)과 도착점 (x2, y2)이 주어진다. 두 번째 줄에는 행성계의 개수 n이 주 www.acmicpc.net import sys import math from collections import deque input = sys.stdin.readline T = int(input()) def is_in(p,x,y): cx,cy,r = p len_x = abs(x-cx) len_y = abs(y-cy) rg = math.sqrt(len_x**2 + len_y**2) if rg 알고리즘 문제풀이/백준 2021. 5. 12.

• [백준 15954] 인형들 www.acmicpc.net/problem/15954 15954번: 인형들 첫 번째부터 세 번째까지의 인형을 선택하면 표준편차는 2/3의 양의 제곱근이 되고, 이 때 표준편차가 최소가 된다. 두 번째부터 네 번째까지의 인형을 선택하는 경우와, 세 번째부터 다섯 번째 www.acmicpc.net from decimal import Decimal N, K = map(int, input().split()) arr = list(map(int,input().split())) sums = [0 for i in range(N+1)] exps = [0 for i in range(N+1)] for i in range(1, len(arr)+1): sums[i] = sums[i-1] + arr[i-1] exps[i] = e.. 알고리즘 문제풀이/백준 2021. 5. 11.

• [백준 1188] 음식 평론가 www.acmicpc.net/problem/1188 1188번: 음식 평론가 첫째 줄에 소시지의 수 N과 평론가의 수 M이 주어진다. (1 ≤ N, M ≤ 100) www.acmicpc.net import math N,M = map(int,input().split()) gcd = math.gcd(N,M) print(M-gcd) 풀이 소시지를 하나로 다 이어붙인다면 n=1일 때 m-1번 잘라야 같은 크기의 소시지로 나눠진다. N,M의 최대공약수를 구하면 [최대공약수-1]이 소시지를 이어붙였을 때 이미 잘려있는 횟수가 된다. 최악의 경우 최대공약수가 1일때 이미 잘려있는 수는 0회 이므로 m-1 이 답이된다. 즉 M - gcd(N,M) 가 답이다. 시간복잡도 유클리드 호제법을 사용한다면 비교대상의 두 수 a.. 알고리즘 문제풀이/백준 2021. 5. 11.

• [백준 17218] ⚾ www.acmicpc.net/problem/17281 17281번: ⚾ ⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종 www.acmicpc.net import itertools,sys input = sys.stdin.readline arr = [1,2,3,4,5,6,7,8] p = itertools.permutations(arr, 8) N = int(input()) mat = [list(map(int,input().split())) for i in range(N)] def game(start,t,arr): out = 0 score = 0 b1,b2,b3 = 0.. 알고리즘 문제풀이/백준 2021. 5. 7.

• [백준 1013] Contact import sys input = sys.stdin.readline T = int(input()) for _ in range(T): code = input().rstrip() l = len(code) i = 0 ch = True while i < l : # 시작이 0인경우 바로 뒤에 1이 안오면 실패 if code[i] == "0": #남은 수가 2개가 안될 때 실패(01이 최소 길이기 때문) if l-i < 2: ch=False break elif code[i+1] != "1": ch=False break else: i+=2 # 시작이 1이 올경우 else: #남은 수가 4개가 안될 때 실패(1001이 최소 길이기 때문) if l-i < 4: ch=False break # 다음 2개가 0이 아닐결우 실.. 알고리즘 문제풀이/백준 2021. 5. 7.

• [백준 2257] 화학식량 www.acmicpc.net/problem/2257 2257번: 화학식량 첫째 줄에 화학식이 주어진다. 화학식은 H, C, O, (, ), 2, 3, 4, 5, 6, 7, 8, 9만으로 이루어진 문자열이며, 그 길이는 100을 넘지 않는다. www.acmicpc.net s = input() d = { "H" : 1, "C" : 12, "O" : 16 } stack = [] for i in s: if i in d: stack.append(d[i]) elif i == "(": stack.append(i) elif i == ")": temp = 0 while True: p = stack.pop() if p == "(": break temp += p if temp == 0: continue else: stack.. 알고리즘 문제풀이/백준 2021. 5. 7.

• [백준 5347] LCM (최소공배수) www.acmicpc.net/problem/5347 5347번: LCM 첫째 줄에 테스트 케이스의 개수 n이 주어진다. 다음 n개 줄에는 a와 b가 주어진다. a와 b사이에는 공백이 하나 이상 있다. 두 수는 백만보다 작거나 같은 자연수이다. www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class BJ5347 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in).. 알고리즘 문제풀이/백준 2021. 5. 7.

• [백준 10610] 30 www.acmicpc.net/problem/10610 10610번: 30 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한 www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Comparator; public class BJ10610 { public static void main(String[] args) throws IOException { Bu.. 알고리즘 문제풀이/백준 2021. 5. 5.