99클럽 코테 스터디 1일차 TIL + 오늘의 학습 키워드

- 오늘의 학습 키워드

#집합#입출력#파이썬 자료형 

 

- 문제

백준 

2776, 암기왕, 실버4 

2776번: 암기왕

 

- 오늘의 회고

어떤 리스트 안에 원소가 있는지 확인하기 위해서는 집합 자료형이 가장 빠르다는 아이디어를 얻었다. 

오랜만에 문제푸니깐 재밌더라. 그와 별개로 알고리즘 공부를 열심히 해야겠다는 생각이 들었다. 

안하니깐 금방 까먹는구나. 

 - 어떤 문제가 있었고, 나는 어떤 시도를 했는지

리스트에 해당 원소가 있는지 판단하는 문제 

내가 처음 제출했던 답안 코드이다. 

리스트 두 개로 원소를 찾았다.

    import sys

    input_data = sys.stdin.readlines()

    T = int(input_data[0].strip())
    lines = [line.strip() for line in input_data[1:]]

    for t in range(T):
        n, n_list, m, m_list = lines[:4]
        n_list = n_list.strip().split()
        m_list = m_list.strip().split()
        for i in m_list:
            if i in n_list:
                print(1)
            else:
                print(0)
        lines = lines[4:]

 - 어떻게 해결했는지

리스트 안에 요새를 찾는 건 집합이 훨씬 빠르다. 

import sys

input_data = sys.stdin.readlines()

T = int(input_data[0].strip())
lines = [line.strip() for line in input_data[1:]]

for t in range(T):
	n, n_list, m, m_list = lines[:4]
	n_list = set(n_list.strip().split()) #리스트를 집합으로 바꿨다.
	m_list = m_list.strip().split()
	for i in m_list:
		if i in n_list:
			print(1)
		else:
			print(0)
	lines = lines[4:]

  

- 무엇을 새롭게 알았는지

파이썬 입출력, 파일 입출력, 자료형, match, 집합의 시간복잡도

match

Python의 match 문은 Python 3.10에서 새롭게 도입된 기능으로, 구조적 패턴 매칭(Structural Pattern Matching)을 제공한다. 이는 데이터를 특정 패턴에 따라 확인하고, 조건에 맞는 블록을 실행할 수 있게 한다. 

 

클래스도 된다는 점에서 파이썬의 편리함에 감탄했다. 

status_code = 404

match status_code:
    case 200:
        print("OK")
    case 404:
        print("Not Found")
    case 500:
        print("Server Error")
    case _:
        print("Unknown Status")

 

data = [1, 2, 3, 4]

match data:
    case [1, 2, 3, 4]:
        print("정확히 [1, 2, 3, 4]입니다.")
    case [1, *rest]:
        print(f"1로 시작하고 나머지는: {rest}")
    case _:
        print("패턴에 맞지 않음")

 

 

 

집합의 시간복잡도

다음과 같을때  

 

• T: 테스트 케이스 수
• M: 각 테스트 케이스에서 m_list의 길이
• N: 각 테스트 케이스에서 n_list의 길이1

 

리스트로 원소를 찾으면 O(M x N) 시간복잡도가 나온다. 

 

1) for i in m_list:

• m_list의 길이를 M이라고 할 때, 이 반복문은 최대 M번 실행

2) if i in n_list:

• n_list의 길이를 N이라고 할 때, in 연산자는 리스트에서 특정 요소를 찾기 위해 최악의 경우 리스트 전체를 탐색한다.
• 따라서 in 연산의 시간복잡도는 최대 O(N)

3) 전체 반복문은 M번 실행되고, 각 반복에서 리스트 탐색(O(N))이 이루어지므로, 이 부분의 시간복잡도는 O(M × N)이다.

 

그래서 리스트를 사용하면 시간복잡도가 O(T x M x N) 으로 시간 초과가 났다. 

 

리스트 대신 집합(set)을 이용하면 2) in 연산을 O(1) 로 줄일 수 있다. (해시테이블 기반이다) 

집합을 만드는데 O(N)이 걸려서 결과적으로 O(T x (N+M))으로 확 줄일 수 있다. 

 

 

 

chat gpt가 알려준 시간 복잡도

 

- 내일 학습할 것은 무엇인지

파이썬의 파일 입출력에 조금 익숙해질 필요가 있을거 같다. DFS/BFS 공부를 좀 할 거 같다.