Review/SW Jungle35 [WEEK03] 힙 / 우선순위 큐 1. 힙이란? 특징 - 힙은 일종의 반정렬 상태 (느슨한 정렬상태)를 유지함 - 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있는 정도 (혹은 반대) - 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진트리 장점 - 시간복잡도가 좋은편 - 힙 정렬이 가장 유용한 경우는 전체를 정렬하기보다 가장 큰 값 몇개만 필요할 때임 시간복잡도 - 힙 트리의 전체 높이 = log(n) / 하나의 요소 개수가 N개 - 따라서 T(n) = O(nlogn) 2. 우선순위 큐? 특징 - 우선순위의 개념을 큐에 도입한 자료구조 - 데이터들이 우선순위를 가지고 있고 우선 순위가 높은 데이터가 먼저 나감 - 우선순위 큐는 배열, 연결리스트, 힙으로 모두 가능하나 힙으로 구현하는 것이 가장 효율적임 - 여러 개.. 2022. 10. 10. [WEEK02] 정렬 알고리즘 [Do it 자료구조와 함께 배우는 알고리즘 입문 with 파이썬] + [이것이 취업을 위한 코딩테스트다] 개념정리 정렬? : 항목의 값을 대소 관계에 따라 데이터 집합을 일정한 순서로 바꾸어 늘어놓는 작업을 말함 : 오름차순 정렬 혹은 내림차순 정렬 : 안정적인 알고리즘 / 그렇지 않은 알고리즘으로 나눌 수 있음 : 교환 / 선택 / 삽입이 핵심 1. 단순 정렬 알고리즘 1) 버블 정렬 (Bubble Sort) : 원소의 수가 n인 배열에서 n-1번 비교, 교환 하면 가장 작은 원소인 1이 맨 앞으로 이동함 (패스) : 이러한 일련의 과정을 지속적으로 거쳐 정렬 : 알고리즘 개선방법 (Do it 참고) : 시간복잡도 = O(n^2) 2) 셰이커 정렬 (Shaker Sort) : 버블정렬을 개선한 알고리.. 2022. 10. 3. [WEEK02] 완전탐색 1) Brute Force : for 문이나 if 문을 활용하여 모든 경우의 수 알아봄 2) 비트마스크 (Bitmask) : 각 원소가 A인지 B인지 두가지 상태만을 가질 때 0, 1로 구분하여 배열을 저장 3) 재귀함수 4) 순열 5) BFS, DFS 6) 백트래킹 : 현재 상태에서 가능한 모든 선택지를 다 따라 들어가며 탐색하는 알고리즘 : 원하는 값과 불일치하는 부분이 생기면 탐색을 진행하지 않고 전단계로 돌아감 ex) 오목에서 앞으로 진행될 수를 생각해보고 가장 적절한 자리에 두는 것 대표문제 : N과 M cf) DFS(Depth First Search)와 백트래킹의 차이점 : 백트래킹은 불필요한 탐색을 하지 않음 : DFS는 모든 경우의 수를 탐색함 2022. 10. 3. [WEEK02] 재귀함수 [Do it 자료구조와 함께 배우는 알고리즘 입문 with 파이썬] + [이것이 취업을 위한 코딩테스트다] 개념정리 재귀함수 (Recursive Function) : 어떤 이벤트에서 자기 자신을 포함 -> 다시 자기 자신을 사용하여 정의 : factorial(n)이 factorial(n-1)을 호출함 => 재귀 호출 : 재귀함수의 수행은 스택 자료구조와 동일함 (함수를 계속해서 호출했을 때 가장 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 끝남) => 따라서 재귀적으로 함수를 표현할 때는 반드시 if 문을 이용하여 종료조건을 구현해야함 : 재귀 함수를 활용하여 소스코드를 작성하는 것은 수학의 점화식과 유사함 직접재귀와 간접 재귀 직접재귀 : 자기 자신과 똑같은 함수 호출 간접재귀 : .. 2022. 10. 3. [WEEK02] 스택(Stack)과 큐(Queue) + Collections.deque [Do it 자료구조와 함께 배우는 알고리즘 입문 with 파이썬] + [이것이 취업을 위한 코딩테스트다] + [Introduction to Algorithms] 개념 정리 1. 스택 (Stack) : 데이터를 임시 저장할 때 사용하는 자료구조 : 접시 쌓기에 비유할 수 있음 : 후입 선출 (Last In First Out) : 스택 사용시 "별도의 라이브러리를 사용할 필요 없음" => 기존 리스트로 사용하면 됨 : 스택에 데이터를 넣는 작업을 푸시(push) / 데이터를 꺼내는 작업은 팝(pop) : append() : 리스트 가장 뒤쪽에 데이터를 삽입 : pop() : 리스트 가장 뒤쪽에서 데이터를 꺼냄 : 윗부분 - top / 아랫부분 - bottom 용어정리 stk : 스택배열 (list형 배열).. 2022. 10. 1. [Week02] 분할정복 (Divide & Conquer) 분할정복? : 문제를 더 이상 나눌 수 없을 때까지 나눈 후 각각 풀고 그 후 다시 합병하여 문제의 답을 얻는 알고리즘 설계요령 1) Divide : 문제의 분할이 가능할 시, 2개 이상의 문제로 나눔 2) Conquer : 나누어진 문제를 해결 3) Combine : Conquer한 문제들을 결합 대표적인 예 : 병합정렬, 거듭제곱, 피보나치 수열 등 Base Case & Recursive Case 1) Base Case : 더 이상 divide 할 수 없는 상태 2) Recursive Case : 문제들을 나눠야 하는 상황 출처 https://namu.wiki/w/%EB%B6%84%ED%95%A0%20%EC%A0%95%EB%B3%B5%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%9.. 2022. 10. 1. 이전 1 2 3 4 5 6 다음
