24.07.12 day24 남추문 스터디 회고

어제 스터디 개념학습을 하고 오늘 스터디 전까지 알고리즘 문제를 풀었다. 확실히 알고리즘 문제를 너무 쉬어서 그런지 이해도 잘 안되고 너무 어렵더라

문제는 총 5문제 였는데 3문제는 도전도 못하고 한문제 풀고 한문제 풀다가 못풀었다. 푼 문제는 이진 탐색 트리인데 

이 문제다.

import sys
input = sys.stdin.readline

K = int(input())
arr = list(map(int, input().split()))
levels = [[] for _ in range(K)]
stack = [(0, len(arr) - 1, 0)]

while stack:
    start, end, level = stack.pop()
    if start > end:
        continue
    
    mid = (start + end) // 2
    levels[level].append(arr[mid])
    
    stack.append((mid + 1, end, level + 1))
    stack.append((start, mid - 1, level + 1))

for level in levels:
    print(' '.join(map(str, level)))

1. 트리의 깊이인 K값을 입력받고 방문한 빌딩의 순서 배열을 입력받고, 이 후 빌딩 번호를 저장하기 위한 빈 리스트를 만든다. 스택 배열은 start, end, level형태로 지정을 해준다.
2. 스택이 있는 동안 start, end, level을 꺼내면서 범위가 유효하지 않으면 continue한다.
3. 부분 배열의 중간 값을 지정해 현재 레벨에 방문할 빌딩 번호이므로 levels 배열의 인덱스 level에 추가한다.
4. 왼쪽 자식 노드부터 처리해야 하는데 스택이라 거꾸로 꺼내야 하기 때문에 오른쪽 자식 노드부터 넣는다.
5. 이 후 마찬가지로 오른쪽 자식 노드를 처리하기 위해 왼쪽 자식 노드를 넣는다.
6. 정리한 중위 순회의 리스트를 하나씩 출력하며 join으로 묶어 한 줄로 출력한다.

 

이진 트리는 어떻게 잘 찾아보며 풀었는데 백준을 너무 오랜만에 풀어서 입력값을 받는 법을 망각했다. 이거 때문에 런타임 에러만 주구장창 발생해서 스트레스..

 

남은 한 문제는 줄 세우기 문제였는데 이 문제는 풀어보다가 도저히 못풀겠어서 스터디 직전까지 풀어보다가 갔다

스터디는 저번주에 어떻게 진행되는지 구경좀 하고 이번주부터 참여하게 되었다. 만석님이랑 재희님이랑 셋이서 스터디를 했는데 이번주 주제는 그제와 어제 학습했던 스케줄링, 데드락, 세마포어, 뮤텍스, 컴파일러 등의 주제로 서로에게 한 문제씩 질문해가며 답변하는 방식으로 진행헀다.

 

오랜만에 정글 방식으로 하려니 긴장되서 질문에 대한 답변을 할 때 너무 버벅였던 것 같다.

 

내가 받은 질문은 

 

 

• 싱글 스레드 CPU 에서 상시로 돌아가야 하는 프로세스가 있다면, 어떤 스케쥴링 알고리즘을 사용하는 것이 좋을까요? 또 왜 그럴까요?
• RR을 사용할 때, Time Slice에 따른 trade-off를 설명해 주세요.
• Wait Free와 Lock Free를 비교해 주세요.
• 본인이 사용하는 언어는 어떤 식으로 컴파일 및 실행되는지 설명해주세요.

정도가 기억이 난다.

 

Wait Free 와 Lock Free는 답변을 못했다 기본 개념은 아는데 차이를 위한 설명이 생각이 안났다.. 더 공부해야 할듯

질문을 바꿔달라 해서 밑의 사용하는 언어의 컴파일 방식을 설명해달라하는 질문이 왔는데 이 부분은 자바스크립트를 공부하면서 한 번 봤던 내용이라 잘 답변했다. 재희님이 다음주는 알고리즘 문제를 조금 낮춰준다고 하니까 담주는 문제 쭉 풀어야 겠다.