코딩아 재윤해

import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int num = sc.nextInt(); for (int i = 1; i

import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputSt..

이진 탐색 알고리즘은 검색 범위를 줄여 나가면서 원하는 데이터를 검색할 때 사용하는 알고리즘이다. 오름차순으로 정렬된 리스트를 반으로 나누고 찾는 원소가 중간에 있는지 확인하고, 없으면 위쪽 또는 아래쪽에 있는지를 판단하여 다시 같은 방식으로 원소를 찾는 방법이다. 게임 'up & down'을 예로 들면, 1부터 100까지의 수 중에서 41이라는 숫자를 찾는다고 한다. 먼저 중간 값인 50이나 51중에서 찾으려는 41이 두 값보다 작기 때문에 1부터 49를 새로운 범위로 설정해서 찾는다. 다시 절반인 25를 기준으로 찾으려는 41이 크기 때문에 26부터 49까지 새로운 범위로 설정해서 찾는다. 이렇게 데이터가 정렬된 상태에서 절반씩 범위를 나눠 분할 정복기법으로 특정한 값을 찾아내는 방법을 이진 탐색 알..

컴퓨터 과학에서 Brute Force는 시행착오 방법론을 말한다. 컴퓨터의 빠른 계산 능력을 이용해 가능한 경우의 수를 모두 나열하면서 답을 찾는 방법이다. 이 방법은 직관적이어서 이해하기 쉬우며 문제의 정확한 답을 얻어낼 수 있는 가장 확실하고 기초적인 방법이다. 예를 들어, 4개의 숫자로 구성된 자물쇠를 푼다고 하면 0000부터 9999까지 모두 시도해 보면 해결할 수 있다. 이렇게 하나하나 대입하여 시도하는 방식 완전 탐색 알고리즘이라고 한다. 완전 탐색 알고리즘은 공간 복잡도와 시간 복잡도의 요소를 고려하지 않고 솔루션을 찾으려고 하는 방법이기 때문에 최적의 솔루션은 아닐 수 있다. 사용 완전 탐색 알고리즘은 크게 다음과 같은 두 가지 경우에 사용한다. 프로세스 속도를 높이는 데 사용할 수 있는 ..

덱(Double-Ended Queue, Deque)은 양방향 대기열이라고도 불리는 자료구조이다. 외형적으로는 queue와 비슷한 구조를 갖고있으며, 한 방향인 queue와 stack과는 다르게 LIFO, FIFO같은 순서에 구속되지 않는다. 즉, 덱은 양쪽 끝에서 삽입과 삭제가 모두 가능하며 어떤 쪽으로 입력하고 출력하느냐에 따라서 stack과 queue로 사용할 수 있다. 이때, 한쪽으로만 입력이 가능하도록 설정한 덱을 스크롤(scroll)이라고 하고 한쪽으로만 출력이 가능하도록 설정한 덱을 셸프(shelf)라고 한다. 특징 덱은 다음과 같은 특징을 갖고 있다. Stack 및 Queue를 모두 사용할 수 있다. 덱은 양쪽으로 데이터를 추가하고 삭제할 수 있기 때문에 둘 다 구현이 가능하다. 만약 양쪽 ..

탐욕 알고리즘(greedy algorithm)은 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다. 즉, 최적해를 구하는 데에 사용되는 근사적인 방법이다. 순간마다 하는 선택은 그 순간에 한해서는 최적이지만 그러한 선택들을 통해 최종적인 해답을 얻었다고 해서 그 해답이 최적이라는 보장이 없다. 예외의 상황이 있을 수 있기 때문이다. 따라서, 이러한 예외 상황을 배제하고 탐욕 알고리즘을 통해 최적의 해를 구하기 위해서는 다음과 같은 두 가지 조건을 만족시켜야 한다. 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않는다. 최적 부분 구조(Optimal Substructure) : 문제에 대한 최적해가 부분문제에..

알고리즘 로직을 코드로 구현할 때, 시간 복잡도를 고려한다는 것은 연산 횟수에 비해 시간이 얼마만큼 걸리는가를 생각하는 것이다. 즉, 문제를 해결하는 데 걸리는 시간과 입력의 함수 관계를 가리킨다. 효율적인 알고리즘을 구현한다는 것은 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구성한다는 것이다. 시간 복잡도를 표기하는 방법은 Big-O, Big-Ω, Big-θ가 있으며, 이 세 가지 표기법은 각각 최악, 최선, 평균의 경우에 대하여 나타내는 방법이다. 주로 Big-O 표기법을 사용한다. Big-O 표기법을 주로 사용하는 이유는 다음과 같다. 바로 프로그램이 실행되는 과정에서 소요되는 최악의 경우 시간까지 고려할 수 있기 때문이다. '최소 이 정도 시간 이상이 걸린다' 고려하기보다는 ..

탐색 알고리즘이란 방대한 데이터에서 목적에 맞는 데이터를 찾아내기 위한 알고리즘이다. 알고리즘의 영역은 그 범위가 매우 넓어서 프로그래밍을 하는 개발자라면 의도하지 않아도 특정 알고리즘을 사용하는 경우가 대부분일 정도이며, 알고리즘의 종류 중에서도 탐색 및 정렬은 가장 많이 사용된다. 그래프의 탐색은 하나의 노드에서 시작해서 모든 노드들을 한 번씩 탐색하는 것이 목적이다. 예를 들면, 특정 장소에서 다른 장소로 갈 수 있는지, 최단 경로를 찾는 경우 등 있다. 그래프의 데이터는 배열처럼 정렬되어있지 않기 때문에 원하는 데이터를 찾기 위해서는 모두 방문해서 찾아야 한다. 너비 우선 탐색(Breadth-First Search, BFS) 너비 우선 탐색이란 임의의 노드에서 시작해서 인접한 노드를 먼저 탐색하는..

특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것을 트리 순회(tree traversal)라고 한다. 선형 자료 구조(stack, queue 등)는 순차적으로 요소에 접근하지만, 트리 구조는 계층적 구조라는 특징을 갖고 있기 때문에 모든 노드를 순회하기 위해서는 다른 방식을 사용해야 한다. 트리를 순회하는 방법은 크게 전위 순회, 중위 순회, 후위 순회가 있으며, 노드를 방문하는 순서에 의해 결정된다. 트리 구조에서 노드를 순차적으로 조회할 때의 순서는 항상 왼쪽부터 오른쪽으로 한다. 전위 순회(preorder traversal) 전위 순회는 다음과 같은 방법으로 진행한다. 루트 또는 서브트리의 루트 노드를 방문한다. 왼쪽 서브 트리를 방문한다. 오른쪽 서브 트리를 방문한다. 방문 순서 : 1 ..

이진 트리(binary tree)는 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 구조이다. 여기서 자식 노드들은 왼쪽 자식 노드, 오른쪽 자식 노드로 나뉜다. 이진 트리는 자료의 삽입, 삭제 방법에 따라서 다음과 같이 나뉜다. 정 이진 트리(ful binary tree) : 각 노드가 0개 혹은 2개의 자식 노드를 갖는다. 포화 이진 트리(perfect binary tree) : 정 이진 트리이면서 완전 이진 트리인 경우이다. 모든 리프 노드의 레벨이 동일하고 모든 레벨이 가득 채워져 있는 트리이다. 완전 이진 트리(complete binary tree) : 마지막 레벨을 제외한 모든 노드가 가득 차 있으며, 마지막 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 한다. 이진 탐색 트리(bi..