🧨 백준 1550번 문제 출처 : 백준 1550번 - 16진수 문제 난이도 : 브론즈5 문제 링크 : www.acmicpc.net/problem/1550 1550번: 16진수 첫째 줄에 16진수 수가 주어진다. 이 수의 최대 길이는 6글자이다. 16진수 수는 0~9와 A~F로 이루어져 있고, A~F는 10~15를 뜻한다. 또, 이 수는 음이 아닌 정수이다. www.acmicpc.net 🧨 알고리즘 선택 및 C++ 코드 16진수를 어떻게 입력받고, 어떻게 10진수로 변환할 것인가의 문제였는데 변환할 생각보다는 입력방식을 달리해보는게 좋을 거 같다. 16진수를 string으로 입력받아 10진수로 변환하는 건 불필요하다. 그냥 %x 16진수로 입력받고 %d로 출력하면 바로 10진수로 변환되어 출력된다. 너무 ..
🧨 문제 출처 문제 출처 : 백준 문제 난이도 : 실버 5 문제 링크 : www.acmicpc.net/problem/11650 11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 🧨 알고리즘 선택 및 C++ 코드 기본적으로 좌표 문제라서 를 쓰는 것이 좋다. 예전에 C언어 공부할 때 pair나 tuple을 구조체로 직접 만들어보는거 했었던 거 같은데 C++의 라이브러리에 다 있다. pair 로 쓰고 first, second로 인덱싱해 값을 받아올 수 있다. 27..
🧨 문제 출처 문제 출처 : 백준 11651번 - 좌표 정렬하기2 문제 난이도 : 실버 5 문제 링크 : www.acmicpc.net/problem/11651 11651번: 좌표 정렬하기 2 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 🧨 알고리즘 선택 및 C++ 코드 11650 풀이를 정리하다가 분명 y, x 순서로 오름차순 하는 코드가 있을 것 같았다. 1) 순서가 바뀌면 순으로 입력받으면 어떨까 싶었고 2) 또는 sort의 compare 함수를 사용자 지정으로 새로 만들어 줄 ..
🧨 문제 출처 문제 출처 : 백준 문제 난이도 : 실버 5 문제 링크 : www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 🧨 알고리즘 선택 및 C++ 코드 문제 그대로 수를 정렬하는 문제였고, 2750번(수 정렬하기) 문제에 비해 정렬할 데이터가 많아져 시간이 부족했다. 2750번은 O(n^2) 정렬로 풀어도 통과됐었지만 2751은 시간초과 오류가 나는 걸 보니 O(nlogn)을 요구하는 문제이다. 퀵 정렬은 데이터 정렬 상태에 따라 n제곱 시간..
버킷정렬, 기수정렬, 계수정렬은 비교에 기반하지 않는 정렬 방법으로 시간복잡도 O(nlogn)보다 빠르게 구현하고자 제안된 정렬 알고리즘이다. 오늘은 기수정렬과 계수정렬에 대해 알아보고자 한다. 간단하니까 툭툭 치고 넘어간다. 📌 기수정렬 Radix Sort 기수정렬의 핵심은 낮은 자리에서 높은 자리로 기준을 바꾸어 가며 정렬하는 것이다. stable sort가 적용된 대표적인 정렬로 이전의 정렬 순서가 바뀌지 않는다. 실제로 정렬을 한다기보다 자릿수에 맞게 0~9까지의 버킷이 있고 이 버킷에 해당하는 자릿수를 포함한 수를 넣는 방식이다. 자리를 바꿔가며 버킷에 넣는 걸 반복하면 자동적으로 정렬이 되는 원리이다. 이때 버킷은 Queue(큐, First In First Out) 방식을 사용한다. 이때 이전..
📌 힙 정렬 힙 정렬은 1등을 뽑아내고 나머지 원소에서 계속 1등을 뽑아내는 정렬 알고리즘으로, 버블정렬과 비슷하다. 버블정렬은 1등(오름차순 정렬에서 가장 큰 수)을 뽑고 나서 이전의 1등들과 비교해야 한다. 그러나 힙정렬에서는 1등이 뽑힌 순서대로 다음은 자동으로 2등, 3등, ... 이렇게 되므로 1등을 뽑고 나서 추가적인 비교가 필요 없다. 매 라운드에서 한번 1등으로 뽑히면 그 원소는 이미 순서가 정해진 것이다. 남은 원소가 없을 때까지 반복적으로 1등을 뽑아내는 것이 핵심이다. 😶 버블정렬에 더 알아보고 싶다면 2020/12/30 - [코딩테스트/알고리즘 & 자료구조] - [알고리즘] 버블정렬 Bubble Sort (C++ 구현) [알고리즘] 버블정렬 Bubble Sort (C++ 구현) 코테..
📌 퀵정렬 퀵정렬은 가장 널리 쓰이는 정렬 알고리즘으로 말 그대로 빠른 정렬이 가능하다. 퀵 정렬도 병합정렬과 마찬가지로 분할정복기법을 이용한 알고리즘이다. 퀵 정렬의 핵심 아이디어는 특정 원소를 기준으로 작은 데이터와 큰 데이터를 분류한다는 것이다. 이렇게 되면 특정 원소를 기준으로 순서가 결정되며 분류된 작은 데이터와 큰 데이터 안에서 각각 기준 원소를 다시 정해 재귀적으로 쪼개나가면서 정렬해나간다. 병합정렬과 마찬가지로 단위를 쪼개나가는 아이디어이므로 분할정복기법이라고 할 수 있다. 이때 생각해봐야 할 것은 기준이 되는 원소(pivot)를 어떻게 정하느냐 인데, 1) 첫번째 원소를 기준으로 하거나 2) 랜덤으로 원소를 선택한다 첫번째 원소를 기준으로 할 경우 이미 정렬된 리스트의 경우 피봇의 한쪽에..
🧨 문제 출처 문제 출처 : 백준 2752번 문제 난이도 : 브론즈 4 문제 링크 : www.acmicpc.net/problem/2752 2752번: 세수정렬 숫자 세 개가 주어진다. 이 숫자는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 이 숫자는 모두 다르다. www.acmicpc.net 🧨 알고리즘 선택 및 C++ 코드 세 개의 수를 입력해 오름차순 정렬하는 문제다. 사실상 N개의 수를 입력해 오름차순 정렬하는 것과 별반 다르지 않은 문제인데 왜 브론즈 4인지는 의문이다. 다른 방법으로 더 간단하게 구현하는 방법이 많을 거다. 사실 3개의 수라면 복잡하게 정렬 알고리즘을 따지지 않고 2번 또는 3번만 비교해도 대중소를 가려낼 수 있긴 하다. 정렬 알고리즘 공부하면서 구현한거라 그냥 병합..
