Programming Story

5월 23, 2024

Git 환경설정하기/ git config/ git 환경 재설정/--global/--local

1. GIT 환경설정하기

git을 처음 사용하기 전에 해야 할 것으로 git 환경설정이 있다.

이 설정은 처음 한번만 해주면 다음부터는 해주지 않아도 되니, 시작하기 전에 설정을 잘 해보자.

굉장히 간단하다.

2. GIT config 명령어

다음과 같이 명령어를 입력해주자.

$ git config --global user.name "설정하려는 이름"
$ git config --global user.email "설정하려는 이메일 주소"

설정하려는 이름과 이메일 주소 앞뒤로 " " 따옴표를 써주면 된다.

여기서 --global 옵션이라는 것은 현재 사용하고 있는 컴퓨터 안의 모든 저장소에서 입력한 사용자 정보를 사용하겠다는 뜻이다. 즉 특정 저장소뿐 아니라 모든 저장소에 global 하게 적용된다는 뜻으로 이해하면 된다. 하지만 이렇게 global하게 사용하지 않고 특정 저장소에서만 해당되는 다른 설정을 해주고 싶다면it을 처음 사용하기 전에 해야 할 것으로 git 환경설정이 있다.

이 설정은 처음 한번만 해주면 다음부터는 해주지 않아도 되니, 시작하기 전에 설정을 잘 해보자.

하지만 이렇게 global하게 사용하지 않고 특정 저장소에서만 해당되는 다른 설정을 해주고 싶다면

$ git config --local user.name "설정하려는 이름"
$ git config --local user.email "설정하려는 메일주소"

위와 같이 --local의 옵션을 붙이거나,

혹은 단순히 --global을 빼주면 된다.

$ git config user.name "설정하려는 이름"
$ git config user.email "설정하려는 이메일 주소"

위와 같이 --global option을 쓰지 않으면 해당 저장소에서만 user configuration을 사용하겠다라는 뜻이다.

3. 사용자 정보 파악하기

만약 내가 설정한 사용자 정보를 알기 위해서는 다음과 같이 입력해보면 된다.

$ git config --list

이렇게 입력어를 친다면

user.name=~

user.email=~

이런식으로 사용자 정보가 출력될 것이다.

4. 사용자 정보 다시 설정하기

다음으로 만약 내가 설정한 사용자 정보를 다시 설정하고 싶다면 어떻게 하면 될까?

바로 --unset을 사용하면 된다.

$ git config --unset --global user.name
$ git config --unset --global user.email

위와 같이 명령어를 입력한 다음에 위에서 했던 것처럼 다시 재설정을 해주면 된다.

$ git config --global user.name "설정하려는 이름"
$ git config --global user.email "설정하려는 이메일 주소"

이런 식으로 말이다.

5월 23, 2024

해시 테이블 충돌 해결법

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과 항상 서로소로 만들 수 있다.

5월 23, 2024

해시 테이블에서 충돌(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이라는 방법이 존재한다.

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

5월 23, 2024

[백준] 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인 값을 적어주면 된다.

5월 23, 2024

네트워크/ 통신 기본 구성요소 및 용어 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

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