글 작성 제목과 내용을 간결하게 정리해 주세요. 제목 내용 <h2>들어가기 전</h2><h3>순차 탐색 (Sequential Search)</h3><p>가장 기본적인 탐색 방법</p><p>리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법</p><p>보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 경우 사용</p><p>수 많은 데이터를 가진 리스트 내에 찾을 데이터가 존재하고 시간만 충분하다면 항상 원하는 데이터를 찾을 수 있음</p><p>사용하는 곳</p><ul><li>리스트 내에 특정 원소가 있는지 체크</li><li>원소의 개수 세기</li><li>등등 수많은 곳에서 순차 탐색이 이용됨</li></ul><p>시간 복잡도</p><ul><li>O(N)</li></ul><p>순차 탐색 예제 코드</p><pre><code class="language-python"># 순차 탐색 소스코드 구현 def sequential_search(n, target, arr): # 각 원소를 하나씩 확인하며 for i in range(n): # 현재 원소가 찾고자 하는 원소와 동일한 경우 if arr[i] == target: return i + 1 # 현재의 위치 반환 (인덱스 때문에 +1) print('생성할 원소 개수와 찾을 문자열을 공백으로 구분하여 입력') input_data = input().split() n = int(input_data[0]) # 원소의 개수 target = input_data[1] # 찾고자 하는 문자열 print('앞서 적은 원소 개수만큼 문자열을 공백으로 구분하여 입력') arr = input().split() # 순차 탐색 수행 결과 출력 print(sequential_search(n, target, arr) </code></pre><h3>트리(Tree) 자료 구조</h3><ul><li>노드<ul><li>정보의 단위, 어떠한 정보를 가지고 있는 개체</li><li>종류<ul><li>부모 노드<ul><li>현재 노드의 바로 위 상위 노드</li></ul></li><li>자식 노드<ul><li>현재 노드의 바로 아래 하위 노드</li></ul></li><li>루트 노드<ul><li>최상단 노드</li></ul></li><li>단말 노드<ul><li>최하단 노드</li></ul></li></ul></li></ul></li><li>서브 트리<ul><li>트리에서 일부를 때어낸 구조의 트리</li></ul></li><li>트리는 파일 시스템과 같이 계층적이고 정렬된 데이터를 다루기에 적합</li><li>큰 데이터를 처리하는 소프트웨어(데이터베이스 같은)는 대부분 데이터를 트리 형태로 저장해 이진 탐색과 같은 탐색 기법을 이용해 빠르게 탐색이 가능</li></ul><h2>이진 탐색 (Binary Search)</h2><ul><li>찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해 원하는 데이터를 찾아내는 탐색 방법</li><li>시작점, 끝점, 중간점의 위치를 나타내는 변수 3개를 사용</li><li><strong>조건</strong> : 정렬이 되어 있어야 함</li><li>시간 복잡도 : O(logN)</li></ul><h3>탐색 과정</h3><ol><li>시작점과 끝점을 확인하고 둘 사이의 중간점을 지정<ol><li>소숫점 이하는 버리는 방식으로 중간점을 지정</li></ol></li><li>중간점과 찾으려는 데이터를 비교하여<ol><li>중간점보다 크면 중간점을 시작점으로 변경</li><li>중간점보다 작으면 중간점을 끝점으로 변경</li></ol></li><li>2의 과정을 데이터를 찾을 때까지 반복</li></ol><h3>구현 방법</h3><p>구현 방법 2가지</p><p>재귀 이용</p><pre><code class="language-python"># 재귀를 통한 이진 탐색 구현 def binary_search(array, target, start, end): if start > end: # 시작점이 끝점보다 큰 경우 None반환 return None mid = (start + end) // 2 # 중간점 지정 if array[mid] == target: # 데이터를 찾은 경우 return mid # 위치 반환 elif array[mid] > target: # 더 큰 경우 return binary_search(array, target, start, mid - 1) # 끝점을 중간점 -1 로 바꾸고 재귀 elif array[mid] < target: # 더 작은 경우 return binary_search(array, target, mid + 1, end) # 시작점을 중간점 +1 로 바꾸고 재귀 # n: 원소 개수, target: 찾을 데이터 n, target = map(int, input().split()) # 전체 원소 입력 array = list(map(int, input().split())) # 결과 받아옴 (None or 중간점) result = binary_search(array, target, 0, n - 1) if result == None: print('원소가 존재하지 않습니다') else: print(result + 1) # 위치 출력 </code></pre><p>반복문을 이용</p><pre><code class="language-python"># 반복문을 통한 이진 탐색 구현 def binary_search(array, target, start, end): while start <= end: # 시작점이 끝점보다 클 때까지 반복 mid = (start + end) // 2 # 중간점 지정 if array[mid] == target: # 데이터를 찾은 경우 return mid # 위치 반환 elif array[mid] > target: # 더 큰 경우 end = mid - 1 # 끝점을 중간점 -1 로 바꿈 elif array[mid] < target: # 더 작은 경우 start = mid + 1 # 시작점을 중간점 +1 로 바꿈 # n: 원소 개수, target: 찾을 데이터 n, target = map(int, input().split()) # 전체 원소 입력 array = list(map(int, input().split())) # 결과 받아옴 (None or 중간점) result = binary_search(array, target, 0, n - 1) if result == None: print('원소가 존재하지 않습니다') else: print(result + 1) # 위치 출력 </code></pre><h3>코딩테스트에서 이진 탐색</h3><ul><li>앞의 코드를 보면 이진 탐색이 단순하다고 생각하고 넘길 수 있음</li><li>하지만 참고할 코드가 없는 상태에서 구현하는 것은 상당히 어려운 작업일 수 있음<ul><li>존 벤틀리에 의하면 이진 탐색 코드를 제대로 작성한 프로그래머는 10% 내외였다고 함</li></ul></li><li>이진 탐색은 코딩 테스트에 자주 등장함 → 코드가 길지 않아 여러번 입력해 보며 외우는 것을 추천함</li><li>높은 난이도의 문제에서 이진 탐색을 같이 사용하는 문제가 출제되기도 함</li><li>탐색 범위가 2,000만을 넘어간다면 이진 탐색으로 문제에 접근하는 편이 좋음</li><li>처리해야 할 데이터의 개수나 값이 1,000만 단위 이상으로 넘어가면 이진 탐색과 같이 O(logN)의 속도를 내야하는 알고리즘을 떠올려야 문제를 풀 수 있는 경우가 많음</li><li><strong>파라메트릭 서치(Parametric Search)</strong> 유형으로 많이 출제됨<ul><li>최적화 문제를 결정 문제로 바꾸어 해결하는 기법</li><li>원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제에 주로 사용</li><li>코딩테스트에서 파라메트릭 서치 유형은 이진 탐색을 주로 이용</li></ul></li></ul><h2>이진 탐색 트리 (Binary Search Tree)</h2><p>이진 탐색이 동작할 수 있도록 고안된, 효율적인 탐색이 가능한 자료구조</p><h3>특징</h3><ul><li>부모 노드보다 왼쪽 자식 노드가 작음</li><li>부모 노드보다 오른쪽 자식 노드가 큼</li></ul><h3>탐색 과정</h3><ol><li>루트 노드부터 시작. 찾을 데이터와 비교<ol><li>크면 오른쪽 자식 노드로 탐색</li><li>작으면 왼쪽 자식 노드로 탐색</li></ol></li><li>1의 과정을 데이터를 찾을 때까지 반복</li></ol><p>→ 구현 방법은 알고리즘보다 자료구조에 가까우며 이진 탐색 트리 구현 문제는 출제 빈도가 낮으므로 패스함</p><h2>문제 풀이</h2><h3>부품 찾기</h3><p>전자 매장에 부품이 N개 있음</p><p>각 부품은 정수 형태의 고유 번호가 있음</p><p>손님이 M개 종류의 부품을 대량으로 구매를 원함</p><p>이때 가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성하거라</p><p>입력 조건</p><ul><li>첫째 줄에 정수 N이 주어짐 (1 ≤ N ≤ 1,000,000)</li><li>둘째 줄에는 공백으로 구분하여 N개의 정수가 주어짐 (1 ≤ 정수 ≤ 1,000,000)</li><li>셋째 줄에는 정수 M이 주어짐 (1 ≤ N ≤ 100,000)</li><li>넷째 줄에는 공백으로 구분하여 M개의 정수가 주어짐 (1 ≤ 정수 ≤ 1,000,000)</li></ul><p>출력 조건</p><ul><li>첫째 줄에 공백으로 구분하여 각 부품이 존재하면 yes, 없으면 no를 출력</li></ul><p>입력 예시</p><pre><code class="language-plaintext">5 8 3 7 9 2 3 5 7 9 </code></pre><p>출력 예시</p><pre><code class="language-plaintext">no yes yes </code></pre><p><strong>문제 풀이</strong></p><pre><code class="language-python">import sys input = sys.stdin.readline def bSearch(arr, t, s, e): while s <= e: mid = (s + e) // 2 if arr[mid] == t: return mid elif arr[mid] > t: e = mid - 1 elif arr[mid] < t: s = mid + 1 n = int(input()) parts = sorted(list(map(int, input().split()))) m = int(input()) fparts = list(map(int, input().split())) for t in fparts: result = bSearch(parts, t, 0, n - 1) if result: print('yes', end=' ') else: print('no', end=' ') </code></pre><ul><li>부품의 번호의 범위가 작으면 계수 정렬을 이용할 수도 있을 것이다</li><li>집합(Set) 자료형을 이용해 in 검사를 이용해 풀 수도 있을 것이다<ul><li>집합 자료형은 특정 데이터가 존재하는지 검사할 때 유용함</li></ul></li></ul><h3>떡볶이 떡 만들기</h3><p>요청한 떡의 총 길이가 M일 때 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구해라</p><p>입력 조건</p><ul><li>첫째 줄에 떡의 개수 N과 요청한 떡의 길이 M이 주어짐 (1 ≤ N ≤ 1,000,000 , 1 ≤ M ≤ 2,000,000,000)</li><li>둘째 줄에는 떡의 개별 높이가 주어짐. 떡의 총 합은 항상 M이상이므로, 손님은 필요한 양만큼 떡을 사갈 수 있음. 높이는 10억보다 작거나 같은 양의 정수 또는 0임</li></ul><p>출력 조건</p><ul><li>적어도 M만큼의 떡을 집에 가져가기 위해 절단기에 설정할 수 있는 높이의 최댓값을 출력</li></ul><p>입력 예시</p><pre><code class="language-plaintext">4 6 19 15 10 17 </code></pre><p>출력 예시</p><pre><code class="language-plaintext">15 </code></pre><p>문제 풀이</p><pre><code class="language-python">import sys input = sys.stdin.readline def bSearch(arr, t, s, e): result = 0 # 떡 길이가 조건을 만족할 경우 담을 변수 while s <= e: mid = (s + e) // 2 # 중간 높이 설정 rc_len = 0 # 잘린 떡의 총 길이를 저장할 변수 for i in arr: # 떡들 중에 if i > mid: # 중간 설정 높이보다 크면 rc_len += i - mid # 잘린 부분을 합함 if rc_len < t: # 떡들의 합이 조건을 만족하지 않으면 e = mid - 1 # 더 자르기 위해 중간 높이 -1을 끝 높이로 설정 elif rc_len > t: # 떡들의 합이 조건을 만족하면 s = mid + 1 # 더 최적화 된 합이 있을 수 있으므로 중간 높이 +1을 시작 높이로 설정 result = mid # 조건을 만족하므로 일단 결과에 저장 else: return mid # 최적화된 높이 일 경우 바로 리턴 return result # 반복이 끝나고 남은 값을 리턴 n, m = map(int, input().split()) rc = sorted(list(map(int, input().split()))) print(bSearch(rc, m, 0, rc[-1])) # 0부터 가장 긴 떡의 길이을 매개변수로 보냄 </code></pre><ul><li>전형적인 이진 탐색 문제</li><li><strong>파라메트릭 서치(Parametric Search)</strong> 유형<ul><li>최적화 문제를 결정 문제로 바꾸어 해결하는 기법</li><li>원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제에 주로 사용</li><li>코딩테스트에서 파라메트릭 서치 유형은 이진 탐색을 주로 이용</li></ul></li></ul><h2>금주의 문제</h2><p><a href="https://www.acmicpc.net/problem/1654">1654번: 랜선 자르기</a></p><p><a href="https://www.acmicpc.net/problem/2805">2805번: 나무 자르기</a></p><p><a href="https://www.acmicpc.net/problem/2110">2110번: 공유기 설치</a></p> 글 종류 이론 정리 알고리즘 이론에 대한 정리글입니다. 문제 풀이 알고리즘 문제 풀이입니다. 알고리즘 분류 수정 취소