해시 테이블 충돌 해결법

Hash table 충돌예방법

https://www.programmingstory.com/2024/05/collision-load-factor.html

지난 포스팅에서 해시 테이블에서의 충돌과 적재율의 개념에 대해 다루었다.

오늘은 지난 포스팅에서 예고한 대로, 충돌을 예방할 수 있는 방법에 대해서 설명해보도록 하겠다.

크게 chaining과 open addressing 방법이 있다.

---

1. chaining

chaining 방법은 linked list를 사용해서 이미 다른 원소가 그 칸을 차지하고 있더라도 linked list로 이어 주는 것이다. 

지난 포스팅에 썼던 예시를 똑같이 사용해보도록 하겠다. 

지난 포스팅처럼 x mod 5라는 해시 함수가 존재한다고 하고 9라는 숫자가 들어갔다고 가정해보자.

hash chaining 예시

그렇다면 이제는 table 자체에 9가 들어가는 것이 아니라 위의 그림처럼 linked list로 9라는 숫자가 들어가게 되는 것이다. 여기에 만약 14라는 숫자가 또 들어온다면 어떻게 될까? 14도 14 mod 5에 따르면 4 자리에 들어가야 하기 때문에 4 자리로 가준다. 하지만 이미 9라는 원소가 들어있다. chaining을 사용하지 않았다면 이전에는 충돌이 일어났지만 이제 우리는 chaining을 사용하기 때문에 linked list로 단순히 연결해주면 된다.

 

chaining 예시

위 그림처럼 말이다. chaining은 적재율 (load factor)가 1이 넘더라도 사용할 수 있다는 장점이 있지만 추가적으로 linked list가 필요하다는 단점도 있다.

---

2. open addressing

 

chaining은 하나의 추가적인 linked list를 잡아먹는다는 단점이 있다. 이것을 보완하기 위해 나온 open addressing은 추가 공간을 허용하지 않고 충돌이 일어나면 다른 공간으로 재배치시키는 과정이라고 볼 수 있다. 

 

즉 open addressing 방법은 충돌이 일어났을 때 추가적인 hash 함수를 사용하여 원소를 다른 곳에다가 재배치시켜준다. 

여기서 해시 함수를 정하는 방법에 따라 open addressing은 추가적으로 3가지 type으로 나뉘게 된다.

 

i ) linear probing

ii) quadratic probing

iii) double hashing

 

hashing의 경우 한번 open addressing을 하더라도 또 충돌이 있을 수 있기 때문에 일반화하여 i번 hashing을 수행한다고 할 수 있다. i번째 hash 함수를 우리는 hi(x)라고 정의하겠다. (여기서 i는 작은 첨자라고 생각해주면 된다)

 

i) linear probing

첫번째 linear probing 부터 알아보자

 

linear probing의 경우 hi(x)는 (h(x) + i) mod m 으로 정의된다. 즉 충돌이 일어난 h(x)에서 i만큼 떨어진 자리에다가 값을 저장하겠다는 것이다. 하지만 i만큼 일차 함수 보폭으로 이동하는 것이기 때문에 특정 영역에 몰릴 경우 굉장히 성능이 저하된다는 단점이 있다. 이것을 "primary clustering"이라고 부르기도 한다.

---

ii) quadratic probing

이러한 단점을 보완하기 위해 나온 것이 quadratic probing이다. 위 linear probing에서 primary clustering이라는 현상이 나타난 이유가 일차 함수 보폭으로 이동하기 때문인 것이어서 quadratic probing에서는 이차함수 거리로 점프하면서 보는 것이다. 

 

즉 hi(x)는

이라고 정의할 수 있다. 이렇게 정의한다면 위 primary clustering의 문제점은 해결할 수 있으나, 원소 몇개가 초기에 같은 값을 가지게 되었다면 계속 같은 과정을 거쳐야 한다는 점에서 비효율적인 모습도 다소 있다. 이러한 것을 secondary clustering이라고 부른다. 즉, quadratic probing은 primary clustering의 문제점은 해결할 수 있으나, secondary clustering의 문제점을 가지고 있는 것을 알 수 있다.

 

---

iii) double hashing

세 번째 방법은 double hashing이라는 방법이다. double hashing 방법은 secondary clustering을 해결하기 위해 나온 방법으로, 매번 같은 점프를 하는 것을 어느정도 방지할 수 있다.

이 경우에 hi(x)는

(h(x) + if(x)) mod m이라고 정의할 수 있다. 

여기서 f(x)는 h(x)와는 또 다른 해시 함수로, double hashing의 의미는 서로 다른 hashing 함수 두개를 사용하였다는 것이다. 

double hashing의 경우에 f(x)의 값은 h(x)와 항상 서로소가 되어야 한다. 

즉 예를 들어 h(x)의 함수가 x mod 17이라면, f(x)의 함수는 x mod 11로 함으로써 m과 항상 서로소로 만들 수 있다. 

해시 테이블에서 충돌(collision)/ 적재율 (load factor) 개념

1. Hash Table 충돌

hash table에서는 충돌을 줄이는 것이 알고리즘의 성능을 높이는 데 핵심 이슈이다. 

여기서 충돌은 한 원소를 해싱해서 저장하려고 하는 상황에서 이미 다른 원소가 그 자리를 차지한 상황을 뜻한다.

---

2. Hash Table 충돌 원인

예를 들어, 

hash table 예시

위와 같은 그림의 hash table이 있다고 하자. 여기서 hash 함수는 간단히 h(x)= xmod5라고 해보겠다. 즉, x를 5로 나눈 나머지라는 것이다. 이럴 때 처음으로 9라는 숫자가 들어간다면,

 

9는 hash 함수에 따라서 9 mod 5 즉, 4의 위치에 저장이 되는 것이다. 

 

hash 함수에 9가 들어간 모습

위 그림처럼 말이다. 여기까지는 문제가 없다. 하지만 만약에 14가 추가로 해시 테이블에 들어가고 싶다면 어떻게 되는가?

그러면 또한 hash 함수에 의해 14 mod 5를 계산한 4 자리에 14를 넣고 싶어한다. 하지만 이미 4 자리에는 9가 있기 때문에 충돌이 일어나는 것이다. 

---

3. 충돌, load factor 정의

이렇게 한 원소를 해싱이란 방법을 통해 저장하려고 하는데 다른 원소가 그 전에 해당 자리를 차지한 상황을 충돌 (collision)이라고 한다. 간단히 말해서 해시 테이블의 한 주소를 두개 이상의 원소가 다투는 상황과 유사하다고 보면 된다. 

 

또한 해시 테이블에서 자주 등장하는 용어로는 load factor (적재율) 이라는 개념이 있다. 위에서 볼 수 있듯이 해시 테이블의 성능을 높이기 위해서는 충돌을 줄여야 하고 그렇기 위해서는 해시 테이블에 원소가 차 있는 비율이 성능에 중요하게 작용한다. 여기서 해시 테이블에 원소가 차 있는 비율을 우리는 load factor (적재율)이라고 하는 것이다.

 

해시 테이블의 전체 크기가 m이라고 가정하고, 테이블에 저장되어 있는 원소의 개수가 n개라고 가정하면 적재율은 n/m이라고 표현할 수 있다. 위 그림에서는 전체 크기 5 중에서 1개만 차 있으므로 적재율은 1/5이 되는 것이다. 주로 load factor는 α로 표현하는 경우가 많다. 

---

4. 충돌을 막기 위한 방법

또한 위에서도 언급했듯이 충돌이 일어나면 해시 테이블의 성능은 굉장히 안좋아지기 때문에 이를 해결할 수 있는 방법이 필요하다. 

 

충돌을 막기 위한 방법으로 chaining이라는 방법과 open addressing이라는 방법이 존재한다.

 

이 두 방법은 다음 포스팅에서 소개하도록 하겠다. 

[백준] 2251번 물통문제 BFS로 풀어보기

1. 문제

1) 링크

www.acmicpc.net/problem/2251

더 자세한 문제의 제한은 위의 링크에 들어가서 확인해보자

 

---

2. 풀이

이 물통 문제는 처음에 어떻게 풀까 고민을 하다가 위 풀이를 보고 BFS로 풀면 된다는 것을 알게 되었다.

 

물통 초기상태

물통의 총합이 변하지 않는다는 것이 문제에서 가장 중요한 열쇠이다. 그러면 물통 자체는 3개가 있지만 두개만 우리는 미지수로 두고 나머지 하나는 총합에서 빼는 식으로 구상하면 된다. 그리고 심지어 전체 합은 문제 시작 때 주어져있기 때문에 (2번 물통 양이 처음에는 sum이다) 매우 편하게 구할 수 있다.

 

그런 다음에 처음 물통 0과 물통 1은 0,0으로 시작하니 이들을 queue에 넣어주고 여기서부터 물통에 물을 옮겨담을 수 있는 모든 조합을 시도해보는 것이다. 

 

순열로 해도 되지만 이렇게 6개밖에 되지 않는 것은 그냥 배열로 from, to 해서 여섯가지를 모두 시도해보는 것이 간단하다. 

그리고 이 문제에서 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다고 했으므로 우선 다른 물통에 물을 다 부어놓고 이것이 용량을 초과하게 되면 다시 원래 물통에 넘친 만큼 부어준다는 식으로 구현을 하면 될 것 같다. 

그러면 비록 넘칠 때까지 부었어도 넘친 부분을 원상복구시켜주면서 물통이 가득찰 때까지만 부은 것이 되기 때문이다. 

 

그리고 제한이 200밖에 되지 않기 때문에 200까지 배열의 용량을 넉넉히 만들어 구해주면 된다.

 

Pair라는 class를 만들어도 되지만 나는 그것이 번거로워서 그냥 0번째 물통 값 넣어주고 1번째 물통 값 넣어주고 이런 식으로 구현했다. 전혀 문제 없는 방식이고 대신 queue에서 뺄 때도 두개를 다 빼주어야 한다.

 

3. 코드 

import java.util.*;

public class Main{
    final static int to[]={0,0,1,1,2,2};
    final static int from[]={1,2,0,2,0,1};
    public static void main(String[] arg){
        Scanner sc=new Scanner(System.in);
        int water[]=new int [3];
        for(int i=0; i<3; i++){
            water[i]=sc.nextInt();
        }
        int sum=water[2];
        boolean check[][]=new boolean[201][201];
        boolean ans[]=new boolean[201];
        Queue <Integer> q= new LinkedList<>();
        q.add(0);
        q.add(0);
        check[0][0]=true;
        ans[water[2]]=true;
        while(!q.isEmpty()){
            int cur[]=new int [3];
            cur[0]=q.remove();
            cur[1]=q.remove();
            cur[2]=sum-cur[0]-cur[1];
            for(int k=0; k<6; k++){
                int next[]={cur[0], cur[1], cur[2]};
                next[to[k]]+=next[from[k]];
                next[from[k]]=0;
                if (next[to[k]]>=water[to[k]]){
                    next[from[k]]=next[to[k]]-water[to[k]];
                    next[to[k]]=water[to[k]];
                }
                if (!check[next[0]][next[1]]){
                    check[next[0]][next[1]]=true;
                    q.add(next[0]);
                    q.add(next[1]);
                    if (next[0]==0){
                        ans[next[2]]=true;
                    }
                }
            }
        }
        for(int i=0; i<=water[2]; i++){
            if (ans[i]){
                  System.out.print(i + " ");
            }
        }
        System.out.println();
    }
}

여기서 check라는 배열은 0번째 물통 값, 1번째 물통 값의 조합이 예전에 나온 조합임을 확인하는 boolean 배열이고 ans 배열은 문제의 조건을 만족시키는지 확인하는 배열이다. 

 

이런식으로 구하면 문제에서 요구하는 조건은 ans 배열을 0부터 2번 물통 최대 값(sum)까지 따라가면서 true인 값을 적어주면 된다.

네트워크/ 통신 기본 구성요소 및 용어 10개 총정리

네트워크/ 통신 기본 구성요소 및 용어 10개 총정리

1. host = end system

실제 사용자가 가지고 있는 노트북, 휴대폰, 신호등, 서버 등 사용자 device. 이 device에서 network service를 요청하는 어플(network apps)이 돌아가고 있는 것이다. 하지만 이렇게 device만 있다고 해서 아직 상호연결된 것은 아니다. 

 

2. communication link

위 device 사이에 데이터를 주거니 받거니 하는 것을 communication link라고 한다. 통신이 가능하게 device를 연결시켜주는 링크라고 할 수 있다. optical fiber, copper와 같이 유선 링크가 될 수도 있고 microwave, satelite처럼 무선 링크를 사용할 수도 있다. 

 

3. mobile network

이동성을 지원하는 네트워크. 이동성을 지원하기 때문에 무선을 사용한다. (wireless network) 핸드폰 이런 것은 mobile network라고 할 수 있다. 예를 들어 빠르게 이동하는 버스 안에서도 네트워크가 가능해야 하므로 다양한 이동속도를 지원해야 한다. 노트북을 가지고 돌아다닐수도 있기 때문에 이를 mobile network의 예시라고 볼 수 있다.

 

4. home network

말 그대로 집 network라고 할 수 있다. 무선 LAN과 유선을 모두 포함한다. 무선 access point를 통해 연결이 되고 무선 access point가 다른 스위치를 통해 밖으로 나갈 수도 있다. 집에서 나온 traffic을 또 다른 곳으로 전달하기 위해서 기관들, ISP (Internet Service Provider) 가 있는 것이다. 

 

5. ISP (Internet Service Provider) 

위에서 말한 것처럼 집이나 다른 기관의 network를 상호연결시켜주는 기관이라고 할 수 있다. 이렇게 하면 안 와닿겠지만 SK broadband, KT 가 ISP의 예시라고 하면 다들 이해가 갈 것이다. 인터넷 서비스들의 네트워크를 상호연결시켜주는 기관이라고 할 수 있다. ISP는 또 regional ISP와 global ISP로 나뉘는데 한 지역만 서비스하는 것을 regional ISP라고 하고 이 ISP를 다 연결해 global 단위에서 서비스하는 것을 global ISP라고 한다. 

 

6. Institutional network

학교, 병원, 공항, 공장은 자체적으로 네트워크를 꾸미고 있다. 이는 home network와는 다른 것으로 기관에서의 자체적 네트워크라고 할 수 있다. 유선 네트워크, 무선 네트워크가 다 포함되고 Institutional network는 자체적으로 통신할 수도 있지만 외부로 나가서 통신할 수도 있기 때문에 ISP와 또 연결된다. 

 

7. transmission rate

초당 몇 비트를 주고받을 수 있느냐를 transmission rate, 또는 link의 capacity라고 한다. 

 

8. packet switch

네트워크의 데이터 단위를 packet이라고 부르는데 이를 switch 해준다고 해서 packet switch라고 부른다. packet은 data라고 생각하면 편하다. device 사이에 상호연결을 시켜서 이 traffic을 연결시켜주는 것이다. 이 연결시켜주는 것을 router라고 하기도 하고 switch라고 하기도 한다. router라고 할때는 데이터의 목적지를 보고 어느쪽 link로 내보내야 하는지를 결정하는 것이기 때문에 목적지의 길을 찾는다는 뜻으로 routing한다고 한다. switch라고 하는 이유는 들어오는 데이터를 switching하기도 하기 때문이다. 각 데이터를 어디로 목적지로 보낼지를 결정해야 하기 때문에 buffer에 담아놨다가 결정이 끝나면 보내주는 것이다. 결정된 링크 쪽으로 forward한다고 해서 store and forward라고 한다. Packet을 forward한다고 한다.

 

9. Internet 인터넷 (Interconnected network)

한마디로 네트워크의 네트워크이다. 개별적으로 network끼리만 있으면 이 안에서만 통신을 하는 것이다. 이렇게 하면 용도가 한정된다. 하지만 전세계 어디서든 데이터를 주고받을 수 있어야 한다. 각종 파트를 유저 장비들이 있는 곳이라고 하고 유저가 access하는 파트라고 해서 access network라고 한다. 이 access network를 상호연결하는 더큰 네트워크가 있고… 상호연결시키는 네트워크는 네트워크의 네트워크라고 한다. 즉 인터넷은 네트워크의 네트워크라고 할 수 있다. 

 

10. Protocol

통신은 무조건 룰에 따라야 한다. 통신에 있어서 룰을 프로토콜이라고 할 수 있는데 프로토콜에 대해서는 다음 포스팅에서 더 자세하게 다루어보도록 하겠다. 

[백준] 16638번 괄호 추가하기 2 비트마스크로 풀어보기

1. 문제

1) 링크

www.acmicpc.net/problem/16638

2) 문제

길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 곱하기의 연산자 우선순위가 더하기와 빼기보다 높기 때문에, 곱하기를 먼저 계산 해야 한다. 수식을 계산할 때는 왼쪽에서부터 순서대로 계산해야 한다. 예를 들어, 3+8×7-9×2의 결과는 41이다.

수식에 괄호를 추가하면, 괄호 안에 들어있는 식은 먼저 계산해야 한다. 단, 괄호 안에는 연산자가 하나만 들어 있어야 한다. 예를 들어, 3+8×7-9×2에 괄호를 (3+8)×7-(9×2)와 같이 추가했으면, 식의 결과는 59가 된다. 하지만, 중첩된 괄호는 사용할 수 없다. 즉, 3+((8×7)-9)×2, 3+((8×7)-(9×2))은 모두 괄호 안에 괄호가 있기 때문에, 올바른 식이 아니다.

수식이 주어졌을 때, 괄호를 적절히 추가해 만들 수 있는 식의 결과의 최댓값을 구하는 프로그램을 작성하시오. 추가하는 괄호 개수의 제한은 없으며, 추가하지 않아도 된다.

3) 입력

첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 번갈아가면서 나온다. 연산자는 +, -, * 중 하나이다. 여기서 *는 곱하기 연산을 나타내는 × 연산이다. 항상 올바른 수식만 주어지기 때문에, N은 홀수이다.

4) 출력

첫째 줄에 괄호를 적절히 추가해서 얻을 수 있는 결과의 최댓값을 출력한다. 정답은 231보다 작고, -231보다 크다.

---

2. 풀이

더 자세한 입출력 예시는 위 백준 링크에서 확인할 수 있다. 

이 문제는 먼저 Class를 하나 더 만들어주는 것이 편하다. class Calc를 하나 만들어주고 instance로 num과 op를 가지고 있도록 만들어준다. 여기서 op는 operator의 약자로 숫자면 0, 더하기면 1, 빼기면 2, 곱하기면 3을 가지게 만들어준다. 

 

즉 아래와 같은 형태인 것이다.

class Calc{
    int num, op;
    Calc(int num, int op) {
        this.num = num;
        this.op = op;
    }
}

그런 다음에 비트마스크를 활용하여 괄호가 올 수 있는 모든 경우를 체크할 것인데, 이 문제는 괄호 안에 하나의 연산자밖에 존재하지 않고 중첩이 불가능하므로 오히려 쉬운 문제이다. 연산자의 개수는 (n-1)/2개이므로 연산자의 개수를 기준으로 비트마스크를 해주면 된다. 즉 for문의 형태가 아래와 같은 식인 것이다.

int m = (n-1)/2; //연산자의 개수
for(int i=0; i<(1<<m); i++){
            boolean possible = true;
            for (int j=0; j<m-1; j++) {
                if ((i&(1<<j)) > 0 && (i&(1<<(j+1))) > 0) {
                    possible = false; //중첩 괄호 확인
                }
            }
            if (!possible) continue;
            
            }

이런식으로 for문이 돌면 중첩괄호가 아닌 모든 괄호의 경우를 체크할 수 있고 이제는 괄호가 있는 경우를 먼저 계산해준다. 이 문제는 순서가 괄호가 있는 수 먼저 계산 -> 곱하기 먼저 계산 -> 나머지 계산 이런 식으로 진행되어야 한다. 

 

괄호를 먼저 계산하면, 원래 있는 수 배열이 훼손될 수 있기 때문에 tmp라는 새로운 배열을 하나 더 만들어주고 괄호를 계산해준다. 아래 코드는 괄호를 계산하는 부분의 코드이다.

Calc[] tmp=new Calc[n]; //tmp 배열에 옮기기
            for (int j=0; j<n; j++) {
                tmp[j] = new Calc(a[j].num, a[j].op);
            }
            for(int j=0; j<m; j++){
                if ((i&(1<<j))>0){ //괄호가 있으면 
                    int k=2*j+1; //실제 괄호의 위치
                     if (tmp[k].op == 1) { //더하기
                         tmp[k-1].num += tmp[k+1].num;
                        tmp[k].op = -1;
                        tmp[k+1].num = 0;
                    } else if (tmp[k].op == 2) { //빼기
                        tmp[k-1].num -= tmp[k+1].num;
                        tmp[k].op = -1;
                        tmp[k+1].num = 0;
                    } else if (tmp[k].op == 3) { //곱하기
                        tmp[k-1].num *= tmp[k+1].num;
                        tmp[k].op = -1;
                        tmp[k+1].num = 0;
                    }
                }
            }

다음에 *, +, -을 더 계산해야 하기 때문에 괄호로 이미 계산한 연산자의 경우 op의 값으로 -1을 가지게 업데이트 시켜주어 다음번 계산 시에 고려하지 않게 한다. 

 

이렇게 되었다면 괄호 부분의 숫자가 다 계산이 된 것이다. 이제 곱하기 부분을 먼저 계산해주고, 그 다음에는 순차적으로 하나씩 계산해주어서 최댓값을 찾아주면 된다. 

 

---

3. 코드

이 모든 것을 종합한 전체 Java code는 아래와 같다.

import java.util.*;
class Calc{
    int num, op;
    Calc(int num, int op) {
        this.num = num;
        this.op = op;
    }
}
public class Main{
    public static void main(String[] args){
          Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String s = sc.next();
        Calc[] a = new Calc[n];
         for (int i=0; i<n; i++) {
            if (i%2 == 0) {
                a[i] = new Calc(s.charAt(i)-'0', 0);
            } else {
                int op = 1; //+일 경우
                if (s.charAt(i) == '-') {
                    op = 2;
                } else if (s.charAt(i) == '*') {
                    op = 3;
                }
                a[i] = new Calc(0, op);
            }
        }
        int m = (n-1)/2; //연산자의 개수
        int ans = -2147483648; //가장 최소값
        for(int i=0; i<(1<<m); i++){
            boolean possible = true;
            for (int j=0; j<m-1; j++) {
                if ((i&(1<<j)) > 0 && (i&(1<<(j+1))) > 0) {
                    possible = false; //중첩 괄호 확인
                }
            }
            if (!possible) continue;
            Calc[] tmp=new Calc[n]; //tmp 배열에 옮기기
            for (int j=0; j<n; j++) {
                tmp[j] = new Calc(a[j].num, a[j].op);
            }
            for(int j=0; j<m; j++){
                if ((i&(1<<j))>0){ //괄호가 있으면 
                    int k=2*j+1; //실제 괄호의 위치
                     if (tmp[k].op == 1) { //더하기
                         tmp[k-1].num += tmp[k+1].num;
                        tmp[k].op = -1;
                        tmp[k+1].num = 0;
                    } else if (tmp[k].op == 2) { //빼기
                        tmp[k-1].num -= tmp[k+1].num;
                        tmp[k].op = -1;
                        tmp[k+1].num = 0;
                    } else if (tmp[k].op == 3) { //곱하기
                        tmp[k-1].num *= tmp[k+1].num;
                        tmp[k].op = -1;
                        tmp[k+1].num = 0;
                    }
                }
            }
            //괄호 계산 완료
            ArrayList<Calc> c=new ArrayList<>();
            for(int j=0; j<n; j++){
                if (j%2==0){ //숫자일 경우
                    c.add(tmp[j]);
                }else if (tmp[j].op==-1){
                 j++; //이미 괄호로 처리한 것
                }
                    else{
                    //우선 곱하기만 먼저 계산
                    if (tmp[j].op==3){
                        int num=c.get(c.size()-1).num* tmp[j+1].num;
                        c.remove(c.size()-1);
                        c.add(new Calc(num, 0));
                        j += 1;
                    }
                        else{
                            c.add(tmp[j]);
                        }
                }
            }
            Calc b[] = c.toArray(new Calc[c.size()]);
            int m2 = (b.length-1)/2;
            int val = b[0].num;
            for (int j=0; j<m2; j++) {
                int k = 2*j+1;
                if (b[k].op == 1) {
                    val += b[k+1].num;
                } else if (b[k].op == 2) {
                    val -= b[k+1].num;
                } else if (b[k].op == 3) {
                    val *= b[k+1].num;
                }
            }
            if (ans < val) {
                ans = val;
            }
        }
          System.out.println(ans);
    }
}

조금 긴 코드이지만 하나씩 이해해보면 어려움이 없을 것이다. 

[Linux/Ubuntu] 파일 오픈 시 Couldn't get a file descriptor referring to the console 에러 해결

1. Couldn't get a file descriptor referring to the console 에러 

html 파일을 ubuntu에서 실행시키기 위해 

open index.html

이라고 하면 

couldn't get a file descriptor referring to the console 이라는 에러가 뜰 때가 있다.

2. xdg-open 명령어로 해결하기

 

이를 해결하기 위해서는 

open 대신 xdg-open 명령어를 사용하면 된다.

xdg-open 명령어는 우분투에서 파일과 연관된 프로그램을 실행시켜주는 명령어이다. 따라서 html 파일 뿐 아니라 pdf, mp3, mkv와 같은 다양한 확장자의 프로그램을 실행시켜준다.

xdg-open index.html

html 파일을 xdg-open으로 실행하면, ubuntu에서 html 화면이 위와 같이 뜬다. 

실제 html과 마찬가지로 inspect 기능도 되고, console에 찍히는 것도 확인할 수 있어 편리하다.

객체 지향 설계 원칙 (SOLID) 한방에 정리! 개발자라면 필수로 알아야 할 개념!

객체 지향 설계 원칙 (SOLID)란?

기술면접의 단골질문이자 시험에도 자주 나오는 SOLID 객체 지향 설계 원칙에 대해 알아보도록 하겠다. SOLID에 대해서는 개념적으로 숙지하고 있는 것도 좋지만 객체 지향 프로그래밍을 직접 할 때도 이를 참고하면 코드의 퀄리티를 높일 수 있기 때문에 꼭 알아두는 것을 추천한다. 

 

SOLID 원칙은 객체 지향 설계 원칙이라고도 불리며 객체 지향 프로그래밍 설계 시 필요한 다섯 가지의 원칙 (Single Responsibility Principle, Open Close Principle, Liskov Substitution Principle, Interface Segregation Principle, Dependency Inversion Principle)의 앞 글자를 따 붙여진 이름이다. 다섯 개 모두 다 중요한 의미를 가지고 있기 때문에 각각에 대해 자세히 알아보자.

---

1. Single Responsibility Principle 단일 책임의 원칙

비교적 간단한 원칙이다. 말 그대로 하나의 클래스는 하나의 책임만을 수행하게 하자는 뜻이다.

 

객체 지향이 절차 지향과 다른 점은 class를 가지고 객체를 생성할 수 있다는 뜻인데, 가끔 객체 지향 언어로 코드를 짜는 사람 중에서는 이러한 객체 지향의 장점을 적극 활용하지 않고 하나의 클래스에 모든 기능을 넣는 사람이 있다. 물론 메소드를 구분하여 기능을 분류할 수 있지만 엄연히 다른 일을 수행하는 객체의 경우 class를 구분하는 것이 더 맞는 방식이다. 만약 class를 책임 별로 구분하지 않는다면 하나의 class가 수행하는 일이 거대해져 객체 지향 프로그래밍의 의미를 잃게 된다.

 

따라서 단일 책임의 원칙 (Single Responsiblity Principle) 에서는 클래스가 제공하는 모든 서비스는 하나의 책임을 수행하는 데 집중되어 있어야 한다고 말하고 있다. 1번 원칙인 만큼 단일 책임의 원칙은 나머지 2~5번 원칙의 기초가 되는 원칙이다. 

---

2. Open Close Principle 개방 폐쇄 원칙

컴포넌트, 클래스, 모듈, 함수와 같은 소프트웨어 구성요소는 확장에는 열려있고, 변경에는 닫혀있어야 한다는 원칙이다.

 

Java 언어를 배운 사람들은 쉽게 이해할 텐데, 상속을 받아서 하위 클래스에서 overriding 등을 하는 것은 가능하지만, 외부 class에서 접근해서 특정 field를 바꾸는 것을 제한하기 위해서 접근 제한자(private, protected 등)를 사용한다. 즉 해당 class뿐 아니라 이외 소프트웨어의 구성요소를 확장하여 사용할 때는 open 되어 있는 반면, 해당 구성요소를 외부에서 임의로 변경하려는 시도는 제한하여 그 경우에는 closed 되어 있어야 한다는 원칙이다.

 

개방 폐쇄 원칙은 협업 개발 시 매우 중요하게 생각해보아야 할 원리로, 내가 개발한 구성요소가 다른 사람에게 적절한 때 개방되고 폐쇄되는지에 대해 신중히 고민해보아야 한다.

 

---

3. Liskov Substitution Principle 리스코프 치환의 원칙

상속받은 하위 클래스는 어디서나 상위 클래스로 교체할 수 있어야 한다는 원칙이다.

 

리스코프 치환의 원칙은 예시로 이해하는 것이 가장 빠른 것 같다. 다음은 리스코프 치환의 원칙에 위배되는 예시이다. 만약 '도형'이라는 상위 class가 있다고 가정해보자. 그리고 '도형'이라는 class에 '꼭짓점의 개수는 ~개이다'라는 것을 나타내주는 method가 있다고 가정해보자. 그리고 '도형'이라는 상위 class를 상속받아 '사각형'이라는 하위클래스와 '원'이라는 하위클래스를 만들어주었다. 사각형이라는 하위 클래스는 꼭짓점을 4개 가지고 있으니 상위클래스인 도형으로 교체가 가능하다. 하지만 '원'이라는 하위클래스는 상위클래스인 도형이 가지고 있는 메서드를 충족시킬 수 없으므로 리스코프 치환의 원칙에 위배된다. 리스코프 치환의 원칙에 위배되지 않게끔 클래스를 설계하려면 '꼭짓점이 있는 도형'과 '꼭짓점이 없는 도형'의 상위클래스를 설계하고 꼭짓점이 있는 도형을 상속받아 삼각형, 사각형 등의 하위클래스를 만들고, 꼭짓점이 없는 도형을 상속받아 타원, 원 등의 하위클래스를 만들어야 할 것이다. 

---

4. Interface Segregation Principle 인터페이스 분리의 원칙

class와 달리 인터페이스는 다중 구현이 가능하다. Java interface를 생각해보면 implements라는 keyword 이후에 여러 interface가 오는 것을 종종 본 적이 있을 것이다. 물론 여러 interface를 구현해도 되지만, 인터페이스 분리의 원칙에서는 한 클래스는 자신이 사용하지 않는 인터페이스는 구현하지 말아야 한다고 말하고 있다. 즉, 클라이언트가 사용하지 않는 인터페이스 때문에 영향을 받아서는 안 된다는 원칙이다.

 

가끔 만들어둔 모든 인터페이스를 모두 구현하여 필요한 것만 사용하는 경우가 있는데, 물론 편리하겠지만 사용하는 인터페이스만 구현하도록 노력해야 할 것이다.

---

5. Dependency Inversion Principle 의존성 역전의 원칙 (DIP) 

의존성 역전의 원칙은 의존성 관계를 맺을 때 변화하기 쉬운 것보다는 변화가 없는 것에 의존관계를 맺어야 한다는 원칙이다. 간단하게 DIP라고 부르기도 한다. 만약 어떠한 상점이 할인정책으로 fixed amount discount policy, 즉 모든 물건에 대해 정해진 양 ex) 2000원 할인을 실시했다고 치자. 

의존성 역전의 원칙이 잘 지켜지지 않는 경우

discount policy로 fixed amount discount policy를 채택해서 위와 같은 diagram 형식의 class 구조가 되었지만, 사실 이는 5번 의존성 역전의 원칙을 잘 준수하지 않은 예시이다. 왜냐하면 만약 이후 상점이 마음이 바뀌어 할인정책으로 정량할인정책이 아닌, 정률할인정책을 사용한다면 단순히 fixed amount class를 바꾸어야 할 뿐만 아니라 store의 다른 영향을 받는 부분까지 모두 다 변경해야 하기 때문이다. 현재 store class는 변화가 있을 수 있는 fixed amount policy라는 class에 의존관계를 맺고 있기 때문에 의존성 역전의 원칙을 만족시키지 않는 것이다. 

 

의존성 역전의 원칙을 잘 만족시키기 위해서는 변화가 없는 interface나 상위 클래스와 의존관계를 맺어야 한다. 위의 예시를 수정하면 아래와 같은 다이어그램이 될 것이다. 

의존성 역전의 원칙이 잘 지켜지는 경우 

즉 store는 변화가 잘 없는 discount policies라는 interface와 의존관계를 맺고 있으며, 이럴 경우 상점이 택하고 있는 할인정책이 변하더라도 store 자체 class는 큰 변경 없이 사용이 가능하다. 만약 두 가지 할인 정책 이외에 새로운 할인정책을 변경하고 싶다면 discount policies 를 구현하는 새로운 하위 클래스를 만들어 사용하면 되기 때문에 문제가 없다. 오히려 개발자의 입장에서는 변경이 용이해진 것이다. 

 

의존성 역전의 원칙은 5가지 원칙 중 가장 이해하기가 까다로운 원칙이었을 것이다. 중요하지 않아 보일 수 있지만 이러한 의존성 역전의 원칙은 자바, 특히 이후 Spring에서 매우 중요하게 강조되는 개념이므로 잘 알아두면 유용할 것이다.

---

개발자라면 필수로 알아야 할 SOLID 원칙에 대해 알아보았다. 개념이 이해되었다고 넘어가지 말고 실제 코드 작성을 할 때 유념하여 의식적으로 이 원칙들을 잘 적용하고 있는지 살펴보면 좋을 것 같다.