본문 바로가기
반응형

분류 전체보기

 (107)
이진 탐색(이분 탐색): 백준 1654 파이썬 문제: https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 정답: import sys k, n = map(int, sys.stdin.readline().split()) array = [int(sys.stdin.readline()) for _ in range(k)] # 이진 탐색을 위한 시작점과 끝점 설정 start = 1 end = max(array) # 이진 탐색 수행(반복적) result = 0 while(start
이진 탐색(이분 탐색): 백준 10816 파이썬 문제: https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 정답: 1. collections 모듈의 Counter 클래스 사용 import sys from collections import Counter n = int(sys.stdin.readline()) n_arr = list(map(int, sys.stdin.readline().split())) m = int(sys.stdin.readline()) m_arr ..
이진 탐색: 백준 1920 파이썬 문제: https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 정답: import sys n = int(sys.stdin.readline()) n_arr = list(map(int, sys.stdin.readline().split())) m = int(sys.stdin.readline()) m_arr = list(map(int, sys.stdin.readline().split())) def binary_..
이진 탐색: 탐색 범위를 반으로 좁혀가며 빠르게 탐색하는 알고리즘 이진탐색: 반으로 쪼개면서 탐색하기 이진탐색(Binary Search)은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 데이터가 무작위일 때는 사용할 수 없지만, 이미 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있다는 특징이 있다. 이진 탐색은 위치를 나타내는 변수 3개를 사용하는데 탐색하고자 하는 범위의 시작점, 끝점, 그리고 중간점이다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는게 이진 탐색 과정이다. 이미 정렬된 10개의 데이터 중에서 값이 4인 원소를 찾는 예시를 살펴보자. step1: 시작점과 끝점을 확인한 다음 둘 사이에 중간점을 정한다. 중간점이 실수일 때는 소수점 이하를 버린다. 그림에서 각각의 인덱스는 시작점은 [0]..
정렬: 백준 18870 파이썬 문제: https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 정답: import sys n = int(sys.stdin.readline()) array = list(map(int, sys.stdin.readline().split())) # set 자료형으로 중복을 없애준 후 정렬 s_array = sorted(set(array)) # 딕셔너리 자료형을 사용해 시간복잡도를 크게 줄임 dic = {s_a..
정렬: 백준 10814 파이썬 문제: https://www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net 정답: import sys n = int(sys.stdin.readline()) array = [sys.stdin.readline().split() for _ in range(n)] array.sort(key=lambda x: int(x[0])) for i in array: print(i[0], i[1]) 풀이: 정렬할 때 key 값을 사용해서 문제 조건대로 정렬을 해주었다. 입력받은 나이를 i..
정렬: 백준 1181 파이썬 문제: https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 정답: import sys n = int(sys.stdin.readline()) array = [input() for _ in range(n)] # 입력받은 문자열의 중복을 제거하기 위해 set으로 바꾸었다가 다시 list로 변경 array = set(array) array = list(array) # 문자열 길이와 문자를 기준으로 정렬 array.sort(key=lambda x..
정렬: 백준 11651 파이썬 문제: 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 정답: import sys n = int(sys.stdin.readline()) array = [list(map(int, sys.stdin.readline().split())) for _ in range(n)] array = sorted(array, key=lambda arr: (arr[1], arr[0])) for i in arra..
반응형

티스토리툴바