본문 바로가기

알고리즘

 (94)
파이썬 | 백준 | 1365 | 꼬인 전깃줄 | LIS(최장 증가 수열) solution 1. LIS(최장 증가 수열) 이용 # 1365, 꼬인 전깃줄 import sys # 해당 숫자 이상의 수 중 가장 가까운 인덱스를 리턴하는 함수 ( 정렬이 되어있을 때만 가능 ) def lower_bound(s, e, v): while s < e: m = (s + e) // 2 if res[m] < v: s = m + 1 else: e = m return e n = int(sys.stdin.readline()) line = list(map(int, sys.stdin.readline().split())) res = [] for i in range(n): if i == 0: # 첫 번째 수는 res에 추가 res.append(line[0]) if res[-1] < line[i]: # lin..
파이썬 | 백준 | 5567 | 결혼식 solution 친구의 친구 : 두 학번 사이의 거리가 2 이내여야 한다. # 5567, 결혼식 import sys from collections import deque def bfs(x): visited = [0] * n visited[x] = 1 q.append(x) while q: x = q.popleft() for i in friends[x]: if not visited[i]: visited[i] = visited[x] + 1 q.append(i) return visited n = int(sys.stdin.readline()) m = int(sys.stdin.readline()) friends = [[] for _ in range(n)] for _ in range(m): a, b = map(int..
파이썬 | 백준 | 15650 | N과 M(2) | lst = range(1, n+1) solution 1. 조합 이용 2. lst = range(1, n+1) # 15650, N과 M(2) import sys from itertools import combinations n, m = map(int, sys.stdin.readline().split()) lst = range(1, n + 1) res = list(combinations(lst, m)) for res_ in res: print(*res_) 29380KB 60ms 문제 출처 https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순..
파이썬 | 백준 | 14888 | 연산자 끼워넣기 solution 1. 순열(permutations) 이용해 연산자의 순서 리스트를 만듦 2. set()으로 중복 제거 # 14888, 연산자 끼워넣기 import sys from itertools import permutations N = int(sys.stdin.readline().rstrip()) num = list(map(int, sys.stdin.readline().split())) arr = list(map(int, sys.stdin.readline().split())) operator = [] for i in range(4): for j in range(arr[i]): operator.append(i) op = list(permutations(operator)) max_ = -100000000..
파이썬 | 백준 | 15686 | 치킨 배달 | 조합(combinations) solution 1. 조합을 이용해 전체 치킨집에서 M개 선택 2. 집에서 치킨거리를 각각 구해 최소가 되는 조합을 구함 # 15686, 치킨 배달 import sys from itertools import combinations def getDistance(x, y): min_ = 100 for i in range(len(y)): min_ = min(min_, abs(y[i][0]-x[0])+abs(y[i][1]-x[1])) return min_ N, M = map(int, sys.stdin.readline().split()) city = [list(map(int, sys.stdin.readline().split())) for _ in range(N)] home = [] chicken = [] for ..
파이썬 | 백준 | 1543 | 문서 검색 solution 1 : replace() 이용 1. 문서에서 검색하려는 단어를 탐색해 특정 문자(*) 로 대체 2. 문서에서 * 갯수 출력 # 1543, 문서 검색 import sys s1 = sys.stdin.readline().rstrip() s2 = sys.stdin.readline().rstrip() s1 = s1.replace(s2, '*') cnt = 0 for ch in s1: if ch == '*': cnt += 1 print(cnt) 29380KB 60ms solutoin 2 : count ()이용 # 1543, 문서 검색 import sys s1 = sys.stdin.readline().rstrip() s2 = sys.stdin.readline().rstrip() print(s1.cou..
파이썬 | 백준 | 2503 | 숫자 야구 | 순열(permutations) solution 1. 순열(permutations) 이용 2. int는 list() 불가능 → list(str(x)) # 2503, 숫자 야구 import sys from itertools import permutations n = [1, 2, 3, 4, 5, 6, 7, 8, 9] num = list(permutations(n, 3))# 순열로 3개씩 뽑음 t = int(sys.stdin.readline()) for _ in range(t): test, s, b = map(int, sys.stdin.readline().split()) test = list(str(test)) removed_cnt = 0 # 배열에서 제거된 튜플 개수 # num : 3개 리스트 leng = len(num) for i in ..
파이썬 | 백준 | 4949 | 균형잡힌 세상 solution 1. 스택 이용 # 4949, 균형잡힌 세상 import sys txt = [] # 문자열 입력 while True: str = sys.stdin.readline().rstrip() if str == '.': break txt.append(str) ans = [] # yes, no 저장할 배열 for txt_ in txt: check = 1 # 균형 잡힌 문자열이면 1 stack = [] for i in txt_: if i == '(': stack.append('(') elif i == ')': if len(stack) == 0 or stack[-1] != '(': check = 0 # 균형 잡힌 문자열 X break else: stack.pop() elif i == '[': stack...

티스토리툴바