본문 바로가기

분류 전체보기225

백준 2751번 파이썬 | 수 정렬하기 2 | Sort 문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 풀이 해당 문제는 시간 초과를 내면 안되므로 O(nlogn)으로 풀면 된다. 파이썬 내장함수가 O(nlogn)이기에 사용했지만 에러가 떳다.. 방법은 총 3가지이다. 첫번째 방법은 파이썬 내장함수 sorted를 사용하고 python3을 pypy3으로 바꾸는것. 두번째 방법은 input을 sys.stdin.readline()으로 받는 것... 2020. 9. 28.
Binary Search 이분 탐색 Binary Search (이분 탐색) 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 O(logN) 알고리즘 정렬된 리스트에서 탐색 범위를 계속 반으로 줄여나가기에 효율이 좋다. 중간값 mid(low+high의 반값)를 선택하고, 찾고자 하는 값 value와 비교하여 value보다 list의 인덱스 mid값이 크다면 mid를 작은쪽으로 반으로 줄인 후 다시 Search, 그 반대의 경우 큰쪽으로 반으로 줄인다. 검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점이 있다. array - sorting된 리스트 value- 찾고자 하는 값 def binarySearch(array, value, low, hi.. 2020. 9. 26.
백준 1920번 파이썬 | 수 찾기 | binary search(이분 탐색) www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안�� www.acmicpc.net 문제 N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이.. 2020. 9. 26.
백준 10994번 파이썬 | 별 찍기 -19 | 재귀함수 문제 예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요. 입력 첫째 줄에 N(1 ≤ N ≤ 100)이 주어진다. 출력 첫째 줄부터 차례대로 별을 출력한다. 풀이 n에 따라서 (4*n -3) 만큼의 칸수들이 생기며 테두리를 감싸고 있는 것들의 내부에는 똑같은 것들이 반복된다. 따라서 recursion으로 n을 1씩 줄이면서 x,y좌표의 값들을 2씩 더해준 후 재귀함수로 풀면 쉽게 풀 수 있다. (처음에 이 로직을 생각하는 것이 익숙하지 않을 수도 있으니 연습하자..) def draw(n, idx): if n == 1: starMap[idx][idx] = '*' return ; l = 4 * n -3 for i in range(idx, l+idx): #위 아래 starMap[idx][i] = '*' star.. 2020. 9. 22.

티스토리툴바