CordCat

문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 난 이 문제를 처음에 수가 100만 개나 입력되기 때문에 시간복잡도가 효율적인 정렬을 사용하기 위해 Quick Sort를 이용해서 풀려고 했었다. Quick Sort import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; impo..

정렬은 컴퓨터 과학에서 핵심적인 작업 중 하나로, 데이터의 순서를 재조정하는 과정입니다. 이는 다양한 분야에서 중요한 역할을 수행하며, 데이터 처리와 탐색에 필수적입니다. 정렬 알고리즘은 데이터 크기, 구현 제약사항, 사용 가능한 메모리 용량 등에 따라 효율적으로 선택되어야 합니다. 이 글에서는 데이터 크기, 구현 제약사항, 메모리 사용 등을 고려하여 상황에 맞는 최적의 정렬 알고리즘을 선택하는 방법에 대해 다루고자 합니다. 작은 데이터 크기 작은 데이터에 대해서는 삽입 정렬(Insertion Sort)이 효율적입니다. 추가적인 메모리 사용 없이 구현이 간단하며, 데이터 크기에 민감하지 않습니다. Insertion Sort 시간 복잡도 : - 최선의 경우 : O(n) - 평균 및 최악의 경우: O(n^2..

백트래킹은 조합 탐색과 같은 문제에서 해를 찾는 도중에 해가 될 수 없는 경우를 미리 파악하여 탐색을 중단하고 다른 경로를 탐색하는 효율적인 기법입니다. 이번 글에서는 백트래킹 알고리즘의 개념과 구현 방법, 그리고 실제 문제를 해결하는 과정을 예시를 통해 알아보겠습니다. 1. 백트래킹 알고리즘이란? 백트래킹은 문제의 조건에 따라 탐색해야 하는 모든 경우의 수를 시도하면서 해를 찾는 알고리즘입니다. 주로 DFS(깊이 우선 탐색)와 함께 사용되며, 재귀 함수를 통해 구현됩니다. 백트래킹은 가능한 경우의 수를 줄여나가면서 해를 찾는 방법으로, 탐색 과정에서 불필요한 경로를 배제하여 실행 속도를 향상할 수 있습니다. 2. 문제 설명 이제 실제로 백트래킹을 사용하여 해결할 문제를 살펴보겠습니다. 주어진 조건에 따..

char 타입으로 초기값을 넣어주고 값을 증가시켜주면 단어사전 순으로 단어가 변화된다. String[] alphabet = new String[26]; char currentChar = 'a'; for (int i = 0; i < 26; i++) { alphabet[i] = String.valueOf(currentChar); currentChar++; } System.out.println(Arrays.toString(alphabet)); 결과는 [a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z] 만약 대문자로 구성된 배열을 만들고 싶으면 'a' 대신 'A'를 넣어주면 된다. 또한 알파벳 뿐만 아니라 한글도 가능하다!

문제 알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다. 입력 첫째 줄에 알파벳 대소문자로 이루어진 단어가 주어진다. 주어지는 단어의 길이는 1,000,000을 넘지 않는다. 출력 첫째 줄에 이 단어에서 가장 많이 사용된 알파벳을 대문자로 출력한다. 단, 가장 많이 사용된 알파벳이 여러 개 존재하는 경우에는?를 출력한다. package codingTest.bronze; import java.util.*; import java.util.stream.Collectors; public class Bj1157 { public static void main(String[] args) { Scanner sc..

https://www.acmicpc.net/problem/9095 6개 211111 2311 2 두 개 -> 22111 5! / (2!*3!) 2 3개 -> 2221 4!/3! 4 3 하나 -> 31111 5! / 4! 3 두개 -> 331 3! / 2! 2 하나 + 3 하나 -> 2311 4!/2! -> 12 2 두개 + 3 하나 -> 223 3 이런 식으로 경우의 수를 나눠 순열조합으로 풀 수 있을 거라 생각을 해서 아래와 같이 문제를 풀었다. 순열을 이용한 풀이 import java.util.*; public cl..

Selection Sort Selection sort is one of the simplest sorting algorithms. It repeatedly selects the smallest value from the given list and moves it to the front, thereby sorting the list Process Explanation Find the smallest value in the given list. Swap the smallest value with the first element of the list. Find the smallest value in the remaining unsorted part of the list (excluding the sorted ..

Selection Sort 선택 정렬(Selection Sort)은 가장 간단한 정렬 알고리즘 중 하나입니다. 이 알고리즘은 주어진 리스트에서 가장 작은 값을 선택하여 맨 앞으로 이동시키는 과정을 반복하여 리스트를 정렬하는 방식입니다. 동작 과정 주어진 리스트에서 가장 작은 값을 찾습니다. 가장 작은 값과 리스트의 맨 앞의 원소를 교환합니다 정렬된 영역을 제외하고 나머지 리스트에서 가장 작은 값을 찾습니다. 다시 가장 작은 값과 정렬되지 않은 부분의 맨 앞 원소를 교환합니다. 이러한 과정을 리스트의 모든 원소가 정렬될 때까지 반복합니다. 예시 코드 public class SelectionSort { /** * i 와 j의 위치에 있는 값을 바꿉니다. (가장 작은 값인 array[j]와 array[i]의 ..

우선순위 큐(Priority Queue)는 개발자가 자주 활용하는 자료구조 중 하나입니다. 이번에는 우선순위 큐에 대해 자세히 알아보고, 실제로 어떻게 사용되는지 예시 코드를 통해 살펴보겠습니다. 우선순위 큐는 요소들을 우선순위에 따라 정렬하여 저장하는 자료구조입니다. 일반적인 큐와 달리 요소들이 저장될 때 우선순위에 따라 정렬되므로, 가장 우선순위가 높은 요소에 먼저 접근할 수 있습니다. 우선순위는 개발자가 지정한 기준에 따라 결정됩니다. 예를 들어, 다익스트라 알고리즘에서 최단 경로를 찾는 과정에서 우선순위 큐를 사용할 수 있습니다. 출발지에서 각 노드까지의 최단 거리를 계산할 때, 우선순위 큐를 활용하여 현재까지의 최단 거리를 기준으로 노드를 선택하고 처리할 수 있습니다. 아래는 우선순위 큐를 활용..

DP는 다양한 문제에서 사용되는 효율적인 알고리즘 기법 중 하나이다. 코딩테스트 문제를 풀다가 최단 경로 문제에 DP의 필요성을 알게 돼서 DP에 대해 정리해 본다. 최단 경로 문제는 출발지에서 도착지까지 가는 경로 중 가장 짧은 경로를 찾는 문제로, 다익스트라 알고리즘과 벨만-포드 알고리즘이 대표적인 예시이다. DP 배열은 중복 계산을 피하기 위해 사용되며, 최단 경로 문제에서는 각 노드까지의 최단 거리를 저장하는 역할을 하고, 각 노드까지의 최단 거리를 DP 배열에 저장하면 다음 계산에서 이전 계산 결과를 활용하여 중복 계산을 피할 수 있다. 아래는 최단 경로 문제를 DP 배열로 해결하는 다익스트라 알고리즘을 사용하여 출발지에서 각 노드까지의 최단 거리를 구하는 예시 코드이다. import java...