Algorithm/Theory && Tip
퀵
퀵
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바이트 등.. 변수를 선언하면 메모리에 주소값이 할당된다. 여기서 할당되는 메모리를 효율적으로 사용하면 공간복잡도가 낮다고 할 수 있다. 최근에는 대용량 시스템이 보편화돼서 공간복잡도보다는 시간복잡도를 향상시키는 쪽으로 기울고 있지만, 공간복잡도..
완전 탐색
완전 탐색
2022.03.05문제 해결을 위해 모든 경우의 수를 탐색하는 방법이다. 가장 간단한 방법으로는 for문을 중첩해서 사용하는 방법이 있지만, 좀 더 효율적으로 탐색을 진행하기 위해 문제 조건을 잘 읽고 백트래킹 혹은 재귀를 사용할 수 있는 경우라면 사용해서 푸는 편이 합리적이다. 완전 탐색을 사용해서 문제를 해결할 때는 주어진 문제를 잘 읽고 함수를 어떻게 정의할 지 생각하는게 매우 중요하다. 재귀를 이용해서 완전 탐색을 구현하면 코드의 길이가 짧아지고 직관적으로 코드를 작성할 수 있지만, 재귀에 익숙하지 않으면 생각해내기가 쉽지 않다. 많이 경험해 봐서 익숙해지자. 완전탐색을 진행할 때 값들에 대해서 중복 허용 여부와 순서의 유무를 확인하자. 조건들에 따라 다른 시간복잡도가 나올 수 있다.
소수 찾기
소수 찾기
2021.10.302 3 5 7 11 13 17 19 .... 1과 자기 자신만을 약수로 가지는 수를 소수라고 한다. 소수가 아닌 양의 정수를 합성수라고 부른다. 소수를 왜 알아야되지.. 싶기도 한데 알고리즘 문제에서 소수를 구하라고 한다. 그리고 수능 수학을 공부할 때도 확률과통계 과목에서 소인수분해를 통해 여러 경우의 수를 찾기도 했고.. 소수를 구하는 방법을 컴퓨터에게 어떻게 설명할 지 알아보자. 가장 처음으로 떠오르는 생각으로는 1~N 까지 싹다 나눠보면서 접근하는 방법이다. 코드로 살펴보면 public static boolean primecheck(int number) { if (number < 2) { return false; } if (number == 2) { return true; } for (int i ..
최대공약수와 최소공배수 - 유클리드 호제법
최대공약수와 최소공배수 - 유클리드 호제법
2021.10.293과 8의 최대공약수와 최소공배수는 얼마인가? 1과 24이다. 2와 4의 최대공약수와 최소공배수는 얼마인가? 2와 4이다. 12와 28의 최대공약수와 최소공배수는 얼마인가? 4와 96이다. 어떻게 구하는지 설명하라고 하면 매끄럽게 설명하기는 힘든데 구하라고 하면 잘 구한다. 그냥 직관적으로 딱 나오는 경우도 있고, FM대로 하면 두 수의 약수를 싹다 구하고 공통된거 찾아서.... 이렇게 구하는 방법이 있긴 하다. 그런데 알고리즘 문제를 푸는데 최대공약수와 최소공배수 개념이 나왔다? 컴퓨터에게 하나 하나 논리적으로 설명해야 한다... 어떻게 최대공약수와 최소공배수를 구하는지 알아보자. 최대공약수 (Greatest Common Divisor) 말 그대로 공통 + 가장 큰 약수라는 의미이다. 최대공약수를 구하..