https://www.acmicpc.net/problem/10815       num_cards_count = int(input()) # 상근이가 가진 카드의 개수owned_cards = list(map(int, input().split())) # 상근이가 가진 카드 리스트query_count = int(input()) # 질문할 카드의 개수queries = list(map(int, input().split())) # 질문할 카드 리스트owned_cards.sort() # 숫자 카드 정렬low, high = 0, num_cards_count - 1 # 이진 탐색 범위 설정def binary_search(cards, low, high, target): # 이진 탐색 함수 while low

이진 탐색 (Binary search) 개념 및 구현 이진 탐색은 정렬된 리스트에서 검색 범위를 줄여 나가면서 검색 값을 찾는 알고리즘입니다. 이진 탐색은 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 검색 범위가 절반으로 줄기 때문에 속도가 빠르다는 장점이 있습니다. 동작 방식 이진 탐색 알고리즘은 리스트의 중간 값과 비교하여 검색값을 찾습니다. 중간 값을 찾아야 하기 때문에 반드시 정렬된 배열에서만 사용할 수 있습니다. 이진 탐색의 동작 방식은 다음과 같습니다. 배열의 중간 값을 가져옵니다. 중간 값과 검색 값을 비교합니다. 중간 값이 검색 값과 같다면 종료합니다. (mid = key) 중간 값보다 검색 값이 크다면 중간값 기준 배열의 오른쪽 구간을 대상으로 탐색합니다. (..

가장 오래된 정렬 알고리즘의 하나로, 삽입정렬을 보완한 알고리즘 Goal - 셸 정렬(shell sort) 알고리즘을 이해한다. - 셸 정렬(shell sort) 알고리즘을 java언어로 구현한다. - 셸 정렬(shell sort) 알고리즘의 특징 - 셸 정렬(shell sort) 알고리즘의 시간복잡도를 이해한다. 셸 정렬(shell sort) 알고리즘의 개념 요약 - ‘Donald L. Shell’이라는 사람이 제안한 방법으로, 삽입정렬을 보완한 알고리즘이다. - 삽입 정렬이 어느 정도 정렬된 배열에 대해서는 대단히 빠른 것에 착안 - 삽입 정렬의 최대 문제점: 요소들이 삽입될 때, 이웃한 위치로만 이동 - 즉, 만약 삽입되어야 할 위치가 현재 위치에서 상당히 멀리 떨어진 곳이라면 많은 이동을 해야만 ..

계수 정렬(Couting Sort)이란? 카운팅 정렬은 각 항목이 몇 개 있는지 카운트하는 정렬 기본 정렬 알고리즘과 다르게 숫자 비교 작업이 없음(카운트만 할 뿐) 자료의 범위를 알고 있으며, 정렬할 값이 정수일 때 사용 시간 복잡도: O(N+K) K = 자료 안 가장 큰 원소값 K가 작으면 문제가 없지만, K가 커질수록 무한대에 가까워질 수 있음 기본 로직 정렬할 배열(배열 A)와 카운팅한 숫자를 저장할 배열(배열 B)을 생성 배열 B의 크기는 배열 A 원소들 중 가장 큰 값 배열 B은 모든 원소 값을 0으로 설정 필요에 따라 결과를 출력할 배열을 따로 생성 배열 A를 처음부터 순회하면서 원소 값에 해당하는 배열 B의 인덱스의 원소 값 +1 결과 출력(누적 합이 필요하면 과정 추가 필요) 정리 정렬할..

알고리즘에서 시간복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 말합니다． 일반적으로 １억번의 연산을 １초의 시간으로 간주하여 예측합니다．

너비 우선 탐색이란? 너비 우선 탐색은 그래프 완전 탐색하는 방법 중 하나다. 시작 노드에서 출발해 시작노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다. 선입 선출 방식으로 탐색하므로 큐를 이용해 구현한다. 또한, BFS는 탐색 시작 노드와 가까운 노드를 우선하여 탐색하므로 목 표 노드에 도착하는 경로가 여러개일때 최단 경로를 보장한다. ❗️ BFS 알아보기 - 기능: 그래프 완전 탐색 => DFS 같음 - 특징: FIFO(선입선출), Queue 자료구조 이용 - 시간 복잡도: O(V+E) ❗️ 1. BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기 BFS도 DFS와 마찬가지로 방문했던 노드는 다시 방문하지 않으므로 방문할 노드를 체크하기 위한 배열이 필요합니다. 그래프를 인..

깊이우선 탐색이란? 깊이 우선 탐색은 그래프 완전 탐색 중 하나다. DFS는 그래프 시작노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색하는 알고리즘이다. ❗️ DFS 알아보기 - 기능: 그래프 완전 탐색 - 특징: 재귀 함수 구현, 스택(FIFO) 자료구조 이용 - 시간 복잡도: O(V+E) - 문제 유형: 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상정렬 * 깊이 우선 탐색 실제 구현 시 재귀함수를 이용하므로 스택오플로를 유의해야한다. 👉 깊이 우선 탐색의 핵심 이론 DFS는 한번 방문 한 노드를 다시 방문하므로 안되므로 노드 방문 여부를 체크할 배열이 필요하며, 그래프는 인접리스트를 표현한다. 그리고 DFS 탐색 방식은 후입선출 특성을..

탐욕 알고리즘(Greedy Algorithm)이란? Greedy는 ‘탐욕스러운, 욕심 많은’ 이란 뜻이다. 탐욕 알고리즘은 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다. 탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법이다. 탐욕 알고리즘은 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다. 하지만 탐욕 알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들이다. [..