공부 기록

✏️ 문제문제 파악이 문제는 이분 탐색을 써서 풀 때 함수를 안쓰면 시간 초과가 뜬다 .. (나만 그런가) 그리고 출력이 수첩2에 있는 숫자를 기준으로 1, 0 출력이 되므로 수첩2는 정렬하면 안된다. 수첩1을 정렬하고 수첩1의 요소를 가지고 이분 탐색을 하면 쉽게 풀 수있다. 알고리즘자료 구조정렬이분 탐색해시를 사용한 집합과 맵  코드import sysinput = sys.stdin.readlinedef bs(start, end, note1, i): while start note2[i]: end = mid - 1 else: start = mid + 1 return 0 for _ in range(int(input())): n = int(input()) ..

✏️ 문제 문제 파악처음에는 a 배열을 기준으로 이분 탐색을 하려했는데 생각해보니 a 배열의 각 요소가 b 배열의 요소보다 큰 지 안 큰 지에 대해서 정답을 구하는 것이므로 b 배열을 기준으로 이분 탐색을 하는 것이 맞다!이분 탐색을 하기 위해선 배열이 정렬되어 있어야한다. 위의 예시를 보면 쌍의 개수는 b 배열의 인덱스+1 한 값과 같다는 걸 알 수 있다.while ... if b[mid]  또한 큰 쌍의 개수를 구하므로 end + 1을 해주어야 한다. 알고리즘두 포인터정렬이분 탐색  코드for _ in range(int(input())): n,m = map(int, input().split()) a = sorted(list(map(int, input().split()))) b = sorted..

✏️ 문제 문제 파악이분 탐색을 사용해야 하는 거의 대표적인 문제!!!!!이분 탐색을 안 사용하면 보통.. 아니 대개 "시간 초과" 가 뜬다... ^^ 알고리즘이분 탐색매개 변수 탐색 코드n, m = map(int, input().split()) trees = list(map(int, input().split())) def binary_search(trees, target): left, right = 0, max(trees) while left mid: total += h - mid if total     ⭐️ 이분 / 이진 탐색에 대해 잘 모른다면?2024.07.25 - [알고리즘] - [알고리즘] 이분 / 이진 탐색 (Binary Search) 알고리즘

이분 / 이진 탐색 (Binary Search) ?정렬된 리스트에서 특정 값을 찾는 데 사용되는 효율적인 알고리즘이다. 리스트의 중앙값과 목표 값을 비교하여 목표 값이 중앙값보다 작으면 리스트의 왼쪽 절반을 탐색하고 크면 리스트의 오른쪽 절반을 탐색하는 방식으로 진행된다. 이렇게 계속해서 리스트를 반씩 줄여 나가면서 값을 찾는다.  이분 / 이진 탐색 알고리즘의 단계초기화: 리스트의 처음과 끝 인덱스 설정반복 또는 재귀: 중앙값을 계산하고 이 값을 목표 값과 비교값 비교:목표 값 = 중앙값 → 해당 인덱스 반환목표 값 목표 값이 > 중앙값 → 리스트의 오른쪽 절반 탐색반복 종료: 리스트의 탐색 범위가 0이 되면 목표 값이 리스트에 없는 것으로 간주하고 탐색 종료 이분 / 이진 탐색 알고리즘의 시간 복잡도..

✏️ 문제 문제 파악양이 적은 에너지 드링크를 버리는 방향으로 하는 게 최대의 에너지 드링크 양을 만들 수 있다.그래서 에너지 드링크를 담은 배열을 오름차순 정렬한 후 마지막에 있는 양이 제일 많은 에너지 드링크를 버리지 않는 에너지 드링크로 해서 풀면 쉽게 풀 수있다. 알고리즘그리디 알고리즘 코드n = int(input())drinks = list(map(int, input().split()))drinks.sort()total = drinks[n-1]for i in range(n-1): total += drinks[i]/2print(total)

✏️ 문제 문제 파악주파수 A에서 B로 가기 위해서 버튼을 누르는 경우는 다음과 같이 2가지가 있다.주파수 A에서 1MHz 단위로 B로 가는 방법: 버튼수 = abs(A-B)주파수 A에서 미리 지정된 주파수로 간 후 B로 가는 방법: 버튼수 = abs((미리 지정된 주파수)-B)+1(여기서 +1 은 미리 지정된 주파수로 가는 버튼수) 알고리즘그리디 알고리즘수학 코드a,b = map(int, input().split())n = int(input())freq = []freq.append(abs(a-b))for i in range(n): freq.append(abs(int(input())-b)+1)print(min(freq))

✏️ 문제 문제 파악정렬(어떤 정렬이든 상관 X)을 한 후에 앞에서 1번인 학생과 뒤에서 1번인 학생이 한 그룹이 된다고 생각하면 쉽게 풀 수 있다.  알고리즘그리디 알고리즘정렬 코드n = int(input())student = list(map(int, input().split()))student.sort()group = []for i in range(n): group.append(student[i] + student[len(student)-i-1])print(min(group))

✏️ 문제 문제 파악작업은 두 가지가 있다.배치된 말 중 임의의 2개의 말을 골라 서로의 위치를 바꾼다.말 1개를 들어 뒤집어 놓아 색상을 변경한다. 나는 다음과 같이 풀었다. if 같은 위치에 있는 문자가 다르다면 if 처음이라면 save 변수 = 초기 상태 문자열의 해당 문자를 저장 else 처음이 아니라면 2번 작업을 해야 하므로 작업 횟수 +1 save 변수 초기화else 같은 위치에 있는 문자가 같다면 if 같은 데 save 변수에 저장되어 있는 값이 있다면 1번 작업을 해야 하므로 작업 횟수 +1 save 변수 초기화근데 자꾸 틀렸다고 나와서ㅠ 결국 못풀었다.. 반례가 뭘까...,.,.?다른 분들 푼 걸 보니 다른 수가 많은 문자의 개수가 정답이 된다는 점을 가지고 푸셨었다. 알고..

✏️ 문제 문제 파악나는 다음과 같이 풀었다. m의 값을 어딘가(max_m)에 저장if 책의 무게 최대 무게 최대 무게 = max_m 상자를 새로 사용해야 하므로 상자 개수 +1if 최대 무게 == 0 최대 무게 = max_m예제로 있던 문제는 다 잘나오는데 제출하면 1%에서 계속 틀렸었다.. 반례...다른 분은 현재 박스에 넣어져 있는 무게 + 넣을 책의 무게를 최대 무게와 비교하며 풀었었다.알고리즘은 이게 더 간편한 듯! 알고리즘그리디 알고리즘구현  코드내가 푼 틀린 코드n,m = map(int, input().split())box = 0if n != 0: book = list(map(int, input().split())) max_m = m for i in range(n): if ..

✏️ 문제 문제 파악나는 먼저 정렬을 한 후 제일 처음에 온 소는 무조건 프리패스니까 소요시간에 먼저 더해줬다.그 후에는 두 가지 경우로 나눠서 생각했다. 처음에 온 소가 검문이 끝난 시간 T을 기준으로 T  다음 소의 도착 시간이라면 다음 소의 도착 시간까지 소요시간이 되어야 하므로→ 소요시간 += (다음 소의 도착 시간 - 소요시간) + 다음 소의 검문 시간T > 다음 소의 도착 시간이라면 다음 소가 바로 검문 받을 수 있으므로→ 소요시간 += 다음 소의 검문 시간로 나눠서 푸니 해결했다! 알고리즘그리디 알고리즘정렬 코드import sysinput = sys.stdin.readlinen = int(input())line = []for i in range(n): line.append(list(map(..