크래프톤 정글 week02, day14 - sys, 람다, 유니온-파인드, 알고리즘 문제

sys 모듈

• 파이썬에서 제공하는 표준 라이브러리로 시스템과 관련된 각종 정보들을 제공하는 모듈이다.
• 몇 가지 기능들
  • sys.argv
    • 파이썬을 실행하면서 입력된 값을 전달받아 활용할 수 있다.
    • argv를 출력하면 입력된 값을 list형태로 저장하고 있고, 첫번째 배열 값은 항상 실행하는 파일의 이름이다. 그래서 입력된 값은 argv[0]이 아닌 argv[1]부터 시작한다.
  • sys.path
    • 파이썬이 설치되어 있는 경로 및 라이브러리들의 경로를 리스트에 모두 저장하고 있는 변수이다.
    • 이 리스트에 경로를 추가해 파이썬 파일들을 import문으로 불러올 수 있다.
  • sys.executable
    • 현재 실행하고 있는 파이썬 실행파일의 절대경로를 알아낼 수 있다.
    • 실행파일의 경로를 알아내야 할 때 사용
  • sys.platform
    • 현재 실행 중인 os 환경 platform의 이름을 출력 가능
  • sys.version
    • 파이썬 버전을 출력한다.
    • ex) 3.8.11 (default, jan 21 2024, 05:03:17)
  • sys.setrecursionlimit
    • 기본 재귀 깊이 제한이 1000으로 매우 얕아 런타임 에러를 자주 볼 것이다.
    • 그런 기본 제한을 바꿔주기 위한 기능, 다만 임의로 재귀의 싶이를 설정할 수 없다.

---

strip

• 문자열 인자가 없을 때 공백을 제거하고, 있을 때 모든 조합을 이용해 제거
  • Istrip
    • 문자열에 왼쪽 공백이나 인자가 된 문자열의 모든 조합을 제거

"jungle".lstrip()
'jungle'

"jungle".lstrip('jun')
'gle

 

• 인자를 넣지 않은 경우 왼쪽 공백 제거
• 인자를 넣은 경우 왼쪽ㅇ로 j, u, n의 문자열의 모든 조합 제거

 

• ​rstrip
  • 문자열에 오른쪽 공백이나 인자가 된 문자열의 모든 조합 제거

"jungle".strip()
'jungle'

"jungle".strip('je')
'ungl'

• 인자를 넣지 않은 경우 왼쪽 공백 제거
• 인자를 넣은 경우 양쪽 끝에 j, e의 문자열의 모든 조합 제거

---

람다

• 익명함수라고 불리며 람다 사용을 통해 코드를 간결하게 작성할수 있고, 함수 자체를 인자로 넘길 수 있는 유연함이 있다.
• 일반 함수와 달리 이름이 없고 표현식을 하나만 사용할 수 있기 때문에, 복잡한 로직 구현은 불가능하다.
• 람다 선언

lambda 변수 : 표현식

#예시
add = lambda a, b : a + b
n = add(1 + 2)

print(n)

• 문제 풀이에서 사용해볼려고 작성했기 때문에 자세한 내용은 나중에 학습할때 작성하려고 한다.

---

유니온-파인드(Union-Find)

• 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘
• 노드를 합치는 Union연산과 노드의 루트 노드를 찾는 Find연산으로 이루어진다.
  • 다른 팀원에게 배운 방식으론 Find 이후 두 노드가 루트 노드가 다른지 판별하는 Connected연산도 사용
• 크루스칼(Kruskal) 알고리즘은 가중치가 작은 간선부터 차례대로 확인하는 알고리즘이며 최소 신장 트리는 사이클이 발생하면 안되는데, 사이클이 있는지 확인하는 방법에 사용되는 개념이 유니온-파인드이다.

• 그림에서 2번과 3번을 비교했을 때 루트 노드가 다르기 때문에 그래프가 다르다고 판별할 수 있지만, 3번과 5번을 비교했을 때도 같다고 판별이 되야 한다.

자기 노드	1	2	3	4	5
부모 노드	1	2	3	4	5

• 처음에 부모 노드에 자기 노드를 입력하고 하나씩 비교를 하며 루트 노드가 같으면 부모노드에 비교 시 작은 값으로 넣는다.
  • ex) 3의 부모노드는 1이다.

자기 노드	1	2	3	4	5
부모 노드	1	2	1	4	5

• 이런 식으로 부모 노드를 확인해 값을 바꿔주는데, 5의 경우는 부모노드를 확인했을 때 3으로 나올 것이다. 이럴 땐 재귀를 이용해서 3의 부모 노드의 값을 찾아 넣어준다.

자기 노드	1	2	3	4	5
부모 노드	1	2	1	4	1

• 5의 루트 노드는 1인 걸 확인해서 변경하고, 나머지도 바꿔주면

자기 노드	1	2	3	4	5
부모 노드	1	2	1	2	5

• 이 된다.

​유니온-파인드 간단 구현

# 입력값을 받기 위해 초기화
def init(n):
    # 부모 노드값을 자기 자신으로 채워 넣기
    parent = [0] * (n + 1)
    for i in range(1, n + 1):
        parent[i] = i
    return parent

# 루트 노드를 찾기
def find(parent, x):
    # 만약 노드값 x의 부모노드가 자기노드가 아니라면
    if parent[x] != x:
        # 루트노드를 찾을 때까지 find함수를 재귀하여 부모노드값에 루트노드값을 넣는다. 
        parent[x] = find(parent, parent[x])
    # 입력한 루트노드 값을 반환
    return parent[x]

# 노드 a와 b의 집합을 합친다
def union(parent, a, b):
    # a 노드의 루트 노드를 찾기
    a = find(parent, a)
    # b 노드의 루트 노드를 찾기
    b = find(parent, b)
    # 만약 a의 루트 노드가 b의 루트 노드보다 작으면
    if a < b:
        # b의 루트노드를 a로 변경
        parent[b] = a
    else:
        # 아니면 a의 루트노드를 b로 변경
        parent[a] = b
# 근데 a, b의 값 비교는 문제에 명시될때나 작성하지 보통은 안나온다고 해서 현재는 어느걸로 골라도 상관없을 듯

 

크루스칼에 유니온-파인드를 넣어서 간단 구현

# 노드 개수를 입력받아 초기화
def init(n):
    # 부모노드에 자기노드값을 넣기
    parent = [0] * (n + 1)
    for i in range(1, n + 1):
        parent[i] = i
    return parent

# find 함수(루트노드로 받을 parent와 자기노드값 x)
def find(parent, x):
    # 부모 노드 값이 자기 노드랑 다르다면
    if parent[x] != x:
        # find함수를 재귀해서 부모노드와 자기노드가 같을때까지 반복
        parent[x] = find(parent, parent[x])
    # 같을 시 값 반환
    return parent[x]

# union 함수(루트노드 parent와 find함수에서 루트노드를 담을 a, b)
def union(parent, a, b):
    # a와 b에 find에서 받아온 루트 노드값을 입력
    a = find(parent, a)
    b = find(parent, b)
    # 만약 a의 루트노드가 b의 루트노드보다 작을 때
    if a < b:
        # b의 루트노드에 a의 루트노드값을 넣기
        parent[b] = a
    # b의 루트노드가 더 작으면 a에 b를 넣기
    else:
        parent[a] = b

# kruskal 함수(노드의 개수 n과 간선리스트 edges를 저장)
def kruskal(n, edges):
    # 간선리스트를 리스트 안 튜플의 2번 인덱스 값인 가중치를 오름차순으로 정렬
    edges.sort(up=lambda x: x[2])
    # 부모노드에 노드를 저장하는 값을 초기화
    parent = init(n)
    # 가중치 합산 변수 생성
    total_weight = 0

    # 간선리스트를 돌리면서
    for edge in edges:
        # 입력값을 노드a, 노드b, 가중치 변수로 분산 
        a, b, weight = edge
        # a와 b의 루트 노드가 다르다면
        if find(parent, a) != find(parent, b):
            # union 함수를 실행해서 노드를 합치기
            union(parent, a, b)
            # 각각의 가중치를 합쳐서 전체 가중치에 담아 반환
            total_weight += weight

    return total_weight

 

---

이진 검색 트리

• 노드의 왼쪽 서브트리의 키는 현재 노드의 키보다 작고 오른쪽 서브트리의 키는 더 크다.
• 전위 순회된 루트를 방문한 노드 순서를 입력값에다 입력받아 후위순회로 바꿔야함.

# class Node:
#     # 노드를 초기화
#     def __init__(self, data):
#         self.data = data
#         self.left = None
#         self.right = None

# # 삽입 함수
# def insert(node, data):
#     # 들어온 node값이 없으면 새 Node를 만들고 반환
#     if node is None:
#         return Node(data)
#     # 만약 넣을 값이 node값보다 작으면 node의 왼쪽트리에 삽입 
#     # 그게 아니면 오른쪽트리에 삽입
#     if data < node.data:
#         node.left = insert(node.left, data)
#     else:
#         node.right = insert(node.right, data)
#     return node

# # 후위 순회
# def postOrder(node):
#     # 만약 node가 있다면 왼쪽트리부터 오른쪽트리로 방문한 후 마지막으로 현재 노드를 방문
#     if node is not None:
#         postOrder(node.left)
#         postOrder(node.right)
#         print(node.data)

# # 전위순회된 입력값 받기
# preOrder = []
# cnt = 0
# # 입력 갯수가 정해져있지 않기 때문에 while문으로 루프돌리기
# # if문으로 입력값이 없을 때 막으면 정확히 빈문자열을 입력해야하기 때문에 try로 막기
# while cnt <= 10000:
#     try:
#         n = int(input())
#     except: 
#         break
#     preOrder.append(n)
#     cnt += 1

# root = None
# # 입력값이 있으면 root에 데이터 삽입
# for data in preOrder:
#     root = insert(root, data)
    
# postOrder(root)

# ------------------- 런타임 에러 ------------------------
import sys
# 재귀호출 최대깊이 설정
sys.setrecursionlimit(10**9)

# 전위순회 배열
preorder_arr = []

# 입력값이 엔터가 되면 스탑(입력값을 그만 받기 위함)
while True:
    # 전위 순회 배열에 입력값을 공백제거하고 정수로 변환해 넣는다.
    try:
        preorder_arr.append(int(sys.stdin.readline().rstrip()))
    except:
        break

# 후위순회 함수
def postorder(root_idx, end_idx):
    # 탐색할 노드가 더 없으면 반환값 없이 종료하기 위해 return만
    if root_idx > end_idx:
        return
    
    # 전역에서 가져온 전위순회 배열을 가져온다.
    global preorder_arr
    
    # 이진검색트리 특성 상, 루트 노드보다 큰 값을 오른쪽 서브트리에 있기 때문에
    #  오른쪽 서브트리 시작을 루트 노드보다 큰 처음 값으로 설정 
    right_start = end_idx + 1

    # 루트인덱스의 다음 인덱스부터 끝까지 순회
    for i in range(root_idx + 1, end_idx + 1):
        # 만약 전위순회의 root 인덱스 값보다 더 크면 오른쪽 서브트리로 넣는다
        if preorder_arr[root_idx] < preorder_arr[i]:
            right_start = i
            break
    
    # root 다음부터 왼쪽 서브트리 탐색
    postorder(root_idx + 1, right_start - 1)

    # 왼쪽 서브트리 탐색 끝나면 오른쪽 서브트리 탐색
    postorder(right_start, end_idx)

    # 왼쪽, 오른쪽 서브트리 탐색 끝나면 root 출력
    print(preorder_arr[root_idx])

# 전위순회 배열을 돌리기 위해 후위순회 함수에 넣기
postorder(0, len(preorder_arr) - 1)

# 출처 : https://storing.tistory.com/48

 

트리 순회에서 사용한 후위순회와 노드를 받았던 코드를 이용해 문제를 풀 생각이였는데 계속 런타임 에러가 발생하고 도저히 못풀것 같아 알기 쉽게 설명이 나와있는 다른 분 블로그 코드를 공부했다.

지피티는 class를 사용해 입력해줘서 트리 순회 문제를 풀 때 class를 사용했는데 다른 팀원분들 푼 걸 보면 class를 안쓰는 코드를 작성하더라. 이제 지피티는 좀 자제해야겠다.

​

문제가 안 풀려서 최소신장트리 문제는 내일 푸는걸로

​

학습시간 : 14시~24시