Study Log Study Log

https://www.acmicpc.net/problem/1920 이코테 이진 탐색 챕터의 부품 찾기 예제와 비슷해서 금방 풀 수 있던 문제였다.n 개의 정수 리스트를 set()함수로 정렬한 후 m개의 정수 리스트를 하나씩 확인하여 풀었다. # 1920 : 수 찾기 n = int(input()) n_list = set(map(int, input().split())) m = int(input()) m_list = list(map(int, input().split())) for i in m_list: # 해당 수가 존재하는 지 확인 if i in n_list: print(1) else: print(0) Uploaded by Notion2Tistory v1.1.0

https://www.acmicpc.net/problem/2110 이진 탐색으로 푸는 문제 같은데 중간점을 이용해서 공유기 개수를 세는 방법이 떠오르지 않아 구글링을 통해 해결했다. 생각하지 못했던 부분은 다음과 같다.시작점은 집들 사이의 최솟값, 끝점은 집들 사이의 최댓값으로 설정공유기 위치는 현재위치와 다음 집이 공유기 사이의 거리 이상인 곳에 설치 이 문제는 sys.readline 을 사용해서 입력값을 받지 않으면 시간 초과가 발생한다. # 2110 : 공유기 설치 import sys input = sys.stdin.readline n, c = map(int, input().split()) house = [int(input().rstrip()) for _ in range(n)] house.sort(..

https://www.acmicpc.net/problem/1072 시간 초과가 발생했던 코드# 1072 : 게임 import sys input = sys.stdin.readline x, y = map(int, input().split()) z = int((y / x) * 100) new_z = z count = 0 while z == new_z: x += 1 y += 1 new_z = int((y / x) * 100) count += 1 if new_z != z: print(count) elif x == y: print(-1) break아마 1씩 증가해서 승률을 다시 측정해서 시간 초과가 발생한 것 같다. 구글링을 해보니 이진 탐색을 통해 문제를 해결한 경우가 많았다. 찾아보니 내가 놓친 히든 케이스가 ..

https://www.acmicpc.net/problem/2512 이진 탐색을 이용해서 풀었고, 이코테의 이진탐색 챕터의 떡볶이 떡 만들기와 비슷해서 금방 풀 수 있었던 문제였다. # 2512 : 예산 import sys input = sys.stdin.readline n = int(input()) request = list(map(int, input().rstrip().split())) m = int(input()) start = 0 end = max(request) result = 0 # 상한액 while start = mid: total += mid # 요청한 예산이 상한액보다 작을 경우 else: total += x # 예산이 충분할 경우 if total

https://www.acmicpc.net/problem/2805 이 문제는 이코테 이진 탐색 챕터의 떡볶이 떡 만들기 예제와 거의 똑같아서 금방 풀었다. 최종 나무의 길이와 필요한 나무의 높이를 비교하며 start, end 위치를 조정해나가면 풀 수 있다. # 2805 : 나무 자르기 n, m = map(int, input().split()) height = list(map(int, input().split())) start, end = 0, max(height) result = 0 while start mid: total += x - mid if total < m: end = mid - 1 else: result = mid start = mid + 1 print(result) Uploaded by N..

https://www.acmicpc.net/problem/1654 이진 탐색으로 풀 수 있는 문제였다. 랜선 개수와 목표 랜선 개수를 비교해서 start 또는 end 지점을 바꿔가며 해결했다. # 1654 : 랜선 자르기 import sys input = sys.stdin.readline k, n = map(int, input().split()) lan = [int(input()) for _ in range(k)] start = 1 end = max(lan) result = 0 while start = n: result = mid start = mid + 1 # 랜선 못 만든 경우 else: end = mid - 1 print(result) Uploaded by Notion2Tistory v1.1.0

Ch7. 이진탐색 1. 순차탐색 💡 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 리스트에 특정 값의 원소가 있는지 체크할 때도 순차 탐색으로 원소를 확인 리스트 자료형에서 특정한 값을 가지는 원소의 개수를 세는 count() 메서드를 이용할 때도 내부에서는 순차 탐색이 수행 시간 복잡도 :O(N) 순차 탐색 소스코드 def sequential_search(n, target, array): # 각 원소 하나씩 확인 for i in range(n): # 현재의 원소가 찾고자 하는 원소와 동일한 경우 if array[i] == target: return i + 1 # 현재 위치 반환(인덱스는 0부터 시작하므로 1 더함) print("생성할 원소 개수를 입력한 ..

https://www.acmicpc.net/problem/20291 n = int(input()) file_dic = {} file = [input().split('.')[1] for _ in range(n)] # { 확장자명 : 파일 개수 } # 확장자(키)가 파일 딕셔너리에 존재하면 for i in file: if i in file_dic: file_dic[i] += 1 # 존재하지 않으면 딕셔너리에 추가해주기 else: file_dic[i] = 1 # 확장자와 파일 개수 둘 다 오름차순 정렬 # (첫 번째 요소, 두 번째 요소), 첫 번째 요소가 우선순위 result = dict(sorted(file_dic.items(), key = lambda x : (x[0], x[1]))) for k, v i..