![]()
삽입 정렬 (Insertion Sort) 기초적인 정렬 방법 중 하나 입니다. 인덱스의 값이 왼쪽보다 작다면 위치를 교환합니다. 이 과정을 왼쪽보다 클 때까지 반복합니다. 이 과정을 반복하면 왼쪽에 정렬된 부분이 생깁니다. 정렬된 부분에 새로운 값이 삽입되므로 삽입 정렬이라 합니다. 삽입된 값은 왼쪽이 자기보다 작을 때까지 교환합니다. 이 과정을 통해 자기 자리를 찾아 정렬을 완성합니다. 시간 복잡도는 O(N^2) 입니다. 버블 정렬, 선택 정렬 보다 평균적인 정렬 속도가 빠릅니다. 평균적인 정렬 속도 : 버블 < 선택 < 삽입 삽입 정렬은 작은 데이터셋에서 효율적입니다. 또한, 동일한 요소가 있을 경우 정렬한 후에 순서가 지켜져 안정적입니다. 삽입 정렬은 이후에 팀소트(TimSort)에서 작은 크기로 ..
![]()
선택 정렬 (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번째 칸으로 가기 위한 주사위를 굴리는 최소 횟수를 구해야..
![]()
개요 우테코에 지원하여 프리코스 과정을 진행했습니다. 매주 과제를 풀고 제출하는 형식으로 4주 동안 진행했습니다. 매주 과제가 끝나면 우테코 측에서 피드백을 제공했습니다. 디스코드로 커뮤니티를 만들어 동료 지원자들끼리 소통의 창구를 만들어 주었습니다. 디스코드에서 스터디를 꾸리거나 서로의 과제 PR을 공유해 코드를 리뷰했습니다. 이 과정에서 많은 부족한 점을 발견하고 개선했으며 다른 사람의 코드를 통해 좋은 점을 많이 흡수했습니다. 과제 1주차 : 숫자 야구 https://github.com/cladren123/java-baseball-6 2주차 : 자동차 경구 https://github.com/cladren123/java-racingcar-6 3주차 : 로또 https://github.com/cladr..
![]()
문제 출저 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의 모든..
![]()
개요 이번에는 Docker Desktop의 내용과 설치를 정리해 보려 합니다. Docker Desktop은 도커를 데스크탑 환경에서 사용할 수 있게 해주는 프로그램 입니다. 여기서 데스크탑 환경이란 Mac이나 Windows를 말합니다. Docker Desktop을 설치하면 Docker Engine, Docker CLI, GUI 환경을 제공해 줍니다. Docker Desktop을 사용하면 개발자는 컨테이너화된 애플리케이션을 쉽게 구축, 배송, 실행할 수 있습니다. 특징 배포 용이성 Docker Desktop에 포함된 Docker Engine을 사용하면 개발자가 어디서든 쉽게 배포하고 실행할 수 있는 컨테이너를 만들 수 있습니다. 이를 통해 다양한 환경에서 일관성과 배포 용이성을 얻을 수 있습니다. 공유 D..
![]()
문제 출저 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..
