맵은 키(key)와 값(value)의 쌍으로 이루어진 자료구조이다. 키를 값에 매핑하는 객체이며, 중복 키는 있을 수 없다. 각 키는 최대 하나의 값에 매핑할 수 있으므로 이름이 된다. 이런 쌍을 map entries(맵 항목)이라고 부른다. 같은 맵에 두 개 이상의 키가 존재하면 안되는 반면, 값은 중복된 값이어도 상관이 없다.
이러한 맵의 특성 때문에 키를 활용하여 값을 검색할 수 있다. 자바 플랫폼에는 HashMap, TreeMap, LinedHashmap의 3가지 범용 맵 구현이 포함되어 있다.
HashMap
말 그대로 해싱된 맵이다. 키를 해싱하여 자료를 저장하고 꺼내오기 때문에 속도가 빠르다.
해싱이란?
대부분의 탐색 방법들은 탐색 키를 저장된 키 값과 반복적으로 비교하면서 원하는 항목에 접근한다. 해싱은 키 값에 직접 산술적인 연산을 적용하여 항목이 저장되어 있는 테이블의 주소를 계산하여 항목에 접근한다. 이렇게 키 값의 연산에 의해 직접 접근이 가능한 구조가 해시 테이블(hash table)이고, 이를 이용한 탐색을 해싱(hashing)이라 부른다. 해싱은 보통 사전(dictionary)과 같은 자료 구조를 구현할 때에 최상의 선택이다.
해싱의 구조※ 주의: HashMap은 쓰레드에 대해 안전하지 않은 컬렉션이다. 오직 단일 쓰레드 환경에서만 안전하게 사용할 수 있다. 이를 보완한 컬렉션이 Hashtable이다.
Map, Hashmap 사용법
Map과 Hashmap은 java.util안에 위치한다.
map을 println으로 출력하게 되면 출력값이 중괄호로 묶이게 된다.
put은 키와 값을 map에 저장하는 메소드이고, get은 입력받은 key에 대응되는 value를 반환한다. 만약 해당하는 key가 없다면 null을 넘겨준다.
import java.util.HashMap;
import java.util.Map;
public class Main {
public static void main(String[] ar) {
Map<String,Integer> map=new HashMap(); //<키 자료형, 값 자료형>
map.put("A", 50);
map.put("B", 60);
map.put("C", 70);
map.put("C", 80); //중복된 key가 들어갈때는 이전 키,값을 업데이트한다.
System.out.println(map);
System.out.println(map.get("A"));
System.out.println(map.get("B"));
System.out.println(map.get("C"));
}
}
//결과
{A=50, B=60, C=80}
100
101
103
Set
집합
중복되는 요소를 허용하지 않는다.
저장 순서를 유지하지 않는다. (단, LinkedHashSet은 예외)
자바에서의 set은 크게 HashSet, LinkedHashSet, TreeSet으로 나뉜다.
HashSet
입력 순서, 저장된 순서, 중복을 허용하지 않는다.
hash에 의해 데이터 위치를 특정시켜 해당 데이터를 빠르게 찾을 수 있게 만든 것으로, 삽입/삭제/색인이 매우 빠르다.
LinedHashSet
중복을 허용하지 않는다.
add() 메소드를 통해 요소들을 넣은 순서대로 연결한다. 즉, LinkedList의 첫번째 요소부터 차례대로 출력하면 입력했던 순서대로 출력된다는 것이고 이는 순서를 보장한다는 의미다.
TreeSet
Tree 자료구조가 데이터를 일정 순서에 의해 정렬한다. 거기에 Set의 중복값 방지가 더해진 자료구조라고 이해하면 편하다.
HashSet과 마찬가지로 입력 순서대로의 저장 순서를 보장하지 않으며 중복 데이터 또한 넣지 못한다. 그러나 데이터의 ‘가중치에 따른 순서'대로 정렬되어 보장한다.
→ n개의 원소가 별다른 규칙 없이 저장되어 있는 배열이나 리스트에서 i번째로 작거나 큰 원소를 찾는 문제를 풀기 위한 알고리즘이다.
선택 알고리즘 종류
평균적으로 선형 시간이 소요되는 선택 알고리즘 → Select algorithm
최약의 경우에도 선형 시간이 보장되는 선택 알고리즘 → LinearSelect algorithm
→ i번째로 작거나 큰 원소를 찾기 위해 적어도 모든 원소를 한 번씩은 봐야 하는데, 이 때문에 선형시간 O(n)이 필요하다. 하지만, 최악의 경우 O(n^2)이 걸리는 경우도 있다.
(cf) 선형 시간이란 n에 비례하는 시간을 말한다. Ex)O(in)
select(A, p, r, i) // 배열 A[p,...,r]에서 i번째 작은 원소를 찾는다.
{
if(p == r) return A[p]; // 원소가 하나만 존재하는 경우 -> i = 1
q <- partition(A, p, r); //
k <- q - p + 1; // 기준원소가 전체에서 k번째 작은 원소임을 의미한다.
if(i < k) then return select(A, p, q-1, i); // 찾아야 하는 i가 k보다 작으면 왼쪽 그룹에서 i번째 작은(큰) 원소를 찾아야 한다.
else if (i = k) then return A[q]; // i == k -> 기준원소 k가 바로 찾던 원소다.
else return select(A, p+1, q, i); // i > k이면 오른쪽 그룹에서 i번째 작은(큰) 원소를 찾아야 한다.
}
평균 수행 시간: T(n) = O(n)
최악의 경우 수행 시간 : T(n) = O(n^2)
예시로 이해하는 선택 알고리즘
<2번째로 작은 숫자를 찾아보자>
20
8
5
45
15
30
기준 원소를 정하자 → 나의 경우는 첫 번째 원소나 마지막 원소로 정하는 편이다! ⇒ 여기서는 20으로 정해보자!
20과 다른 원소와 크기를 비교한다 → 20 vs 5, 20 vs 8, 20 vs 45, 20 vs 15, 20 vs 30
8
5
15
20
30
45
기준 원소 20의 왼쪽 그룹은 길이가 3, 오른쪽 그룹은 길이가 2이다. 찾아야 하는 원소는 2번째로 작은 숫자이므로 기준 원소에서 왼쪽 그룹으로 한 칸 움직여 기준 원소를 15로 하여 다시 분할을 수행한다.
원쪽 그룹은 아래와 같고, 기준 원소 15와 8, 5를 비교한다. 15가 둘 보다 크기 때문에 위치 이동은 없고, 찾아야 하는 원소의 위치 2 < 기준 원소의 위치 3 이므로 다시 한 칸 왼쪽으로 이동해 5를 기준 원소로 한다.
8
5
15
2) 꼬리 물기 최적화(Tail Call Optimization)
→ 꼬리 물기 최적화란, 꼬리 물기(Tail Call), 즉, 꼬리 호출을 최적화하는 것이다.
cf) Tail Recursion도 꼬리 물기 최적화이다.
꼬리 물기(호출)란?
→ 서브루틴의 호출을 프로시저(procedure)의 마지막 행위로 수행하는 것을 말한다.
Ex) 재귀 호출(recursive call)
언제 사용할까?
재귀 호출을 사용할 때!
재귀 호출의 대표적인 예 → 피보나치 수열로 알아보자!
private static int factorial(int n){
if (n == 1){
return 1;
}
return n * factorial(n - 1);
}
재귀 호출의 장점
코드의 단순화가 가능해진다.
재귀 호출의 단점
메모리 사용이 많아질 수 있다 ⇒ 스택 오버플로우(Stack Overflow)가 발생할 수 있다.
→ 재귀 함수에 있는 매개변수, 지역변수, 반환값, 함수 종료 후 돌아가는 위치 등을 계속해서 프로세스의 스택(Stack)에 저장해야 하기 때문이다.
속도가 상대적으로 느리다.
→ 함수 호출과 복귀를 하는 과정 속에서 context swtiching 비용이 발생하기 때문이다.
→ 이런 재귀 호출의 단점을 해결하기 위해 사용하는 것이 꼬리 재귀(Tail Call Recursion) 기법이다.
⇒ 즉, 메모리의 최적화를 하기 위해 꼬리 물기 최적화를 한다.
꼬리 물기를 “어떻게” 최적화할까?
💡 “컴파일러”는 꼬리 재귀로 작성된 코드를 변경하여 반복문의 형태로 변경해줌으로써 최적화시킨다.
→ return을 할 때 함수를 호출하면 호출이 된 함수에서 호출을 한 함수로 돌아오는 반환 지점을 가지고 있음으로써 꼬리 물기를 최적화한다.
→ 호출을 한 함수가 메모리(실행 컨텍스트 - Argument, Local Variable)를 가지지 않으면 호출을 한 함수로 돌아올 필요가 없으며 함수들이 한 번씩 호출이 되고 마지막으로 호출이 된 함수는 최초 함수 호출 지점으로 값을 반환하는 것을 뜻한다.
→ 이렇게 하기 위해서는 return에서 스택에 메모리를 쌓는 연산자를 사용하면 안 된다.
💡 만약 서브루틴의 내부 연산이 필요하면 스택에 메모리를 쌓지 않는 연산자를 사용해 서브루틴의 매개인자로 넘긴다.
예시1) 피보나치 수열로 알아보는 꼬리 물기 최적화 코드
// 1번
private static int factorial(int n){
return factorialTail(n, 1);
}
private static int factorialTail(int n, int acc) {
if (n == 1) {
return acc;
}
return factorialTail(n-1, acc * n);
// 2번
const factorial = (n, result) => {
return (n <= 1 ? result : factorial(n*result));
};
→ 컴파일러에서 어떻게 이 코드를 변경할까?
int factorialMethod(int n) {
int acc = 1;
do {
if(n == 1) {
return;
}
acc *= n;
n -= 1;
} while(true);
}
컴파일러가 반복문 형태로 변경해줌으로 리턴 후 별도 작업을 처리할 필요 없이 다시 새로운 값을 계산하여 반환한다. 따라서 스택에 호출 주소를 쌓지 않아 스택 오버플로우가 발생하지 않는다.
지연 평가를 하는 삼항연산자, &&, ||를 사용한다. → 삼항연산자, &&, || 연산자는 지연 평가를 하기 때문에 스택을 잡지 않는다.
⇒ 재귀 함수를 만들 때 꼬리 물기 최적화를 할 수 있게 하자!
배열 A의 최댓값, 최솟값 구하기
1. for문 사용하기 ← 가장 대표적이면서 많이 사용하는 풀이 방식
int max = 0;
for(int i = 0; i < A.length; i++){
if(max < A[i]){
max = A[i];
}
}
int min = 0;
for(int i = 0; i < A.length; i++){
if(min > A[i]){
min = A[i];
}
}
시간복잡도 : O(n) → 최대, 최소를 각각 구할 때 시간복잡도가 O(n)인 것이다. ⇒ 최대값과 최소값을 동시에 찾을 수 없다.
2. 선택 알고리즘 이용하기(깃허브에 나와있는 3번 풀이) ⇒ O(n)의 시간복잡도로 최대 / 최소 값을 한번에 확인할 수 있다.
def optimization_find_small_and_largest_number_in_array(A):
_max = _min = A[0]
for idx in range(0, len(A), 2):
first = A[idx]
second = A[idx + 1]
if first < second:
if first < _min: _min = first
if second > _max: _max = second
else:
if second < _min: _min = second
if first > _max: _max = first
return _max, _min
원소를 하나씩 가지고 비교하는 것이 아니라, 2개씩 묶어 그 2개끼리 비교한 후, 더 큰 것이 max 값이 될 가능성이 존재하고 작은 것이 min이 될 가능성이 존재하기에 더 큰 것을 max와 작은 것을 min과 비교해 최댓값과 최솟값을 구한다.
이렇게 2개씩 묶어 확인하는 경우에는 원소 개수가 짝수인 경우에는 문제가 없지만, 홀수인 경우에는 index out of range exception이 발생한다. 따라서, 배열의 총 원소 개수가 홀수인 경우 패딩 값을 하나 추가하거나 맨 처음이나 마지막 원소를 _max, _min에 대입하고 range(1, len(A), 2)로 해주는 것이 중요하다.
3. 이미 해당 언어에 구현되어 있는 정렬 기능 사용 ⇒ 길이가 n이라면 max = A[n-1], min = A[0]
자바 : Collections.sort(ArrayList<> 이름) Arrays.sort(리스트명) 등
파이썬 : 리스트명.sort(), sorted(리스트명)
주의할 점!!
파이썬의 sorted() 함수는 .sort()와 다르게 정렬된 리스트를 “반환”해주는 함수로 반환 값이 존재하므로, 변수에 반환 값을 저장해야 한다.
언어마다 다르겠지만, 대부분 직접 for 문을 돌려 작성하는 것보다 시간이 오래 걸린다. → O(nlogn) = 정렬의 최소 시간복잡도
