본문 바로가기

분류 전체보기

 (257)
파이썬) 차집합 - BOJ https://www.acmicpc.net/problem/1822 1822번: 차집합 첫째 줄에는 집합 A의 원소의 개수 n(A)와 집합 B의 원소의 개수 n(B)가 빈 칸을 사이에 두고 주어진다. (1 ≤ n(A), n(B) ≤ 500,000)이 주어진다. 둘째 줄에는 집합 A의 원소가, 셋째 줄에는 집합 B의 원소 www.acmicpc.net 이문제는 이분탐색으로 분류된 문제였다. 그래서 이분탐색으로 풀어봤다. na, nb = map(int, input().split()) a = list(map(int, input().split())) b = list(map(int, input().split())) b.sort() answer = 0 for target in a: temp = False start =..
파이썬) 상자넣기 - BOJ https://www.acmicpc.net/problem/1965 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 www.acmicpc.net 이 문제는 "가장 긴 증가하는 부분 수열2"문제와 똑같은 문제이다. 현재 인덱스 i보다 크면서 인덱스 i에 해당하는 숫자보다 큰 숫자를 찾아야하는 문제이다. from bisect import bisect_left n = int(input()) arr = list(map(int, input().split())) dp = [] for i in range(len(arr)): if not dp or dp[-1] ..
파이썬) 파도반 수열 - BOJ https://www.acmicpc.net/status?user_id=dlwnsgml203&problem_id=9461&from_mine=1 t = int(input()) for _ in range(t): dp = [0, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9] n = int(input()) if n
파이썬) 계단 오르기 - BOJ https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 이 문제는 알고리즘 dp문제였다. 처음 이 문제를 접했을 때, 당연히 dfs로 풀 수있는 문제라 생각했고 실제로 그렇게 코드를 작성해나갔다. n = int(input()) arr = [] for _ in range(n): arr.append(int(input())) result = -1 def dfs(idx,sums,his): store = arr[idx] if idx == n -1: global result..
파이썬) 문자열 교환 - BOJ https://www.acmicpc.net/problem/1522 s = input() # 문자열 입력 a = s.count('a') # 입력된 str에서의 a의 개수 answer = float('inf') s = s + s[0:a-1] for i in range(len(s) - (a-1)): answer = min(answer, s[i:i+a].count('b')) print(answer) 문제는 연속된 b를 만들기 위해 몇 번의 교환을 해야할까?를 묻는 문제다. 바꿔말하면 문자열 s중 0번 부터 a의 개수만큼까지는 a로 가득 채워져있어야한다는 뜻이다. 이를 잘 기억해서 다음과 같이 풀어보자. 문자열이 abababababababa 라고 생각해보자. a의 개수는 8이다. 즉 aaaaaaaabbbbbbb가..
파이썬) 개미 - BOJ https://www.acmicpc.net/problem/3048 3048번: 개미 T초가 지난 후에 개미의 순서를 출력한다. 첫 번째 개미 그룹은 왼쪽에서 오른쪽으로 움직이고, 두 번째 그룹은 반대 방향으로 움직인다. www.acmicpc.net 이 문제는 좀 어려웠다. 우선 처음 작성한 코드를 보자 n1, n2 = map(int, input().split()) a = input() a = a[::-1] # a = '' b = input() t = int(input()) dic = {} dic2 = {} k = 0 m = min(len(b), len(a)) for i in range(len(a)): dic[a[i]] = k k += 1 for i in range(len(b)): dic2[b[i]] = ..
파이썬) 미로 만들기 -BOJ https://www.acmicpc.net/problem/1347 n = int(input()) s = input() arr = [[0, 0]] # 동 남 서 북 0,1,2,3 x, y, d = 0, 0, 1 for i in s: if i == 'R': d = (d + 1) % 4 elif i == 'L': d = (d - 1) % 4 else: if d == 0: # 동 x = x y += 1 elif d == 1: x += 1 y = y elif d == 2: x = x y -= 1 else: x -= 1 y = y arr.append([x, y]) min_x = 0 min_y = 0 max_x = 0 max_y = 0 for i in arr: x, y = i[0], i[1] min_x = min(x..
파이썬) 로봇 청소기 - BOJ https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net import sys input = sys.stdin.readline graph = [] dr = [-1, 0, 1, 0] dc = [0, 1, 0, -1] n, m = map(int, input().split()) r, c, d = map(int, input().split()) for _ in range(n): graph.append(list(ma..

티스토리툴바