본문 바로가기

IT 지식/알고리즘4

이진트리 (JAVA 코드 포함) 대학생때부터 취업 직전까지 많이 듣고 많이 공부한 알고리즘 중 하나는 당연 트리이고, 그 중 이진트리를 기초로 생각하고 배운 적이 있다. 한창 취준하며 코테를 공부하던 때에는 과장해서 말하자면 이진트리는 굳이 생각이라는 것을 거치지 않고도 단어만 듣고 코드가 줄줄 써지는 정도였다. 하지만 너무 기초라고 생각했고, 취업 이후에는 이 구현 방법 자체를 머리속에서 지우고 살았다. 자기변명을 해보자면, 이진 트리를 굳이 실무에서 적용할 일이 없었고, 또 지난 여러 기업의 코딩 테스트를 응시하며 이진 트리가 나온 적은 한 번도 존재하지 않았었기 때문이다. *물론 많은 회사의 코딩테스트에 응시했던 것은 아니므로, 언제 어디서 등장할 지는 모른다. 이 사실을 상기하지 못한 것에 대한 변명일 뿐이다. 그렇게 살던 중 .. 2024. 2. 26.
[알고리즘] DP 취업 준비를 시작하며 알고리즘을 배울 때 아, 이건 DFS 문제구나. 라고 생각해서 DFS로 푼 문제가 있었다. 하지만 정확도는 100%여도 효율성은 0에 가까운 결과를 보여주었었는데, 같은 알고리즘을 풀던 친구에게 물어보니 해당 알고리즘은 DFS가 아니라 DP로 풀어야 한다고 대답을 해줬었던 기억이 있다. DP (동적 계획법, Dynamic Programming) 알고리즘을 풀다보면 연산이 쓸데없이 반복되는 경우가 있다. 피보나치 수열이 그 예시이다. 피보나치 수열 첫째, 둘째 항이 1이며 그 뒤의 모든 항들은 앞의 두 항의 합인 수열. 평범한 피보나치 수열 구하기 문제의 코드는 다음과 같다. public class main{ public static void main(String[] args) { i.. 2021. 10. 26.
[알고리즘] BFS와 DFS 그래프 탐색 그리프란 정점과 간선으로 이루어진 자료구조의 일종이다. 그리고 그래프에서의 탐색은 하나의 정점, 즉 시작점에서 출발하여 차례대로 정점을 방문하여 목표 정점을 방문하는 것을 말한다. 예를 들자면 그래프 내 어떤 노드와 다른 특정 노드가 연결되어 있는지를 검사하는 것, 혹은 사람간의 관계가 이어져있는지 검사하는 것이 바로 그래프 탐색이다. BFS와 DFS는 모두 이러한 그래프 탐색 알고리즘의 일종이다. BFS (너비 우선 탐색, Breadth-First Search) BFS는 쉽게 말해, 인접한 노드들을 전부 방문한 후 다음 노드로 이동하는 방법이다. 아래와 같은 그래프가 있다고 가정하자. BFS를 위해 다음 두 개의 조건을 설정하자. 시작 노드는 1이다. 다음 노드로 향할 때 숫자가 작은 노드.. 2021. 10. 26.
[알고리즘] 정렬 알고리즘 1) 버블 정렬 시작 5 3 2 1 4 1회차 3 2 1 4 5 2회차 2 1 3 4 5 3회차 1 2 3 4 5 4회차 1 2 3 4 5 가장 기본적인 정렬 중 하나이다. 인접한 i번째 키와 i+1번째 키를 비교하여 교환한다. 즉 1, 2번째 키를 비교하고, 2,3번째 키를 비교하여 정렬한다. 이러한 방식은 자연스럽게 가장 큰 값을 가장 뒤로 정렬하게 된다. 시간복잡도는 평균과 최악 모두 n^2 으로 같으며, 사용 메모리는 n이다. public class HelloWorld{ public static void main(String []args){ int[] nums = {2, 3, 6, 1, 4, 9, 10}; for(int i=0; i 2021. 4. 5.

티스토리툴바