KOMAS

투 포인터를 이용한 문제다.

투 포인터를 둘다 시작 지점으로 놨더니

생각할게 너무 많아지고, 시간복잡도도 증가했다.

투포인터를 시작지점, 끝점으로 양쪽으로 옮겨서 구현했더니 간단하게 풀렸다.

구간합이 아니면 투포인터를 시작지점에 두지 말아야 겠다.

코드구현

[알고리즘] 플로이드 워셜 알고리즘 (Floyd Warshall Algorithm)

플로이드 워셜 알고리즘은 edge에서 edge로 이동할 때 최소비용을 구하는 알고리즘이다.

모든 경로의 최소비용을 구할 수 있다.

구현

플로이드 워셜 알고리즘의 구현은 간단하다.

k, i, j를 사용하는 3중 for문이 있을 때

3중 for문으로 가장 바깥 k를 사용하는 for문은 edge의 총개수만큼 반복한다.

k는 중간에 거쳐가는 edge이다.

i는 시작 edge, j는 도착 egde로 사용한다.

현재 비용보다 거쳐가는 비용이 더 적다면 거쳐가는 비용을 사용한다.

자기 자신으로 가는 경로는 0, 도착이 불가능한 경로는 INF(충분히 큰 값)로 표시한다.

이해

구현은 간단하지만 이해는 쉽지 않았다.

플로이드 워셜 알고리즘은 가장 바깥 for문

즉, 거쳐가는 k가 계속 증가한다고 생각하면 된다.

(경로 값이 크다면 증가하지 않겠지만, 이해를 위해 증가한다고 생각)

[거쳐가는 edge]

 시작 -> 0 -> 도착

시작 -> 0->1 -> 도착

시작 -> 0->1->2 -> 도착

시작 ->  0->1->2->3... -> N개의 edge까지 -> 도착

단순히 거쳐가는 경우가 증가하게끔 나타냈지만

 모든 순열의 경로를 알 수 있다.

시작 -> 0->1 -> 도착

시작 -> 1->0 -> 도착

시작 -> 2->4->1 -> 도착

시작 -> 1->4->2->3->5 -> 도착

...

다른예제

k는 0번 edge부터 가장 마지막 edge까지  증가하며

i 부터 j까지 가는 모든 경우를 계속 갱신한다.

예를 들어

가장 처음 0번을 거쳐가는 경우를 생각하자. (k= 0)

0번을 거치며 2번 edge에서 4번 edge의 경로는 갱신되어

2번 (시작)  ->  0번 (거쳐감)  ->  4번 (도착)

2번 -> 4번 는 현재까지의 최소비용으로 갱신되었다.

(k=1)인 경우는 잠시 제쳐두고

그다음 2번을 거쳐가는 경우를 생각하자. (k=2)

그럼 2번을 거쳐가는 경우에서

1번 (시작) -> 2번 (거쳐감) -> 4번 (도착)

을 갱신하려 할 때

보기에는 단순히 2번을 거쳐가는 것으로 보이지만 사실

2번 -> 4번은

2번 -> 0번 -> 4번 을 사용한다. 이게 현재까지의 최소비용이었기 때문이다.

dist[2][4]는 2->0->4로 update되어있다.

1번 -----------> 2번 ------(0번을 지나는 경로)------> 4번

결국, 앞에서 구한 최소 경로를 반복적으로 사용하기 때문에

보기완 달리 사실 많은 edge들을 이동하는 경로의 최소 비용을 사용하는 것이다.

https://www.acmicpc.net/problem/13418

최소 신장 트리 (MST)를 알아야 풀 수 있는 문제다.

문제는 (최대 신장 트리 - 최소 신장 트리)의 값을 요구한다.

제곱을 해줘야 하긴 하지만 사소하기 때문에

MST를 적용하면 풀 수 있는 문제다.

크루스칼, 프림 모두 적용 가능하며 크루스칼을 이용해서 해결했다.

우선순위 큐에서 최대 신장 트리, 최소 신장 트리로 정렬할 수 있도록

두 가지 방식으로 정렬하는 큐를 만들어서 

간선들을 넣어준후 크루스칼 알고리즘을 적용했다.

이 문제의 최대 주의할 점은

오르막길이 1이라고 착각할 수 있다.

오르막길은 0이다.

예제는 오르막길이 1이라고 판단해도 정답이 되기 때문에 주의해야 한다.

코드구현

https://www.acmicpc.net/problem/2252

위상정렬을 이용한 문제다.

정점 1의 간선이 정점 3에 방향그래프로 연결되어있다면 1을 처리해준 후 3을 정렬시켜 주면된다.

만약 정점 3을 향해 연결된 정점 2가 하나 더 있다면 정점 3은 정점 2 이후에 나열될 수 있다.

정점1과 정점2는 순서가 없으므로

1 -> 2 -> 3

2 -> 1 -> 3

둘다 가능하므로 나열하는 순서는 뒤바뀔 수 있다.

"자신에게 들어오는 간선이 없는 정점"을 확인하기 위해 int 배열을 만들어 준다.
ex) 0, 1, 2, 0, 0 // b에 들어오는 간선 1개, c에 들어오는 간선 2개

처음에 0인 정점을 q에 넣고, 큐를 순회하며 간선이 있다면 향하는쪽 정점을 1씩 줄여주면 된다.
정점이 0이 되면 큐에 넣는다. // 0이 될때는 딱 한번이다. inDegree 를 이미 세주었기 때문에.

코드 구현

[애드센스] AdSense 본문 페이지 중간 광고 없애기

공부한 내용을 정리할 겸 블로그를 운영 중인데,

작성한 글을 다시 보려고 할 때마다 페이지 내 중간 광고가 가독성을 굉장히 방해했다.

방문자도 마찬가지로 가독성이 좋지 않을 것이라 판단했고,

 광고 노출은 줄겠지만 가독성을 위해 중간광고는 포기하려고 한다.

노출 RPM과 관련 있는지는 모르겠다.

애드센스 페이지 내 광고 - 개요

수정 클릭

인 페이지 광고 OFF

이렇게 설정하면 더 이상 본문 페이지 내에서 중간에 광고가 삽입되지 않는다.

[학습일지] Java & SpringBoot로 시작하는 웹 프로그래밍 : 자바 인강 4주차

Java & SpringBoot로 시작하는 웹 프로그래밍 강의는 전체 분량이 8주 분량이고 이번이 4주차로 절반이 지났다.

4주차에서는 3주차에 이어서 객체에 대해서 좀 더 깊게 다룬다.

상속

자바에서 모든 클래스는 Obejct class를 상속받는다.

상속은 extends 키워드로 단 하나의 클래스만 상속 가능하다.

클래스가 생성되는 순서는 부모 클래스 -> 자손 클래스이다.

그 이유는 super 키워드 때문인데, super 키워드는 생성자 제일 상단에 위치하여 부모 클래스의 생성자를 호출한다.

자손은 부모의 필드와 메서드를 상속받지만 생성자는 상속받지 않는다.

부모 클래스는 일반적인 개념이고

자손 클래스는 부모 클래스를 좀 더 구체화한 개념이다.

main에서 Child의 생성자를 이용해서 인스턴스를 생성하면

Child class 생성자에서 super()로 Parent class의 생성자를 호출하고

Parent class 생성자에서 super()로 Object class를 호출한다.

호출 순서: main -> Child -> Parent -> Object

생성 순서: Object -> Parent -> Child -> main

super() 키워드는 항상 생성자의 첫 줄에 위치하고 있어야 하며 이는 this()와 같다.

그러므로 한 생성자에서 super()와 this()를 같이 사용하는 것은 불가능하다.

 기본 생성자와 마찬가지로 명시하지 않았다면 super()를 컴파일러가 자동으로 추가한다.

상위 클래스에 기본 생성자가 없다면 super(변수)로 명시적으로 부모 생성자를 호출해줘야 한다.

부모 클래스에는 parentMethod가 있다.

자손 클래스에는 childMethod와 부모 메서드를 재정의한 parentMethod가 있다.

Child 인스턴스의 타입이 Child라면 부모 메서드와 자손 메서드를 전부 사용할 수 있다.

이때 부모 메서드를 자손 메서드가 오버 라이딩했다면 오버 라이딩된 자손 메서드를 사용한다.

형 변환하여 타입을 부모로 바꾸게 되면 자손 메서드를 사용할 수 없게 된다.

타입이 부모이므로 자손 필드와 메서드에 접근할 수 없게 된다.

단, 부모 메서드가 오버 라이딩되어있다면 오버 라이딩된 메서드를 사용한다.

오버라이딩된 메서드를 통해 자손의 필드와 메서드에 접근하여 사용할 수 있다.

추상 클래스

추상 클래스는 추상 메서드를 1개 이상 갖고 있는 클래스이다.

추상 메서드는 구현부가 없는 메서드이다.

추상 클래스는 인스턴스화 될 수 없고 자손 클래스가 상속하여 사용한다.

상속받은 자손 클래스는 추상 메서드를 모두 구현해야 한다.

메서드 참조란 말 그대로 다른 클래스의 메소드를 참조하여 사용한다입니다.

구현부를 빌려쓴다고 이해하시면 됩니다.

함수형 인터페이스가 클래스의 메서드 구현부를 빌려서 자신이 구현한 메서드인 것처럼 사용합니다.

람다식같은 경우는 직접 개발자가 구현부를 작성하는 것이고,

메서드 참조는 클래스를 빌려 쓰는 것입니다.

코드로 설명하겠습니다.

public class ProviderClass {
    public int providerFunc1(int x, int y){
        return x + y;
    }

    public int providerFunc2(int x, int y){
        return x - y;
    }

    public static int providerFunc3(int x, int y){
        return x * y;
    }

    public static int providerFunc4(int x, int y){
        return x / y;
    }
}

ProviderClass (메서드를 제공해줄 클래스)를 정의해두었습니다.

4개의 메소드를 정의해두었습니다.

3번 메소드, 4번 메서드는 static으로 선언해두었습니다.

@FunctionalInterface
public interface FuncInterface {
    public int shell(int x, int y);
}

메서드를 참조 사용하기 위해 껍데기 메서드가 있어야 합니다.

함수명 shell로 정의해두었습니다.

함수형 인터페이스 하나를 선언해두었습니다.

FuncInterface의 shell 메서드는 ProviderClass의 메서드의 구현부를 빌려서 사용할 겁니다.

껍데기 역할을 해줄 곳은 반드시 함수형 인터페이스여야 합니다.

함수형 인터페이스란 오로지 하나의 추상 메서드만을 갖고 있는 인터페이스를 말합니다.

하나의 추상 메서드만을 갖고 있어야 하는 이유는

여러 개의 추상 메서드를 갖고 있는 인터페이스가 다른 클래스의 메서드를 빌려 쓴다면,

타입의 혼란을 야기할 수 있기 때문에 반드시 하나의 추상 메서드만 있어야 합니다.

자바에서는 함수형 인터페이스가 아니면 메서드 참조를 할 수 없도록 막아둠

자바는 이러한 함수형 인터페이스를 제네릭으로 선언해 타입을 맞춰 API로 제공해줍니다.

java.util.function.*

public class mainClass {

    public static void main(String[] args) {

        // 메소드 제공 클래스
        ProviderClass providerClassInstance = new ProviderClass();

        // 제공받는 인터페이스
        FuncInterface funcInterface1 = providerClassInstance::providerFunc1; // 인스턴스 메소드는 "변수 명"으로 사용
        FuncInterface funcInterface2 = providerClassInstance::providerFunc2;
        FuncInterface funcInterface3 = ProviderClass::providerFunc3; // static 메소드는 "클래스 명"으로 사용
        FuncInterface funcInterface4 = ProviderClass::providerFunc4;

        // 참조하여 사용
        int sum = funcInterface1.shell(30,10); // 더하기
        int sub = funcInterface2.shell(30,10); // 빼기
        int mul = funcInterface3.shell(30,10); // 곱하기 (static)
        int div = funcInterface4.shell(30,10); // 나누기 (static)

        System.out.println(sum);
        System.out.println(sub);
        System.out.println(mul);
        System.out.println(div);
    }
}

인스턴스 메서드를 사용해야 할 때는

제공 클래스의 변수명::메서드명

클래스 메서드(static)를 사용할 때는

클래스 명::static 메서드 명

함수형 인터페이스 FuncInterface가 ProviderClass의 메서드들을 참조하면서

자신의 빈 껍데기 메서드 shell()로 ProviderClass에 구현된 메서드 기능을 참조하면서 자신의 것처럼 사용할 수 있습니다.

메서드를 참조하기 위해선 매개변수 타입, 리턴 타입, 개수가 일치해야 합니다.

메서드 참조: 함수형 인터페이스를 이용해서 다른 클래스의 메서드를 빌려쓰는 것

익명 클래스는 말 그대로 클래스의 이름이 없다.

익명 클래스는 설계도가 1회성이라는 말이다.

이름이 없으므로 생성자를 구현할 수 없다.

익명 클래스를 정의하려면 상속을 받거나 인터페이스로 구현해야한다.

참조 변수에 넣어두고 재사용할 수 있다.

상위 클래스의 생성자 지정, 오버 라이딩은 가능하다.

상속을 받은 익명 클래스

상속받아서 사용할 Outer 클래스

Outer 클래스를 익명 클래스로 활용

참조변수 o는 Outer를 상속받아서 1회성 구현부를 작성하고 인스턴스를 생성한 것과 같다.

인터페이스로 구현한 익명 클래스

추상메서드 2개를 갖는 인터페이스를 정의한 후

상속과 마찬가지로 인터페이스를 익명 클래스로 구현해서 사용할 수 있다.

참조변수 ti는 TestInterface의 추상메서드들을 구현하고 인스턴스를 생성한 것과 같다.

람다식(함수형 인터페이스)

위에서 본 익명클래스들의 생성을 코드 구현을 더 짧게 하고자 하는 것이 람다식이다.

마찬가지로 람다식은 단순히 함수를 구현하는 것 같지만 사실 객체의 생성이다.

인터페이스를 구현받아서 추상메서드를 작성하고 익명 객체를 생성한 것이다.

익명 클래스의 구현을 람다식으로 바꿔줄 수 있다.

(매개변수) -> 메서드 구현부

대신, 조건으로 인터페이스는 하나의 추상 메서드만을 갖고 있어야 한다.

하나의 추상 메서드만을 갖고 있는 인터페이스를 함수형 인터페이스라 한다.

람다식은 함수형 인터페이스를 이용해서 익명 객체로 구현하는 과정을 짧게 만든 것이다.

함수형 인터페이스가 갖고 있는 하나의 추상메서드의 1회성의 구현부를 만든 후 객체를 생성한 것

자바에는 이러한 함수형 인터페이스를 미리 만들어 둔 API가 있다.

https://docs.oracle.com/en/java/javase/15/docs/api/java.base/java/util/function/package-summary.html

[JAVA] String 참조값 비교와 StringBuilder, StringBuffer 사용 이유

String에서 + 연산을 사용하면 안 되는 이유

StringBuilder, StringBuffer를 사용하는 이유

String에서 + 연산을 사용하면 메모리를 추가로 사용한다.

str1, str2 는 같은 곳을 참조함 (String pool에서의 같은 위치)

str3는 String을 + 연산을 사용해서 "abc"를 만들었는데도 String pool의 "abc"를 참조하지 않는다.

+연산을 String에서 하게 되면 String pool에서 찾지 않고 마치 new("abc")를 한 것처럼 "abc" 새로운 메모리가 생성된다.

이는 GC의 부담, 메모리의 낭비를 야기한다.

그러므로 String에서는 + 연산을 지양해야 함

== 연산자가 아닌 equals()를 사용하면 문자열은 전부 같으므로 결과는 모두 true이다.

StringBuilder, StringBuffer

StringBuilder도 내부적으로 toString()을 처리할 때 new 연산자를 사용하므로 새로운 메모리가 생성되지만,

toString()할 때 new 연산자를 단 한번 사용하기 때문에 여러 문자 결합에서 이점을 갖는다.

[JAVA] 자바 접근 제어자

자바의 접근제어자는 4종류가 있다.

                                                         public : 제한 없음

                                                         protected : 패키지 내부  //  다른 패키지여도 상속(extends) 했다면 사용 가능

                                                         defalut : 패키지 내부

                                                         private : 클래스 내부

이 중 접근제어자로 protected가 헷갈리는 경우가 많아 정리하고자 한다.

protected는 같은 패키지 내부에서 사용 가능하다. 이점은 헷갈리지 않는다.

헷갈리게 하는 부분은 다른 패키지여도 상속했다면 사용가능하다는 의미에서 헷갈린다.

결론부터 말하자면 protected는 메서드, 멤버변수에 사용가능하고

다른 패키지에서 사용하려면 protected 메서드, 멤버변수를 가진 class가 public이어야 한다.

테스트 구조도

패키지 Classtest

• (default) DefaultClass 
• (public) PublicClass

패키지 Classtest2

• MainCalss

다른 패키지에서 DefaultClass를 import할 수 없다.

default는 같은 패키지에서만 사용할 수 있기 때문이다.

이제 PublicClass를 이용해서 protected를 테스트해보자.

PublicClass의 내부는 다음과 같다.

public 변수 number1

protected 변수 number 2

다른 패키지인 MainClass에서 PublicClass를 import 후 사용을 해봤다.

protected인 number 2가 보이지 않는다.

protected는 상속해야 사용 가능하기 때문이다.

상속을 하고 나서야 number 2를 확인할 수 있다.

사용 가능한 접근제어자

Class : public, default

멤버, 메서드, 생성자 : public, protected, default, private

Class에서는 public default 밖에 사용하지 못함에 주의하자.