How Radix Sort works? 구성요소들을 마지막 자릿수 기반으로 정렬한다.(Least Significant Digit) 그리고 그 결과는 다시 마지막에서 두 번째 자릿수 기반으로 정렬하고, 이러한 행위를 가장 큰 자릿수(Most Significant Digit)까지 행한다. Key Points for radix sort algorithm Radix Sort는 선형의 정렬 알고리즘이다. Radix Sort의 시간 복잡도는 $O(nd)$로, 배열의 크기는 n이며, d는 가장 큰 수의 자릿수이다. 이는 In-place sorting 알고리즘이 아니므로, 추가 공간이 필요하다. Radix sort는 Stable Sort로, 상대적인 순서가 보존된다. Radix sort는 다른 merge sort나 q..

https://www.acmicpc.net/problem/17779 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름 www.acmicpc.net 문제를 처음부터 제대로 안 읽고 얼기설기 덧대면서 풀었더니 푸는 데 시간이 예상보다 오래 걸렸다. 이 문제를 처음 보면 너무 어렵다고 생각이 드나, 주어진 x와 y의 범위를 코드에 그대로 녹이면 어렵지 않게 풀 수 있다. 대신 핵심은 5번 선거구를 획정할 것인가이다. 우선 경계선은 문제에서 주어졌는데, 경계선 내부 또한 5번 선거구로 획정해야 한다. 처음에는 d1, d2의 길이 차이에 따른 패턴을 형성..

https://www.acmicpc.net/problem/17140 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net vector의 resize함수를 잘 쓰면 어렵지 않게 풀 수 있는 문제이다. 2차원 vector의 resize는 적용이 원하는 대로 안되어서 행마다 resize를 vector.resize(n, value) 로 해주었다. 이 함수는 만약 해당 크기보다 원래 작으면 value로 채워서 만들고, 해당 크기보다 원래 크면 크기에 맞게 자른다. 그리고 행마다 열마다 배열을 정렬하는데, 어차피 ..

https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 매우매우 유용한 문제였다. 여기서 관건은 물고기의 정보를 어떻게 관리하고, 어떻게 좌우로, 상하로 반복적으로 움직이게 하느냐가 관건이었다. 우선 매번 배열에 물고기의 정보를 저장하고 옮기기엔 불편하다. 그래서 물고기마다 번호를 매겨서 별도의 벡터에 물고기의 정보를 저장해두고, 인덱스로 시간복잡도는 $O(1)$로 정보를 바로 파악할 수 있게 했다. 그리고 2차원 배열에는 살아있는..

https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 이번에도 구현 문제인데, 문제 자체가 어려운 변수들을 많이 제거한 상태로 출제되었다. 처음에 공기청정기가 위아래 간격이 최소 2칸이 된다는 점을 제대로 안 읽어서 헛발질 할 뻔했다...;; 그렇게 전제조건이 깔리면서 일반적인 경우의 수만 풀어내면 된다. 이러한 구현 문제는 실수를 미연에 방지하는 것이 중요하기 때문에 함수를 최대한 패턴화해서 쪼개는 게 중요하다. 미세먼지의 확산 공기청정기의 위쪽..

https://www.acmicpc.net/problem/23288 23288번: 주사위 굴리기 2 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼 www.acmicpc.net 앞서 풀었던 주사위 문제와 구조 자체는 비슷하다. 그러나 조금 더 살이 덧붙여져서 이 점까지 고려해야 한다. 예를 들면 더이상 해당 방향으로 진입이 불가능하면 방향을 뒤집거나, 추가적으로 DFS 혹은 BFS를 써서 탐색을 해서 추가점수를 고려해야 한다. 궁극적으로 삼성 SW 역량 테스트를 준비하기 위해 이 문제를 푸는 것이기 때문에, 이에 맞추어 입력을 편하게 받는 방법을 학습했..