CS/알고리즘

재귀(Recursion) 알고리즘과 피보나치 수열

1. 재귀 알고리즘 재귀(Recursion) 함수란 특정 함수 내에서 자기 자신을 다시 호출해서 문제를 해결하는 함수를 말한다. 재귀함수는 자신의 로직을 내부적으로 반복하여 문제를 해결하고 조건이 만족되면 함수를 이탈해서 결과를 도출한다. 따라서 재귀함수는 함수 내에서 자기 자신을 계속 호출하기 때문에 반드시 종료하는 부분을 정확히 구현해야한다. 그리고 함수를 호출할 때마다 메모리상에서 추가적으로 생긴다. public class Recursion_Test { public static void main(String[] args) { recursion(); } //재귀함수 public static void recursion(){ System.out.println("안녕하세요"); recursion(); } ..

재귀함수를 이용해 배열의 최대값찾기

재귀(Recursion) 먼저 재귀(Recursion) 함수란 특정 함수 내에서 자기 자신을 다시 호출해서 문제를 해결하는 함수를 말한다. 재귀함수는 자신의 로직을 내부적으로 반복하여 문제를 해결하고 조건이 만족되면 함수를 이탈해서 결과를 도출한다. 따라서 재귀함수는 함수 내에서 자기 자신을 계속 호출하기 때문에 반드시 종료하는 부분을 정확히 구현해야한다. Java Code public class RecursionEx03Ver2 { public static int arr[] = {1, 2, 4, 8}; public static void main(String[] args) { int n = arr.length; System.out.println(recursion(n)); } public static int..

그리디(Greedy) 알고리즘

그리디(Greedy) 알고리즘그리디 알고리즘은 다른 말로 탐욕법이라고한다. 이름에서 알수 있듯이 어떠한 문제가 있을 때 단순 무식하게 탐욕적으로 문제를 푸는 알고리즘이다. 여기서 탐욕적이라는 말은 ‘현재 상황에서 지금 당장 좋은 것만 고르는 방법’을 의미한다. 모든 선택지를 고려하고 그중 전체 답이 가장 좋은 것을 찾아야하는 다른 알고리즘 방법과 다르다. 코딩테스트에서 그리디 알고리즘 유형의 문제는 매우 다양해서 암기한다고 잘 풀 수 없다. 기준에 따라 좋은 것을 선택하는 알고리즘이므로 ‘가장 큰 순서대로’, ‘가장 작은 순서대로’와 같은 기준을 알게 모르게 제시해준다. 따라서 이런 기준을 정렬 알고리즘을 사용했을 떄 만족시킬 수 있으므로 정렬 알고리즘과 짝을 이뤄 출제된다. 위와 같은 트리가 존재할 때..

이진 탐색(Binary Search)

이진탐색을 알기전에 먼저 순차탐색을 알아야한다. 순차탐색(Sequential Search)는 배열 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법이다. 보통 정렬되지 않은 배열에서 데이터를 찾아야 할 때 사용한다. 배열에서 원소의 개수를 확인하는 count() 메서드를 이용할때도 내부에서는 순차 탐색이 수행된다. 이진탐색 이진 탐색(Binary Search)는 반으로 쪼개면서 탐색하는 방법 으로 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 데이터가 무작위일때는 사용할 수 없지만 이미 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있는 특징이 있다. 이진탐색은 위치를 나타내는 변수 시작점, 끝점, 중간점을 사용한다. 찾으려는 데이터와 중간점 ..

퀵 정렬(Quick Sort)

퀵 정렬(Quick Sort) 퀵 정렬은 이름처럼 가장 많이 사용되고 있는 빠른 정렬 알고리즘이다. 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 정렬방법이다. 퀵 정렬에는 피벗(Pivot)이 사용되는데 이 피벗은 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 ’기준’을 말한다. 퀵정렬을 수행할때는 피벗을 어떻게 설정할지는 미리 명시해야하는데 가장 대표적인 분할 방식인 호어 분할(Hoare Partition)방식으로 설명하겠다. (참고로 피봇을 정하는 기준에서 수행시간의 차이가 존재한다. ) 호어 분할 방식에서는 리스트에서 첫 번째 데이터를 피벗으로 정한다. 따라서 피벗을 정한 뒤에 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다. ..

삽입정렬(Insertion sort)

삽입정렬(Insertion Sort) 정렬 알고리즘은 데이터를 특정한 기준에 따라 순서대로 나열한 것을 말한다. 프로그램에서 데이터를 가공할 떄 오름차순이나 내림차순 등 대부분 어떤 식으로든 정렬해 사용하는 경우가 많아서 가장 많이 사용되는 알고리즘이다. 데이터를 정렬하면 이진탐색(Binary Search)이 가능하다. 삽입정렬은 특정한 데이터를 적절한 위치에 ‘삽입’한다는 의미에서 삽입정렬이다. 따라서 삽입정렬은 선택정렬에 비해 구현 난이도가 높은 편이지만 선택 정렬에 비해 실행 시간측면에서 더 효율적이다. 삽입 정렬은 필요할 때만 위치를 바꾸므로 ‘데이터가 거의 정렬되어있을 때’ 훨씬 효율적이다. 선택 정렬은 현재데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 위치를 바꾸면 반면 삽입 정렬을 그..

DFS와 BFS 와 이진트리순회

먼저 그래프 탐색(Graph Search)이란 하나의 정점으로부터 시작해 차례대로 모든 정점을 방문한다.예시로는 도로망에서 특정 도시에서 다른 도시로갈 수 있는지 여부, 전자회로에서 특정 단자와 다른 단자가 서로 연결되어 있는지 여부가 있다.대표적은 그래프 탐색 알고리즘에는 DFS/BFS가 있다. DFS(Depth-First Search, 깊이 우선 탐색)트리나 그래프에서 한 루프로 탐색하다가 특정 상황에서 최대한 깊숙이 들어가서 확인한 뒤, 다시 돌아가 다른 루트로 탐색하는 방식이다.대표적으로 백트래킹에 사용된다.일반적으로 재귀 호출을 사용해 구현하지만, 단순하게 스택 배열로 구현할 수도 있다. (참고로 트리는 특정 조건을 만족하는 그래프이다. 즉 트리는 그래프이지만, 그래프는 트리가 아님!) DFS..

시간복잡도 & 공간복잡도

복잡도(Complexity)는 알고리즘의 성능을 나타내는 척도이다. 복잡도란 시간복잡도와 공간복잡도로 나뉜다. 동일한 기능을 수행하는 알고리즘이 있다면 일반적으로 복잡도가 낮을수록 좋은 알고리즘이다. 따라서 시간복잡도를 측정함으로써 알고리즘을 위해 필요한 연산의 횟수, 공간복잡를 측정함으로써 알고리즘을 위해 필요한 메모리의 양을 계산할 수 있다. 시간 복잡도 : 입력 크기에 대해 알고리즘이 얼마나 오래 걸리는지를 의미 공간 복잡도 : 입력 크기에 대해 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미 하지만 효율적인 알고리즘을 사용한다고 했을 때, 보통 시간 복잡도와 공간복잡도는 일종의 거래 관계(trade off)가 성립된다. 메모리를 조금더 많이 사용하는 대신에 반복되는 연산을 생략하거나 더많은 정보..