전체 (38) 썸네일형 리스트형 [Python] input() vs sys.stdin.readline() 백준 시간초과? 나는 여태 Python을 쓰면서 입력을 받을 일이 있으면 input()으로 받았고, sys.stdin.readline()은 사용하지 않았다. 근데 백준 문제를 푸는데, 코드에는 문제가 없어보이는데 자꾸만 시간초과 에러가 났고, 원인을 찾아 구글에 검색해보니 input() 때문이라고 한다. input()과 sys.stdin의 차이점은, input()은 입력받은 값에 개행문자를 삭제시켜 리턴한다. (=strip()) 반면, sys.stdin은 한 번에 읽어와 buffer에 보관해뒀다가 사용자가 요구할 때 buffer에서 읽어온다. 이 때문에 input()을 호출하는 것이 더 느린 것이었다. 내가 보기 위해 정리하는 sys.stdin~ import sys # 여러 줄 입력 lst=[] for line in s.. 그리디 - 큰 수의 법칙 문제 '큰 수의 법칙'은 일반적으로 통계 분야에서 다루어지는 내용이지만 동빈이는 본인만의 방식으로 다르게 사용하고 있다. 동빈이의 큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다. 단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징이다. 예를 들어 순서대로 2, 4, 5, 4, 6으로 이루어진 배열이 있을 때 M이 8이고, K가 3이라고 가정하자. 이 경우 특정한 인덱스의 수가 연속해서 세 번까지만 더해질 수 있으므로 큰 수의 법칙에 따른 결과는 6 + 6 + 6 + 5 + 6 + 6 + 6 + 5인 46이 된다. 단, 서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으.. 피보나치 수열의 항 구하기 (피사노 주기) 문제 피보나치 수열에 대한 정의가 다음과 같이 재귀적으로 주어졌다고 하자. f(0) = f(1) = 1 f(n) = (f(n-1) + f(n-2)) % 1,000,000, for all 2 차대값과 차소값 찾기 문제 주어진 N개의 숫자에서 차소값(두번째로 작은 값)과 차대값(두번째로 큰 값)과 차대값, 차소값의 합을 출력하라. N은 5보다 크고 1000보다 작은 수이다. 주어지는 각 숫자는 1보다 크거나 같고, 2^32(2의 32승)보다 작은 값이다. 이때, 주어지는 숫자들은 모두 서로 다른(distinct)값이라고 가정해도 된다. Input 첫 번째 줄에 입력값 N이 주어진다. 두 번째 줄에 N개의 숫자가 주어진다. Output 주어진 N개의 숫자 중에서 차소값, 차대값, 차소값과 차대값의 합을 순서대로 출력한다. Sample Input 15 2 3 5 8 12 1 7 10 13 30 6 14 15 18 22 Sample Output 2 22 24 이 문제의 포인트는 주어지는 숫자의 범위는 부호 없는 정수형의.. [자료구조] 재귀 - 하노이 타워 (The Tower of Hanoi) 하노이 타워는 재귀함수의 힘을 보이는 대표적인 예로 꼽힌다. 하노이 타워 문제는 '하나의 막대에 쌓여 있는 원반을 다른 하나의 원반에 그대로 옮기는 방법'에 관한 것이다. 다음 제약 조건을 만족하면서 A의 원반을 C로 옮겨야 한다. 원반은 한 번에 하나씩만 옮길 수 있다. 옮기는 과정에서 작은 원반의 위에 큰 원반이 올려져서는 안된다. 이를 해결하기 위한 과정은 3가지가 있다. 작은 원반 n-1개를 A에서 B로 이동 큰 원반 1개를 A에서 C로 이동 작은 원반 n-1개를 B에서 C로 이동 + 여기에 탈출조건이 더해져야 한다. => 이를 재귀적으로 활용하면 하노이타워 문제를 해결할 수 있다. #include void HanoiTowerMove(int num, char from, char by, char t.. [자료구조] 시간복잡도(time complexity)와 공간복잡도(space complexity) #시간복잡도(time complexity) : 알고리즘을 프로그램으로 실행하여 완료하기까지 소요되는 시간(속도) : 컴파일타임과 런타임의 합 1) Big-Oh 표기법 "n>=0, f(n)>=0, g(n)>=0에 대해서 두 개의 함수 f(n)과 g(n)이 주어졌을 때, 모든 n>=K에 대하여 f(n) =0, f(n)>=0, g(n)>=0에 대해서 두 개의 함수 f(n)과 g(n)이 주어졌을 때, 모든 n>=K에 대하여 f(n) >= Cg(n)을 만족하는 두 개의 상수 C와 K가 존재하면, f(n)의 Big-Omega는 Ω(g(n))이다." 즉, 시간의 하한선을 표현한다. (best case) 해당 알고리즘은 Big-Omega보다 빠를 수 없다. Ω(2ⁿ) < Ω(n³)< Ω(n²) 이전 1 2 3 4 5 다음
