취업 준비 및 일상

https://www.acmicpc.net/problem/16455 16455번: K번째 수 찾는 함수 C++17, Java 8, C11, PyPy3, C99, C++98, C++11, C++14, Java 8 (OpenJDK), Go, C99 (Clang), C++98 (Clang), C++11 (Clang), C++14 (Clang), C11 (Clang), C++17 (Clang) www.acmicpc.net 풀이 N = pivot} 으로 나누어, |L| + |C| K이면 L에서 새로운 pivot을 찾고, |L| = K이면 적당히 L or C에서 K번째 원소를 찾는 방법입니다. quicksort랑 다르게 amortized O(N) 시간복잡도를 가지지만, worst case..

https://www.acmicpc.net/problem/5648 5648번: 역원소 정렬 모든 원소가 양의 정수인 집합이 있을 때, 원소를 거꾸로 뒤집고 그 원소를 오름차순으로 정렬하는 프로그램을 작성하세요. 단, 원소를 뒤집었을 때 0이 앞에 선행되는 경우는 0을 생략해야합니 www.acmicpc.net 문제 모든 원소가 양의 정수인 집합이 있을 때, 원소를 거꾸로 뒤집고 그 원소를 오름차순으로 정렬하는 프로그램을 작성하세요. 단, 원소를 뒤집었을 때 0이 앞에 선행되는 경우는 0을 생략해야합니다. 입력 첫 번째로 입력되는 건 n (1 ≤ n ≤ 106)으로 사용자가 뒤이어 입력할 원소값을 결정합니다. 입력하는 줄에는 하나의 원소값 뿐만 아니라 여러 원소값도 들어갈 수 있습니다. 단, 입력하는 정수는..

* 바킹독, 위키피디아 등을 참고하여 작성함. 목차 1. O(N^2) 시간복잡도 정렬 알고리즘 - 선택 정렬, 버블 정렬 2. O(NlogN) 시간복잡도 정렬 알고리즘 - 병합 정렬, 퀵소트 3. Non-comparison sorts: 카운팅 정렬, 기수 정렬 4. JAVA에서의 사용 ※ 구분 stable sort: 크기가 같은 원소들끼리 정렬 후에도 원래의 유지하는 정렬 알고리즘(↔ unstable sort) comparison sort: 우리가 일반적으로 아는, 원소의 값끼리 비교하여 정렬하는 알고리즘(↔ non-comparison sort) 1. O(N^2) 시간복잡도 정렬 알고리즘 일반적으로 구현하기 쉽다. 실제로 쓰이지 않으며, '선택 정렬과 버블 정렬의 차이점을 설명하여라'와 같은 지엽적인 질..

문제 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자. 입력 첫째 줄에 N이 주어진다. 둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다. 출력 첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다. 내 풀이 input 값이 저장되어 있는 리스트("num")가 index를 보관할 수 있도록, 각 원소를 [index, nums[index]] 형태로 저장한 후, 첫 번째 원소를 기준으로 정렬. 이후 ..

문제 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 온라인 저지 회원의 수 N이 주어진다. (1 ≤ N ≤ 100,000) 둘째 줄부터 N개의 줄에는 각 회원의 나이와 이름이 공백으로 구분되어 주어진다. 나이는 1보다 크거나 같으며, 200보다 작거나 같은 정수이고, 이름은 알파벳 대소문자로 이루어져 있고, 길이가 100보다 작거나 같은 문자열이다. 입력은 가입한 순서로 주어진다. 출력 첫째 줄부터 총 N개의 줄에 걸쳐 온라인 저지 회원을 나이 순, 나이가 같으면 가입한 순으로 한 줄에 한 명씩 나이와 이름을 공백으로 구분해 출력한다. 풀이..

문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 풀이 https://en.wikipedia.org/wiki/Counting_sort 를 참고하되, 수도코드대로 작성하면 메모리 오류가 발생한다. 그래서, input값을 리스트로 저장하지 않고, 10001 길이의 count list를 선언해 준 후, count[input] += 1을 해줘야 한다. 시간이 엄청 오래 걸리던데, 다른 풀이 보니까 다들 이렇게 했더라. 코드 im..

문제 알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오. 길이가 짧은 것부터 길이가 같으면 사전 순으로입력 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. 입력 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. 출력 조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다. 내 풀이(안 좋음) a...