정렬11

• 

  삽입 정렬(Insertion Sort) 삽입 정렬이란? 삽입 정렬은 두 번째 원소부터 시작하여 그 앞의 원소들과 비교하면서 앞의 원소가 크다면 해당 원소를 뒤로 옮기고, 크지 않다면 해당 위치의 다음 인덱스에 비교를 시작한 원소를 삽입하여 정렬하는 알고리즘입니다. 삽입 정렬의 기본 동작은 다음과 같습니다. 1. 정렬을 시작할 때, 첫 번째 요소는 이미 정렬된 상태로 간주합니다. 2. 두 번째 요소부터 시작하여 삽입하고자 하는 요소를 이전에 정렬된 부분 리스트와 비교합니다. 3. 삽입하고자 하는 원소보다 작은 원소를 만날 때까지 계속해서 비교하며, 작은 원소를 만나면 그 원소의 다음 위치에 비교를 시작한 원소를 삽입합니다. 4. 이 과정을 리스트의 끝까지 반복합니다. 삽입 정렬의 특징 1. stable 정렬: 동일한 값의 원소들 간에는 순서가 .. 프로그래밍 공부/Java 2024. 1. 18.

• 

  거품 정렬(Bubble Sort) 거품 정렬이란? 거품 정렬은 간단하면서 기본적인 정렬 알고리즘 중 하나입니다. 이 알고리즘은 인접한 두 원소를 비교하여 순서가 잘못된 경우에 서로 교환하는 방식으로 정렬을 진행합니다. 이러한 교환 작업을 계속해서 반복하면서 가장 큰 원소가 배열의 마지막 위치로 이동하게 됩니다. 이 과정을 배열의 모든 원소가 정렬될 때까지 반복합니다. 거품 정렬은 하나의 원소를 정렬하는 과정에서 많은 교환(swap)과정이 일어날 수 있어서 하나의 원소에 대해 한 번의 교환 과정을 갖는 선택 정렬에 비해 평균적으로 더 많은 시간이 소요됩니다. 거품 정렬의 특징 1. stable 정렬: 동일한 값의 원소들 간에는 순서가 유지되므로 안정 정렬입니다. 2. in-place 정렬: 자료 구조를 그대로 두고 그 안에서 요소들의 위치.. 프로그래밍 공부/Java 2024. 1. 18.

• 

  선택 정렬(Selection Sort) 선택 정렬이란? 선택 정렬은 간단하면서도 기본적인 정렬 알고리즘 중 하나입니다. 이 정렬 알고리즘은 한 번의 배열 탐색에서 가장 작은 원소의 위치를 찾아 첫 번째 위치의 원소와 교환하고, 그다음으로 작은 원소를 찾아 두 번째 위치의 원소와 교환하는 과정을 배열의 마지막 원소까지 반복하여 배열을 정렬합니다. 선택 정렬의 특징 1. unstable 정렬: 같은 값을 갖는 원소들의 순서가 정렬 이후 변경될 수 있기에 불안정 정렬입니다. 2. in-place 정렬: 자료 구조를 그대로 두고 그 안에서 요소들의 위치를 바꾸어 정렬합니다. 3. 시간복잡도: 최선, 평균, 최악의 경우 모두 O(N^2)의 시간 복잡도를 갖습니다. 왜냐하면 비교를 해 보기 전에는 어떤 원소가 가장 작은지 모르기 때문에 배열이 최선의 경.. 프로그래밍 공부/Java 2024. 1. 18.

• 

  [BOJ_20920] 영단어 암기는 괴로워 📌 문제 링크: https://www.acmicpc.net/problem/20920 20920번: 영단어 암기는 괴로워 첫째 줄에는 영어 지문에 나오는 단어의 개수 $N$과 외울 단어의 길이 기준이 되는 $M$이 공백으로 구분되어 주어진다. ($1 \leq N \leq 100\,000$, $1 \leq M \leq 10$) 둘째 줄부터 $N+1$번째 줄까지 외울 단 www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: 습관처럼 코테를 준비해야 되는데, 회사에서 살아남기 위한 공부도 있다보니 생각보다 코테를 준비할 시간이 없던 것 같다. 사실 이 말도 핑계이고, 시간을 계획적으로 분배해서 사용하는 연습을 해야겠다. 성격이 워낙 즉흥적이고, 무계획이라서 쉽지 않겠지만, 의식적인 연습.. 알고리즘 문제 풀이: 파이썬/BOJ 2023. 6. 14.

• 

  [BOJ_5648] 역원소 정렬 📌 문제 링크: https://www.acmicpc.net/problem/5648 5648번: 역원소 정렬 모든 원소가 양의 정수인 집합이 있을 때, 원소를 거꾸로 뒤집고 그 원소를 오름차순으로 정렬하는 프로그램을 작성하세요. 단, 원소를 뒤집었을 때 0이 앞에 선행되는 경우는 0을 생략해야합니 www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: 보통의 문제와 다르게 입력값의 개수인 n이 처리해야 되는 데이터와 같은 줄에 입력이 돼서 해당 데이터들과 추가적으로 입력받아야 되는 데이터를 어떻게 처리하는 것이 좋을지 잠시 고민했던 문제였다. 요즘 파이썬의 문법을 복습하지 않았지만 세부적인 부분들도 기억나서 짧고 간단한 코드로 구현할 수 있었다. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 12. 19.

• 

  [BOJ_3758] KCPC 📌 문제 링크: https://www.acmicpc.net/problem/3758 3758번: KCPC 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫 번째 줄에는 www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: 순위를 정하기 위해 팀 ID를 키(key)로 모든 문제들의 점수를 값(value)으로 갖는 score 딕셔너리와 팀 ID를 키로 [최종 점수, 제출 횟수. 제출시간]을 값으로 갖는 record 딕셔너리를 사용했다. 로그 엔트리 수인 m만큼 for 반복문을 돌면서 i, j, s(팀 ID, 문제 번호, 점수)를 입력받고, 두 딕셔너리를 적절히.. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 11. 7.

• 

  [BOJ_2535] 아시아 정보올림피아드 📌 문제 링크: https://www.acmicpc.net/problem/2535 2535번: 아시아 정보올림피아드 첫 번째 줄에는 대회참가 학생 수를 나타내는 N이 주어진다. 단, 3 ≤ N ≤ 100이다. 두 번째 줄부터 N개의 줄에는 각 줄마다 한 학생의 소속 국가 번호, 학생 번호, 그리고 성적이 하나의 빈칸을 사 www.acmicpc.net ✅ 내 풀이(Success) : 🚩 Idea: 1. 입력 받은 데이터를 성적순으로 내림차순 정렬한다. 2. 가장 성적이 좋은 두 명을 answer 배열에 담는다. 3. for 반복문을 이용해서 answer 배열에 담긴 두 원소들과 같은 국가가 아니면서 그 중에서 점수가 가장 큰 원소를 answer 배열에 담고, break로 반복문을 종료한다. 4. 두 번째 .. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 7. 12.

• 

  [BOJ_10867] 중복 빼고 정렬하기 📌 문제 링크: https://www.acmicpc.net/problem/10867 10867번: 중복 빼고 정렬하기 첫째 줄에 수의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. www.acmicpc.net ✅ 내 풀이(Success) : 🚩 Idea: - 입력 받은 수들을 집합을 이용해서 중복을 제거한다. - 중복을 제거한 수들을 오름차순으로 정렬하고, 한 줄로 출력한다. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 7. 11.

• 

  [BOJ_5635] 생일 문제 링크: https://www.acmicpc.net/problem/5635 5635번: 생일 어떤 반에 있는 학생들의 생일이 주어졌을 때, 가장 나이가 적은 사람과 가장 많은 사람을 구하는 프로그램을 작성하시오. www.acmicpc.net 내 풀이: Idea: 1. 학생의 수 n만큼 for 반복문을 돌며 데이터를 입력받고, 리스트에 담는다. 2. 리스트를 연도, 월, 일 순으로 오름차순으로 정렬한다. -> 정렬을 통해 연도, 월, 일이 가장 작은 값이 앞쪽으로 이동한다. 3. 정렬된 원소중의 첫 번째 원소는 가장 나이 많은 사람이 되고, 마지막 원소는 가장 나이가 적은 사람이다. 4. 출력 형식에 맞게 해당 원소들을 출력한다. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 6. 5.

• 

  [BOJ_6996] 애너그램 문제 링크: https://www.acmicpc.net/problem/6996 6996번: 애너그램 첫째 줄에 테스트 케이스의 개수( 알고리즘 문제 풀이: 파이썬/BOJ 2021. 11. 4.