본문 바로가기
728x90
반응형

분류 전체보기

 (198)
[백준] 좌표 정렬하기 2 : 11651번 - Python https://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 문제를 풀면서 몰랐던 개념 (1) [Python] 2차원 배열 만들기 -> 문제에서는 입력 받은 두 x,y 좌표 값을 묶어서 총 n개만큼 저장하여 리스트에 넣으려고 했기 때문에 2차원 배열이 필요했다. # 반복문을 통해 n번만큼 x,y 좌표 값을 입력받는다. for i in range(n): x,y = input().split() # x,y..
[백준] 소트인사이드 : 1427번 - Python https://www.acmicpc.net/problem/1427 1427번: 소트인사이드 첫째 줄에 정렬하고자하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제를 풀면서 몰랐던 개념 [Python] 숫자를 각 자리수의 list로 변환 -> map 함수를 사용하면 된다! n = 12345 n_list = list(map(int, str(n))) # 각 자리수를 문자열로 받아 하나하나씩 int형으로 변환해주어서 n_list에 넣는다. 문제의 접근 방법 - 각 자리수를 내림차순으로 정렬할 수 있도록 리스트로 변환하는 것이 포인트! - 마지막에 출력할 때, 리스트의 원소들을 붙여서 한 줄에 표현해야 한다는 점을 주의! 내가 막혔던 부분 아이디어..
[백준] ATM : 11399번 - Python https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제를 풀면서 몰랐던 개념 (1) [Python] 한 줄에 정수형 변수 여러개 입력받기 -> 리스트에 map 함수를 사용하기!! 'map'은 리스트이 요소를 지정된 함수로 처리해주는 함수이다. map은 원본 리스트를 변경하지 않고 새 리스트를 생성한다. a = list(map(int, input().split())) 10 20 # (입력) >>> print(a) [10, 20] # a, b = input().split() 이렇..
[백준] 수 정렬하기 : 2750번 - Python https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 문제를 풀면서 몰랐던 개념 [Python] 리스트 오름차순으로 정렬하기 -> sorted 함수를 사용해서 정렬! alist = [4, 2, 1, 3, 5] alist = sorted(alist, reverse = False) # 오름차순 정렬 print(alist) >> [1, 2, 3, 4, 5] alist = sorted(alist, reverse = True) # 내림차순 정렬 print(alis..
합병 정렬 (Merge Sort) 합병 정렬 : 배열을 좌 우로 나눈 후, 나눈 배열을 정렬하고 다시 붙인다. 퀵 정렬(Quick Sort)과 마찬가지로 재귀 용법을 활용하는 알고리즘이다. 분할 정복 알고리즘 중 하나로, 리스트 길이가 1 이하면 이미 정렬된 것으로 본다. 분할 : 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 리스트로 만든다. 정복 : 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다. 결합 : 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 이 때 정렬 결과가 임시 배열에 저장된다. 복사 : 임시 배열에 저장된 결과를 원래 배열에 복사한다. 알게된 개념 1. 리스트 요소 끄집어내기(pop) -> pop()은 리스트의 맨 마지막 요소를 돌려주고 그 요소는 삭제한다. >>> a = [1,2,3] ..
힙 정렬 (Heap Sort) 힙 정렬 : 힙은 완전 이진트리의 구조를 갖고 있는데, 자식 노드의 값이 부모 노드의 값보다 클 수 없다(작거나 같아야 함)는 조건을 만족해야 한다. 1. 최대 힙을 구성한다. (인덱스의 0번째 값이 최댓값이 된다) 2. 최댓값을 배열의 가장 마지막 위치에 놓는다. (큰 값을 뒤로 보내주는 과정 - 교환) 3. 그 다음 새로운 루트 노드에 대해 최대 힙을 수행한다. 4. 원소의 개수만큼 2~3번의 과정을 반복한다. 주어진 자료 구조에서 힙 성질을 만족하도록 하는 연산을 heapify라고 한다!!! heapify에서는 left = index * 2 +1, right = index * 2 + 2 공식을 만족한다. 파이썬으로 구현한 힙 정렬 def heapify(arr, index, heap_size): la..
삽입 정렬 (Insertion Sort) 삽입 정렬 : 앞에서부터 차례차례 비교해나가면서 자신의 위치를 찾아 삽입하는 것을 의미한다. i for문에서는 0번째 인덱스부터 차례차례 뒤로 가야하기 때문에 인덱스값이 증가하고, 반대로 j for문에서는 현재 선택한 데이터를 배열 속에서 역방향으로 비교해나간다. 만약, 이전 값이 현재 선택한 데이터보다 큰 경우 두 값의 위치를 바꿔주는 과정을 반복한다. 파이썬으로 구현한 삽입정렬 from random import randint def insertion_sort(arr): for i in range(n-1): for j in range(i, 0, -1): if arr[j-1] > arr[j]: arr[j], arr[j-1] = arr[j-1], arr[j] return arr arr = [randint(..
퀵 정렬 (Quick Sort) 퀵 정렬 : 특정 키 값(pivot)을 중심으로 좌측은 pivot보다 작은 수, 우측은 pivot보다 큰 수가 오도록 서로 교환하는 과정을 의미한다. 왼->오 pivot 보다 큰 값을 찾는 A와 오->왼 pivot 보다 작은 값을 찾는 B로 나누어서 A와 B의 위치를 바꾸는 과정을 계속 반복한다. 이처럼 2개의 서브 리스트가 구성되면 첫 번째 리스트부터 앞의 과정을 반복하는 것이다. 문제를 여러개로 분리해서 수행한 후, 그 해결 결과 값들을 합쳐서 원래의 문제를 해결하는 분할 정복 방식을 따르고 있다. "분할 정복 기법 + 재귀 알고리즘 = 퀵 정렬 알고리즘" 파이썬으로 구현한 퀵 정렬 from random import randint def quick_sort(arr): if len(arr) pivot:..
728x90
반응형

티스토리툴바