STUDY/Algorithm

이분 탐색 알고리즘순차탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서 부터 데이터를 하나씩 확인하는 방법 이진탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색범위를 설정합니다. 단계마다 탐색범위를 2로 나누는 것과 동일하므로 연산횟수는 $log_2 N$에 비례합니다. 다시 말해, 이진 탐색은 탐색범위를 절반씩 줄이며, 시간 복잡도는  $O(log_2 N)$ 을 보장합니다.  이진탐색 소스코드 : 재귀적 구현 def binary_search(arr , target , start , end) : if start > end : return None mid = (start + end) // 2 ..

https://www.acmicpc.net/problem/18008  모스부호는 점(dot)과 대시(dash) 기호의 배열을 알파벳 문자에 할당한 것이다. 모스 부호의 배열을 다시 지정하여 주어진 메세지가장 짧은 길이를 반환하도록 해라.  dot : 1 dash : 3 기호 사이 간격: 1 문자 사이 간격: 3  단, 공백, 구두점, 알파벳 대소문자는 무시된다.   💡해결한 아이디어  가장 짧은 길이를 반환하기 위해서는 "빈도수가 높을 수록 작은 길이의 모스부호 배열을 할당" 해야 한다는 것이다.   1. 주어진 메세지가 알파벳인지 확인. 만일 알파벳이라면 대문자 변환한 다음 공백 제거  s = input() filter_s = "".join([char.upper() for char in s if s...

그래프 탐색 알고리즘 : DFS / BFS  탐색(Search)란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말한다.대표적인 그래프 탐색 알고리즘으로는 DFS 와 BFS가 있다. 스택과 큐 스택 (STACK)먼저 들어 온 데이터가 나중에 나가는 형식(선입후출)의 자료구조이다. → FILO 구조  파이썬에서 스택자료구조를 이용하기 위해서는 단순히 리스트를 이용하면 된다.ex) 박스쌓기  원소 삽입 : .append() 원소 삭제 : .pop()  큐 (Queu) 먼저 들어온 데이터가 먼저 나가는 형식(선입선출)의 자료구조이다.→ FIFO 구조 맛집 줄서기  리스트 자료형을 이용하여 큐를 구현할 수 있지만, 시간복잡도가 높아 deque 라이브러를 사용하는 것이 좋다.  원소삽입 : .append(..

그리디 알고리즘(탐욕법)이란 ?현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미합니다. 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올 릴 수 있는 능력을 요구합니다. 그리디 해법은 그 정당성 분석이 중요합니다. 단순히 가장 좋아보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토합니다. [문제상황]  루트 노드부터 시작하여 거쳐 가는 노드 값의 합을 최대로 만들고 싶습니다.  Q. 단순히 매 상황에서 가장 큰 값만 고른다면 어떻게 될까요?  일반적인 상황에서는 그리디 알고리즘은 최적의 해를 보장할 수 있을 때가 많습니다.  연습문제 1. 거스름돈 : 정당성 분석 https://www.acmicpc.net/problem/5585   최적의 해를 빠르게 구하기 위해 ..