목록알고리즘 (5)
DevSSOM
K번째 숫자 찾기 n개의 숫자가 차례대로 주어질 때, 매 순간마다 “지금까지 입력된 숫자들 중에서 k번째로 작은 수”를 반환하는 프로그램을 작성하세요. 프로그램의 입력으로는 첫째줄에 n과 k가 입력되고, 둘째줄에 n개의 숫자가 차례대로 주어집니다. 문제 조건 n은 100보다 작은 숫자입니다. 매 순간마다 지금까지의 입력중 kk번째로 작은 수를 출력하되, 없다면 -1을 출력합니다. 입력 예시 10 3 1 9 8 5 2 3 5 6 2 10 출력 예시 -1 -1 9 8 5 3 3 3 2 2 10개의 숫자가 차례대로 주어집니다. 맨 처음 1만 입력을 받았을 경우, 3번째로 작은 숫자가 없으므로 -1을 출력합니다. 그 다음 9도 마찬가지입니다. 세 번째로 숫자 8을 입력받는 순간, 지금까지 입력받은 숫자는 1, ..
연습문제 : 가장 큰 부분합 구하기 정수들의 리스트가 입력으로 들어옴. 이 정수들의 리스트를 일부분만 잘라내어 모두 더했을 때의 값을 부분합이라 부름. 이때 가장 큰 부분합을 구해봐. 예를 들어, [-10, -7, 5, -7, 10, 5, -2, 17, -25, 1]이 입력으로 들어왔다면 [10, 5, -2, 17]을 모두 더한 30이 정답. ※입력에는 최소 하나 이상의 양수가 존재. ※이 문제에는 여러 종류의 풀이법이 존재. 각 풀이법의 시간 복잡도를 고려하면서 여러가지 방법으로 문제를 풀어봐. def maxSubArray(nums): return 0 def main(): print(maxSubArray([-10, -7, 5, -7, 10, 5, -2, 17, -25, 1])) # 30이 리턴되어야 합..
연습문제 : 중복된 하나의 숫자 찾아내기 숫자들의 배열이 주어짐. 이 배열은 길이 n을 가지며, 1부터 n-1까지의 숫자로 이루어져 있음. 모든 숫자가 배열에 단 한번씩만 나타남. 그런데, 딱 하나의 수가 배열에 두 번 등장함. 이 중복되는 숫자를 찾아내봐. 예를 들어서, [1, 5, 2, 4, 5, 6, 3] 를 살펴보면, 배열의 길이는 7이며, 따라서 1~6까지의 숫자들이 한번씩 등장. 그런데 5만 한번 더 등장한 것. 따라서 이 경우에는 5를 찾아내면 됨. def findDuplicate(nums): return 0 def main(): print(findDuplicate([1, 5, 2, 4, 5, 6, 3])) if __name__ == "__main__": main() >>> 내가 작성해본 답..
연습문제 : 가장 큰 두 수의 차 보다 큰 정수들의 배열이 주어졌다고 하자. 여기서 가능한 모든 서로 다른 두 숫자의 차이를 고려해보고, 이중 가장 큰 차이를 반환하는 함수를 적어봐. 예를 들어서, [2, 8, 19, 37, 4, 5, 12, 50, 1, 34, 23] 가 입력으로 주어졌을 경우 가장 큰 차이를 내는 숫자쌍은 50-1 = 49임. 두 수의 차에 해당하는 값을 반환하면 됨. 위 예시의 경우, 49를 반환함. 양의 값을 반환해야 함. 위 예시의 경우 -49가 아니라 49를 반환해야 함. 배열의 길이는 2보다 크거나 같다고 가정. 이 문제에는 여러 종류의 풀이법이 존재함. 각 풀이법의 시간 복잡도를 고려하면서 여러가지 방법으로 문제를 풀어봐. def maxTwoDiff(nums): nums.s..
프로그램은 입력(input), 실행(process), 저장(strore), 출력(output)으로 구성됨. 그림의 화살표는 데이터의 흐름과 저장, 즉 어떤 자료구조의 데이터를 어떻게 저장해서 보낼 것인지를 보여줌. 실행(process)에 해당하는 사각형에서 거의 모든 프로그램의 실행 방식이 결정되기 때문에, 이 단계가 가장 알고리즘과 연관이 있어. 알고리즘은 효율적인 프로그래밍을 위해서 시간과 공간의 복잡성을 고려해서 짜여져야 되기 때문에, 시간과 공간의 효율성이 알고리즘과 연관돼. 자료구조(Data Structure) 프로그램이 돌아가기 위해서는 많은 값들을 저장하고, 기억해야 됨. 이때 이 값들을 어떻게, 그리고 어디에 저장하면 좋을까?에 자료구조가 활용됨. 자료구조에는 여러 종류가 있음. 가장 간단..