Computer Science/Algorithms30 👀 Binary Search 👀 intro 🐧 순차 탐색 - 선형 탐색) 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인 (가장 기본적인 형태 - 한 개씩 확인) 🐧 이진 탐색) 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색(시작점, 끝점, 중간점을 이용하여 탐색 범위 설정) ※ 이진 탐색은 순차 탐색에 비해 탐색 범위가 훨씬 줄어들기 때문에 시간 복잡도는 log시간을 보인다. Q. 이미 정렬된 10개의 데이터 중에서 값이 4인 원소를 찾기 0 - 2 - 4 - 6 - 8 - 10 - 12 - 14 - 16 - 18 ① 시작점) index 0, 중간점) index 4, 끝점) index 9 → 중간점이 2개 존재한다면, 소수점은 제외한 앞부분을 설정한다 → 4가 중간점 기준 왼쪽에 존재.. Computer Science/Algorithms 2022. 12. 6. understanding pesudo-code of QuickSort 🦢 백준 퀵 정렬 대표 문제 모음) 추후 🦢 퀵 정렬 concepts 포스팅) 추후 🦢 QuickSort pseudo-code quick_sort(A[p..r]) { # A[p..r]을 오름차순 정렬한다. if (p < r) then { q Computer Science/Algorithms 2022. 12. 5. DFS / BFS ① DFS(Depth-First Search) ⚡️ 먼저 DFS는 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 ⚡️ 스택 자료구조(또는 재귀함수)를 이용하며, 구체적인 동작 과정은 아래와 같다 ① 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. ② 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. ③ 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다. ⚡️ 동작 예시 ※ 먼저 방문노드 / 방문기준을 정하는 게 중요 → 문제마다, 상황마다 방문노드 정하는 기준은 제각각이다 ex) 예시에서는 방문노드는 1, 방문기준은 번호가 낮은 인접노드.. Computer Science/Algorithms 2022. 10. 14. 🧭Recursion intro 🍓 재귀함수란, 자기 자신을 다시 호출하는 함수이다. 함수 내에 다시 함수를 불러서, 동일 함수 로직을 반복적으로(재귀적) 진행한다. DFS 구현을 위해 자주 사용되는 개념. 아래 코드 예시 참조. def recursive_function(): print('recursive call') recursive_function() recursive_function() → 무한히 출력되다가 python의 경우 'RecursionError: maximum recursion depth exceeded while calling a Python object'라는 메시지 출력 - 재귀 최대 허용 깊이가 있어 오류 메시지가 끝에 출력되며 종료. 함수를 부를 때 마다 스택 자료 구조에 함수가 계속 쌓이면서 컴퓨터 .. Computer Science/Algorithms 2022. 9. 27. Implementation 1. intro ★ 코딩의 대부분, 즉 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정 ★ 어떤 알고리즘을 사용하더라도, 최종적으로는 구현을 해야 하기 때문에, 사실 모든 문제가 구현 유형이라고 할 수 있다. ★ 흔히 말하는 '구현' 문제는, 풀이를 떠올리는 건 쉽지만 직접 소스 코드로 옮기기 어려운 문제를 지칭 ① 알고리즘은 간단하나, 코드가 지나칠 만큼 길어지는 문제 (프로그래밍 언어 종류에 따라 어려울 수도, 매우 쉬울 수도 있음) ② 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제 ③ 문자열을 특정 기준에 따라서 끊어 처리해야 하는 문제 (python으로 매우 쉽게 풀 수 있는 경우 많고, 대표적으로 난이도 하의 1-2번 문제 위주) ④ 적절한 라이브러리를 찾아서 사용해야 하는 문제.. Computer Science/Algorithms 2022. 9. 21. Greedy * intro "현재 상황에서 지금 당장 좋은 것만 고르는 방법" → 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 적절히 떠오르면 풀리는 경우 많음 → 단순히 가장 좋아보이는 걸 반복적으로 선택해도 최적의 해를 구할 수 있는 지 검토하게 된다. → 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없는 경우가 많음 → 하지만 코딩 테스트에서의 대부분 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 추론할 수 있어야 풀리게 출제 ★ 주어진 문제를 모든 상황을 다 고려한 채로, 각 상황의 최적의 결과를 상황별로 계속 모으면, 그 결과가 곧 최적의 결과가 되는 유형이 greedy 유형 ☆ 주의점: 문제의 모든 상황을 생각해야 하고 / 각 상황의 greedy한 솔루션.. Computer Science/Algorithms 2022. 9. 12. 이전 1 2 3 다음
