본문 바로가기

전체 글225

백준 17521번 파이썬 | Byte Coin 문제 국제자본부동산회사(ICPC)는 바이트 코인(Byte Coin)에 자금을 투자하고 있다. 바이트 코인은 김박사가 만든 가상 화폐이다. 실제로는 바이트 코인 가격을 예상할 수 없지만 이 문제에서는 바이트 코인 가격 등락을 미리 정확히 예측할 수 있다고 가정하자. 우리는 1일부터 n일까지 n일 동안 그림 1과 같이 바이트 코인의 등락을 미리 알 수 있으며 우리에게는 초기 현금 W가 주어져 있다. 그림 1의 빨간색 네모는 해당 일자의 바이트 코인 가격을 나타낸다. 매일 바이트 코인을 매수하거나 매도할 수 있다고 하자. 다만 바이트 코인 하나를 나누어 매도하거나 매수할 수는 없다. 우리는 n일 날 보유하고 있는 모든 코인을 매도할 때 가지고 있는 현금을 최대화하고 싶다. 그림 1. 10 일간 바이트 코인 가.. 2020. 9. 30.
백준 10989번 파이썬 | 수 정렬하기 3 | Sort 문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 풀이 수 정렬하기2와 같은 방식으로 풀었는데 메모리를 초과해서 실패했다..(당연한 건가..?) 그래서 방법을 새롭게 여러가지 sort 방법을 사용했는데 계속 메모리 초과.. 그래서 생각한 방법은 배열을 0으로 미리 만들어 놓고 순서대로 출력. (중복값이 있으니 배열 값에 +1씩 해주고 추후에 배열 값만큼 수를 출력하는 방식)!! import sys N = int(sys... 2020. 9. 28.
백준 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.

티스토리툴바