코딩 테스트/개념34 이진 탐색 이진 탐색 Bnary Search 데이터가 정렬되어 있는 상태에서 원하는 값을 찾아내는 알고리즘대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾음 과정1. 현재 데이터 셋의 중앙값(median) 선택2. 중앙값 > 타겟 데이터(target data) 일 때 중앙값 기준으로 왼쪽 데이터셋 선택3. 중앙값 4. 1~3 반복하다 중앙값 = 타깃 데이터(target data) 일 때 종료 그림으로 표현하면 아래와 같다. 2024. 6. 8. 소수 구하기 소수 Prime Number 1과 자기자신만 약수로 갖는 1보다 큰 자연수 소수 구하기의 핵심이론: 에라토스테네스의 체1. 구하고자 하는 소수의 범위만큼 1차원 리스트 생성2. 2부터 시작하고 현재 숫자가 지워진 상태가 아닌 경우,현재 선택된 숫자의 배수에 해당하는 수를 리스트에서 끝까지 탐색하고 제거함(** 첫 숫자는 지우지 않음!)3. 리스트의 끝까지 2 반복 후 리스트에 남아 있는 모든 수 출력 2024. 6. 2. 우선순위 큐 Method 우선순위 큐 Method Priority Queue Method 0.라이브버리 from queue import PriorityQueue 1. 우선순위 큐 생성 queue = PriorityQueue() 2. 삽입 queue.put(값) 3. 삭제 queue.get(값) ** 삭제된 원소를 return함!! 4. 정렬 기준 변경 (순위, 값)의 형태로 데이터 추가 및 제거 queue.put((1, 'Kim')) 5. 비어있는지 확인 / 채워져 있는지 확인 비어있는지 확인 queue.empty() ** 결과 True/False 채워져 있는지 확인 queue.full() ** 결과 True/False 6. 크기 확인 queue.qsize() 2024. 6. 1. 그리디 알고리즘 그리디 알고리즘 Greedy 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘 과정 1. 해 선택: 현재 상태에서 가장 최선이라고 생각되는 해를 선택 2. 적절성 검사: 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사 3. 해 검사: 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사. 만약 해결하지 못한다면 1로 돌아가 다시 검사 2024. 5. 26. BFS 너비 우선 탐색 BFS (Breadth-Frist Search) 완전 탐색 방법 중 하나 시작 노드에서 출발해서 시작 노드 기준 가장 가까운 노드를 방문하면서 탐색하는 알고리즘 - 큐 구조 이용 탐색 방식: 선입선출 (queue 이므로!) 1. BFS 시작할 노드 정한 후 사용할 자료구조 초기화하기 방문했던 노드를 다시 방문하지 않음 -> 체크리스트 필요 그래프를 인접 리스트로 표시 (탐색에 스택이 아닌 큐 이용) 2. 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입 큐에서 노드를 꺼내며 인접 노드 큐에 삽입 방문 리스트 체크 (방문 이미 완료 시 삽입하지 않음) 3. 큐 자료 구조에 값이 없을 때까지 반복하기 그림으로 표현하면 아래와 같다! 2024. 5. 19. DFS 깊이 우선 탐색 DFS (Depth-First Search) 그래프 완전 탐색 기법 중 하나 그래프의 시작 노드에서 출발해서 탐색할 한 쪽 분기를 정해서 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘 - 재귀 함수로 구현 -> 스택 오버플로 (stack overflow)에 유의!! - 스택 자료 구조 이용 한번 방문한 노드를 다시 방문하면 안되므로 노드 방문 여부를 체크할 리스트 필요 그래프는 인접 리스트로 표현 탐색 방식: 후입선출 (stack 이므로!) 1. DFS 시작 시 시작 노드를 정한 후 사용할 자료 구조 초기화하기 초기작업 - 인접 리스트로 그래프 표현하기 - 방문 리스트 초기화하기 - 시작 노드 스택에 삽입하기 2. 스택에서 노드를 꺼낸 후 꺼낸 노드.. 2024. 5. 18. 이전 1 2 3 4 5 6 다음 728x90
