이진 트리(Binary Tree) 란? 트리란 부모와 자식이 상하 구조로 나뉘어진 그래프입니다. 이진 트리는 트리의 종류 중 하나이며 자식 노드를 왼쪽과 오른쪽에 하나씩 배치할 수 있는 형태의 그래프입니다. 탐색 방식 종류 전위 순회 후위 순회 중위 순회 층별 순회 전위 순회 (루트) -> (왼쪽 자식 노트) -> (오른쪽 자식 노드) 순 탐색 탐색 순서 A – B – D – C – E – F – G 전위 순회 예시 코드 후위 순회 (왼쪽 자식 노트) -> (오른쪽 자식 노드) -> (루트) 순 탐색 탐색 순서 D – B – E – G – F – C – A 후위 순회 예시 코드 중위 순회 (왼쪽 자식 노트) -> (오른쪽 자식…

LCS (Longest Common Subsequence) 란? 최장 공통 부분수열이라고도 부르며 여러 개의 수열 모두의 부분수열이 되는 수열들 중에 가장 긴 것을 찾는 방법 시간 복잡도 O(a1 × a2 × a3 … × an) 최장 공통 부분수열(Longest Common Subsequence) 백준 9252번 – LCS 2를 예시로 설명하겠습니다. 풀이 방법 먼저 두 수열을 비교를 통해 최대 길이를 구합니다 a 수열의 i번째와 b 수열의 j번째가 같은 경우 LCS[i][j] = LCS[i-1][j-1]+1 a 수열의 i번째와 b 수열의 j번째가 같은 경우 LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1]) 자 이제 거의 다 왔습니다! 😃😃 길이를 구한 수열의 값만 찾으면 되는데요! 순서는 아래와 같습니다. 수열 찾기 순서 리스트의 마지막 값 ( LCS[-1][-1])을 기준 값으로 정한다 인접 값에 동일한 값이 있을경우 해당 위치로 이동 ( LCS[move_y-1][move_x],…

투 포인터 알고리즘 이란? 1차원 배열에서 두 개의 점 위치를 이용하여 문제를 해결하는 알고리즘 시간 복잡도 = O(N) 예제 – 소수의 연속합 (백준 1644번) 과정 – 소수의 연속합 (백준 1644번) 결과 값 : 2 참고 자료 백준 – 소수의 연속합

삽입 정렬 (Insertion Sort) 이란? 두 번째 원소부터 자신의 앞에 먼저 정렬된 리스트 안에서 자신의 위치를 찾아 삽입하여 정렬하는 알고리즘 비교 정렬에 속함 삽입 정렬 특징 최적의 상태에서 굉장히 빠른 성능을 가진 알고리즘 – O(N) 최악의 경우 O(N2) 로 성능의 편차가 심함 구현이 쉬움 삽입 정렬 알고리즘 시간 복잡도 최악, 평균 – O(N2) 최선 – O(N) 참고 – 각 정렬 알고리즘의 시간복잡도 예제 – 오름차순 과정 – 오름차순 두 번째 원소부터 비교를 시작하며 자신의 앞에 정렬된 리스트 내에서 자신의 위치를 찾아 삽입합니다. 위 과정을 반복하여 마지막 배열까지 정렬 시 아래와 같이 완성됩니다! 이상으로 삽입 정렬에 대한 설명을 마칩니다! 😀

선택 정렬 (Selection Sort) 이란? 자신의 뒤에 속하는 원소들과 순차적인 비교를 통해 자리를 교환하여 정렬하는 알고리즘 비교 정렬에 속함 선택 정렬 특징 버블 정렬과 방식이 비슷하며 구현이 쉬움 잦은 비교와 교환으로 성능이 나쁨 선택 정렬 알고리즘 시간 복잡도 최악, 최선, 평균 – O(N2) 참고 – 각 정렬 알고리즘의 시간복잡도 예제 – 선택 정렬 (오름차순) 과정 – 오름차순 첫 번째 배열부터 뒤에 속하는 배열과 순차적으로 값을 비교합니다. 1회전과 마찬가지로 (배열의 수 – 1) 회전까지 진행하면 아래와 같은 배열이 완성됩니다. 이상으로 선택 정렬에 대한 설명을 마칩니다! 😀

버블정렬(Bubble Sort) 이란? 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘 비교 정렬에 속함 버블 정렬 특징 선택 정렬과 마찬가지로 구현이 쉬움 잦은 비교와 교환으로 성능이 나쁨 버블 정렬 알고리즘의 시간복잡도 최악, 최선, 평균 – O(N2) 참고 – 각 정렬 알고리즘의 시간복잡도 예제 – 버블 정렬 (오름차순) 과정 – 오름차순 첫 번째 배열부터 마지막 배열까지 자신의 인접한 배열과 순차적으로 비교를 통해 교환하여 정렬합니다. 현재까지 진행된 1번째 ~ 마지막 배열 비교를 배열을 수만큼 반복 작업을 하게 되면 아래와 같은 정렬이 완성됩니다. 이상으로 버블 정렬에 대한 설명을 마칩니다! 😀

버블 정렬 인접한 원소끼리 자리 교환을 통해 첫 번째 원소부터 마지막 원소까지 정렬하는 방식 장점 구현이 쉽다 단점 다른 정렬 알고리즘에 비해 성능이 좋지않다 선택 정렬 첫 번째 원소부터 자신의 뒤에 속하는 원소들과 순차적인 비교를 통해 자리를 교환하여 정렬하는 방법 장점 버블 정렬과 마찬가지로 구현이 쉽다 단점 버블 정렬과 마찬가지로 성능이 좋지않다 삽입 정렬 두 번째 원소부터 자신의 앞에 먼저 정렬된 배열 안에서 자신의 위치를 찾아 삽입하는 방법 장점 최적의 상태에서 빠른 성능을 가진 알고리즘 단점 성능의 편차가 심하다 (입력 자료가 역순일 경우 O(N2)의 느린 성능을 갖게됨) 셸 정렬 삽입 정렬에서 고안된 방법 정렬할 리스트를 임의의 기준에 따라 분류한 후 분류한 리스트를 여러 개의 부분 리스트로 만들어 각 부분 리스트를…

heap 이란? 우선순위 큐 구현을 위한 자료구조로 최대, 최솟값을 찾기 용이 완전 정렬이 아닌 반정렬 구조 모든 부모 노드는 그의 자식 노드보다 값이 작거나 큰 이진트리 구조 큰 경우 – 최대 힙 작은 경우 – 최소 힙 heap 에서의 부모 노드와 자식 노드의 관계 왼쪽 자식의 인덱스 = (부모의 인덱스) * 2 오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1 부모 인덱스 = 자식 인덱스 // 2 힙 정렬 알고리즘의 시간복잡도 최악, 최선, 평균 – O(logN) 참고 – 각 정렬 알고리즘의 시간복잡도 예제 – 최대 힙 정렬 과정 – 최대 힙 이후 부모 노드가 자식 노드보다 작지 않으므로 추가적인 교체는 없다. 최소 힙와 최대 힙은 큰 값과 작은…