ALGORITHM (31) 썸네일형 리스트형 [알고리즘] Queue Queue Queue는 stack과 같이 선형 자료구조 중 하나이며 대표적인 자료구조이다. 선형구조는 '자료가 일렬로 존재하는 구조'를 뜻한다. 예를들면 stack, queue, linked list 등이 있다. Queue에서 꼭 알아야할 개념은 FIFO이다. FIFIO는 First in First out이며 '가장 먼저 들어간 값이 가장 먼저 나간다'라는 의미이다. 즉 우리가 일반적으로 비행기 탑승게이트에서 줄을 서게 되면 먼서 줄선 사람이 먼저 비행기에 탑승할 수 있는 것과 동일하다. 그림을 보면 알 수 있듯이 '앞'에 인는 정보가 추출이 되고 삽입되는 정보는 '뒤'에 쌓이는 것을 알 수 있다. 프로그래밍에서 사용될때는 보통 프린터 버퍼나 영상 버퍼와 같은 '버퍼'를 구현할때도 사용하고, 시뮬레이션을.. [알고리즘] Stack Stack Stack은 선형 자료구조이며 가장 기초적이고 중요한 개념이다. 선형 자료구조란 '자료가 일렬로 존재하는 구조'를 의미한다. 예를들면 stack, queue, linked list 등 이다. stack에서 꼭 알아야 할 것은 바로 LIFO이다. LIFO는 Last in First out이며 '가장 마지막에 들어온 값이 가장 먼저 나간다는 뜻'을 가진다. 즉 데이터가 삽입되는 구멍과 삭제되는 구멍이 동일하다고 이해하면 되겠다. 아래 그림을 보면 좀더 쉽게 이해할 수 있다. 간단하게 예를 들면, 상자 안에 책을 눕혀서 국어책-수학책-영어책 순으로 넣는다면 뺄때는 영어책-수학책-국어책 순으로 빼게 될 것이다. 상자를 부시지 않는 이상 국어책을 빼기 전까지는 수학책 영어책을 빼낼 수 없다 (어떻게서든.. [문제풀이] Hash - 카드 1차 시도 n = int(input()) cards = {} for idx in range(n): card = int(input()) if card in cards: cards[card] += 1 else: cards[card] = 0 many = max(list(cards.values())) pick = sorted([key for key, value in cards.items() if value == many]) print(pick[0]) 어렵지 않게 풀만 했음. Hash로 풀수 있는 문제 스타일이 좀 눈에 읽는 중이다. [문제풀이] Hash - 듣보잡 1차 시도 n, m = map(int, input().split()) d_names = {} for idx in range(n+m): name = input() if name in d_names: d_names[name] += 1 else: d_names[name] = 1 dbj = [key for key, value in d_names.items() if value == 2] dbj.sort() print(len(dbj)) for name in dbj: print(name) 좀 쉬운 문제를 선택했나보다. 어렵지 않았다. [문제풀이] Hash - 전화번호 목록 1차 시도 def solution(phone_book): phone_book.sort() # 어차피 길이가 같으면 절대 있을수 없지 phone_dict = {} for phone in phone_book: phone_dict[len(phone)] = phone if len(set(list(phone_dict.keys()))) == 1: return True for i in range(len(phone_book)): for j in range(1, len(phone_book)): if phone_book[i+j].startswith(phone_book[i]) or phone_book[i].startswith(phone_book[i+j]): return False del phone_book[i] return.. [문제풀이] Hash - 완주하지 못한 선수 1차 시도 def solution(participant, completion): part_dic = {person: 0 for person in participant} for person in completion: part_dic[person] = 1 for key, value in part_dic.items(): if value == 0: return key 첫번째 시도에서는 동명이인을 해결하지 못하였다. dictionary는 동일한 key를 가지는 형태를 허용하지 않기 때문이다. 어떻게 해결할까고민을 하다가 value에 사람의 인원수를 넣으면 어떨까 싶었다. 그래서 "사람:인원" 의 key-value형태를 구성하고, 반복문으로 completion 리스트를 돌면서 인원수를 감소시키고 인원수가 음수가 되.. [알고리즘] 해시 테이블 (Hash Table) Hash Table Hash Table는 연관배열 구조를 이용하는 자료구조 중 하나로써 단순하게 생각하면 'key-value'의 구조라고 할 수 있다. 연관배열 자료구조(associative array)란 key와 value가 1:1로 이루어진 구조이다. Hash는 검색과 저장이 빠른 자료구조이다. 파이썬에서는 Dictionary로 구현이되어있고, 자바에서는 java.util 하위에 HashMap, Map으로 정의되어있다. 해시는 값 자체를 Index로 사용하기 때문에 시간복잡도 O(1)로 매우 빠르다. hash table을 사용하여 해결할 수 있는 문제유형은 한 묶음의 데이터에 '중복이 없거나', 데이터가 몇번 발견되는지에 대한 '빈도를 세거나', '순서가 필요하지 않거나', 'key-value 쌍으로.. 이전 1 2 3 4 다음
