본문 바로가기

Develop/Algorithm29

a를 b로 나눈 수를 올림할 때, 알고리즘 문제를 풀다가, a를 b로 나눈 수를 올림하는 과정이 필요했다. 항상 반올림, 올림, 내림할 상황이 생기면, Math 클래스의 메서드를 이용하곤 했다. Math.round(), Math.ceil(), Math.floor() 순서대로 반올림, 올림, 내림 그러나, 다른 분들이 푸신 풀이 중에 올림하는 과정을 수식으로 나타내서 코드의 실행 시간을 줄이는 걸 볼 수 있었다. 정수 a를 정수 b로 나눈 수를 올림한 수가 필요할 때, 다음과 같이 작성하면 될 것 같다. (a + b - 1) / b 모든 올림의 과정에 쓰일지는 모르겠지만, 정수 a를 b로 나눈 올림 수가 필요할 때, Math.ceil() 메서드 대신 써보려고 한다. 왜 이렇게 쓰일 수 있는지, 다른 상황에서도 쓰일 수 있는지는 계속 알고리.. 2022. 10. 23.
Java) 버블 정렬(Bubble Sort) 알고리즘 여러 정렬(Sort) 알고리즘 중에 '버블 정렬'에 대해 알아보자. 버블 정렬은 정렬 알고리즘 중에서 가장 기본적인 알고리즘이다. 인접한 두 요소를 검사하여 정렬하는 방법이다. 시간 복잡도는 O(n^2)으로 상당히 느리다. 하지만, 코드는 짜기 매우 단순하다. 코드는 다음과 같다. public class SortAlgorithm { public int[] bubbleSort(int[] arr) { // 외부 for문은 배열의 길이만큼 반복문을 돌려야 함 for (int i = 0; i < arr.length; i++) { boolean swapped = false; // 내부 for문은 끝을 제외한 나머지 길이(n-1)만큼 반복문을 돌려야 함 for (int j = 0; j < arr.length - i.. 2022. 10. 20.
Java) 피보나치 수열 + Advanced 피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수이다. 피보나치 수열은 재귀 함수를 이용한 풀이가 일반적이다. 다음 코드와 같다. public int fibonacci(int num) { if (num 2022. 10. 20.
바빌로니아 법의 점화식을 이용한 제곱근의 근삿값 찾기 다음 코드를 통해 예시를 살펴보자. public class Solution { public String computeSquareRoot(int num) { // 바빌로니아 법 정밀도 상수 (높을수록 정밀해짐) final int PRECISION = 10; double x = PRECISION; for (int i = 0; i < PRECISION; i++) { x = 0.5 * (num / x + x); } // 바빌로니아 법을 통한 제곱근을 소수점 두 자리까지 반환 return String.format("%.2f", x); } } 여기서, PRECISION 변수가 높은 수를 가질수록, 근삿값의 정밀도는 올라간다. 또, 바빌로니아 법의 점화식은 다음 코드 구문이라고 생각하면 된다. x = 0.5 * (n.. 2022. 10. 11.
시간복잡도 2022. 9. 28.
그래프(Graph) 구조 그래프(Graph)는 실제 세계의 현상이나 사물을 정점(Vertex) 또는 노드(Node)와 간선(Edge)로 표현하기 위해 사용한다. 이해하기 어렵다면, 지하철 노선도라고 생각하면 편하다. 그래프 종류는 다음과 같다. 무방향 그래프(Undirected Graph) 방향이 없고, 간선을 통해 노드는 양방향으로 갈 수 있다. 보통 노드 A, B가 연결되어 있는 경우, (A, B) 또는 (B, A)로 표기한다. 방향 그래프(Directed Graph) 간선에 방향이 있는 그래프이다. 보통 노드 A, B가 A -> B로 가는 간선으로 연결되어 있을 경우, 로 표기한다.(와는 다르다) 가중치 그래프(Weighted Graph) 간선에 비용 또는 가중치가 할당된 그래프 가중치를 각 노드 간의 거리라고 생각하면 편.. 2022. 9. 24.
트리(Tree) 구조 트리(Tree)는 Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조이다. 탐색(검색) 알고리즘 구현을 위해 많이 사용된다. 이진 트리(Binary Tree)는 Node의 최대 Branch가 2개인 트리 이진 탐색 트리(Binary Search Tree; BST)는 이진 트리에 추가적인 조건이 있는 트리 추가적인 조건이라 하면, 왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값을 가짐 2022. 9. 24.
스택(Stack)과 큐(Queue) 스택(Stack)은 데이터를 순서대로 쌓는 자료구조이다. 모두가 아는 대표적인 예로 프링글스가 있다. 또, 브라우저의 뒤로 가기, 앞으로 가기 기능을 예로 들 수 있다. 후입선출(LIFO), 가장 마지막에 들어간 데이터가 가장 먼저 나오게 되는 자료구조이다. 스택(Stack)의 특징은 입출력 방향이 한 개로, 같다. 하나의 방향으로 입력되고 다시 그 방향으로 출력이 된다. 쌀보리를 하는 내 주먹과 같이 말이다. 큐(Queue)는 순서대로 들어간 데이터가 그 순서대로 나오는 자료구조이다. 톨게이트를 지나는 차량들에 비유할 수 있다. 선입선출(FIFO), 가장 먼저 들어간 데이터가 가장 먼저 나오게 되는 자료구조이다. 큐(Queue)에 데이터를 넣는 것은 'enqueue', 데이터를 꺼내는 것은 'deque.. 2022. 9. 22.
재귀 함수와 메모리 사용량 관계 _ 꼬리 재귀 재귀 함수는 반복하여 매서드를 호출한다. 그 과정에서 지역 변수, 매개 변수, 반환 값을 모두 process stack에 저장하게 된다. 이러한 과정은 반복문보다 더 많이 메모리를 사용하기 때문에, 성능이 좋지 않다. 스택 오버플로우를 일으킬 위험이 있다. 이러한 단점을 보완하기 위한 최적화 방법이 바로 꼬리 재귀이다. 꼬리 재귀는 재귀 호출이 끝난 후, 현재 함수에서 추가적인 연산을 요구하지 않는 재귀의 형태이다. 이는 컴파일러가 선형으로 코드를 처리하도록 알고리즘을 바꿔서 스택을 재사용 가능하게끔 한다. 단, 컴파일러가 이 기능을 지원해야 사용 가능하다. 다음 코드를 예시로 일반적인 재귀 함수와 꼬리 재귀를 파악해보자. 위 두 코드 모두 같은 결과를 출력한다. 좌측의 일반적인 재귀 함수는 스텍이 계속.. 2022. 9. 21.