개발 · 컴퓨터공학/알고리즘

백준 2606 바이러스 파이썬 문제풀이 (python DFS BFS)

문제 보러가기  백준 바이러스 파이썬 문제풀이이렇게 연결된 컴퓨터 그래프가 있고, 1번에 연결된 컴퓨터는 모조리 감염이다.위 그림에서는 4,7만 감염되지 않은 것이다. 그래프가 연결된 것들을 탐색해내는 문제이다. n = int(input())m = int(input())computer = [[] for _ in range(n+1)]check = [0 for _ in range(n+1)]def recur(num): check[num] = 1 for i in computer[num]: if check[i] == 0: recur(i)for i in range(m): a,b = map(int,input().split()) computer[a].append(b..

2024. 11. 6. 11:50

개발 · 컴퓨터공학/알고리즘

백준 2805 나무 자르기 파이썬 문제풀이 (python 이분탐색)

문제 보러가기 백준 나무 자르기 파이썬 문제풀이N개의 나무를 일정한 높이로 잘라서 잘려나간 나무 윗부분을 M길이 이상만큼 가져간다. 나무의 높이가 각각 있으면, 높이 H만큼 잘랐을 때 나무마다 잘리는 길이가 다를 것이고이걸 모두 합했을 때 길이 M을 만족하면서 나무를 낭비하지 않는 높이 H의 최대값을 구하는 문제이다. 그러면 높이 H를 최소길이와 최대길이 사이에서 탐색하는 문제가 된다.탐색의 시간을 줄이기 위해서 mid를 이용하는 이분탐색을 사용할 것이다. 나무 높이의 start를 s, end를 e라고 하면s=0이고, e는 가장 높은 나무의 높이이다. mid 높이를 한 번 결정하고 잘라본 다음 잘린 나무 길이들이 합을 sum이라고 하자.sum이 필요한 길이 M보다 크면 높이를 높여야하니 s를 업데이트하고..

2024. 11. 2. 11:47

개발 · 컴퓨터공학/알고리즘

백준 10815 숫자카드 파이썬 문제풀이 (python 이분탐색)

문제 보러가기 백준 숫자카드 파이썬 문제풀이이 문제는 N개의 숫자 카드들을 입력 받고 나서M개의 숫자들을 입력 받으면, 각 숫자들에 대해서숫자 카드에서 찾을 수  있는 숫자인지를 체크하는 문제이다. 로직은 단순하지만, N,M의 수가 10,000,000이기 때문에 시간이 중요한 문제이다.즉 탐색 중 시간이 덜 걸리는 이분탐색을 사용해야한다. 정답코드n = int(input())card = list(map(int,input().split()))card.sort()m = int(input())num = list(map(int, input().split()))result = []for find in num: mid = int(n / 2) start = 0 end = n-1 while sta..

2024. 10. 29. 11:44

개발 · 컴퓨터공학/알고리즘

백준 22988 재활용 캠페인 파이썬 문제풀이 (python 투포인터)

문제 보러가기  백준 재활용 캠페인 파이썬 문제풀이결국 이것도 투 포인터를 이용하는 문제인데,단순히 생각하면 합이 넘으면 두 포인터를 모두 안쪽으로 옮기고,넘지 않으면 작은 인덱스를 증가시키는 로직으로 떠올렸다. 물론 반복은 a와 b가 있을 때 a같아지거나 a>b가 되면 끝낸다. n,x = map(int, input().split())bottles = list(map(int, input().split()))a = 0b = n-1cnt = 0while a = x/2: a+=1 b-=1 cnt+=1 # 합이 안넘으면 else: a+=1print(cnt)생각대로 짰지만 틀렸다.뭔가 더 있는 모양이다.  문제를 잘못 이해했다. 두 병을 가지고 합쳐 채..

2024. 10. 28. 11:16

개발 · 컴퓨터공학/알고리즘

백준 3273 두 수의 합 파이썬 문제풀이 (python 투포인터)

문제 보러가기 백준 두 수의 합 파이썬 문제풀이n개의 수열이 있고,이 중 두 개의 합이 특정한 수 x를 만족하는 쌍이 몇 개인지 구하는 문제이다. 이 문제가 투포인터로 푼다는 것을 알고 있었기에 방법은 생각났다. i와 j 인덱스를 잡고, i=0, j=n-1 에서 출발해서 중간쪽으로 인덱스를 좁혀온다. i번째 j번째를 더해서 target 수와 같은지 비교해보고,합이 목표보다 크면 j - 1목표보다 작으면 i + 1 그리고 i i == j이거나 i > j 이면 수열이 뒤집힌 것이므로 중단한다. 정답코드n = int(input())number = list(map(int,input().split()))target = int(input())i = 0j = n-1answer = 0number.sort()while ..

2024. 10. 17. 11:03

개발 · 컴퓨터공학/알고리즘

백준 9251 LCS 파이썬 문제풀이 (python LIS, LCS)

문제 보러가기  백준 LCS 파이썬 문제풀이혼자 막 풀려고 했을 때는 아무리 생각해도 답이 나오지 않았다.   풀이를 좀 찾아보면,  끝에 있는 문자가 같으면 무조건 +1 이다. 만약 같지 않다면, 필요없는 문자들을 끝에서부터 삭제한다. 2차원의 dp table에 각 축이 비교할 두 문자열이다. 정답 코드M = list(str(input()))N = list(str(input()))dp = [[0 for _ in range(len(N) + 1)] for _ in range(len(M)+1)]for i in range(1, len(M) + 1): for j in range(1, len(N)+1): if M[i-1] == N[j-1]: dp[i][j] = dp[i-1][..

2024. 10. 15. 11:46