L.O.K

문제) 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 풀이 ) 퀵정렬, 병합정렬, 힙정렬로 풀었다. 버블정렬은 시간초과가 발생한다. 파이썬은 리스트에 중복된 값을 제거할 때, 조건문에 not in 연산자를 사용하면 된다. 나는 이를 힙정렬 풀이 때 알게 되어 힙정렬에서 not in 연산자를 이용하여 풀었다. - 퀵정렬 풀이 # 입력 n = int(input()) input_list = [] for i in range(n) : input_list.append(input()) # 퀵소트 함수 def ..

문제) 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 알고리즘) [알고리즘] 힙 정렬 ( Heap Sort ) 힙 정렬( Heap Sort )은 성능 좋은 정렬 알고리즘이지만 원리를 이해하기 쉽지 않다. 그 이유는 완전 이진 트리를 이용하기 때문이다. [자료구조] 완전이진트리 배열에 저장하기 완전 이진 트리를 lordofkangs.tistory.com 힙정렬은 힙트리를 이용한 정렬이다. 힙트리는 두 가지 조건이 충족되어야 한다. 1) 완전이진트리여야 한다. 2) 부모는 반드시 자식보다 커야 한다. ( 부모는 반드시..

문제 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 알고리즘 [JAVA] 백준 2751번 수 정렬하기2 : 병합 정렬( Merger Sort ) 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. lordofkangs.tistory.com 위 알고리즘을 사용하여 풀었으나, 파이썬의 장점을 살리지 못한 풀이가 되었다. 파이썬은 리스트를 생성하..

문제) 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 알고리즘) [알고리즘] 퀵 정렬 (Quick Sort) 퀵 정렬(Quick Sort)은 이름 그대로 정렬을 빠르게 하는 알고리즘이다. 그러나 버블정렬에 비해 빠를 뿐, 이름만큼 가장 빠른 정렬 알고리즘은 아니다. 퀵 정렬(Quick Sort) 알고리즘이란? 정렬 알고리 lordofkangs.tistory.com 위 개념은 JAVA언어로 구현되어 있는데 파이썬 언어로 바꾸어 실행한 결과, 메모리초과가 발생했다. 원인은 파악하는 중이다. 그래서 원리는 같지만 조금 ..

문제 ) 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 알고리즘) [알고리즘] 버블정렬 향상 시키기 버블정렬은 가장 쉽고 이해하기 쉬운 정렬이다. 그러나 시간복잡도가 O(n2)이어서 효율이 좋지 않다. 7개의 수를 일차원 배열에 저장하였다. 이제 버블정렬을 사용하여 오름차순으로 바꾸어 보자 lordofkangs.tistory.com 코드) 1) 교환횟수 카운트하여 버블정렬 향상시키기 N = int(input()) sortArr = [] for i in range(N) : sortArr.append(int(input..

1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 1. 문제 추상화 알파벳으로 이루어진 단어들을 길이가 짧은 순으로 정렬하시오. 길이가 같으면 알파벳 순으로 정렬하시오. 2. 알고리즘 1. HashSet 자료구조 예제를 보면 동일한 단어를 입력받으면 출력시, 중복을 제거해주는 것을 확인할 수 있다. 중복제거를 위해 HashSet 자료구조를 사용한다. 2. 정렬 알고리즘 Quick, Merge, Heap 정렬 알고리즘을 사용하였다. ( Bubble 정렬은 시간초과가 난다. ) [알고리즘] 퀵 정렬 (Q..

11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 1. 문제 추상화 X좌표와 Y좌표가 주어질 때, X좌표의 내림차순으로 정렬하라. X좌표가 같으면 Y좌표의 내림차순으로 정렬하라. 2. 알고리즘 1. X좌표와 Y좌표를 저장할 수 있는 이차원 배열을 생성한다. 2. X좌표의 내림차순으로 비교하다가 X좌표가 같은 경우 Y좌표의 내림차순으로 비교하는 조건을 분기한다. 퀵정렬, 병합정렬, 힙정렬을 사용하였다. 버블정렬은 시간초과가 나고 카운팅정렬은 메모리초과가 났다. ..

1427번: 소트인사이드 첫째 줄에 정렬하고자하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 1. 문제 추상화 주어진 수의 각 자리수를 내림차순으로 정렬하시오 2. 알고리즘 1. 수를 문자열로 받는다. 2. 문자열의 길이만큼 정수 배열을 생성한다. 3. 문자열의 각 문자를 배열에 정수로 저장한다. 4. 내림차순 정렬을 한다. 1번 - 3번까지의 코드는 아래와 같다. // 1. 수를 문자열로 받기 public static void setInputData() { Scanner sc = new Scanner(System.in); input = sc.next(); } // 2. 문자열의 길이만큼 정수배열 생성하기 public static void ..

2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 1. 문제 추상화 주어진 수들의 산술평균, 중앙값, 최빈값, 범위를 구하시오. 2. 알고리즘 1) 정렬 알고리즘 퀵정렬, 합병정렬, 카운팅 정렬, 힙정렬로 풀어볼 것이다. ( 참고로 버블정렬은 시간초과가 난다. ) (각 정렬의 알고리즘은 아래 포스팅을 참고바랍니다!) [알고리즘] 퀵 정렬 (Quick Sort) 퀵 정렬(Quick Sort)은 이름 그대로 정렬을 빠르게 하는 알고리즘이다. 그러나 버블정렬에 비해 빠를 뿐, 이름만큼 가장 빠른 정렬 알고리즘은 아니다. 퀵 정렬(..

10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 1. 문제 추상화 N개의 수를 오름차순 정렬 하시오. 2. 알고리즘 카운팅 정렬을 사용하는 문제이다. 카운팅 정렬은 퀵, 병합, 힙 정렬같이 복잡하지 않고 단순하고 직관적이다. 시간복잡도도 O(N)으로 굉장히 빠르다. 이해하기 쉽고 빠르다는 장점이 있지만 많은 수의 정렬은 힘들다. 1. 입력받은 N개의 수를 배열에 저장하고 제일 큰 값을 구한다. 2. 제일 큰 값이 10이므로 배열의 크기가 ( 10 + 1 )인 카운팅 배열 하나를 생성한다. 3. 입력받은 수와 대응하는 인덱스가 가..