![]()
선택 정렬 (Selection Sort) 기초적인 정렬 방법 중 하나입니다. 배열에서 가장 작은 값을 찾아서 맨 앞에 숫자와 교환합니다. 이 작업을 반복하여 앞에서부터 작은 값을 채워 정렬을 완성합니다. 가장 작은 값을 선택해서 선택 정렬 입니다. 시간 복잡도는 O(N^2) 입니다. 버블 정렬 보단 빠르고 삽입 정렬 보단 느립니다. 평균적인 정렬 속도 : 버블 < 선택 < 삽입 선택 정렬은 이해하기 쉽고 구현하기 간단하지만 효율성은 낮은 편입니다. 각 요소를 나머지 모든 요소와 비교해야 하기 때문입니다. 대규모 데이터셋에는 효과적이지 않고 작은 데이터셋에서 사용합니다. 동작 과정 시간 복잡도 : O(n^2) 1. 최소값 탐색 : 주어진 배열에서 최소값을 찾습니다. 2. 최소값과 교환: 배열의 첫 번째 위..
![]()
버블 정렬 (Bubble Sort) 기초적인 정렬 방법 중 하나입니다. 큰 값이 끝으로 가는 것이 거품처럼 피어오른다고 해서 버블 정렬이라고 합니다. 시간 복잡도는 O(N^2) 이고 느린 편에 속합니다. 버블 정렬은 선택 정렬, 삽입 정렬 보다 느립니다. 평균적인 정렬 속도 : 버블 < 선택 < 삽입 버블 정렬은 구현이 간단하지만 효율성이 낮은 편입니다. 각 요소가 평균적으로 여러 번 비교되고 이동해야 하기 때문입니다. 동작 과정 시간 복잡도 : O(n^2) 1. 비교화 교환 : 배열을 순회하면서 현재 인덱스의 값과 다음 인덱스의 값을 비교하여 오른쪽이 큰 값이 오도록 교환합니다. 2. 반복 : 이 과정을 한 번 수행하면 가장 큰 값이 배열의 끝으로 버블링(상승)하게 됩니다. 이 과정을 반복합니다. 3...
![]()
정렬이란? 정렬이란 데이터를 특정 기준에 따라 순서대로 나열한 것 입니다. 정렬이 중요한 이유는 데이터를 정렬하면 이진 탐색을 할 수 있게 되기 때문입니다. 이진 탐색은 절반씩 탐색하므로 전체를 탐색하는 선형 탐색 보다 압도적으로 빠르게 원하는 자료를 찾을 수 있습니다. 대신, 이진 탐색은 정렬된 배열에서만 사용할 수 있습니다. 이로 인해, 정렬 알고리즘이 중요해졌고 다양한 정렬 알고리즘이 등장했습니다. 정리 정렬이란 데이터를 특정 기준에 따라 순서대로 나열한 것 정렬을 하면 이진 탐색이 가능해져 검색 속도를 올릴 수 있다. 정렬 알고리즘의 종류 정렬 알고리즘의 종류는 다양하며, 각각의 알고리즘은 그 특성과 성능이 다르므로 주어진 환경에 맞게 적절한 알고리즘을 선택하는게 중요합니다. 다음은 정렬 알고리즘..
![]()
문제 출저 https://www.acmicpc.net/problem/2346 2346번: 풍선 터뜨리기 1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선 www.acmicpc.net 문제 풀이 풍선의 갯수와 풍선 안에 숫자가 주어집니다. 풍선 안에 숫자는 양수와 음수로 양수면 오른쪽부터 세고, 음수면 왼쪽으로 셉니다. 셈을 마친 풍선을 터뜨리고 해당 풍선의 숫자만큼 반복합니다. 1번부터 풍선을 터뜨렸을 때, 어떤 순서로 풍선들이 터지는지 구해야 합니다. Deque를 이용해 문제를 풀었습니다. 양수인 경우 해당 숫자만큼 처음에서 빼서 끝에 넣었습니다..
![]()
문제 출저 https://www.acmicpc.net/problem/7490 7490번: 0 만들기 각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다. 각 테스트 케이스의 결과는 한 줄을 띄워 구분한다. www.acmicpc.net 문제 풀이 테스트 케이스 t가 주어지고 t번 만큼 숫자 n이 주어집니다. 1부터 n까지 차례대로 숫자를 사용하고 숫자 사이에 +. -. " "(공백)을 넣어 수식을 완성합니다. 공백은 숫자 2개를 붙인다는 의미 입니다. (2 3 => 23) 수식을 완성하고 계산했을 때, 0이 되는 수식을 구해야 합니다. dfs를 이용해 전체 수식의 경우의 수를 구했습니다. 수식은 공백을 붙이기 위해 String으로 구했습니다. String의 replace..
![]()
문제 출저 https://www.acmicpc.net/problem/1722 1722번: 순열의 순서 첫째 줄에 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄의 첫 번째 수는 소문제 번호이다. 1인 경우 k(1 ≤ k ≤ N!)를 입력받고, 2인 경우 임의의 순열을 나타내는 N개의 수를 입력받는다. N개의 수에는 1부터 N www.acmicpc.net 문제 풀이 이 문제는 2가지 문제를 풀어야 합니다. 첫 번째 입력은 n이 주어지고 두 번째 입력의 첫 번째 숫자는 어떤 문제를 풀어야 하는지 타입입니다. 1인 경우, k가 주어지며 k번째 순열을 구해야 합니다. 2인 경우, 순열이 주어지며 이 순열이 몇 번째 순서인지 구해야 합니다. 문제의 n은 20이므로 일일히 다 순열을 구하면 20! 이 되므로 시간초과..
![]()
문제 출저 https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 문제 풀이 주사위를 굴려 1부터 시작해서 100번째 칸에 가려합니다. 이 때, 주사위는 원하는 숫자를 뽑을 수 있고 칸에는 사다리와 뱀이 있습니다. 사다리는 낮은 숫자에서 높은 숫자로 이동하고 반대로 뱀은 높은 숫자에서 낮은 숫자로 이동합니다. 사다리와 뱀의 정보가 주어질 때, 100번째 칸으로 가기 위한 주사위를 굴리는 최소 횟수를 구해야..
![]()
문제 출저 https://www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 문제 풀이 테스트 케이스 t가 주어집니다. t의 수 만큼 n이 주어질 때, 1,2,3을 더해서 n을 만들 경우의 수를 구해야 합니다. 이 때 연속으로 같은 수가 오면 안됩니다. 경우의 수에 1_000_000_009의 나머지 값을 구해야 합니다. dp로 문제를 풀었습니다. n의 범위는 100_000 입니다. dp[100_001][4] 2차원 배열을 만들었습니다. dp[n][1] 이것은 n번째 수의 1로 끝나는 경우의 수 입니다. n의 모든..
![]()
문제 출저 https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 문제 풀이 숫자가 주어졌을 때, 3이나 2로 나누어 떨어지면 나눌 수 있고 -1을 할 수 있다. 이런 식으로 연산을 거쳐 1을 만들 때 최소한 연산 횟수와 그 과정을 구해야 합니다. DP를 이용해서 풀었습니다. 처음에 BFS로 Queue를 이용하고 이미 방문한 곳이 횟수가 적으면 가지치기를 하는 방식으로 풀었는데 시간 초과가 발생했습니다. 1차원 배열과 메모리제이션으로 코드를 바꿔서 문제를 풀었습니다. 문제를 풀기 위해 dot 클래스를 새로 만들었습니다. dot 클래스는 횟수를 저장하는 co..
![]()
문제 출저 https://www.acmicpc.net/problem/2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 문제 풀이 번호를 가진 아이들이 있습니다. 이 아이들을 번호 순서대로 줄을 세우려 할 때 이동해야 하는 최소한의 갯수를 구해야 합니다. DP를 이용해 풀었습니다. 이동해야 하는 최소 갯수는 오름차순이 되지 않은 숫자들의 갯수 입니다. 예제의 경우를 보면 3 7 5 2 6 1 4 인데 이 때 가장 긴 오름차순의 길이는 3 5 6 으로 3 입니다. 그러면 나머지 숫자들의 자리를 바꿔주면 되므로 정..
![]()
문제 출저 https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 문제 출저 2차원 배열에 바이러스가 숫자로 부여됩니다. 바이러스는 1초에 상하좌우로 퍼지고 이미 바이러스가 있다면 퍼지지 않습니다. s 초 후, (x,y) 좌표에 어떤 바이러스가 있는지 구해야 합니다. 구현으로 문제룰 플었습니다. dot 클래스를 만들어 x,y,count 좌표를 만들었습니다. List virus 자료형을 만들어 바이러스 번호대로 위치를 저장..
![]()
문제 출저 https://www.acmicpc.net/problem/20002
