자료구조

• Hash Table

  • from collections import Counter
    from collections import defaultdict
    
    word_list = ["222", "111", "333", "222", "123", "333", "321", "333"]
    
    # collections.Counter 으로 손쉽게도 가능!
    counter = Counter(word_list)
    print(f"counter={counter}")
    
    count_dict = dict()
    for w in word_list:
    	if w not in count_dict:
    		count_dict[w] = 1
    	else:
    		count_dict[w] += 1
    print(f"count_dict={count_dict}")
    
    
    # 각 단어의 인덱스를 세알리기~
    index_dict = dict()
    index = 0
    for w in word_list:
    	if w not in index_dict:
    		index_dict[w] = [index]
    	else:
    		index_dict[w].append(index)
    	index += 1
    print(f"index_dict={index_dict}")
    
    
    # enumerate 을 사용하면... 루프에서 직접 가능
    # collections.defaultdict 는 value 의 타입을 초기화 해줘서 편함
    dd = defaultdict(list)
    for i, w in enumerate(word_list):
        print(f"i={i} c={c}")
        dd[w].append(i)
    print(f"dd={dd}")
    
    ...

  • ...
• Stack(LIFO), Queue(FIFO)

  • from collections import deque
    
    dq = deque('123')
    dq.append('4')
    dq.appendleft('0') 
    # deque(['0', '1', '2', '3', '4'])

  • ...
• TREE, Graph
  • ...
• Heap

  • import heapq as hq
    
    nums = [10, 1, 2, 3, 9, 5]
    heap = list()
    for num in nums:
      hq.heappush(heap, (-num, num))  # 튜플로 추가하면, 맨앞값을 기준으로 구성되는 원리 이용.
    
    max_list = [hq.heappop(heap) for _ in range(len(heap))]

  • 최소값 연산을 빠르게 하기 위해 고안된, Complete Binary Tree
  • (즉, 데이터가 입력이 되면 가장 말단에서 왼쪽부터 차례대로 채워져 나감)
    • heappush(heap, x) : x 를 heap에 추가.
    • heappop(heap) : heap에서 가장 작은 x 를 Pop. (빈경우 IndexError)
    • heapify(x_list) : 리스트를 -> heap 으로 변환. ( in linear time, O(N) )
  • ...
• List 루핑 remove

  • edit_list = [1, 0, 2, 0, 3]
    copy_list = edit_list.copy()
    for copy in copy_list:
        if copy == 0:
            edit_list.remove(copy)
    print(f"edit_list={edit_list}")
    print(f"copy_list={copy_list}")

  • ...
• mean(평균), median(중위값), mode(최빈값)

  • numbers = [11, 0, 2, 10, 1, 3, 4, 5, 6, 9, 12, 7, 8]
    n = len(numbers)
    sort_list = sorted(numbers)
    
    if n % 2 == 0:
        m2 = sort_list[n//2]
        m1 = sort_list[n//2 - 1]
        median = (m2 + m1) / 2
    else:
        median = sort_list[n // 2]
    print(f"median={median}")

  • ...
• 숫자범위 겹침 판단

  • sch_list = [
        [[10, 20], [30, 40]],
        [[0, 10], [40, 50]]
    ]
    size = 10
    
    ok = -1
    for i in range(0, 24 * 60):
        is_all_ok = True
        for employee in sch_list:
            for times in employee:
                begin = times[0]
                end = times[1]
                if (i+size) <= begin or end <= i:
                    ...
                else:
                    is_all_ok = False
                    break
            if is_all_ok is False:
                break
        if is_all_ok is True:
            ok = i
            break
    print(f"ok={ok}")

  • ...
• Sorting

  • first_list = ['12', '3', '4', '5678', '90']
    sorted_list1 = sorted(first_list, key=lambda x: len(x), reverse=True)
    second_list = ['90', '5678', '4', '3', '12']
    sorted_list2 = sorted(second_list, key=lambda x: len(x), reverse=True)
    
    counting = 0
    max_len = 0
    for first in sorted_list1:
        if len(first) <= max_len:
            break
        for i in range(0, len(first)):
            if (i+1) <= max_len:
                continue
            prefix = first[:i+1]
            is_not_all_startswith = True
            for second in sorted_list2:
                counting += 1
                if second.startswith(prefix):
                    is_not_all_startswith = False
                    max_len = len(prefix)
                    print(f"prefix={prefix}")
                    break
            if is_not_all_startswith:
                break
    print(f"max_len={max_len} (counting={counting})")

  • sorted(... , key=lambda x: (x.a, x.b), ...) 식으로 다중정렬 가능.
  • ...
• 탐색

  • # 전체~최소1 창크기로 탐색
    totals = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    size = len(totals)
    for i in range(0, size):
    	for j in range(0, i+1):
        	window = totals[j:j+size-i]
            print(f"i={i} j={j} window={window}")
    
    
    # 섬 크기 탐색
    """
    1 1 0 0 0
    1 1 0 0 0
    0 0 0 0 1
    0 0 0 1 1
    """
    
    # 섬 갯수 탐색
    arrays = [0,1,1,0,0,1,0,1,1,0]
    i_list = list()
    for i,a in enumerate(arrays):
    	if a > 0:
        	i_list.append(i)
        ...

  • ...
• String
  • 문자열 합침 : ''.join(str_list)
  • 문자 갯수 : string.count(char)
• Set

  • vector1 = [1, 3, 4]
    vector2 = [5, 2, 1]
    team_list = list()
    
    def new_teams(team_list, v1, v2)
    	union_list = list()
        new_team_list = list()
        
        for team in team_list:
        	if v1 in team or v2 in team:
            	union_list.append(team)
            else:
            	new_team_list.append(team)
        
        union_set = set()
        for team in union_list:
        	union_set = union_set.union(team)
        union_set.add(v1)
        union_set.add(v2)
        
        new_team_list.append(union_set)
        return new_team_list

  • ...
• List 부분 뒤집기

  • def overturn(circle_list, ss, ee):
        if ss == ee:
            return circle_list
        elif ss < ee:
            a1 = circle_list[:ss]
            a2 = circle_list[ss:ee+1]
            a3 = circle_list[ee+1:]
            a2.reverse()
            a1.extend(a2)
            a1.extend(a3)
            return a1
        else:
            a1 = circle_list[ss:]
            a2 = circle_list[:ee+1]
            a3 = circle_list[ee+1:ss]
            a1.extend(a2)
            a1.reverse()
            tt = len(circle_list) - ss
            a4 = a1[:tt]
            a5 = a1[tt:]
            a5.extend(a3)
            a5.extend(a4)
            return a5

  • ...

-끝-