Algorithm
Backtracking
Backtracking
2022.04.11분할정복이나 dp처럼 문제를 풀기 위한 전반적인 전략 같은 알고리즘이다. 문제의 해가 될 수 있는 후보군들 중에서 특정 조건에 부합하는 해의 집합을 찾을 때 사용한다. 처음에 해가 될 수 있는 후보를 하나 선택하고, 처음 선택과 연관해서 다음 해가 될 수 있는 후보를 하나 선택하는 방식으로 진행하고, 만약 연관된 해를 구할 수 없다면 처음으로 돌아가서(backtrack) 다시 후보를 선택한다. 트리 자료구조와 연관해서 이해하면 편하다. 각 후보를 DFS방식으로 확인하며, 조건에 맞지 않으면 해의 후보가 될 수 있는 위치로 돌아가 다시 탐색한다. 조건에 맞지 않아서 연관된 요소를 모두 포기하는 기법을 Pruning이라고 하고, 해당 요소가 조건에 부합하는지 확인하는 기법을 Promising이라고 한다. 백..
[백준] 17262 팬덤이 넘쳐흘러 - Java
[백준] 17262 팬덤이 넘쳐흘러 - Java
2022.04.06(가장 늦게 등교하는 사람의 등교 시간) - (가장 빨리 하교하는 사람의 하교 시간) import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); Student[] arr = new Student[N]; for(int i=0;i o2.end){ return 1; }else{ return -1; } } }); int temp1 = arr[0].end; Arr..
Greedy
Greedy
2022.04.06탐욕 알고리즘이라고도 불린다. 재귀, 분할정복과 dp처럼 특정 문제를 해결하기 위한 알고리즘이라기보다는, 문제 해결에서 사용할 수 있는 도구 중 하나라고 생각하면 좋을 것 같다. 여러 가지 경우 중 하나를 결정해야 할 때, 선택의 순간마다 최적이라고 판단되는 케이스를 선택하는 방향으로 진행해 최종 값을 산출하는 알고리즘이다. 그리디 알고리즘을 사용해서 풀 수 있는 대표적인 문제로, 부분 배낭 문제가 있다. 무게 제한이 있는 상황에서, 최대 가치를 담을 수 있도록 배낭에 물건을 넣어야 한다. 물건들에 대한 무게와 가치 정보가 주어진다. 여기서, 물건을 쪼개서 넣을 수 있다면 분할 가능 배낭 문제 (Fractional knapsack problem)이고, 쪼갤 수 없으면 knapsack problem이라고 ..
DFS
DFS
2022.04.06Depth First Search. 깊이 우선 탐색이다. BFS와 마찬가지로 그래프 자료구조를 탐색할 때 사용하는 알고리즘이다. BFS와는 달리 DFS는 정점의 자식을 먼저 탐색한다. BFS에서는 두 개의 큐 자료구조를 사용해서 구현했지만, DFS에서는 BFS에서 탐색해야 하는 부분을 저장하는 큐 (needvisit)를 스택으로 바꿔서 활용한다. BFS의 로직과 DFS의 로직을 비교해서 공부해보자. import java.util.*; import java.io.*; public class Main { public ArrayList dfsFunc(HashMap graph, String startNode) { ArrayList visited = new ArrayList(); Stack needVisit = ..
BFS
BFS
2022.04.06이진 탐색과 순차 탐색처럼 특정 자료구조 내부를 탐색하는 알고리즘이 있듯, BFS는 그래프 자료구조를 탐색하는 알고리즘이다. 풀 네임은 Breadth-First Search으로, 너비 우선 탐색을 의미한다. BFS는 위와 같이 탐색을 진행한다. 그래프에서 레벨에 해당하는 부분을 탐색하고, 하나의 레벨에 대해 탐색을 마치면 다음 레벨에 대해 탐색을 시작하며 마지막 모든 원소를 확인할 때 까지 탐색을 진행한다. BFS를 구현하기 위해 먼저 Java에서 그래프를 구현하는 방법에 대해 알아보자. 자바에서는 HashMap과 ArrayList자료구조를 이용해 그래프를 구현한다. HashMap의 Key부분에는 그래프의 노드에 해당하는 정보가 들어가고, Values부분에는 해당 노드에 인접한 노드에 대한 정보가 들어간..
이분탐색
이분탐색
2022.04.04배열이나 리스트에서 특정 원소를 찾을 때 탐색 알고리즘을 사용한다. 순차탐색은 말 그대로 맨 처음부터 탐색을 시작해 원하는 원소를 찾을 때 까지 탐색을 수행한다. ( O(n) ) 좀 더 효율적으로 탐색하기 위해 이분 탐색 알고리즘이 고안됐다. 일단, 탐색하려는 배열이나 리스트는 정렬된 상태여야 한다. 1. 전체 데이터의 중간을 비교한다. 2. 찾으려는 원소와 중간 원소를 비교해 중간 원소보다 찾으려는 원소의 값이 더 작다면 중간값을 기준으로 좌측을, 그렇지 않으면 우측으로 탐색 구간을 재정의한다. 3. 1 2 를 반복한다. 만약 찾으려는 원소가 배열 안에 없어도 쉽게 파악할 수 있다. 미루어 짐작할 수 있듯, 이분 탐색도 분할정복 기법과 재귀를 사용하는 알고리즘이다. import java.util.*; ..
퀵
퀵
2022.04.03기준점을 잡고 기준점보다 작은 데이터는 좌측, 큰 데이터는 우측으로 정렬한다. 좌측과 우측에 정렬된 데이터들에 대해서 다시 피봇을 설정하고 위 작업을 반복한다. 피봇으로 설정할 때 마다 원소의 위치가 정해진다. 모든 원소들에 대해서 피봇을 설정했으면, 정해진 위치를 기반으로 합치며 정렬을 수행한다. import java.util.*; public class Main { public static void main(String[] args) { ArrayList testData = new ArrayList(); for (int index = 0; index < 100; index++) { testData.add((int) (Math.random() * 100)); } QuickSort qSort = new ..
병합
병합
2022.04.03분할정복 기법을 정렬에서 적용한 정렬 방법이다. 1. 정렬되지 않은 배열을 하나의 원소로 분리 2. 분리된 원소를 정렬하며 병합 두 단계로 구성된다. public ArrayList mergeSplitFunc(ArrayList dataList) { if (dataList.size() leftPoint && rightList.size() > rightPoint) { if (leftList.get(leftPoint) > rightList.get(rightPoint)) { mergedList.add(rightList.get(rightPoint)); rightPoint += 1; } else { mergedList.add(leftList.get(leftPoint)); leftPoint += 1; } } // le..
동적 계획법 (Dynamic Programming)
동적 계획법 (Dynamic Programming)
2022.04.01한 문제를 여러 부분으로 쪼개서 각각의 문제들을 해결한 다음 해결한 결과들을 합병해 문제를 해결하는 분할 정복과 비슷한 알고리즘이다. 동적 계획법은 최하단의 결과를 이용해 상단 결과를 해결하는 방식이고, 이전에 계산한 값을 저장해 다시 계산하지 않게 하는 메모이제이션 기법을 사용해 문제를 효과적으로 풀 수 있게 한다. 분할 정복에서는 메모이제이션을 사용하지 않아 쪼갠 문제들의 결과를 활용하지 않는다. public class dp { public int dpfunc(int data) { int[] num = new int[data + 1]; num[0] = 0; num[1] = 1; for (int i = 2; i < data + 1; i++) { num[i] = num[i - 1] + num[i - 2]..
버블 / 선택 / 삽입
버블 / 선택 / 삽입
2022.03.31버블 정렬 가장 기본적인 정렬 방법이다. 배열이나 리스트의 인덱스 0부터 시작해 오름차순으로 정렬을 수행한다. import java.util.*; public class BubbleSort { public ArrayList sort(ArrayList dataList) { for (int index = 0; index dataList.get(index2 + 1)) { Collect..
선 설계 후 코딩
선 설계 후 코딩
2022.03.31문제를 읽고 바로 키보드에 손이 가면 안된다. 특히 시간이 촉박한 상황에서, 급한 마음에 바로 키보드에 손을 올리게 되는 경우가 많은데 좋은 습관이 아니라고 생각한다. 1. 일단 문제를 천천히 읽으며 연습장에 간단한 케이스부터 고려해 어떻게 해결할 지 생각한다. 2. 해결 방법이 보이면, 문제를 여러 파트로 분리해 파트별로 풀이 로직을 메모한다. 3. 파트별로 사용할 변수와 알고리즘을 생각하고 메모한다. 알고리즘 문제를 풀 때는 항상 침착해야 한다.
시간복잡도와 공간복잡도
시간복잡도와 공간복잡도
2022.03.31시간 복잡도는 코드의 실행 시간을 의미하고, 공간복잡도는 코드가 메모리를 얼마나 잡아먹는지를 의미한다. 배열에서 특정 원소에 접근할 때는 인덱스를 기반으로 한 번에 찾아갈 수 있지만, LinkedList에서 특정 원소에 접근하려하면 처음이나 끝에서부터 시작해서 특정 원소의 위치까지 접근해야 한다. 이 때 배열은 원소의 접근에 있어서 시간복잡도가 낮고, 링크드리스트는 접근에 있어서 시간복잡도가 높다고 할 수 있다. C언어에서 int타입은 4바이트, char타입은 1바이트 등.. 변수를 선언하면 메모리에 주소값이 할당된다. 여기서 할당되는 메모리를 효율적으로 사용하면 공간복잡도가 낮다고 할 수 있다. 최근에는 대용량 시스템이 보편화돼서 공간복잡도보다는 시간복잡도를 향상시키는 쪽으로 기울고 있지만, 공간복잡도..