고양이 두 잔

자바에서 정렬을 하려면 Arrays 클래스가 import 되어야 한다. import java.util.Arrays; 오름차순 정렬의 경우 문자열이나 정수형이나 같은 방법을 이용한다. int[] arr = {3, 7, 4, 1, 0, 6}; String[] arr2 = {"AD", "GA", "ET", "BX", "GY"}; Arrays.sort(arr); Arrays.sort(arr2); System.out.println(Arrays.toString(arr)); System.out.println(Arrays.toString(arr2)); // 출력 결과 [0, 1, 3, 4, 6, 7] [AD, BX, ET, GA, GY] 내림차순 정렬의 경우엔 문자열과 정수형의 방법이 다르다. 정수형의 경우 Integ..

완전 탐색이란 컴퓨터의 성능을 믿고 모든 경우의 수를 다 체크하는 방법이다. 상대적으로 구현이 간단하고, 해가 존재한다면 반드시 찾을 수 있는 방법이기도 하다. 예를 들어 숫자 4자리로 구성된 자물쇠의 암호를 푼다면, '0000'부터 '9999'까지 다 넣어보는 방식이다. 당연하게도 최적의 솔루션을 제공해주지 않으며, 때문에 다음 두 상황에 주로 쓰인다. 적용 가능한 다른 알고리즘이 없을 때 복수의 솔루션을 확인해야 할 때 예를 들어 책 한 권이 주어지고 그 책에서 '고양이'라는 단어를 찾아야 한다고 가정해보자. 책은 당연하게도 단어들이 정렬되어 있지 않으므로 처음부터 끝까지 단어를 비교하는 수밖에 없다. 이럴 때 사용되는 것이 완전 탐색 알고리즘이며, 이 경우 시간 복잡도는 O(n)이다. 계속해서 완전..

목차 효율적인 알고리즘이란 입력값의 증가에 따른 시간의 비율을 최소화한 것이다. 따라서 효율적인 알고리즘을 고민한다는 것과 시간 복잡도를 낮춘다는 건 같은 말이 된다. 시간 복잡도란 '입력값과 연산 수행 시간의 상관관계를 나타내는 척도'이며, 쉽게 말하면 아래와 같다. 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가? 시간 복잡도를 표기하는 방법은 다음의 세 가지가 있으며, Big-O(빅-오) - 최악의 경우 고려 Big-Ω(빅-오메가) - 최선의 경우 고려 Bid-θ(빅-세타) - 중간(평균)의 경우 고려 언제나 최악의 경우를 고려하는 것이 바람직하기 때문에 빅-오 표기법이 많이 쓰인다. O(f(n))과 같이 표시하며, 이는 입력값 n이 증가할 때 연산 횟수가 f(n..

Graph(그래프)는 노드 사이의 연결 관계를 표현할 수 있는 자료구조이다. 앞서 보았던 트리구조 역시 사실은 그래프의 일종인데, 두 구조의 차이는 아래와 같다. 구분 그래프(Graph) 트리(Tree) 정의 객체 혹은 노드(Node)와 그것을 연결하는 간선(Edge)으로 모인 구조 그래프의 한 종류 방향성이 없으며 순환하지 않음 방향성 무방향 혹은 유방향으로 가능 단방향 그래프 순환성 순환 가능 자기 자신을 연결하는 간선(Self-Loop) 가능 순환(Cyclic), 비순환(Acyclic) 그래프 모두 가능 순환 불가능 자기 자신을 연결하는 간선(Self-Loop) 불가능 비순환 그래프(Acyclic Graph) 루트 루트의 개념이 있거나 없을 수 있음 하나의 루트 노드 존재 모델 네트워크 모델 계층 ..

Tree 자료구조 Tree(트리)는 주로 계층적인 구조를 표현하기 위해 사용한다. /Users/username 토너먼트 경기의 대진표 조직도 트리구조는 루트(Root)라는 최상위 노드에서 시작해 각 데이터를 간선(Edge, Link, Branch)으로 연결한다. 두 개의 노드가 상하관계를 가질 때 위의 노드를 부모 노드(Parent Node), 아래의 노드를 자식 노드(Child Node)라 부른다. 자식 노드가 없는 노드를 리프 노드(Leaf Node)라고 하며, 리프 노드를 제외한 노드를 인터널 노드(Internal Node)라 부른다. 또한 트리구조는 깊이와 레벨, 높이를 측정할 수 있는데 그 정의는 아래와 같다. 깊이(Depth) - 루트로부터 특정 노드까지의 간선 개수. 위 Animal의 경우 ..

Queue는 (대기)줄이라는 의미를 가지고 있다. 위 그림에서 보는 것처럼 데이터의 입력과 출력 방향이 따로 정해져 있으며, 먼저 들어간 데이터가 먼저 나오는 선입 선출(FIFO - First In First Out) 구조를 가지고 있다. 또한 스택의 경우와 마찬가지로 데이터의 입출력을 하나씩만 할 수 있다는 특징도 가지고 있다. 추가로 큐에 데이터를 집어넣는 동작을 'enqueue'라고 하며, 데이터를 빼는 동작을 'dequeue'라고 부른다. 주로 프린터의 출력 순서 알고리즘과 같이 이벤트의 실행 순서를 규칙적으로 만들기 위해 사용되는 큐는 태생적으로 LinkedList와 함께 사용된다. import java.util.LinkedList;//import import java.util.Queue;//i..

Stack은 더미, 퇴적, 쌓다 등의 의미를 지니고 있다. 하노이의 탑 퍼즐에서 기둥에 원판을 꽂듯이 데이터를 쌓는 구조라고 할 수 있는데, Stack(스택)의 가장 큰 특징은 바로 이 퍼즐과 같이 후입 선출(LIFO - Last In First Out)로 동작한다는 것이다. 설명을 추가로 덧붙이자면 스택 자료구조는 반드시 데이터를 하나씩만 넣고 뺄 수 있고, 그림에서 보이는 것과 같이 단 하나의 입출력 방향을 가지고 있다. 브라우저의 앞으로 가기나 뒤로 가기 기능을 구현할 때 사용되는 스택 자료구조는 간단하게 사용 가능하다. import java.util.Stack; // import Stack stack = new Stack(); // Integer형 스택 선언 위와 같이 먼저 Stack 클래스를 i..

배열을 출력하기 위해 바로 배열의 이름을 입력하거나 배열 자체의 메서드 toString()을 사용하려고 하면 원하던 내용이 아닌 배열의 주소 값이 출력된다. 이럴 때 사용하는 메서드가 Arrays.toString()이다. 예는 다음과 같다. public class Main { public static void main(String[] args) { int[] arr = {2, 4, 6, 8, 10}; System.out.println(arr); // 주소값 [I@129a8472 가 출력된다 System.out.println(arr.toString()); // 주소값 [I@129a8472 가 출력된다 System.out.println(Arrays.toString(arr)); // [2, 4, 6, 8, 1..

지난 번 글에서 재귀함수의 정의와 구현방법에 대해 알아보았다. https://gnidinger-coding.tistory.com/37 [Java]재귀 함수(Recursive Functions) 출처: https://www.geeksforgeeks.org/recursive-functions/ Recursive Functions - GeeksforGeeks A Computer Science portal for geeks. It contains well written, well thought and well explained computer.. gnidinger-coding.tistory.com 이 글을 바탕으로 이번 글에선 여러가지 적용 예를 들어본다. sayHello 이름 그대로 문자열 "Hello"를 n..

재귀 함수는 위 그림처럼 정의 단계에서 자기 자신을 다시 호출하는 함수를 말한다. 수학으로 봤을 땐 점화식이라고 생각하면 편하다. f(n) = f(n - 1) + n // 점화식 재귀 함수를 활용하면 반복적인 작업을 해야 하는 문제를 간결하게 풀 수 있는 경우가 있다. 반면 코드에 대한 직관적인 이해가 어렵고, 메모리를 많이 사용하게 된다는 단점도 존재한다. 재귀 함수에 익숙해지기 위해선 문제를 작게 쪼개는 연습을 하는 게 중요한데, 가장 간단한 예 중 하나인 팩토리얼로 예를 들어보자. 먼저 팩토리얼은 다음과 같이 계산한다. n! = n * (n - 1) * (n - 2) * ... * 2 * 1 0! = 1 1부터 n까지의 모든 자연수를 곱하는 계산이라고 생각하면 된다. 먼저 이 계산을 반복문을 통해 ..