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. 문제 설명 이제 실제로 백트래킹을 사용하여 해결할 문제를 살펴보겠습니다. 주어진 조건에 따..

문제 알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다. 입력 첫째 줄에 알파벳 대소문자로 이루어진 단어가 주어진다. 주어지는 단어의 길이는 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)은 가장 간단한 정렬 알고리즘 중 하나입니다. 이 알고리즘은 주어진 리스트에서 가장 작은 값을 선택하여 맨 앞으로 이동시키는 과정을 반복하여 리스트를 정렬하는 방식입니다. 동작 과정 주어진 리스트에서 가장 작은 값을 찾습니다. 가장 작은 값과 리스트의 맨 앞의 원소를 교환합니다 정렬된 영역을 제외하고 나머지 리스트에서 가장 작은 값을 찾습니다. 다시 가장 작은 값과 정렬되지 않은 부분의 맨 앞 원소를 교환합니다. 이러한 과정을 리스트의 모든 원소가 정렬될 때까지 반복합니다. 예시 코드 public class SelectionSort { /** * i 와 j의 위치에 있는 값을 바꿉니다. (가장 작은 값인 array[j]와 array[i]의 ..

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

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

시간 복잡도 위에 그래프의 모습에서 보이는 것처럼 간단한 출력과 같은 O(1) 혹은 단순한 증가함수인 O(n), O(log n ) 들과 O(n^2), O(2^n)의 그래프의 기울기가 큰 차이가 나타나는 걸 볼 수 있습니다. 컴퓨터가 계산할 때 사용하는 알고리즘,함수에 따라 값에 증가에 따른 결괏값을 구하는 시간이 달라지는데 이를 시간 복잡도라고 얘기합니다. 시간 복잡도를 고려해야 하는 이유 우리가 프로그램을 만들 때 구현하려는 값을 어떤 알고리즘을 이용해 구현하느냐에 따라 그 프로그램의 최적화에 영향이 가기에 항상 어떻게 하면 더 효율적으로 구현할 수 있는지 고민해야 하며 알고리즘 문제를 풀 때도 문제에서 원하는 시간을 초과하면 문제를 풀 수 없는 경우도 있기에 어떠한 방식으로 알고리즘을 구현할지 생각할..

재귀함수의 요건에는 두 가지가 있다. 하나는 재귀함수가 탈출할 수 있도록 재귀를 할 때마다 값에 변화를 탈출 조건에 다가가게 설정하는 것이고 하나는 그 탈출 조건, 즉 탈출구를 만드는 것이다. public class anything { static int num; static int sum; public static void main(String[] args) { System.out.println(CordJg(0)); } public static int CordJg(int count){ if(count==5){ sum = num; return sum; } num=num+1; System.out.println(num); //출력 1,2,3,4,5(재귀가 반복될 때마다 1증가) CordJg(count+1);..