싱글톤이란

  • 인스턴스를 한 개만 만들기
  • 클래스의 인스턴스가 단 하나만 필요한경우
  • 싱글톤 - 요소를 한개밖에 가지고 있지 않은 집합

Singleton 클래스

  • 인스턴스를 1개 밖에 만들수 없음
  • static 필드로서 Singleton클래스의 인스턴스에서 초기화됨 (Singleton 클래스 로드시 1회만 실행)
  • 생성자는 private로 되어있음
    • 왜? 외부에서 생성자의 호출을 금지하기 위해서
    • 만약 new로 한다면 ? 싱클돈 패턴이 아님 (싱글톤은 클래스에서 단 하나의 인스턴스만 존재하는 것이기 때문)

 


싱글톤 예제

요소 설명

  • - : Singleton이 private임
  • 밑줄 : 메소드가 static 메소드임

 

싱글톤 예제

[ static 란? ]
전역, 정적 이라고함
해당 데이터의 메모리 할당을 컴파일 시간에 하는것
런타임중 필요할때마다 동적으로 메모리를 할당 하는 것이아니라 데이터는 프로그램 실행 직후부터 끝날 때까지 메모리 수명이 유지

- static: 변수인스턴스 간에 데이터 공유가 필요한 상황
- static final: 클래스 내부 또는 외부에서 참조의 용도로만 선연
- static 메소드: 인스턴스를 생성하지 않아도 static 메소드 호출 가능
- public static void main: 자바에서 메인 메소드 실행할때 사용인스턴스의 생성과 상관없이 JVM에 의해 호출되므로 static무조건 선언 해야함 cf ) final 변수한번 값이 결정되었다면 변경이 불가능
- final 클래스: 상속을 허용하지 않음
- final 메소드: 오버라이딩을 허용하지 않음

소스 코드

  • 정말 같은 메모리를 사용하는 것인지 확인하기위한 예제
  • Main.java
package Singleton;

public class Main {
    public static void main (String[] str) {
        Singleton s1 = Singleton.getInstance();
        Singleton s2 = Singleton.getInstance();
        if(s1==s2) {
            System.out.println("같음");
            System.out.println(s1);
            System.out.println(s2);
        } else {
            System.out.println("다름");
        }
    }
}

 

  • Singleton.java
package Singleton;

public class Singleton {
    // static 프로그램 실행전에 하나메모리에 할당해서 끝날때까지 유지가됨
    // 왜 static인가? 외부에서 호출하는것을 금지하기위해 -> 싱글톤이라는 의미는 해당 클래스에서 인스턴스가 딱 한개만 존재하는것
    private static Singleton singleton = new Singleton();
    private Singleton() {
        System.out.println("인스턴스 생성");
    }
    public static Singleton getInstance() {
        return singleton;
    }
}

싱글톤 클래스내 같은 객체로 사용한다

Singleton각각의 역할

  • Singleton 패턴에는 Singleton의 역할만 존재

    ⇒ 유일한 인스턴스를 얻기 위한 static 메소드를 가짐 (언제나 동일한 인스턴스 반환)

왜 사용하는가?

  • 싱글톤 패턴은 인스턴스 수를 제한함으로서 복수의 인스턴스가 존재하면 서로 영향을 미치고 뜻하지 않는 버그가 발생할 수 있기에 인스턴스가 1개만 있다 라고 보증 하는 것이다

싱글톤에서 인스턴스 생성시점

  • 프로그램 실행후 인스턴스를 얻는 함수 호출하면 static필드 초기화 되면서 인스턴스가 생성됨

싱글톤 인스턴스 생성 시점


연습문제

  1. 싱글톤 패턴 적용
  • 매번 객체 생성 코드
  • TicketMater.java
package Singleton;

public class TicketMater {
    private static TicketMater ticketMater = new TicketMater();
    private static int ticket = 100;

    public static int getNextTicket() {
        return ticket++;
    }

    public static TicketMater getInstance() {
        return ticketMater;
    }
}
for(int i=0 ;i<10;i++) {
            int ticketMater = TicketMater.getNextTicket();
            System.out.println(TicketMater.getInstance() +"||" +ticketMater);
        }
  • result

싱글톤 예제 1

  1. 싱글톤 패턴이 아닌이유

다수의 스레드가 동시 실행되면 다수 인스턴스가 생성될 가능성이 있음

solv1 ) 복수 인스턴스 생성을 막기위해 sleep 추가

  • Singleton.java
private static Singleton singleton = null;
    private Singleton() {
        System.out.println("create");
        slowdown();
    }
    public static Singleton getInstance( ) {
        if(singleton == null) {
            singleton = new Singleton();
        }
        return singleton;
    }
    private void slowdown() {
        try {
            Thread.sleep(1000);
        } catch (InterruptedException e) {
        }
    }

solv2 ) 동기화를 이용해 엄격한 싱글톤 패턴 적용

  • Singleton.java
private static Singleton singleton = null;
    private Singleton() {
        System.out.println("create");
        slowdown();
    }
    public static synchronized Singleton getInstance( ) {
        if(singleton == null) {
            singleton = new Singleton();
        }
        return singleton;
    }
    private void slowdown() {
        try {
            Thread.sleep(1000);
        } catch (InterruptedException e) {
        }
    }
synchronized 란?
- 자바로 프로그래밍 하다보면 멀티 스레드가 발생해서 동기화를 제어해야하는 상황이 생김
- 동시성을 제어

'Study(Language)' 카테고리의 다른 글

[Design Pattern] FactoryMethod Pattern  (0) 2021.01.04

Factory Method

  • 하위 클래스에서 인스턴스 작성하기

  • 인스턴스를 생성하는 공장을 Template Method패턴으로 구성하는 것이 Factory Method패턴

  • Template Method 패턴 이란?

    하위클래스에서 구체적으로 로직이 들어가는 패턴

  • 인스턴스를 만드는 방법을 상위 클래스 측에서 결정하지만 구체적인 클래스 이름까지는 결정하지 않음

  • 구체적인 내용은 모두 하위 클래스에서 수행
    ⇒ 인스턴스 생성을 위한 골격과 실제 인스턴스를 생성하는 클래스를 분리해서 생각하는 패턴

  • 디자인 패턴 중 생성 패턴에 포함

생성 패턴이란?

  • 시스템이 어떤 Concrete Class를 사용하는지에 대한 정보를 캡슐화함
  • 클래스의 인스턴스 들이 어떻게 만들어지고 어떻게 결합하는지에 대한 부분을 완전 가려준다
    ⇒ 생성패턴을 이용하면 무엇이 생성되고, 누가 생성하며, 어떻게 생성되는지, 언제 생성할 것인지에 대한 유연성을 확보할 수 있음

  • 주의깊게 봐야하는것

  • 여기에서 Factory, Product 클래스는 framework라는 패키지 소속

  • IDCard, IDCardFactory 클래스는 구체적인 내용을 구현하여 idcard라는 패키지에 소속

각각의 class의 역할

    추상적인 골격 ⇒ framework , 구체적인 내용 ⇒ idcard

Creator(작성자) 역할

  • 예제에서는 Factory 클래스가 작성자 역할을함

    예제에서 createProduct는 인스턴스 생성을 위한 메소드

  • 실제로 생성하는 ConcreateProduct에 가지고 있는 정보가 없고 Product와 인스턴스 생성의 메소드를 호출하면 Product가 생성되는 것 뿐이다

  • new를 사용해서 실제 인스턴스를 생성하는 것 대신, 인스턴스 생성을 위한 메소드를 호출해서 구체적인 클래스 이름에 의한 속박에서 상위 클래스를 자유롭게 만듦

Product(제품) 역할

  • 예제에서 Product 클래스가 제품 역할을함
  • famework에 포함
  • 생성되야하는 인스턴스가 가져야할 인터페이스(API)를 결정하는 것 ⇒ 추상클래스
  • 구체적인 내용은 하위클래스인 ConcreteProduct 역할
  • Product를 생성하는 추상 클래스는 framework

ConcreteCreator.java (구체적인 작성자)

  • 예제에서는 IDCard가 구체적인 작성자 역할을 함
  • idcard
  • 구체적인 제품을 만드는 클래스

ConcreteProduct.java (구체적인 제품)

  • 예제에서는 IDCardFactory 클래스가 구체적인 제품 역할을함
  • 구체적인 제품
  • idcard

예제

  • Main.java
package FactoryMethod;

import FactoryMethod.framework.Factory;
import FactoryMethod.framework.Product;
import FactoryMethod.idcard.IDCardFactory;

public class Main{
  public static void main(String[] args) {
    Factory factory = new IDCardFactory();
    Product card1 = factory.create("김카드");
    Product card2 = factory.create("이카드");
    Product card3 = factory.create("박카드");

    card1.use();
    card2.use();
    card3.use();
  }
}
  • Factory.java
package FactoryMethod.framework;

// import FactoryMethod.idcard.IDCard;
// Template Method 패턴이 사용되는 class
// 제품을 실제로 만들고 등록하는 구현은 하위클래스에서 함
// Tempplte Method 패턴 - 하위 클래스에서 구체적으로 처리하는 패턴
public abstract class Factory {
    public final Product create(String owner) {
        Product p = createProduct(owner);
        // Product p = createNew(owner);
        registerProduct(p);
        return p;
    }
//     자바의 특징 -> 접근지정자 (protected, public, private) => 캡슐화
//     createProduct : 인스턴스 생성을 위한 메소드
//     new로 실제 인스턴스를 생성하는 대신 인스턴스 생성을 위한 메소드를 호출해서 구체적인 클래스 이름에 의한 속박에서 상위 클래스를 자유롭게함
//    protected Product createNew (String owner) {
//        return new IDCard(owner);
//    }
    protected abstract Product createProduct(String owner);
    protected abstract void registerProduct(Product product);
}
  • Product.java
package FactoryMethod.framework;
// FactoryMethod.framework 는 제품에 대해서 표현한 패키지, 사용 생성 이런것
public abstract class Product {
    public abstract void use();
}
  • IDCardFactory.java
package FactoryMethod.idcard;
import FactoryMethod.framework.*;
import java.util.*;

public class IDCardFactory extends Factory {
    private List owners = new ArrayList();

    @Override
    protected Product createProduct(String owner) {
        return new IDCard(owner);
    }

    @Override
    protected void registerProduct(Product product) {
        owners.add(((IDCard)product).getOwner());
    }
    public List getOwners() {
        return owners;
    }
}
  • IDCard.java
package FactoryMethod.idcard;
import FactoryMethod.framework.*;
// 인식 카드를 나타내는 클래스
public class IDCard extends Product {
    private String owner;

    // 생성자
    public IDCard(String owner) {
        System.out.print(owner + "카드 만듦\n");
        this.owner = owner;
    }
    @Override
    public void use() {
        System.out.print(owner + "카드 사용\n");
    }

    public String getOwner() {
        return owner;
    }
}

왜 사용해야 하는가?

  • 팩토리 패턴은 클라이언트 코드로 부터 서브 클래스의 인스턴스화를 제거해서 서로 간의 종속성을 낮추고, 결합도를 느슨하게해서 호가장을 쉽게함

  • 만약 framework패키지를 이용해서 제품과 공장을 만든다고 가정

    TV의 클래스 Television과 TV공장 TelevisionFactory를 만든다고 하면 framework 패키지를 import한 별도의 Television 패키지를 만들게됨

    ⇒ 이때 framework 패키지를 수정하지 않아도 전혀 다른 제품과 공장을 만들수 있다

    ⇒ 즉. framework패키지는 내용을 수정할 수 없다

    ⇒ 왜? framework 패키지 안에 idcard 패키지를 import하지 않음

    ⇒ 이로 알수 있는점 : framework 패키지는 idcard패키지에 의존하고 있지 않음

Factory.java의 createProduct 메소드 구현방법

  1. 추상메소드

    하위 클래스가 반드시 이 메소드를 override해야함

  2. 디폴드의 구현

    디폴트 구현을 준비하고 하위 클래스에서 구현하지 않을 때 사용

    이 경우 Product를 new해서 사용하므로 Product를 추상클래스로 놓을수 없다

  3. 에러이용

    FactoryMethodRuntimeExecption이 별도로 작성되어야함

    하위클래스에서 구현하지 않을 경우에 실행시 에러 발생

추상 클래스

  • 클래스간의 공통점을 찾아내서 공통의 부모를 설계하는 작업
  • 아직 구현되지 않은 클래스를 포함한 것으로 무조건 자식클래스에서 재구현해서 인스턴스 화해야한다
  • 없거나 하나 이상의 추상 메소드(아직 구현되어 있지 않은 abstract로 정의된 메소드)를 가지고 있는 것
  • 추상 클래스는 생성자는 가질수있음 하지만
  • 인스턴스를 만들수 없지만 추상클래스를 상속받은 클래스를 통하면 인스턴스화 가능함

왜 사용하는가?

  • 부모 클래스에서 공통 부분의 구현과 설계가 완료되면 자식이 상속받아 기능 확장 가능
  • 자식 클래스에서 추상클래스를 반드시 구현해야함
  • 공통 사항이 한곳에서 관리되어 개발 및 유지보수 용이
  • 부모 추상 클래스에서 기본 생성자가 없으므로 하위 클래스에 사용 된 생성자는 부모 생성자를 명시적으로 호출해야함

참고

 

디자인 패턴(Design Pattern)이란?

객체지향 소프트웨어를 '잘' 설계한다는 것은 쉬운 일이 아닙니다. 게다가, 재사용할 수 있는 객체지향 소프트웨어를 만드는 것은 더 힘듭니다. 설계를 할 때에는 지금 당장 갖고 있는 문제를 해

readystory.tistory.com

 

[JAVA/자바] 추상 클래스(abstract class), 추상 메소드

이번 포스팅은 추상 클래스에 대해서 알아보도록 하겠다. 추상이란 말처럼 공통적인 특성이나 속성들을 추...

blog.naver.com

 

'Study(Language)' 카테고리의 다른 글

[Design Pattern] Singleton  (0) 2021.01.07

그래프

노드와 노드사이에 연결된 간선의 정보를 가지고 있는 자료구조

ex ) 여러개의 도시가 연결되어 있다

 

 

그래프 구현 방법

  1. 인접 행렬 : 2차원 배열을 사용
  2. 인접 리스트 : 리스트를 사용

두가지 방식 특징 ( 노드의 갯수 V, 간선의 갯수 E인 그래프)

인접 행렬 이용

  • 장점 - 특정한 노드 A에서 다른 특정한 노드 B로 이어진 간선의 비용을 $O(1)$의 시간으로 즉시 알수 있음
  • 단점 - 간선 정보를 저장하기 위해 $O(V^2)$ 만큼의 메모리 공간이 필요

인접 리스트 이용

  • 장점 - $O(V)$만큼의 시간 소요
  • 단점 - 간선의 개수만큼 $O(E)$만큼의 메모리 공간 필요

서로소 집합 (유니온 파인드 - Union find)

공통 원소가 없는 두 집합

union - 합집합 연산 - 2개의 원소가 포함된 집합을 하나의 집합으로 합침

find - 찾기 연산 - 특정 원소가 속한 집합이 어떤 집합인지 알려줌

트리 자료 구조 이용

  1. union(합집합) 연산을 확인하여, 서로 연결된 두 노두 A,B 확인
    1. A와 B의 루트 노드 A', B'를 찾음
    2. A'를 B'의 부모 노드로 설정
  2. 모든 union(합집합) 연산을 처리할 때까지 1번 과정 반복

(A', B' 중 보통 더 작은 숫자가 부모가 됨)

#include <stdio.h>
#include <string>
#include <iostream>
#include <stdlib.h>
#include <deque>
#include <stack>
#include <vector>
#include<cstdio>
#include<algorithm>
#include<memory.h>
#include<queue>
#include<map>
#define MAX 100001
#define INF 1e9 // 무한을 의미하는 값으로 10억을 설정

using namespace std;

int parent[MAX];
int V, E;
int findParent(int num) {
    if (num == parent[num]) return num;
    findParent(parent[num]);
}
void func(int a, int b) {
    a = findParent(a);
    b = findParent(b);
    if (a > b) parent[a] = b;
    else parent[b] = a;
}
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> V >> E;
    for (int i = 1; i <= V; i++) {
        parent[i] = i;
    }
    for (int i = 0; i < E; i++) {
        int a, b;
        cin >> a >> b;
        func(a, b);
    }
    // 각원소가 속한 최상위 집합
    int cnt = 0;
    for (int i = 1; i <= V; i++) {
        cout << findParent(i) << " ";
    }
    cout << "\n";
    // 각원소의 부모 테이블
    for (int i = 1; i <= V; i++) {
        cout << parent[i] << " ";
    }

}

⇒ 해당 코드는 만약 하나의 그래프로 쭉~연결되어 있다면 최대 O(V)시간이 걸릴 수 있다

노드개수가 V이고 find 혹은 union연산 개수가 M개인 경우 전체 시간복잡도는 O(VM)이 되어 비효율적임

find 과정을 최적화 하는 법

  • 경로 압축기법 - 재귀적 호출한 뒤 부모 테이블값 갱신
int findParent(int num) {
    if (num == parent[num]) return num;
    return parent[num] = findParent(parent[num]);
}

서로소 집합을 활용한 사이클 판별

무방향 그래프 내에서의 사이클 판별할 때 사용
  1. 각 간선을 확인하며 두 노드의 루트 노드를 확인
    1. 루트 노드가 서로 다르면 두 노드에 대해 union연산 수행
    2. 루트 노드가 서로 같다면 사이클 발생
  2. 그래프에 포함되어 있는 모든 간선에 대해 1번 과정 반복
#include <stdio.h>
#include <string>
#include <iostream>
#include <stdlib.h>
#include <deque>
#include <stack>
#include <vector>
#include<cstdio>
#include<algorithm>
#include<memory.h>
#include<queue>
#include<map>
#define MAX 100001
#define INF 1e9 // 무한을 의미하는 값으로 10억을 설정

using namespace std;

int parent[MAX];
int V, E;
int findParent(int num) {
	if (num == parent[num]) return num;
	return parent[num] = findParent(parent[num]);
}
void func(int a, int b) {
	a = findParent(a);
	b = findParent(b);
	if (a > b) parent[a] = b;
	else parent[b] = a;
}
int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> V >> E;
	bool check;
	for (int i = 1; i <= V; i++) {
		parent[i] = i;
	}
	for (int i = 0; i < E; i++) {
		int a, b;
		cin >> a >> b;
		if (findParent(a) == findParent(b)) {
			check = false;
		}
		else {
		func(a, b);
		}
	}
	if (check) {
		cout << "사이클 없음";
	}
	else {
		cout << "사이클 있음";
	}

}

 

 

가장 빠르게 도달 하는 방법

그리디 알고리즘 및 다이나믹 알고리즘의 한 유형

가장 짧은 경로를 찾는 알고리즘

예 )

  • 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야하는 경우
  • 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야하는 경우

종류

  • 다익스트라 최단경로 알고리즘
  • 플로이드 워셜
  • 벨만 포드 알고리즘

다익스트라 최단 경로 알고리즘

각 노드에서 현재까지의 최단거리 정보를 항상 1 차원 리스트에 저장하며 리스트를 계속 갱신

  • 그래프에서 여러 개의 노드가 있을 때, 특정 노드에서 출발해 다른 노드로 가는 각각의 최단 경로 구해주는 알고리즘
  • 음의 간선이 없을 때 사용 가능
  • **가장 비용이 적은 노드**를 선택해 임의의 과정 반복
  • 원리
    1. 출발 노드를 정함
    2. 최단 거리 테이블 초기화
    3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택
    4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신
    5. 위 과정에서 3,4 반복

다익스트라 알고리즘 구현방법

  1. 구현하기 쉽지만 느림
  2. 구현하기 조금 까다롭지만 빠름

1.
시간 복잡도 - O(V^2)

#include <stdio.h>
#include <string>
#include <iostream>
#include <stdlib.h>
#include <deque>
#include <stack>
#include <vector>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<map>
#define MAX 10001
#define INF 1e9 

using namespace std;

int N, cnt, start;
vector<pair<int, int>> v[MAX];
bool visit[MAX];
int ans[MAX];
int findSmallN() {
    int tmpN = INF; // 가장 작은 수
    int index; // 가장 작은 수 index
    for (int i = 1; i <= N; i++) {
        if (ans[i] < tmpN && !visit[i]) {
            tmpN = ans[i];
            index = i;
        }
    }
    return index;
}
void func(int n) {
    visit[n] = true;
    // 배열 초기화
    for (int i = 0; i < v[n].size(); i++) {
        ans[v[n][i].first] = v[n][i].second;
    }
    // 노드들 중에서 가장 작은수 선택
    int smallN = findSmallN();

    for (int i = 0; i < N - 1; i++) {
        visit[smallN] = true;
        for (int j = 0; j < v[smallN].size(); j++) {
            ans[v[smallN][j].first] = min(ans[v[smallN][j].first], ans[smallN] + v[smallN][j].second);
        }
        smallN = findSmallN();
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    // 배열 가장 큰수로 초기화
    fill_n(ans, MAX, INF);

    cin >> N >> cnt >> start;
    ans[start] = 0;

    for (int i = 0; i < cnt; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        v[a].push_back({ b,c });
    }

    func(start);
    for (int i = 1; i <= N; i++) {
        cout << ans[i]<<"\n;
    }

}

2.

시간복잡도 - O(ElogV)

(E - 간선 갯수, V - 노드 갯수)

힙 자료구조 이용

#include <stdio.h>
#include <string>
#include <iostream>
#include <stdlib.h>
#include <deque>
#include <stack>
#include <vector>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<map>
#define MAX 100001
#define INF 1e9 // 무한을 의미하는 값으로 10억을 설정

using namespace std;

// 노드의 개수(N), 간선의 개수(M), 시작 노드 번호(Start)
// 노드의 개수는 최대 100,000개라고 가정
int n, m, start;
// 각 노드에 연결되어 있는 노드에 대한 정보를 담는 배열
vector<pair<int, int> > v[100001];
// 최단 거리 테이블 만들기
int ans[100001];

void func(int n) {
    priority_queue < pair<int, int>, vector<pair<int,int>>> pq;
    pq.push({ 0,n });
    ans[n] = 0;
    while (!pq.empty()) {
        int node = pq.top().first;
        int now = pq.top().second;
        pq.pop();

        if (ans[now] < node) continue; //이미 연결한 적이 있는경우
        for (int j = 0; j < v[now].size(); j++) {
            int tmp = node + v[now][j].second;
            if (tmp < ans[v[now][j].first]) {
                ans[v[now][j].first] = tmp;
                pq.push({ tmp, v[now][j].first });
            }
        }

    }
}
int main(void) {
    cin >> n >> m;
    cin >> start;
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        v[a].push_back({ b,c });

    }
    fill(ans, ans+ 100001, INF);

    func(start);

    for (int i = 1; i <= n; i++) {
        if (ans[i] == MAX) { cout << "INF" << "\n"; }
        else { cout << ans[i] << "\n"; }
    }
}

cf ) 힙이란?

  • 우선순위 큐 - 우선순위가 가장 높은 데이터를 가장 먼저 삭제

  • 데이터를 우선순위에 따라 처리하고 싶을 때 사용

  • 다익스트라 최단 경로 알고리즘에서는 비용이 적은 노드를 우선시함 (최소힙)

최소 힙을 최대 힙 처럼 사용하기
일부러 우선순위에 해당하는 값에 음수 부호(-)를 붙여서 넣었다가, 나중에 우선순위 큐에서 꺼낸 다음에 음수 부호(-) 를 붙여서 원래의 값으로 돌려놓는 방식
  • C++ 최소힙/ 최대힙

      priority_queue<int, vector<int>, greater<int>> q; // 최소힙
      priority_queue<int, vector<int>> q;   // 최대힙

자료구조 


플로이드 워셜 알고리즘

모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우

다익스트라 알고리즘과 비교하면 구현 과정에서 어려움을 겪지 않을 것이지만핵심아이디어가 중요하다

시간 복잡도 - O(N^3)

#include <stdio.h>
#include <string>
#include <iostream>
#include <stdlib.h>
#include <deque>
#include <stack>
#include <vector>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<map>
#define MAX 100001
#define INF 1e9 // 무한을 의미하는 값으로 10억을 설정

using namespace std;

// 노드의 개수(N), 간선의 개수(M), 시작 노드 번호(Start)
// 노드의 개수는 최대 100,000개라고 가정
int n, m, start;
// 각 노드에 연결되어 있는 노드에 대한 정보를 담는 배열
vector<pair<int, int> > v[100001];
// 최단 거리 테이블 만들기
int ans[100001];

void func(int n) {
    priority_queue < pair<int, int>, vector<pair<int,int>>> pq;
    pq.push({ 0,n });
    ans[n] = 0;
    while (!pq.empty()) {
        int node = pq.top().first;
        int now = pq.top().second;
        pq.pop();

        if (ans[now] < node) continue; //이미 연결한 적이 있는경우
        for (int j = 0; j < v[now].size(); j++) {
            int tmp = node + v[now][j].second;
            if (tmp < ans[v[now][j].first]) {
                ans[v[now][j].first] = tmp;
                pq.push({ tmp, v[now][j].first });
            }
        }

    }
}
int main(void) {
    cin >> n >> m;
    cin >> start;
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        v[a].push_back({ b,c });

    }
    fill(ans, ans+ 100001, INF);

    func(start);

    for (int i = 1; i <= n; i++) {
        if (ans[i] == MAX) { cout << "INF" << "\n"; }
        else { cout << ans[i] << "\n"; }
    }
}

'Algorithm > C++' 카테고리의 다른 글

[개념] 다이나믹 프로그래밍(동적계획법)  (0) 2020.10.11
[개념] DFS/BFS  (0) 2020.10.09
[개념] 이진탐색  (0) 2020.10.09
[개념] 정렬 알고리즘  (0) 2020.10.01

연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘

다이나믹 프로그래밍 사용할 수 있는 경우

  1. 큰 문제를 작은 문제로 나눌 수 있다
  2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다

메모이제이션 (캐싱)

  • 다이나믹 프로그래밍을 구현하는 방법 중 한 종류로, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법
  • 한 번 구한 정보를 리스트에 저장하는 것

탑다운(Top-Down) / 보텀업(Bottom-Up) 방식

탑 다운 방식 (메모이제이션)

  • 하향식
  • 재귀 함수를 이용해 다이나믹 프로그래밍 소스코드를 작성하는 방법
  • 큰 문제를 해결하기 위해 작은 문제를 호출 하는 방법

보텀업 방식 (DP)

  • 다이나믹 프로그래밍의 전형적인 형태
  • 상향식
  • 단순히 반복문을 이용해 소스코드를 작성하는 경우 작은 문제부터 차근차근 답을 도출하는 방법

대표 문제 : 피보나치 수열

#include <iostream>
#include <stdlib.h>
#include<cstdio>
#include<algorithm>
using namespace std;

int fibo(int x) {
    if (x == 0 || x == 1) {
        return 1;
    }
    return fibo(x - 1) + fibo(x - 2);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    int num[6];
    memset(num,sizeof(num), 0);

    cout<<fibo(5);
}

'Algorithm > C++' 카테고리의 다른 글

[개념] 최단 경로 구하기  (0) 2020.10.13
[개념] DFS/BFS  (0) 2020.10.09
[개념] 이진탐색  (0) 2020.10.09
[개념] 정렬 알고리즘  (0) 2020.10.01

스택

  • 박스 쌓기에 비유
  • 선입후출 구조 혹은 후입 선출 구조

  • 놀이공원 줄서기 비유
  • 선입선출 구조

queue 보다는 deque 구조 사용
스택과 큐의 장점을 택한것이고 데이터를 넣고 뺴는 속도가 리스트 자료형에 디배 효율적이며 queue라이브러리를 사용하는 것 보다 간단하다

재귀함수

  • 자기자신을 호출하는 함수
  • 재귀함수 사용시 스택 자료 구조 이용
  • 함수를 계속 호출했을 때 가장 마지막에 호출함 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료됨

재귀 함수 사용시 재귀함수가 언제 끝나고, 종료할지 꼭 명시

 


팩토리얼 예제

#include <stdio.h>
#include <string>
#include <iostream>
#include <stdlib.h>
using namespace std;
int answer = 0;
int factorial(int n) {
    // n = 1 인경우 재귀함수 멈춤
    if (n <= 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

int main (){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    int num;
    cin >> num;

    cout<<factorial(num);

}

DFS 스택 자료구조

  1. 탐색 시작 노드를 스택에 삽입하고 방문 처리
  2. 스택의 최상단 노드를 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리,
    방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄
  3. 2번 과정을 더이상 수행할 수 없을 때까지 반복

cf ) 방문 처리 - 스택에 한 번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것

BFS

  • 너비 우선 탐색
  • 가까운 노드부터 탐색하는 알고리즘
  • 선입선출 방식인 큐 자료구조 사용
  • 인접한 노드를 반복적으로 큐에 놓도록 알고리즘 작성하면 자연스럽게 먼저 들어온 것이 먼저 나가게됨
  1. 탐색 시작 노드를 큐에 삽입하고 방문 처리함
  2. 큐에서 노드를 꺼내 해당 노드의 인접노드 중 방문하지 않은 노드를 모두 큐에 삽입 후 방문처리
  3. 2번 과정을 더이상 수행할 수 없을 때까지 반복

너비 우선 탐색은 DFS보다 수행시간이 좋음

 

dfs / bfs 비교

'Algorithm > C++' 카테고리의 다른 글

[개념] 최단 경로 구하기  (0) 2020.10.13
[개념] 다이나믹 프로그래밍(동적계획법)  (0) 2020.10.11
[개념] 이진탐색  (0) 2020.10.09
[개념] 정렬 알고리즘  (0) 2020.10.01

순차 탐색

최악의 시간 복잡도: O(N)

리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법

보통 정렬되지 않은 리스트에서 데이터를 찾을 때 사용

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

int main (){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int num;
    vector<string> str;
    string target;
    int ans;
    cin >> num >> target;

    for (int i = 0; i < num; i++) {
        string strTmp;
        cin >> strTmp;
        str.push_back(strTmp);
    }
    for (ans = 0; ans < num; ans++) {
        if (str[ans] == target) {
            break;
        }
    }
    cout << ans+1;
}

이진탐색 : 반으로 쪼개면서 탐색하기

시간복잡도: O(logN)

배열 내부가 정렬되어있어야만 사용가능

#include <iostream>
#include <stdlib.h>
#include <vector>
#include<cstdio>
#include<algorithm>
using namespace std;

int cnt;
vector<int> num;
int target;

int func(int left, int right) {
    if (left > right) return -1;
    int mid = (left + right) / 2;
    if (num[mid] == target) {
        return mid;
    }
    else if (num[mid] > target) {
        return func(left, mid - 1);
    }
    else {
        return func(mid + 1, right);
    }

}

int main (){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> cnt >> target;
    for (int i = 0; i < cnt; i++) {
        int tmp;
        cin >> tmp;
        num.push_back(tmp);
    }
    sort(num.begin(), num.end());
    int ans = func(0, cnt-1);
    if (ans == -1) {
        cout << "원소가 존재하지 않습니다.";
        return 0;
    }
    cout << ans+1;

}

Parametric Search (파라메트릭 서치)

최적화 문제를 결정하는 문제로 바꿔서 해결하는 기법

⇒ 결정하는 문제 = '예' '아니오'로 대답

ex ) 범위 내에서 조건을 만족하는 가장 큰 값을 찾으려는 최적화 문제라면 이진 탐색으로 결정 문제를 해결하면서 범위를 좁힐 수 있다

떡볶이 떡 자르기 문제

  • '떡볶이 떡 자르기' 문제를 예로 하면 적절한 높이를 찾을 때까지 절단기의 높이 H를 반복적으로 조정한다
  • 현재 이 높이로 자르면 조건을 만족할 수 있는가 → 예 vs 아니오
  • 범위로 좁힐 때는 이진 탐색 원리를 이용해 절반찍 좁혀나간다
#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <vector>
#include<cstdio>
#include<algorithm>
using namespace std;
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    int cnt;
    int etc;
    vector<int> rice;
    cin >> cnt >> etc;
    for (int i = 0; i < cnt; i++) {
        int tmp;
        cin >> tmp;
        rice.push_back(tmp);
    }
    int left, right;
    sort(rice.begin(), rice.end());
    left = 0;
    right = rice.back();
    int ans, mid;

    while (left < right) {
        ans = 0;
        mid = (left + right) / 2;
        for (int i = 0; i < cnt; i++) {
            int tmp = rice[i] - mid < 0 ? 0 : rice[i] - mid;
            ans += tmp;
        }
        if (ans == etc)  break;
        else if (ans < etc) {
            right = mid - 1;
        }
        else {
            // 적어도 M만큼의 떡을 얻기 위해
            result = mid;
            left = mid + 1;
        }
    }
    cout << result;

}

'Algorithm > C++' 카테고리의 다른 글

[개념] 최단 경로 구하기  (0) 2020.10.13
[개념] 다이나믹 프로그래밍(동적계획법)  (0) 2020.10.11
[개념] DFS/BFS  (0) 2020.10.09
[개념] 정렬 알고리즘  (0) 2020.10.01

정렬

  • 데이터를 특정한 기준에 따라 순서대로 나열한 것

선택정렬

  • 시간복잡도 - $O(N^2)$
  • 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두번째 데이터와 바꾸는 과정을 반복
  • 가장 작은 것을 선택
#include <iostream>
#include <stdlib.h>
#include<cstdio>
#include<algorithm>
using namespace std;

int main (){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int num[] = { 7,5,9,0,3,1,6,2,4,8 };
    // 선택 정렬
    for (int i = 0; i <10; i++) {
        int idx = i; // 가장 작은 원소 인덱스
        for (int j = i; j < 10; j++) {
            if (num[j] < num[idx]) {
                idx = j;
            }
        }
        swap(num[idx], num[i]);
    }
    for (int i = 0; i < 10; i++) {
        cout << num[i] << " ";
    }

삽입 정렬

알고리즘 문제 풀이에 사용하기엔 느림
But 정렬이되어 있는 상태로 입력이 주어지는 문제라면 다른 알고리즘을 사용하는 것보다 효율적

  • 시간 복잡도 - 최선 $O(N)$ , 최악 $O(N^2)$
  • 필요할 때만 위치를 바꿔서 '데이터가 거의 정렬 되어 있을 때' 효율적
  • 선택 정렬은 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 위치를 바꾸는 반면 삽입 정렬은 그렇지 않다
#include <iostream>
#include <stdlib.h>
#include<algorithm>
using namespace std;

int main (){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int num[] = { 7,5,9,0,3,1,6,2,4,8 };
    // 삽입 정렬
    for (int i = 1; i < 10; i++) {
        for (int j = i; j>0; j--) {
            if (num[j] < num[j - 1]) {
                swap(num[j], num[j - 1]);
            }
            else {
                break;
            }
        }
    }
    for (int i = 0; i < 10; i++) {
        cout << num[i] << " ";
    }
}

퀵 정렬

c++ STL의 algorithm 헤더에 있는 sort() 함수 ⇒ 퀵정렬

  • 시간 복잡도 - $O(NlongN)$
  • 기준을 설정한 다음 큰 수와 작은 숫자를 교환한 후 리스트를 반으로 나누는 방식
  • 피봇 : 큰 수와 작은 수를 교환 할 때, 교환하기 위한 기준을 명칭
#include <iostream>
#include <stdlib.h>
#include<cstdio>
#include<algorithm>
using namespace std;
void quickSort(int* arr, int start, int end) {
    if (start >= end) return; // 원소가 1개인 경우 종료
    int pivot = start; // 피벗은 첫 번째 원소
    int left = start + 1;
    int right = end;
    while (left <= right) {
        // 피벗보다 큰 데이터를 찾을 때까지 반복
        while (left <= end && arr[left] <= arr[pivot]) left++;
        // 피벗보다 작은 데이터를 찾을 때까지 반복
        while (right > start && arr[right] >= arr[pivot]) right--;
        // 엇갈렸다면 작은 데이터와 피벗을 교체
        if (left > right) swap(arr[pivot], arr[right]);
        // 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
        else swap(arr[left], arr[right]);
    }
    // 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
    quickSort(arr, start, right - 1);
    quickSort(arr, right + 1, end);
}

int main (){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int num[] = { 7,5,9,0,3,1,6,2,4,8 };
    // 퀵 정렬
    // 라이브러리 이용
    // sort(num, num + 10);
    // 일반 구현
    quickSort(num, 0, 9);
    for (int i = 0; i < 10; i++) {
        cout << num[i] << " ";
    }

}

계수 정렬

  • 시간복잡도 - $O(N+K)$
  • 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘
  • 데이터의 크기 범위가 제한되어 정수로 표현할 수있을 때만 사용 가능
  • 가장 큰 데이터와 작은 데이터 크기가 작아야함
#include <iostream>
#include <stdlib.h>
#include<cstdio>
#include<algorithm>
using namespace std;

int main (){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int num[] = { 7,5,9,0,3,1,6,2,4,8,0,5,2};
    int ans[13] = {0,};
    // 계수 정렬
    for (int i = 0; i < 13; i++) {
        ans[num[i]]++;
    }
    for (int i = 0; i < 10; i++) {
        if (ans[i] > 0) {
            while (ans[i]--) {
                cout << i << " ";
            }
        }
    }
}

C++ sort STL

오름차순 (default)

  • sort()는 algorithm 헤더 파일에 속함
  • 퀵 정렬이용
  • 평균 시간복잡도 - $O(NlongN)$

사용법

sort(arr, arr+1);
sort(v.begin(), v.end());
sort(v.begin(), v.end(), compare); // compare : 사용자 정의 함수
sort(v.begin(), v.end(), greater<자료형>()); // 내림차순
sort(v.begin(), v.end(), less<자료형>()); // default - 오름차순

'Algorithm > C++' 카테고리의 다른 글

[개념] 최단 경로 구하기  (0) 2020.10.13
[개념] 다이나믹 프로그래밍(동적계획법)  (0) 2020.10.11
[개념] DFS/BFS  (0) 2020.10.09
[개념] 이진탐색  (0) 2020.10.09

+ Recent posts