본문 바로가기

Develop/Algorithm12

이진탐색 (Binary Search) 오늘은 이진탐색 (Binary Search) 알고리즘 에 대해 정리해 두려고 한다. 이진탐색 이란? 이진 탐색은 정렬된 배열의 가운데 값과 키값을 비교하고 비교 대상을 좌우로 줄여가면서 비교를 되풀이 하는 방법이다. 아래 그림을 보면 간단하게 이해 되지 않을까 싶다. 먼저 key 값은 6 이고, 배열은 {1,4,6,8,11,13,15} 라고 가정했다. 1. 먼저 8 (mid) 과 6 (key) 을 비교 했을 때, key 값보다 mid 값이 크기때문에 8(mid) 값보다 작은 1,4,6 대상으로 범위를 줄인다. 2. 다음은 4 (mid) 와 6 (key) 을 비교 했을 때, key 값보다 mid 값이 작기 때문에 4(mid) 값보다 큰 6 을 대상으로 범위를 줄인다. 3. 다음은 6(mid) 와 6 (mi.. 2021. 10. 3.
dfs 를 이용하여 조합 구하기 오늘은 dfs를 이용한 조합 구하기를 정리해볼꺼다. 조합은 서로다른 n 개중에 r개를 선택하는 경우의 수를 의미한다. 조합을 다른식으로 표현하면 아래처럼 표현이 되는데 알고리즘을 구현할때는 아래 방법을 알고 있어야 한다. 그리고 이를 dfs를 이용해 내려가다 보면 이런 생각이 들것이다. "중복되는 것들이 생기네?" 이렇게 중복되는 값을 또 재귀로 돌리다보면 분명 성능이 좋지 않다. 이를 위해 다이나믹 프로그래밍 즉 dp를 이용하여 효과적으로 구현할 수가 있다. 아래는 구현안 예제 코드이다. import java.util.Scanner; public class Combination { static int[][] dp ; public static void main(String[] args) { Combina.. 2021. 9. 12.
dfs를 이용한 순열 구하기 하이 .. 전에 dfs 알고리즘에 대해 글을 올린적이 있다. https://devkingdom.tistory.com/263?category=956302 DFS (Depth-First Search) 알고리즘 정리 오늘은 알고리즘에서 가장 중요한 개념중에 하나인 DFS에 대해 설명을 드리고자 한다. DFS는 다양한 경우의 수를 구할때 굉장히 많이 쓰이는 알고리즘이나 꼭 익혀두길 권장한다. 일단 코드소스 devkingdom.tistory.com 오늘은 우리가 고등학교 시절 수학시간에 배웠던 순열, 조합 을 dfs 알고리즘을 이용해서 구현해보려고한다. 중복순열 중복순열은 서로 다른 n개 중 r 개를 순서를 고려해서 나열하는 순열을 의미한다. 기로호는 nΠr 로 나타낼 수 있다. 이를 dfs로 각 경우의 수를 p.. 2021. 9. 6.
백트래킹 (Back Tracking) 알고리즘 이해하기 하이 오늘은 백트래킹 알고리즘을 정리해두려고한다. 먼저 백트래킹 알고리즘을 알려면 DFS알고리즘을 정확하게 알고 있어한다. 혹시 DFS 에 대해 잘 모르겠다 싶으면 아래 링크를 차곰해서 보고 오자. https://devkingdom.tistory.com/263 DFS (Depth-First Search) 알고리즘 정리 오늘은 알고리즘에서 가장 중요한 개념중에 하나인 DFS에 대해 설명을 드리고자 한다. DFS는 다양한 경우의 수를 구할때 굉장히 많이 쓰이는 알고리즘이나 꼭 익혀두길 권장한다. 일단 코드소스 devkingdom.tistory.com 백트래킹 알고리즘은 dfs 알고리즘 방식으로 가장 깊은 레벨까지 가서 정답인지 체크하고 아니면 그노드의 부모로 돌아가서 다른 자식노드를 체크하고 이렇게 쭈우우우.. 2021. 7. 29.
BFS (Breadth-First Search) 알고리즘 정리 저번 포스팅에서 내가 DFS 에 대하 포스팅을 했었다. DFS 알고리즘이 경우의수를 찾기 위해 사용하는 알고리즘이라면, BFS 알고리즘은 최단 거리를 찾기 위해 사용하는 알고리즘이라고 생각하면 좋을 것 같다. 먼저 코드를 보여드리겠다. import java.util.LinkedList; import java.util.Queue; public class BFS { public static void main(String args[]) { BFS tree = new BFS(); Node root = new Node(1); root.lt = new Node(2); root.rt = new Node(3); root.lt.lt =new Node(4); root.lt.rt = new Node(5); root.rt.l.. 2021. 7. 28.
DFS (Depth-First Search) 알고리즘 정리 오늘은 알고리즘에서 가장 중요한 개념중에 하나인 DFS에 대해 설명을 드리고자 한다. DFS는 다양한 경우의 수를 구할때 굉장히 많이 쓰이는 알고리즘이나 꼭 익혀두길 권장한다. 일단 코드소스를 먼저 보여드리겠다. public class DFS { public static void main(String args[]) { DFS tree = new DFS(); Node root = new Node(1); root.lt = new Node(2); root.rt = new Node(3); root.lt.lt =new Node(4); root.lt.rt = new Node(5); root.rt.lt = new Node(6); root.rt.rt = new Node(7); tree.dfs(root); } publi.. 2021. 7. 28.
재귀 함수 정리 하이 ... 요즘은 정말 틈틈이 시간을 내서 알고리즘을 열심히 공부하고 있는 중이다. 예전에 취업 준비할 때는 알고리즘에 대해 자신감도 있었고, 문제도 곧잘 풀었었는데 뭔가 공부를 다시하려니 마음먹은대로 쉽게 되진 않는다. 사설이 조금 길었다. 오늘은 알고리즘 문제에서 다양하게 많이 사용되는 재귀함수에 대한 내용을 정리해 두려고 한다. 1. 스택 프레임 먼저 재귀함수에 대해 알기 위해서는 스택 프레임이라는 것을 잘알아야 한다. 스택 프레임이란 스택 영역에 차례로 저장되는 함수의 호출 정보를 의미한다. 보통의 언어에서 메모리의 스택 영역은 함수의 호출이랑 그와 관련된 지역 변수와 파라미터를 저장한다. 이 스택영역은 함수의 호출이 완료되면 소멸된다. 우리가 흔히 들어본 스택 오버플로우가 바로 이 영역이 넘쳐.. 2021. 7. 27.
병합 정렬 (Merge Sort) 알고리즘을 공부하는 학생들이나 취준생들은 이 정렬알고리즘이 꼭 필요할 때가 있다. 많고 많은 정렬 알고리즘 중에 하나를 선택해야한다면 이 병합 정렬을 공부해서 익혀두길 권장한다. 병합 정렬은 안정 정렬에 속하고, 분할 정복(devide & conquer) 알고리즘 중 하나이다. 구현 방법은 아래와 같다. 1. 배열의 길이가 한개가 될때까지 배열을 분할한다. 2. 각 부분의 배열을 재귀적으로 정렬한다. 3. 하나의 리스트가 될때까지 정렬한다. 음 위의 구현방법이 이해가 잘 안되면 아래그림을 보면 이해가 쑤욱 될것이다. 병합정렬의 가장 큰 장점은 입력데이터가 무슨 데이터이든 상관없이 일관되게 O(nlog₂n) 의 복잡도를 가진다는 것이다. 구현 방법은 아래와 같다. public class MergeSort .. 2021. 7. 6.
퀵 소트 (Quick Sort) 오늘은 Quick Sort를 구현해 보려 한다. 퀵 소트는 기준이 되는 값(pivot)을 하나 잡고 , 기준 값 보다 작거나 같은 값을 가지고 있는 자료는 앞쪽으로 보내고, 큰 값을 가지고 있는 자료는 뒤쪽으로 보내 기준 값을 기준으로 분할해서 정렬을 진행하는 방법을 의미한다. 정렬 방식은 아래와 같다. 1. 기준 값(pivot)을 정한다. 2. pivot 앞에는 pivot 보다 작은 값이 오고, pivot 뒤에는 큰값이 오도록 배열을 둘로 분할한다. 3. 분할된 두 개의 배열에 대하여 재귀함수를 통하여 정렬하는 과정을 반복한다. 위처럼 이렇게 정렬이 된다. 시간복잡도는 평균적인 경우에는 O(nlogn) 이지만 최악의 경우는 O(N²) 이다. 최악의 경우는 피봇을 최소값이나 최대값을 선택할때이다. ( 즉.. 2021. 7. 5.

티스토리툴바