자료구조&알고리즘 Python

 문자열 (str)

리스트(list)

사전(dict)

순서쌍(tuple), 집합(set), …

자료구조 알고리즘 차이

 자료구조는 데이터를 상황에 맞게 저장하기 위한 구조이고, 알고리즘은 자료구조에 있는 데이터를 활용해 어떠한 문제를 해걸하기 위한 여러 방법들의 모임이라고 볼 수 있다.

Coding Test Training > 2022 KAKAO BLIND RECRUITMENT > 신고 결과 받기

 문제 설명

신입사원 무지는 게시판 불량 이용자를 신고하고 처리 결과를 메일로 발송하는 시스템을 개발하려 합니다. 무지가 개발하려는 시스템은 다음과 같습니다.

• 각 유저가 한 번에 한명의 유저를 신고할 수 있습니다.
• 신고 횟수에 제한은 없습니다. 서로 다른 유저를 계속해서 신고할 수 있습니다.
• 한 유저를 여러 번 신고할 수도 있지만, 동일한 유저에 대한 신고 횟수는 1회로 처리합니다.
• K번 이상 신고된 유저는 게시판 이용이 정지되며, 해당 유저를 신고한 모든 유저에게 정지 사실을 메일로 발송합니다.
• 유저가 신고한 모든 내용을 취합하여 마지막에 한꺼번에 게시판 이용 정지를 시키면서 정지 메일을 발송합니다.

다음은 전체 유저 목록이 [“muzi”,”frodo”,”apeach”,”neo”]이고, k = 2(즉, 2번 이상 신고당하면 이용 정지)인 경우의 예시입니다.

각 유저별로 신고당한 횟수는 다음과 같습니다.

자료구조 Hash Table

 1. 해시 구조

• Hash Table : Key에 데이터 Value를 저장하는 구조
• Key를 통해 바로 데이터를 받아온 수 있으므로, 속도가 획기적으로 빠름
• Python Dictionary Type이 Hash Table의  ex : Key를 가지고 바로 Data Value를 꺼냄
• 보통 Array로 미리 Hash Table Size만큼 생성 후에 사용(공간과 탐색 시간을 맞바꾸는 기법)
• 단, Python에서 Hash를 별도로 구현할 이유가 없음 => Dictionary Type을 사용하면 됨

2. 알아둘 용어

• Hash : 임의 값을 고정 길이로 변환하는 것
• Hash Table : Key Value의 연산에 의해 직접 접근이 가능한 데이터 구조
• Hashing Function : Key에 대해 산술 연산을 이용해 Data 위치를 찾을 수 있는 함수
• Hash Value or Hash Address : Key를 Hashing Function으로 연산하여, Hash 값을 알아내고, 이를 기반으로 Hash Table에서 해당 Key에 대한 Data를 찾을 수 있음
• Slot : 한 개의 데이터를 저장할 수 있는 공간
• 저장할 Data에 의해 Key를 추출할 수 있는 별도 Function도 존재할 수 있음

3.1 Hash Table 만들기

3.2 초간단 Hash Function 만들기