기본적인 용어의 정의 Map부터 알아보자. 기본적으로 Map은 어떠한 데이터를 저장할 때 key와 value 쌍을 저장하는 자료구조로, 데이터를 Map 내부에서 탐색하거나 값을 참조하기 위해서는 key를 통해 접근해야 한다. 이를 조금 더 이해하기 쉽도록 생각하자면 배열에서 색인(index)을 통해 요소에 접근하는것 처럼, Map에서는 key를 통해 요소에 접근한다. 즉 기존 정수로만 제한되어 있던 색인을 정수 뿐만이 아닌 여러 타입으로 확장하였다고 생각하면 이해하기가 쉬울 것이다. Map의 특징으로는 key의 중복을 허용하지 않으며 대신 value의 중복은 허용된다. 또한 key를 통해 데이터의 접근, 탐색에 $O(1)$라는 강력한 성능을 가지는 것도 특징이다. Hash는 어떠한 데이터를 입력받은 후 ..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42578 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 접근 해시맵을 사용하는 문제이지만 기본적으론 경우의 수를 구하는 문제이다. 만약 얼굴을 동그란 안경, 검정 선글라스로 상의를 파란색 티셔츠, 하의를 청바지, 겉옷을 긴 코트로 한다면 해당 부위를 입지 않는 경우의 수까지 포함하여 곱의 경우의 수를 계산해야 한다. 그렇다면 동그란 안경 - 파란색 티셔츠 - 청바지 - 겉옷, 동그란 안경 - 파란색 티셔츠 - 없음 - 겉옷 등으로 경우의 수..

문제 https://www.acmicpc.net/problem/26008 26008번: 해시 해킹 첫째 줄에 비밀번호의 길이 $N$과 문자 종류의 개수 $M$, 정수 $A$가 주어진다. ($1 \le N, M, A \le 5\,000\,000$) 둘째 줄에 재현이가 알아낸 해시값 정수 $H$가 주어진다. ($0 \le H < M$) www.acmicpc.net 문제 접근 해당 문제는 해싱에 대해 묻고 있다. 주목해야 할 점은 해싱하는데 사용하는 해시 함수 h(P)에 대해서이다. 문제에서 제시한 해시 함수는 아래와 같다. $$ h(P) = (P_0 \ast A^0 + P_1 \ast A^1 + \cdots + P_{N-1} \ast A^{N-1}) mod M $$ 이때 $P_0$ 을 보자 $A^0$ 이 1..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/17684 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 접근 LZW 압축의 동작을 그대로 구현하는 것이다. 이때 단어가 세팅된 사전에 존재하는지를 체크하고 없다면 그 단어를 사전에 넣고, 존재한다면 해당 색인(index)를 넣음으로서 압축을 할 수 있다. 나이브하게 접근하면 사전을 순회하면서 현재 단어가 사전에 존재하는지 비교를 하며 존재한다면 인덱스를 반환하고 존재하지 않는다면 사전에 포함시키는 동작을 구현하면 된다. 하지만 이는 단어가 ..

개념탐구 Python에서 Dictionary 자료형에 대한 것을 본 적이 있을 것이다. 해당 자료형은 [key: value]의 쌍으로 묶여있으며 일반적인 배열/리스트 접근방식으로는 접근할 수 없고 해당 key를 사용해야 접근이 가능하다. 가령 다음과 같이 과일의 이름과 그 개수가 담겨있는 Dictionary가 있다고 가정해보자 my_dic = { 'apple': 1, 'banana': 2, 'grape': 3 } 이때, 'apple'은 key라고 정의하고 옆의 숫자 1은 value라고 정의한다. my_dic에서 바나나의 개수를 알고 싶다면, 다음과 같이 접근 할 수 있다. print(my_dic['banana']) # 2 보통 이러한 자료구조를 python에서는 Dictionary라고 하나, 알고리즘에서..