본문 바로가기

알고리즘7

이진탐색 (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.
백트래킹 (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.
코딩 테스트 준비할 때 꿀팁 (feat. 네카라쿠배) 하이 ...! 오늘은 대학생 분들이나 이직을 준비하시는 많은 분들에게 도움을 드리고자 글을 좀 적어보려고 한다. 취업을 준비하던 시절 꾸준하게 알고리즘 문제를 풀었었고, 요즘도 감이 죽지 않도록 하루에 한 두 문제는 꾸준히 풀고 있다. 솔직히 나는 고등학교 시절까지 문과였고 머리속에는 논리적인게 하나도 없어서 처음에 알고리즘을 풀때 굉장히 곤혹 스러웠다. 문제를 해석하는 것부터 시작해서 문제를 푼다해도 채점사이트에서 돌려보면 오답으로 나오는 것 까지... 굉장히 고비와 고난이 많았다.. 그래도 지금은 나름대로 잘하는 건 아니라도 알고리즘 문제가 주어지면 어느정도 접근은 되고, 어려운 난이도가 아니라면 어찌 저찌 풀어내긴 한다. 이렇게 알고리즘 초보자가 중초보자(?)가 될 수 있는 노하우를 알려드리려 한다.. 2021. 7. 22.
버블 정렬 (Bubble Sort) 버블 정렬은 인접해 있는 두 배열 요소를 차례대로 검사하여 정렬하는 방식이다. 정렬은 아래와 같이 진행된다. 1. 시작은 배열의 첫번째 요소와 두번째 요소로 시작된다. 인접한 두 요소를 비교하여 정렬한다. 2. 배열의 다음 인접한 요소를 비교하여 정렬한다. (두번째 세번째) 3. 배열의 끝까지 비교를 반복하면 맨끝에는 정렬이 완료된 요소가 온다. 4. 마지막에 정렬된 요소를 제외하고 1~3 과정을 반복한다. 예제 코드 public class BubbleSort { public static void main(String[] args) { int[] data = {3,5,-5,1,4,0}; int[] result = bubbleSort(data); for(int num : result) { System.ou.. 2021. 7. 5.

티스토리툴바