본문 바로가기

알고리즘

 (158)
파이썬) 듣보잡 https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net n, m = map(int, input().split()) dic = {} arr = [] arr2 = [] for _ in range(n): arr.append(input()) for _ in range(m): arr2.append(input()) inter = list(set(arr) & set(arr2)) print(len(inter)) inter.sort() for i in inter: ..
파이썬) 차집합 - 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..

티스토리툴바