JArchive 프로그래밍 일기

그래프의 정의와 표현

연결 관계를 표현하기 위한 자료구조

그래프의 정의

그래프 G(V, E)는 어떤 자료나 개념을 표현하는 정점(vertex)의 집합 V와 정점들을 연결하는 간선(edge)들의 집합 E로 구성된 자료구조이다.

그래프는 정점과 간선으로 정의된다. G(V, E)

(cf. 정점의 위치나 간선의 순서 등은 그래프 정의에 포함되지 않는다.)

관련 용어

각 정점에 연결된 간선의 갯수를 차수(degree)라고 한다.

유향 그래프에서는 간선에 방향성이 존재하므로 차수가 두 개로 나뉜다.

정점으로 들어오는 간선의 갯수를 진입차수(in-degree), 정점에서 나가는 간선의 갯수를 진출차수(out-degree) 라고 한다.

그래프의 종류

그래프는 표현하려는 대상에 따라 속성이나 형태의 제약을 추가할 수 있다.

ex) 간선에 방향 속성 추가, 간선에 가중치 속성 추가, 정점을 2개의 그룹으로 나누기 etc.

• 방향 속성
  • 방향그래프(directed graph) 혹은 유향그래프두 정점 v와 u 가 있을 때, v->u 방향의 간선과 u->v 방향의 간선은 서로 다른 간선이다.
  • : 간선에 특정한 방향이 정해진 그래프
  • 무향그래프(undirected graph) : 간선에 방향이 없는 그래프
  • : 간선을 양방향으로 지날 수 있다.
• 가중치 속성
  • 가중치 그래프(weighted graph) : 간선에 가중치(weight) 라는 실수 속성을 부여
• 형태 속성
  • 다중 그래프(multigraph) : 두 정점 사이에 2개 이상의 간선이 존재할 수 있는 그래프
  • 단순 그래프(simple graph) : 두 정점 사이에 간선이 최대 1개만 있는 그래프
• 트리 혹은 루트 없는 트리(unrooted tree)
• : 부모 자식 관계는 없고, 두 정점간의 간선이 1개만 있는 그래프
• 이분 그래프 (bipartite graph)
• : 그래프의 정점들을 겹치지 않는 두 개의 그룹으로 나눈다. 서로 다른 그룹에 속한 정점 간에만 간선이 존재하도록 만든 그래프
• DAG (사이클 없는 방향 그래프, directed acyclic graph): 상호 의존 관계 또는 순서가 정해진 작업들을 표현할 때 활용
• cf) 위상정렬 : 순서가 정해진 작업들에서 순서를 정렬하는 알고리즘 (그래프의 정점을 정렬)
• : 한 점에서 출발해 자기 자신으로 돌아오는 경로(사이클)이 없는 그래프

그래프의 경로

경로(path)란, 끝과 끝이 서로 연결된 간선들을 나열한 것이다.

• 단순 경로(simple path) : 한 정점을 최대 한 번만 지나는 경로 (1-5-4-2)
• 사이클 (cycle 혹은 회로) : 시작한 정점에서 끝나는 경로 (1-5-4-1)

특별한 명시가 없다면 ''경로''는 보통 ''단순 경로''를 의미한다.

• 연결그래프(connected graph) : 모든 정점쌍들에 대해 ''경로''가 존재하는 그래프
• 비연결그래프(disconnected graph) : 특정 정점쌍 사이에 ''경로''가 없는 그래프
• 완전그래프(complete graph) : 모든 정점들이 연결되어 있는 그래프

그래프의 표현 방법

대부분 그래프는 트리에 비해 정적인 용도로 사용된다.

정적이라는 뜻은 새로운 정점이나 간선을 추가/삭제 하는 일이 드물다는 의미다.

따라서 대부분 그래프는 구조의 수정이 어렵더라도 간단하고 메모리를 적게 차지하는 방법으로 구현하는 편이다.

인접 리스트 (adjacency list)

그래프의 각 정점마다 해당 정점에서 나가는 간선의 목록(인접 노드)을 저장해서 그래프를 표현한다.

즉, 각 정점마다 하나의 연결 리스트를 갖는 방식으로 구현한다.

정점 간에 인접한지 list를 모두 확인하는 데에 오래 걸린다.

• 무향 그래프에서 (a, b) 간선은 2 번 저장된다. (a->b) (b->a)는 다르기 때문이다.
• 유향 그래프에서는 (a, b)는 특정 방향이 존재하므로 한 번만 저장된다.

vector<list<int> > adjacent;

간선의 가중치 그래프를 표현하려면?

struct Edge{
    int vertex; // 간선의 반대쪽 끝 정점의 번호 
    int weight; // 간선의 가중치 
}

또는 단순하게 pair STL 이 자주 쓰인다.

pair<int, int>  // 도착 정점, 가중치

가중치 있는 무향 그래프에서 정점, 간선, 가중치 입력받기

(pair 객체 사용)

시작 정점, 도착 정점, 가중치 순으로 입력받는다. 도착정점과 가중치를 pair로 묶는다.

• 그래프 구조 : 정점 개수 5, 간선 개수 6
• 입력 : 시작 정점, 도착 정점, 가중치

- 아래와 같이 입력이 주어진다 -
 5 6 // 정점 개수, 간선 개수
 1 2 1 // 시작 정점, 도착 정점, 가중치 순서
 4 1 5
 2 3 3
 5 2 2
 3 5 4
 4 5 6

• 입력받는 코드

#include <vector>
#include <stdio.h>
using namespace std;

int ver, ed; // 정점, 간선
vector<pair<int,int> > vertex[200];

int main(void){
    scanf("%d %d", &ver, &ed); // 정점 수, 간선 수 입력받기

    for(int i = 0; i < ver; i++){
        int start, end, weight = 0;
        scanf("%d %d %d", &start, &end, &weight);

        vertex[start].push_back(make_pair(end, weight));
        vertex[end].push_back(make_pair(start, weight)); // 무방향 그래프니까 반대 경우도 저장 
    }

}

인접 행렬 (adjacency matrix)

V x V 크기의 2차원 배열로 간선 정보를 저장

• 무향 그래프의 경우: 행렬에 대각선을 그어보면 대칭 모양이 나온다. 대칭 행렬(Symmetric Matrix)
• : 정점 1에서 2, 정점 2에서 1 모두 연결되어 있으므로 1로 표시하고, 연결이 안 된 정점끼리 0으로 표시한다.

• 유향 그래프예를 들어, 정점 6은 가리키고 있는 정점이 5밖에 없다. 정점 6의 인접 정점은 5뿐이다.
• ㅍ
• 
• : 정점 자신이 가리키고 있는 정점에 대해서만 인접해 있다고 표현한다.

vector<vector<bool> > adjacent; // 유향 그래프
vector<vector<int> > adjacent_weight; // 가중치 유향 그래프

• 가중치 가진 유향 그래프
  
• : 간선의 정보를 bool 값 대신 정수나 실수 변수로 쓰면 된다.

인접 리스트와 인접 행렬 표현의 비교

두 방식은 정반대의 특성을 가져서 한 방식의 단점이 다른 방식의 장점이 된다. 구현하려는 알고리즘이나 그래프의 종류에 맞게 사용하자.

• 희소 그래프 : 간선의 수가 V^2 에 비해 적은 그래프
• 밀집 그래프 : 간선의 수가 V^2 에 비례하는 그래프.

그래프와 트리 비교

[참고]

그래프 인접행렬 인접리스트

알고리즘 문제해결전략(도서 종만북 요약)

도움이 되셨다면 '공감'을 눌러주세요 :)

문제

하샤드 수

프로그래머스 level 1

문제 설명

양의 정수 x가 하샤드 수이려면 x의 자릿수의 합으로 x가 나누어져야 합니다. 예를 들어 18의 자릿수 합은 1+8=9이고, 18은 9로 나누어 떨어지므로 18은 하샤드 수입니다. 자연수 x를 입력받아 x가 하샤드 수인지 아닌지 검사하는 함수, solution을 완성해주세요.

제한 조건

• x는 1 이상, 10000 이하인 정수입니다.

입출력 예

입출력 예 설명

입출력 예 #1
10의 모든 자릿수의 합은 1입니다. 10은 1로 나누어 떨어지므로 10은 하샤드 수입니다.

입출력 예 #2
12의 모든 자릿수의 합은 3입니다. 12는 3으로 나누어 떨어지므로 12는 하샤드 수입니다.

입출력 예 #3
11의 모든 자릿수의 합은 2입니다. 11은 2로 나누어 떨어지지 않으므로 11는 하샤드 수가 아닙니다.

입출력 예 #4
13의 모든 자릿수의 합은 4입니다. 13은 4로 나누어 떨어지지 않으므로 13은 하샤드 수가 아닙니다.

코드

#include <string>
#include <vector>

using namespace std;


bool solution(int x) {
    bool answer = true;
    int sum = 0;
    int x_old = x;

    while(x>0){
        sum += (x % 10);
        x = x / 10;
    }

    if(x_old % sum != 0){
        answer = false;
    }

    return answer;
}

문제

핸드폰 번호 가리기 문제링크

프로그래머스 level 1

프로그래머스 모바일은 개인정보 보호를 위해 고지서를 보낼 때 고객들의 전화번호의 일부를 가립니다.
전화번호가 문자열 phone_number로 주어졌을 때, 전화번호의 뒷 4자리를 제외한 나머지 숫자를 전부 *으로 가린 문자열을 리턴하는 함수, solution을 완성해주세요.

제한 조건

• s는 길이 4 이상, 20이하인 문자열입니다.

입출력 예

리뷰

뒤에서 4번째까지만 string을 *로 바꾸면 되는 문제였다.

코드

#include <string>
#include <vector>

using namespace std;

string solution(string phone_number) {
    string answer = "";
    int i = 0; 

    for(i=0; i<phone_number.size()-4; i++){
        phone_number[i] = '*';
    }

    answer = phone_number;

    return answer;
}

문제

이상한 문자 만들기

프로그래머스 level 1

문제 설명

문자열 s는 한 개 이상의 단어로 구성되어 있습니다. 각 단어는 하나 이상의 공백문자로 구분되어 있습니다. 각 단어의 짝수번째 알파벳은 대문자로, 홀수번째 알파벳은 소문자로 바꾼 문자열을 리턴하는 함수, solution을 완성하세요.

제한 사항

• 문자열 전체의 짝/홀수 인덱스가 아니라, 단어(공백을 기준)별로 짝/홀수 인덱스를 판단해야합니다.
• 첫 번째 글자는 0번째 인덱스로 보아 짝수번째 알파벳으로 처리해야 합니다.

입출력 예

입출력 예 설명

try hello world는 세 단어 try, hello, world로 구성되어 있습니다. 각 단어의 짝수번째 문자를 대문자로, 홀수번째 문자를 소문자로 바꾸면 TrY, HeLlO, WoRlD입니다. 따라서 TrY HeLlO WoRlD 를 리턴합니다.

리뷰

처음에 문제를 잘못 읽어서 완전히 틀렸었다. 문제를 똑바로 읽자...

코드

#include <string>
#include <vector>
using namespace std;

string solution(string s) {

    string answer = "";
     int i = 0;
     bool start_flag = 1;

     while(i != s.size()){

         if(s[i] == ' '){ // 공백 
             answer += s[i];
             start_flag = 1;
        }else{

            if(start_flag == 1){ // 첫 문자는 무조건 짝수번째
                answer += toupper(s[i]); 
                start_flag = 0; // 플래그 갱신
            }else{ // 홀수번째
                answer += tolower(s[i]); 
                start_flag = 1; // 플래그 갱신 
            }
        }
        i++;

    }

    return answer;
}

문제

x만큼 간격이 있는 n개의 숫자 문제링크

프로그래머스 level 1

문제 설명

함수 solution은 정수 x와 자연수 n을 입력 받아, x부터 시작해 x씩 증가하는 숫자를 n개 지니는 리스트를 리턴해야 합니다. 다음 제한 조건을 보고, 조건을 만족하는 함수, solution을 완성해주세요.

제한 조건

• x는 -10000000 이상, 10000000 이하인 정수입니다.
• n은 1000 이하인 자연수입니다.

입출력 예

리뷰

자료형을 주의하면 되는 문제였다.

int

4byte 크기 (대강 -2,147,000,000 ~ 2,147,000,000 )

printf 서식문자 %d

long long

8byte 크기

-9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807

printf 서식문자 %lld

자료형 출력시 서식문자는 자꾸 헷갈리지만.. 자꾸 보면 익숙해지겠지.

코드

#include <string>
#include <vector>

using namespace std;

vector<long long> solution(int x, int n) {
    vector<long long> answer;
    long long init_num = x;

    for(; n>0; n--){ 
        answer.push_back(init_num);
        init_num += x;
    }

    return answer;
}

문제

제일 작은 수 제거하기 문제링크

프로그래머스 level 1

정수를 저장한 배열, arr 에서 가장 작은 수를 제거한 배열을 리턴하는 함수, solution을 완성해주세요.

단, 리턴하려는 배열이 빈 배열인 경우엔 배열에 -1을 채워 리턴하세요.

예를들어 arr이 [4,3,2,1]인 경우는 [4,3,2]를 리턴 하고, [10]면 [-1]을 리턴 합니다.

제한 조건

• arr은 길이 1 이상인 배열입니다.
• 인덱스 i, j에 대해 i ≠ j이면 arr[i] ≠ arr[j] 입니다.

입출력 예

리뷰

algorithm 헤더파일 에는 유용한 메소드가 참 많다. min_element() 함수로 편하게 풀 수 있었다.

코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> solution(vector<int> arr) {
    if(arr.size() == 1) {
        arr[0] = -1;
    } else {
        arr.erase(min_element(arr.begin(), arr.end()));
    }
    return arr;
}

문제

2016년 문제링크 프로그래머스 level 1

2016년 1월 1일은 금요일입니다. 2016년 a월 b일은 무슨 요일일까요? 두 수 a ,b를 입력받아 2016년 a월 b일이 무슨 요일인지 리턴하는 함수, solution을 완성하세요. 요일의 이름은 일요일부터 토요일까지 각각 SUN,MON,TUE,WED,THU,FRI,SAT

입니다. 예를 들어 a=5, b=24라면 5월 24일은 화요일이므로 문자열 TUE를 반환하세요.

제한 조건

• 2016년은 윤년입니다.
• 2016년 a월 b일은 실제로 있는 날입니다. (13월 26일이나 2월 45일같은 날짜는 주어지지 않습니다)

입출력 예

리뷰

윤년이라서 2월이 29일 까지 있다는 것만 주의하면, 나머지연산(%)을 이용해 금방 풀수있었다.

풀고나서 다른사람들의 코드를 구경했는데.

앞의 달의 날짜를 31+29+31+30+31 이렇게 직접 코딩한 분이 있어서 재미있었다.

반복문 안쓰고 일일히 다 쓴게 너무 귀여웠다. 웃고간다는 댓글이 수두룩이었다. ㅋㅋ

코딩은 역시 같이해야 재미있다.

코드

#include <string>
#include <vector>
using namespace std;

int month_days[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
string days_arr[] = {"THU", "FRI", "SAT", "SUN", "MON", "TUE", "WED"};

string solution(int a, int b) {
    string answer = "";
    int days = 0;  
     int i = 0, days_diff = 0;
    /*    
    2월 이라면, days에 1월까지 더하고 시작
    3월 이라면, days에 2월까지 더하고 시작  
    */
    for(i = 1; i <a; i++){
        days += month_days[i]; 
    }
    days += b;
    days_diff = (days % 7); // 요일 알아내기 
    answer = days_arr[days_diff];

    return answer;
}