실습_1. 자료구조와 알고리즘
Updated:
실습
두 수의 합
숫자들의 배열이 주어지고 표적 숫자가 주어졌다고 합시다.
배열에 주어진 숫자들 중 두 개의 숫자를 더하면 표적 숫자가 되는데요,
이때 어떤 두 수를 더하면 표적숫자가 되는지 찾는 문제를 풀어 봅시다.
예를 들어서, [2, 8, 19, 37, 4, 5] 가 배열로 주어지고
12 가 표적으로 주어지면 8,4 를 찾아내시면 됩니다.
- 입력 배열에는 중복되는 수가 없습니다.
- 입력 배열에는 합해서 표적이 되는 어떤 두 수가 반드시 있습니다.
- 출력의 순서는 상관 없습니다. 위 예시의 경우, 8,4 와 4,8은 둘 다 정답으로 인정합니다.
def twoSum(nums, target):
# for n in nums:
# if target - n in nums:
# return target-n, n
nums.sort()
start = 0
end = len(nums) - 1
# 2 4 5 8 19 37
while True:
if nums[start] + nums[end] == target:
return nums[start], nums[end]
elif nums[start] + nums[end] > target:
end-=1
else
start+=1
def main():
print(twoSum([2, 8, 19, 37, 4, 5], 12))
if __name__ == "__main__":
main()
- 배열의 시작점과 끝점에서 시작해서 시간복잡도가 효율적이다
- 주석의 방식 풀면 배열을 2번 돈다(비 효율적)
가장 큰 두 수의 차
0보다 큰 정수들의 배열이 주어졌다고 합시다.
여기서 가능한 모든 서로 다른 두 숫자의 차이를 고려 해 보고,
이중 가장 큰 차이를 반환하는 함수를 적어봅시다.
예를 들어서, [2, 8, 19, 37, 4, 5, 12, 50, 1, 34, 23] 가
입력으로 주어졌을 경우 가장 큰 차이를 내는 숫자쌍은 50-1 = 49 입니다.
def maxTwoDiff(nums):
min = nums[0]
max = nums[0]
for i in nums:
if min > i:
min = i
if max < i:
max = i
return max - min
def main():
print(maxTwoDiff([2, 8, 19, 37, 4, 5, 12, 50, 1, 34, 23])) # 49가 리턴되어야 합니다.
if __name__ == "__main__":
main()
- sort를 사용해서 끝값에서 첫번째 값을 빼면 시각복잡도 비효율적
자동차 객체
class Car:
def __init__(self):
self.speed = 0
self.year = 2017
self.wheel = Wheel("aluminum")
self.color = "white"
def speedUp(self, addSpeed):
self.speed += addSpeed
def speedDown(self, minusSpeed):
self.speed -= minusSpeed
def changeColor(self,color):
self.color = color
def wheelChange(self, newWheelType):
self.wheel = Wheel(newWheelType)
# 객체의 데이터로 다른 객체를 사용 할 수도 있다.
class Wheel:
def __init__(self, newWheelType):
self.wheelType = newWheelType
def main():
audi = Car()
print("고객님의 차량은 {} 년에 출고되었습니다.".format(audi.year))
print("현재 속도는 {} km/h 입니다.".format(audi.speed))
audi.speedUp(200)
print("변경된 속도는 {} km/h 입니다.".format(audi.speed))
randomWheel = Wheel("aluminum")
print("바닥에 {} 재질의 바퀴가 떨어져 있습니다.".format(randomWheel.wheelType))
if __name__ == "__main__":
main()
미션
중복된 하나의 숫자 찾아내기
숫자들의 배열이 주어집니다. 이 배열은 길이 n을 가지며,
1부터 n-1까지의 숫자로 이루어져있습니다.
모든 숫자가 배열에 단 한번씩만 나타납니다.
그런데, 딱 하나의 수가 배열에 두번 등장합니다.
이 중복되는 숫자를 찾아내어 보세요.
예를 들어서, [1, 5, 2, 4, 5, 6, 3] 를 살펴봅시다. 배열의 길이는 7이며,
따라서 1~6까지의 숫자들이 한번씩 등장합니다.
그런데 5만 한번 더 등장했네요.따라서 이 경우에는5를 찾아내면 됩니다.
def findDuplicate(nums):
nums.sort()
for i in range(len(nums)):
if nums[i] == nums[i+1]:
return nums[i]
return 0
def main():
print(findDuplicate([1, 5, 2, 4, 5, 6, 3]))
if __name__ == "__main__":
main()
가장 큰 부분합 구하기
정수들의 리스트가 입력으로 들어옵니다.
이 정수들의 리스트를 일부분만 잘라내어 모두 더했을 때의
값을 부분합이라 부릅니다. 이때 가장 큰 부분합을 구해봅시다.
예를 들어, [-10, -7, 5, -7, 10, 5, -2, 17, -25, 1]이 입력으로
들어왔다면 [10, 5, -2, 17]을 모두 더한 30이 정답이 됩니다.
※입력에는 최소 하나 이상의 양수가 존재합니다.
def maxSubArray(nums):
sum = 0
max = 0
for i in nums:
sum += i
if sum < 0:
sum = 0
if max < sum:
max = sum
return max
def main():
print(maxSubArray([-10, -7, 5, -7, 10, 5, -2, 17, -25, 1])) # 30이 리턴되어야 합니다
if __name__ == "__main__":
main()
1로 만들기
어떤 수가 입력으로 들어오면 몇번의 연산을 통해 숫자를 1로
가장 빨리 만들 수 있을지 계산하는 함수를 작성해 봅시다.
할 수 있는 연산은 다음과 같으며 어느연산을 먼저 수행하는지에 대한 순서는 없습니다.
3의 배수라면 3으로 나눕니다.
2의 배수라면 2로 나눕니다.
1을 뺍니다.
예를 들어 10이 입력되었다면, 10 -> 5 -> 4 -> 2 -> 1의 4번의 과정을 거쳐 1로 만들 수 있습니다.
하지만 10 -> 9 -> 3 -> 1의 방법으로 3번의 과정을 거쳐 더 빠르게 1로 만들 수 있습니다.
또한 이것이 가장 빠른 방법입니다.
이와같이 숫자가 입력되면 가장 빠르게 1로 만드는 연산의 횟수를 출력하는 프로그램을 작성해 봅시다.
def convertTo1(num):
nums = [num+1 for i in range(num+1)]
nums[1] = 0
for i in range(2, num+1):
if i%2==0:
if nums[int(i/2)] + 1< nums[i]:
nums[i] = nums[int(i/2)] + 1
if i%3==0:
if nums[int(i/3)] + 1 < nums[i]:
nums[i] = nums[int(i/3)] + 1
if nums[i-1] + 1 < nums[i]:
nums[i] = nums[i-1] + 1
return nums[num]
def main():
print(convertTo1(10))
if __name__ == "__main__":
main()
Leave a comment