[TIL] 자료구조 / 하노이 타워, 쿠버네티스 리소스, 백준 2775 시간 초과, 백준 1769 [21-10-23]

목차

TIL

- 하노이 타워

- 쿠버네티스 리소스

- 백준 2775 시간 초과

- 백준 1769

---

TIL

매일매일 이렇게 공부하니까 집중도 잘되고 생산성이 갈수록 높아지는 것 같다. 오늘 여유롭게 공부를 했는데 목표하는 만큼 해냈다. 쿠버네티스 강의에 소요되는 시간이 2~3시간이었는데도 오늘은 집중이 잘돼서 이해하고 넘어갈 수 있었다. 하노이 타워도 난이도가 있는 편이라서 2시간 정도 소요한 것 같고 알고리즘 문제도 2시간 정도 걸린 것 같다.

 

 

하노이 타워

https://valuelog.tistory.com/83

[Data Structures][02-3] 하노이 타워 : The Tower of Hanoi

 

 재귀의 꽃이라고 하는 하노이 타워를 오늘 학습했다. 어제 공부했을 때 윤성우 저자께서 말씀하셨듯 피보나치에서는 함수 호출 순서를 추적할 수 있겠지만 하노이 타워로 가서 추적하려고 한다면 끝도 없기때문에 추적이 힘들다고 했었는데 그 말씀이 정확하게 맞았다. 하노이 타워에서는 호출 순서로 접근한다면 정말 끝도 없어서 추적이 너무 힘들었다. 그래서 호출 함수 간의 관계에 집중하고 그 논리를 이해하려고 했었다.  

 

 하노이 타워를 이해한다고 끝나는 것이 아니라 많은 문제에 적용해봐야겠다.

 

쿠버네티스 리소스

https://valuelog.tistory.com/82

[Kubernetes] Kubernetes Architecture(4)[쿠버네티스 리소스 : 컨트롤러 오브젝트, 로드밸런서 오브젝트, 스

 강의 시간이 1시간이라서 강의 듣는데 버거웠지만, 2회 정도 반복해서 들었다. 1.5배속으로 들으니 훨씬 더 편하게 수강할 수 있었다. 

 

 

 pod개념이 적용된 deployment, replicaset, daemonset 등 controller object에 대해 학습했고 Load balancer object의 서비스 종류에 대해 학습했다. 데이터 저장을 위한 storage object에 대한 개괄적 개념을 이해했다.

 

 APP 업데이트 방법으로는 롤링 업데이트, 블루 그린 업데이트 방식, 카나리 업데이트 방식 등이 있다.

 

 replicaset의 경우는 실습을 통해서 확실하게 이해했다. deployment로 replicaset으로 pod 개수를 설정하고 deploy하고 나서 pod 하나를 삭제했었는데, replicaset이 스스로 pod을 다시 생성하는 것을 눈으로 직접 보았기 때문에 이해하기 쉬웠다.

 

 

백준 2775 시간 초과

https://www.acmicpc.net/problem/2775

2775번: 부녀회장이 될테야

 오늘 학습한 내용을 최대한 활용해서 재귀 함수를 사용해 문제를 풀려고 했다.

 time out이 나서 갈아엎어야 겠지만, test case는 모두 통과했다. 아무래도 시간 복잡도가 너무 크게 나오는 것 같다. 그 부분을 유의해서 해결해야겠다.

 

# 0층은 각각 호 번호만큼 산다.
# 1층의 1호는 (1 - 1)층의 1호 사람 수만큼 f == 1, b == 3 -> f == 0, total(b)
# 1층의 2호는 (1 - 1)층의 1 + 2호 사람 수 만큼
# 1층의 3호는 (1 - 1)층의 1 + 2 + 3호 사람 수 만큼
# 1층의 4호는 (1 - 1)층의 1 + 2 + 3 + 4호 사람 수 만큼
# 2층의 1호는 (2 - 1)층의 1호 사람 수 만큼 (1)
# 2층의 2호는 (2 - 1)층의 1 + 2호 사람 수 만큼 (1) + (1 + 2)
# 2층의 3호는 (2 - 1)층의 1 + 2 + 3호 사람 수 만큼  (1) + (1 + 2) + (1 + 2 + 3)
# f == 2, b == 3 -> f == 1, total(b) -> f == 0, total(total(b))

# n층의 b호 사람 수는, n - 1층의 b호까지 더한 사람 수 이다
# n - 1층의 b호 사람 수는, n - 2층의 b호까지 더한 사람 수 이다
# n - 3층의 ....
# 탈출 조건 => Floor is zero.
# def count
# if floor == 0:
#   return 호수
# else:
#   return floor - 1
# count(n) = total(count(n - 1))

# 0층이면 탈출
n = int(input())
nums = [input() for _ in range(2 * n)]


def solution(f, b):
    if f == 0:
        return b
    else:
        i = 1
        total = 0
        while i <= b:
            total += solution(f - 1, i)
            i += 1
        return total


for i in range(0, len(nums), 2):
    f = int(nums[i])
    b = int(nums[i + 1])
    output = solution(f, b)
    print(output)

# f = int(input())
# b = int(input())

 

문제 풀이 시간 1시간 20분 내외, 재귀 논리를 최대한 찾아보려고 노력했다. 그러나 너무 시간복잡도가 크게 나왔다.

 

 

 

백준 1769

https://www.acmicpc.net/problem/1769

1769번: 3의 배수

 처음에 제출했었던 것은 input으로 값을 받아오는 코드였다. 그러나 1,000,000 의 수가 아닌 자릿수라고 하니.. 얼마나 큰 값인지, 그래서 readline으로 받아오는 것으로 바꿨다. 

 이번 문제도 재귀를 사용해서 푸는 문제였다. 특이 사항으로는 매개변수로 들어오는 값이 str이기에 return도 다시 str로 해줘야했다. 

 그리고 새롭게 알게된 것은 전역 변수인데, 재귀적으로 함수가 호출이 되었을 때도 그 전역 변수를 사용해서 함수가 얼마나 호출되었는지 알 수 있었다. global, 이런 식으로도 사용할 수 있구나.. 꼭 기억해서 다음에도 써야겠다.

 

import sys
n = sys.stdin.readline().strip()
# print(type(n))
# print(n)
# n_list = []
#
# for i in range(len(n)):
#     n_list.append(int(n[i]))
#
# total = 0
# for j in range(len(n_list)):
#     total += n_list[j]

cnt = 0


def changer(_str_nb):
    global cnt
    if len(_str_nb) < 2:
        return _str_nb
    else:
        cnt += 1
        # tmp_nb = str(nb)
        tmp_list = []
        total = 0
        # for i in range(len(tmp_nb)):
        #     tmp_list.append(int(tmp_nb[i]))
        for j in range(len(_str_nb)):
            total = total + int(_str_nb[j])
        total = str(total)
        return changer(total)


output = changer(n)

print(cnt)
if int(output) % 3 != 0:
    print("NO")
else:
    print("YES")

 

문제 풀이시간 40분 내외

 

 

 

---