Let's Begin Programming

www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net 두 가지 조건을 이용해 정렬하는 문제이다. 이전 문제들과 다른 점은 두 조건의 자료형이 다르다는 점이었다. 좌표 정렬 문제에서는 x와 y모두 정수로 주어졌고, 단어 정렬 문제에서는 문자열만 주어졌다. 이번 문제에서는 입력 받는 한 쌍이 (숫자, 문자열)로 이루어져 있다. 먼저 나이 순으로 정렬하는 조건을 위해서 sort()함수의 key 파라미터에 현재 리스트의 첫 번째 원소, 나이(숫자)를 전달한다. 만약에 나이가 ..

개발 공부 (알고리즘) 2021. 2. 2. 02:16

www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 문자열들을 입력 받아 주어진 조건에 맞게 정렬하는 문제이다. 이전에 좌표를 정렬했던 문제들과 유사한 문제였다. 두 가지 조건이 주어지고 이에 따라 정렬하면 되는 문제였다. 이전과 마찬가지로 sort() 함수의 key 파라미터에 두 가지 조건을 전달했다. 첫 번째 조건은 문자열의 길이였다. len() 함수를 이용해서 현재 문자열의 길이를 전달했다. 만약 문자열의 길이가 동일한 원소들이 존재할 경우 두 ..

개발 공부 (알고리즘) 2021. 2. 2. 02:10

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 이전의 두 개의 정렬 조건을 이용해서 풀었던 문제와 유사한 문제이다. 이 문제에서는 두 조건의 우선 순위를 바꾸었다. y를 기준으로 먼저 정렬하고 동일하다면 x를 기준으로 정렬한다. 입력은 x, y 순이기 때문에 정렬하는 sort()함수의 key 파라미터의 순서만 변경해주면 된다. 만약 파이썬이 아닌 다른 언어였다면 아마 생각할 점과 수정해야될 부분들이 ..

개발 공부 (알고리즘) 2021. 2. 2. 02:04

www.acmicpc.net/problem/11650 11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 정렬 기준에 관련된 문제였다. 우선 정렬 기준과 차선 정렬 기준을 적용해서 정렬하는 문제이다. 파이썬에서는 정말 간단하게 두 가지 조건을 sort()나 sorted()함수에 적용할 수 있다. sort()의 파라미터에는 key= 을 지정할 수 있다. key= 뒤에는 lambda를 이용해서 함수를 구현할 수 있다. 미리 선언해놓은 함수의 이름을 써도 되고 이름 ..

개발 공부 (알고리즘) 2021. 2. 2. 02:01

www.acmicpc.net/problem/1427 1427번: 소트인사이드 첫째 줄에 정렬하고자하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 숫자를 입력받아 각 자릿수를 내림차순으로 정렬하는 문제이다. 먼저 입력받는 수 N의 범위가 1,000,000,000 이하이다. python3의 경우 오버플로우가 발생하기 전에 자동으로 메모리를 할당해 오버플로우가 발생하지 않는다. 하지만 이 문제에서 입력을 숫자로 받을 필요는 없다. 어차피 자릿수마다 한 자리씩 숫자를 나누어서 정렬해야 하기 때문에 애초에 입력을 문자열로 받으면 모든 것이 해결된다. 문자열로 받은 숫자를 하나씩 리스트에 저장한 후에 내림차순으로 정렬하고 띄어쓰기없이 출력한다. 원래는..

개발 공부 (알고리즘) 2021. 2. 2. 01:50

www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 숫자를 입력 받아 4가지의 결과를 출력해야 하는 문제였다. 정렬도 중요하지만 출력을 할 때 값을 어떻게 포맷할지도 중요한 문제였다. 1. 산술평균 산술평균은 리스트의 모든 값을 더한 후 갯수로 나눈 값이다. (a + b + c + ... ) / n 으로 나타낼 수 있다. 단순하게 입력 받은 수들을 모두 더하고 나눠주면 되지만, 출력 조건이 소수점 이하 첫째 자리에서 반올림한 값이었다. 파이썬에는 round()라는 반올림 함수가 기본 내장 함수로 ..

개발 공부 (알고리즘) 2021. 2. 2. 01:43

www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 이전의 수를 정렬하는 두 문제와 같이 수들을 오름차순으로 정렬하는 문제이다. 이 문제에서는 입력이 최대 10,000,000까지 주어질 수 있으나 입력할 수 있는 수의 유효 범위는 10,000까지 밖에 안된다. 이 입력이 의미하는 것은 중복되는 수는 많을 수 있지만 작은 범위안에서 주어진다는 것이다. 이러한 특징을 이용해 효율적으로 빠르게 정렬할 수 있는 정렬 알고리즘은 계수 정렬이다. 계수 정렬은 한정된 범위안에서 주어지는 정수..

개발 공부 (알고리즘) 2021. 2. 2. 01:14

www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 이전 문제와 크게 다르지 않은 문제이다. 차이점은 입력의 범위이다. 최대 1,000,000개의 숫자가 주어질 수 있고, 절댓값이 1,000,000보다 작은 수 이므로 음수도 포함된다. 아마 문제의 의도는 O(nlogn)의 시간 복잡도를 갖는 정렬 알고리즘의 효율성을 깨닫는 것으로 보인다. 하지만 파이썬의 내장 함수를 이용해도 충분히 빠른 시간에 문제를 해결할 수 있다. 중요한 문제는 정렬 알고리즘이..

개발 공부 (알고리즘) 2021. 2. 2. 01:05