이 문제는 주어진 N개의 수를 오름차순으로 정렬해야 한다. 수의 개수(N)가 최대 10,000,000이지만, 주어진 값이 10,000 이하의 자연수로 한정적이라는 점에서 카운팅 정렬(Counting Sort)을 사용할 수 있다. 카운팅 정렬은 정수 데이터의 범위가 제한되어 있을 때 매우 효율적인 알고리즘이다.카운팅 정렬의 시간 복잡도는 O(N+K)이며 K는 값의 범위이다. 따라서 입력 크기가 크더라도 효율적으로 정리할 수 있다.  N = 10입력: 5, 2, 3, 1, 4, 2 ,3 ,5, 1, 7 카운트 배열 생성데이터의 범위가 1~10,000이므로 크기가 10,0001인 카운트 배열을 생성한다. 입력된 값의 등장 횟수를 카운트 배열에 저장한다. 카운팅 정렬에서는 값의 크기를 인덱스로 사용한다. 예를 ..

정렬된 배열에서 특정 값의 등장 횟수를 효율적으로 구하는 방법으로 이진탐색을 활용할 수 있다. 이진탐색은 정렬된 배열에서 원하는 값을 찾기 위해 검색 범위를 절반으로 줄여나가는 알고리즘이다. 배열에서 중간값을 선택하고, 검색 대상 값이 중간값보다 크거나 작은지에 따라 검색 범위를 좁혀나갈 수 있다. 반복적으로 범위를 줄이다보면 값을 찾거나 값이 존재하지 않음을 확인할 수 있다. 이진탐색의 시간복잡도는 O(logN)으로 매우 빠르다.  이진탐색은 정렬이 된 배열에서 사용해야 하므로 주어진 배열을 우선 정렬해야 한다.[6, 3, 2, 10, 10, -10, -10, 7, 3] -> [-10, -10, 2, 3, 3, 6, 10, 10, 10]찾고자 하는 값(target = 10)일 경우 10은 주어진 배열에..

알고리즘을 시작할 때 가장 먼저 접하게 되는 주제는 정렬(Sorting)이다.여러가지 정렬 알고리즘이 있지만 병합정렬은 시간 복잡도가 항상 O(nlogn)으로 안정적이고 효율적이며 성능도 좋다.병합정렬은 재귀적으로 배열을 계속 반으로 나누기 때문에 분할하는 단계는 배열의 크기 n에 대해 log₂n번 실행된다. 참고: 백준 문제를 사용해서 글을 작성했으나 병합정렬로 수 정렬하기2를 풀면 시간초과가 나오므로 해당 문제는 언어에 내장된 함수를 써야함. 수 정렬하기 2 답은 더보기 클릭.더보기import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.InputStreamReader;import java.io.OutputStreamWrit..

풀이import java.util.Stack;class Solution { public int solution(int[][] board, int[] moves) { int answer = 0; Stack stack = new Stack(); for (int i : moves) { for (int j = 0; j   이 문제는 stack을 사용하면 쉽게 풀 수 있다.풀면서 헷갈리게 만드는 점이 두 가지 있었는데 풀면서 문제가 참 불친절하다고 생각했다...우선 제일 헷갈렸던 건 행렬인데 i가 행, j가 열인 줄 알고 풀었다가 대차게 틀리고 그림을 그려보고 확실하게 이해하게 됐다. 문제의 예시를 인형뽑기 크레인처럼 놓아본다면 아래와 같다. Row ..

풀이import java.util.*;class Solution { public int[] solution(int N, int[] stages) { int[] answer = new int[N]; double[] noClearUser = new double[N]; double[] reachUser = new double[N]; HashMap map = new HashMap(); for (int i = 0; i = i+1) { reachUser[i]++; } } if (noClearUser[i] == 0.0 || reachUser[i] ==..

[작성일: 2023. 10. 23] https://www.acmicpc.net/problem/1181  풀이import java.util.ArrayList;import java.util.Collections;import java.util.HashSet;import java.util.List;import java.util.Scanner;import java.util.Set;public class Main { public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); String[] strArr = new String..