✔ 병합 정렬 병합 정렬이란? 분할 정복 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬한 후, 이미 정렬된 부분 집합들을 효율적으로 병합해 전체를 정렬하는 방식 시간 복잡도의 평균값은 O(NlogN) 코딩 테스트의 정렬 관련 문제에서 자주 등장 특히 투 포인터를 사용하여 2개의 그룹을 병합하는 원리가 중요 병합 정렬 과정 가장 작은 데이터 집합으로 분할 2개씩 그룹을 병합하여 합치면서 정렬 투 포인터 개념을 사용하여 왼쪽, 오른쪽 그룹을 병합하며, 왼쪽 포인터와 오른쪽 포인터의 값을 비교하여 작은 값을 배열에 추가하고 포인터를 오른쪽으로 1칸 이동 만약 한 쪽 그룹의 데이터가 모두 배열에 추가될 경우, 다른 쪽 그룹에 남아있는 데이터를 그대로 모두 추가 전체 데이터가 1개의 그룹으로 병합될 때까지 ..
✔ 퀵 정렬 퀵 정렬이란? pivot 값을 선정해 해당 값을 기준으로 정렬하는 방식 기준값이 어떻게 선정되는지가 시간 복잡도에 많은 영향을 미침 평균적인 시간 복잡도는 O(NlogN)이지만, 최악의 경우에는 시간 복잡도가 O(N²) 시간 복잡도가 비교적 준수하므로 코딩 테스트에서도 종종 응용 퀵 정렬 과정 데이터를 분할하는 pivot을 설정 pivot을 기준으로 데이터를 2개의 집합으로 분리 start가 가리키는 데이터가 pivot이 가리키는 데이터보다 작으면 start를 오른쪽으로 1칸 이동 end가 가리키는 데이터가 pivot이 가리키는 데이터보다 크면 end를 왼쪽으로 1칸 이동 start가 가리키는 데이터가 pivot이 가리키는 데이터보다 크고, end가 가리키는 데이터가 pivot이 가리키는 데..
✔ 삽입 정렬 삽입 정렬이란? 대상을 선택해 정렬된 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬하는 방식 평균 시간 복잡도는 O(N²)으로 느린 편이지만 구현하기가 쉬움 삽입 정렬 과정 현재 index에 있는 데이터 값을 선택 현재 선택한 데이터가 정렬된 데이터 범위에 삽입될 위치를 탐색 (이때, 이진 탐색을 이용하면 시간 복잡도를 줄일 수 있음) 삽입 위치부터 index에 있는 위치까지 shift 연산을 수행 삽입 위치에 현재 선택한 데이터를 삽입하고 index++ 연산을 수행 전체 데이터의 크기만큼 index가 커질 때까지, 즉 선택할 데이터가 없을 때까지 반복 더보기 Do it! 알고리즘 코딩테스트 with JAVA https://inf.run/w9Tn
✔ 소트인사이드 [백준 1427] 문제 분석하기 숫자를 각 자릿수별로 나누는 작업이 필요하므로 입력값을 String으로 받은 후 substring() 함수를 이용해 자릿수 단위로 분리하고, 이를 다시 int형으로 변경해 배열에 저장하도록 함 이후 N의 길이가 크지 않으므로 선택 정렬 알고리즘을 이용해 해결 손으로 풀어보기 String 변수로 정렬할 데이터를 받은 후 substring() 함수를 사용해 각 자릿수별로 나눈 후 int형 배열에 저장 배열의 데이터를 선택 정렬 알고리즘을 이용해 최댓값을 찾아 swap하며 내림차순 정렬 슈도코드 작성하기 str(정렬할 수) A(자릿수별로 구분해 저장한 배열) for(str의 길이만큼 반복하기) { A 배열 저장 → str.substring 사용하기 } for(i..
✔ 선택 정렬 선택 정렬이란? 대상에서 가장 크거나 작은 데이터를 찾아가 선택을 반복하면서 정렬하는 방식 구현이 복잡하고, 시간 복잡도도 O(N²)으로 효율적이지 않아 코딩 테스트에서는 많이 사용하지 않음 최솟값 또는 최댓값을 찾는데 N * 남은 정렬 부분마다 N + (N - 1) + (N -2) + ... + (N-N) = N² 선택 정렬 과정 남은 정렬 부분에서 최솟값 또는 최댓값을 찾음 남은 정렬 부분에서 가장 앞에 있는 데이터와 선택된 데이터를 swap 가장 앞에 있는 데이터의 위치를 변경해 (idex++) 남은 정렬 부분의 위치를 축소 전체 데이터 크기만큼 index가 커질 때까지, 즉 남은 정렬 부분이 없을 때까지 반복 더보기 Do it! 알고리즘 코딩테스트 with JAVA https://i..
✔ 수 정렬하기 [백준 2750] 문제 분석하기 N의 범위가 1000으로 매우 작기 때문에 O(N²)의 시간 복잡도를 갖는 버블 정렬 알고리즘을 이용해도 해결 가능 손으로 풀어보기 비교 연산이 필요한 루프 범위를 설정 인접한 데이터 값을 비교 swap 조건에 부합하면 swap 연산을 수행 루프 범위가 끝날 때까지 2~3을 반복 정렬 영역을 설정한 후, 다음 루프를 실행할 때는 이 영역을 제외 비교 대상이 없을 때까지 1~5를 반복 슈도코드 작성하기 N(정렬할 수 개수) A(정렬할 배열 선언) for(루프의 개수만큼 반복) { for(정렬하는 범위만큼 반복) { 현재 A 배열의 값보다 1칸 오른쪽 배열의 값이 더 작으면 두 수 바꾸기 } } A 배열 출력 코드 구현하기 /** * 2750) 수_정렬하기 *..
✔ 버블 정렬 버블 정렬이란? 데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식 간단하게 구현할 순 있지만, 시간 복잡도는 O(N²)으로 다른 정렬 알고리즘보다 속도가 느린 편 1번의 루프를 도는데 N * N번의 루프 = N² 버블 정렬 과정 비교 연산이 필요한 루프 범위를 설정 인접한 데이터 값을 비교 swap 조건에 부합하면 swap 연산을 수행 루프 범위가 끝날 때까지 2~3을 반복 정렬 영역을 설정한 후, 다음 루프를 실행할 때는 이 영역을 제외 비교 대상이 없을 때까지 1~5를 반복 만약 특정한 루프의 전체 영역에서 swap이 한 번도 발생하지 않았다면 그 영역 뒤에 있는 데이터가 모두 정렬됐다는 뜻이므로 프로세스를 종료 더보기 Do it! 알고리즘 코딩테스트 with J..
✔ 카드2 [백준 2164] 문제 분석하기 큐의 원리를 정확하게 알고 있는지 묻는 문제 큐의 선입선출 성질을 이용하여 문제에 접근 손으로 풀어보기 poll을 수행하여 맨 앞의 카드를 버림 add를 수행해 맨 앞에 있는 카드를 가장 아래로 옮김 큐의 크기가 1일 될 때까지 과정 1~2를 반복한 후 큐에 남은 원소를 출력 슈도코드 작성하기 N(카드의 개수) myQueue(카드 저장 자료구조) for(카드의 개수만큼 반복) { 큐에 카드 저장하기 } while(카드가 1장 남을 때까지) { 맨 위의 카드를 버림 : poll() 맨 위의 카드를 가장 아래의 카드 밑으로 이동 : poll() → add() } 마지막으로 남은 카드 출력 코드 구현하기 /** * 2164) 카드_2 */ public class D0..
