알고리즘 (22) 썸네일형 리스트형 정렬 1) 정렬이란? - 정렬은 어떤 자료들이 주어졌을 때, 그 자료들에 대해서 오름차순 혹은 내림차순 등의 기준이 주어졌을 때, 그것에 맞게 자료들을 정렬하는 것을 말합니다. 오름차순이라면 크기가 작은 것이 앞에, 내림차순이라면 크기가 큰 것이 앞에 정렬합니다. 2) 정렬의 특징 (1) 정렬 조건이 필요하다 - 정렬 조건이란 어떤 자료들이 주어졌을 때, 2개 중에서 어떤 것이 앞에 와야 하는지에 관한 것입니다. 자료 4개가 주어졌을 때, 오름차순으로 정렬해달라는 조건이 들어 왔다면, 크기가 작은 것이 앞에 오게 합니다 예를 들어, 자바에서는 Comparable 인터페이스를 구현해서 이를 나타낼 수 있습니다. static class Elem implements Comparable{ public int num,.. 이진 트리 순회[너비 우선 탐색] 1) 너비 우선 탐색이란? - 너비 우선 탐색은 트리의 레벨 단위로 위에서 아래로, 좌에서 우로 탐색하는 방법입니다. 너비 우선 탐색은 트리에서 레벨 순회라고도 불립니다. - 너비 우선 탐색으로 트리를 순회하려면 큐를 사용해서 탐색해야 합니다. 큐는 먼저 들어간 것이 먼저 나오는(FIFO) 자료구조입니다. 다음에 방문할 노드를 큐에 삽입하고, 큐에서 꺼내서 방문하는 식으로 진행합니다. 참고 코드라떼 자료구조 이진트리 순회(깊이 우선 탐색) 1) 순회 - 트리의 모든 노드를 방문하는 것을 순회라고 합니다. 배열을 인덱스를 통해 접근할 수 있듯이, 트리도 순회를 통해 모든 노드에 접근할 수 있습니다. 그리고 이진 트리를 순회하는 방법은 크게 두 가지가 있으며, 깊이 우선 탐색과 너비 우선 탐색이 있는데, 깊이 우선 탐색에는 3가지 방법이 있습니다. 트리의 순회는 재귀의 백트레킹 방식으로 순회하는데, 백트레킹 방법에 따라 노드의 방문 순서가 달라집니다. 2) 트리 순회의 3가지 방법 (1) 전위 순회 - 전위 순회는 부모를 먼저 방문하고, 좌측 서브 트리로 이동하여, 좌측 서브 트리를 다 탐색하면 우측 서브 트리로 넘어가 우측 서브 트리를 전부 탐색합니다. (2) 중위 순회 - 중위 순회는 먼저 좌측 서브 트리로 넘어 가서 탐색 후, 부모를 방.. 재귀의 3가지 관점에 대해 - 재귀는 3가지 관점에서 접근할 수 있습니다. 그것은 점화식 관점, 분할 관점, 백트래킹 관점입니다. 각각에 대해 좀 더 자세히 살펴보겠습니다. 1) 점화식 관점 - 재귀를 잘 이해하려면 첫번째로 점화식으로 이해할 수 있습니다. 예를 들어, 다음과 같은 시그마를 계산하면 15라는 결과값을 얻을 수 있습니다. - 그렇다면 시그마를 어떻게 재귀로 표현할 수 있을지 고민해보겠습니다. 점화식의 각 단계를 표현하면 다음과 같습니다. - 그리고 점화식을 재귀적 구문의 코드로 작성하면 다음과 같습니다. 이 때, if(5 < n)은 재귀적 구문의 중단 조건입니다. - 그리고 n=1부터 시작한다면, 다음과 같이 순서대로 함수가 호출됩니다. 2) 분할 관점 - 분할 관점은 재귀적인 점화식을 포함할 수도 있지만, 점화식으.. 완전 탐색 기초 1) 완전 탐색 - 완전 탐색이란 문제를 해결하기 위해 확인해야 하는 모든 경우를 전부 탐색하는 방법입니다. 그 중에서도 백트레킹(back-tracking)을 통해 문제를 해결할 수 있어야 합니다. 2) 완전 탐색을 할 때 주의할 점 - 완전 탐색은 함수의 정의가 50%입니다. 백트레킹의 경우는 크게 4개의 케이스로 나눠지는데 (1) N개 중 중복을 허용해서 M개를 순서 있게 나열하기 (2) N개 중 중복없이 M개를 순서 있게 나열하기 (3) N개 중 중복을 허용해서 M개를 고르기 (4) N개 중 중복없이 M개를 고르기 입니다. (1) N개 중 중복을 허용해서 M개를 순서 있게 나열하기 15651번: N과 M (3) (acmicpc.net) import java.util.*; public class Ma.. 재귀 함수 1) 재귀 함수란? - 재귀 함수란 자기 자신을 호출함으로써, 같은 함수를 '재사용'하는 것을 의미합니다. 예를 들어, 다음과 같은 재귀 함수를 작성할 수 있습니다. public void countDown(int number){ System.out.println(number); countDown(number-1); } - 위의 코드에서 countDown 함수는 함수 내부에서 자기 자신(countDown)을 호출하고 있습니다. 이를 통해 countDown 함수를 '재사용'할 수 있습니다. 2) 재귀 함수의 기저 조건 - 위의 countDown 함수는 한 가지 문제점이 있습니다. 바로 number가 1씩 감소하면서 무한히 실행될 수 있다는 점입니다. 이와 같이 함수가 무한히 실행되면 스택오버플로우(stack.. 정렬 알고리즘 1. 선택 정렬 - 선택 정렬은 시간 복잡도가 O(N^2), 공간 복잡도가 O(N)인 정렬 알고리즘입니다. - 선택 정렬의 구현은 다음과 같습니다. public void selectionSort(int[] arr){ int N = arr.length; for(int i=0; i 재귀 Q1. 재귀에 쓰이는 용어로 함수가 반복되지 않는 이러한 경우를 무엇이라고 하는가? - 빅 오 Q1. 7.5의 코드의 시간 복잡도는 무엇인가? - 삽입 정렬 Q1. 어떤 시나리오를 구분하는 능력은 기존 알고리즘을 최적화해서 훨씬 빠르게 만드는 것만큼이나 사용자 요구에 맞는 최적의 알고리즘을 고르는 핵심 기술인가? - 최악, 평균, 최선의 시나리오를 구분하는 능력 Q2. 어떤 경우를 대비하는 것도 좋지만 대부분은 어떤 경우가 일어나는가? - 최악의 경우를 대비하는 것도 좋지만 대부분은 평균적인 경우가 일어난다. Q3. 삽입 정렬을 구현하라 class InsertionSort{ public int[] insertionSort(int[] arr){ int len = arr.length; for(int i=1; i=0 && arr[j] > target){ j--; arr[j+1] = arr[j]; } arr[j+1] = value; } } } class Main{ .. 이전 1 2 3 다음
