어플리케이션이 시작될 때 어떤 클래스가 최초 한번만 메모리를 할당하고(static) 그 메모리에 인스턴스를 만들어 사용하는 디자인 패턴이다.

즉, 메모리 낭비를 방지할 수 있고, 전역이기 때문에 다른 클래스의 인스턴스들이 데이터를 공유하기 쉽다!

구조

public class Singleton {
    // static 으로 선언하여 전역에서 단독으로 존재하는 인스턴스 보장
    private static Singleton instance;

    // private 생성자로 외부에서 객체 생성을 막음
    private Singleton() {
    }

    // 외부에서는 getInstance() 로 instance 를 반환
    public static Singleton getInstance() {
        // instance 가 null 일 때만 생성
        if (instance == null) {
            instance = new Singleton();
        }
        return instance;
    }
}

문제점

• 하지만, 공유되는 객체기 때문에 멀티 쓰레드 환경에서 Race Condition이 발생할 수 있다. (syncronized 키워드로 락을 걸어서 해결할 수 있지만, 마치 멀티쓰레드가 싱글쓰레드 처럼 동작이 되므로 효울이 매우 안좋아짐..)
• instance = new Singleton(); 처럼 구체 클래스에 의존하게 되므로, DIP와 OCP 원칙을 위반하게 되어 유연성이 매우 떨어진다.
• 테스트하기가 불편하다. 싱글톤 인스턴스는 공유되기 때문에, 테스트 환경에서 격리해서 쓰기 위해서는 매번 인스턴스의 상태를 초기화 시켜주어야한다.

스프링 싱글톤

스프링 컨테이너에서는 싱글턴 패턴을 적용하지 않아도 등록한 스프링 빈을 싱글톤으로 관리한다. 이러한 기능 덕분에 싱글톤 패턴의 모든 단점을 해결하고 객체를 싱글톤으로 유지할 수 있다.

싱글톤을 어떻게 보장하지?

• 스프링에서 defalut로 프록시 객체를 생성해주는 방식인 CGLIB이 해준다.
• @Configuration이 붙은 클래스에 속한 @Bean들을 등록할 때 프록시 CGLIB 클래스가 내부 로직을 구현하여, 싱글톤 패턴을 적용해서 스프링 빈으로 등록한다.

Stateful 싱글톤 객체

스프링 컨테이너에서 싱글톤으로 관리된다고 하여도, 만약 객체의 상태가 유지된다면(Stateful) thread-safe 하지 못하게된다. 즉, 무상태(Stateless)로 설계되어야 한다.

public class StatefulService {

    private int price; //상태를 유지하는 필드

    public void order(String name, int price) {
        this.price = price; //특정 클라이언트에 의해 상태값이 변경된다.
    }

    public int getPrice() {
        return price;
    }
}

StatefulService statefulService1 = ac.getBean("statefulService", StatefulService.class);
StatefulService statefulService2 = ac.getBean("statefulService", StatefulService.class);

//ThreadA : A사용자 10000원 주문
statefulService1.order("userA",10000);
//ThreadB : B사용자 20000원 주문
statefulService2.order("userB",20000);

//ThreadA : 사용자 A주문 금액 조회
int price = statefulService1.getPrice();
//ThreadA : 사용자 A는 10000원 기대했지만, 기대와 다르게 20000원 출력

→ 공유하는 필드가 있으면 안된다!!! (상태가 유지됨)

→ 특정 클라이언트가 값을 변경할 수 있는 필드가 있으면 안된다.

동시성을 어떻게 해결하지?

→ 스프링에서는 보통 불변 객체를 빈으로 등록하여 방지한다던가, 가변 객체가 존재하더라도 synchronized 키워드나 concurrent 패키지의 클래스들을 사용하여 동시성 문제를 해결했을 것이다. 또한 스프링 빈 사이의 데이터를 주고받을 때에는 스프링 빈의 상태를 변경 시키는 것이 아니라 메소드의 파라미터를 이용했을 것이다. 즉, 스프링이 지향하는 객체지향적 관행을 따라하다 보니 자연스럽게 Thread-safe하게 개발이 된다.

Reference

https://tecoble.techcourse.co.kr/post/2020-11-07-singleton/

https://alwayspr.tistory.com/11

https://velog.io/@syleemk/Spring-Core-싱글톤-컨테이너

https://velog.io/@lshn1007/Spring-11-싱글톤-컨테이너-CGLIB

• Factory 패턴은 객체 생성 역할을 별도의 클래스 (Factory) 에게 위임하는 것이 가장 궁극적인 목표

  → 클래스간 결합도(의존성)를 낮춤으로써 객체지향적 설계

• 디자인 패턴 중 Factory 와 관련된 패턴은 팩토리 메서드 패턴과 추상 팩토리 패턴이 존재함

• 이 두 가지 패턴의 베이스가 되는 가장 단순한 형태가 Simple Factory 패턴

Simple Factory 패턴

public interface Phone {
}

public class Iphone implements Phone {
}

public class Galaxy implements Phone {
}

Phone iphone = new Iphone();
Phone galaxy = new Galaxy();

객체는 여러 곳에서 생성될 수 있는데, 호출하는 쪽이 객체의 생성자에 직접 의존하고 있으면 나중에 요구사항이 변경되었을 때 호출 코드가 모두 직접 수정되어야 하는 경우가 많이 발생하게된다.

public interface Phone {
    enum Type {
        IPHONE, GALAXY
    }
}

public class PhoneFactory {

    public Phone createPhone(Phone.Type phoneType) {
        switch (phoneType) {
            case IPHONE:
                return new Iphone();
            case GALAXY:
                return new Galaxy();
            default:
                throw new IllegalArgumentException("Phone 타입이 아닙니다");
        }
    }
}

PhoneFactory phoneFactory = new PhoneFactory();
Phone iphone = phoneFactory.createPhone(Phone.Type.IPHONE);
Phone galaxy = phoneFactory.createPhone(Phone.Type.GALAXY);

그래서 생성자 호출 (new) 을 별도의 클래스 (Factory) 에서 담당하고 호출 코드에서는 팩토리를 통해 객체를 생성한다.

→ PhoneFactory를 선언한 후 생성 메서드만 호출하면 실제 구현 클래스인 Iphone, Galaxy에 의존하지 않은 코드를 작성할 수 있게 된다!

→ 하지만 새로운 phone 클래스로 Zplip 이 추가된다면 PhoneFactory 내부를 수정해야하므로, 기존 코드에 영향을 주지 않는 것을 지향하는 객체지향 원칙을 지키기 힘들다. (OCP 원칙)

Factory Method 패턴

public interface Phone {
    void register();
}

public class Iphone implements Phone {
    @Override
    public void register() {
        System.out.println("아이폰 유저 입니다."); // iphone 전용 로직
    }
}

public abstract class PhoneFactory {

    public Phone newInstance() {
        Phone phone = createPhone();
        phone.register();
        return phone;
    }

    protected abstract Phone createPhone();
}

public class IphoneFactory extends PhoneFactory {
    @Override
    protected Phone createPhone() {
        return new Iphone();
    }
}

public class ZFlipFactory extends PhoneFactory {
    @Override
    protected Phone createPhone() {
        return new ZFlip();
    }
}

팩토리를 추상 클래스로 정의하여, 실제로 어떤 객체를 생성할 지는 추상 메서드로 정의해서 하위 클래스에서 정의

PhoneFactory phoneFactory = new IphoneFactory();
Phone phone = phoneFactory.newInstance();

• 호출 코드에서 Iphone 클래스에 대한 의존성 없이 사용 가능
• 의존성 주입을 사용해서 외부에서 Factory 클래스를 받아온다면 PhoneFactory 에 대한 의존성도 제거 가능

→ 새로운 phone 클래스로 Zplip 이 추가될때, 기존 코드의 변경 없이 phone 인터페이스와 ZplipPhoneFactory 를 새로 정의하여 확장 가능

→ 확장때마다 많은 클래스를 정의하여야 하기 때문에 코드량이 증가한다는 단점이 있음

Abstract method 패턴

public interface PhonePartsFactory {
    Cpu createCpu();
    Speaker createSpeaker();
}

서로 연관된 또는 의존적인 객체(parts)들을 모아서 인터페이스로 제공함. 각 phone 클래스(서브 클래스)에서는 parts 들을 오버라이딩하여 사용!

→ 팩토리 메서드 패턴과 비슷하지만 공통된 집합을 모아둔다는 점이 특징임

Reference

https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/DesignPattern

https://bcp0109.tistory.com/367

https://school.programmers.co.kr/learn/courses/30/lessons/70129

문제 설명

0과 1로 이루어진 어떤 문자열 x에 대한 이진 변환을 다음과 같이 정의합니다.

1. x의 모든 0을 제거합니다.
2. x의 길이를 c라고 하면, x를 "c를 2진법으로 표현한 문자열"로 바꿉니다. 예를 들어, x = "0111010"이라면, x에 이진 변환을 가하면 x = "0111010" -> "1111" -> "100" 이 됩니다.

0과 1로 이루어진 문자열 s가 매개변수로 주어집니다. s가 "1"이 될 때까지 계속해서 s에 이진 변환을 가했을 때, 이진 변환의 횟수와 변환 과정에서 제거된 모든 0의 개수를 각각 배열에 담아 return 하도록 solution 함수를 완성해주세요.

입출력 예

문제 풀이

이진법 변환만 하면 쉬운 문제. counter로 문자열 내 문자 갯수 세어봤따.

맞은 코드

from collections import Counter

def solution(s):
    nowS = s
    cntChange, cntZero = 0, 0
    while nowS != "1":
        zero = Counter(nowS)["0"]
        nowS = bin(len(nowS) - zero)[2:]
        cntZero += zero    
        cntChange += 1
    answer = [cntChange, cntZero]
    return answer

어떠한 프로그램 내에서, 특히 프로세스 내에서 실행되는 흐름의 단위를 말한다.

스레드는 CPU 활용의 기본 단위로, 프로그램 카운터, 스택, 레지스터들, 그리고 스레드 ID로 구성되어있음

• 프로그램 카운터 - 다음에 실행될 명령어의 주소 (register 안에 있음!)
• 스택 - 변수나 주소를 저장하는 공간
• 레지스터

싱글 스레드 프로세스는 한 개의 레지스터와 스택을 가진다.

하지만, 멀티 스레드 프로세스에서는 code, data, file은 공유하지만 각 스레드가 레지스터와 스택은 따로 사용한다고 한다.

→ 각 스레드가 독립적인 프로그램 카운터(레지스터)와 스택을 가지면서 자신만의 실행 흐름을 가질 수 있게 되고, 동시에 한 프로세스에서 여러 작업을 처리할 수 있게 된다.

장점

• Concurrency를 얻을 수 있다.
• 스레드 몇개가 죽어도 정상작동한다.
• 같은 메모리를 공유하므로, 자원 분배가 효과적이다.

단점

• 동기화로 스레드간 자원 접근이나 처리 순서를 제어할 수 있는데, 잘못 lock을 걸었다간 오히려 성능이 안좋아질 수 있다. -> 프로세스 동기화 참고
• 스레드를 생성하는 시간이 오버헤드가 될 수 있다.

스레드 풀

단점에 있던 스레드 생성 시간 문제를 해결하기 위해서 미리 스레드를 만들어두는 방법

Node.js는 싱글 스레드

node는 싱글 스레드로 동작한다고 알려져 있습니다. (싱글스레드 논블로킹)

우리가 앞서 본 바에 따르면 싱글 스레드 프로세스에서는 한 번에 한개의 작업만 수행할 수 있는것으로 보이는데, nodejs는 어떻게 싱글 스레드 프로세스에서 여러 작업을 동시에 수행 할 수 있었을까요?!

그 이유는 노드가 논블로킹 IO를 지원하기 때문인데요!

노드에서는 Libuv를 사용해 IO를 백그라운드에서 처리하고 그 결과를 받아 처리합니다. → libuv는 멀티스레드로 작동한다고 한다.

동기/비동기, block / non-block 참고!

Reference

https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/OS#%EB%A9%80%ED%8B%B0-%EC%8A%A4%EB%A0%88%EB%93%9C

https://velog.io/@daeseongkim/Node.js-Node.js%EB%8A%94-%EC%8B%B1%EA%B8%80-%EC%8A%A4%EB%A0%88%EB%93%9C

https://school.programmers.co.kr/learn/courses/30/lessons/86052

문제 설명

각 칸마다 S, L, 또는 R가 써져 있는 격자가 있습니다. 당신은 이 격자에서 빛을 쏘고자 합니다. 이 격자의 각 칸에는 다음과 같은 특이한 성질이 있습니다.

• 빛이 "S"가 써진 칸에 도달한 경우, 직진합니다.
• 빛이 "L"이 써진 칸에 도달한 경우, 좌회전을 합니다.
• 빛이 "R"이 써진 칸에 도달한 경우, 우회전을 합니다.
• 빛이 격자의 끝을 넘어갈 경우, 반대쪽 끝으로 다시 돌아옵니다. 예를 들어, 빛이 1행에서 행이 줄어드는 방향으로 이동할 경우, 같은 열의 반대쪽 끝 행으로 다시 돌아옵니다.

당신은 이 격자 내에서 빛이 이동할 수 있는 경로 사이클이 몇 개 있고, 각 사이클의 길이가 얼마인지 알고 싶습니다. 경로 사이클이란, 빛이 이동하는 순환 경로를 의미합니다.

예를 들어, 다음 그림은 격자 ["SL","LR"]에서 1행 1열에서 2행 1열 방향으로 빛을 쏠 경우, 해당 빛이 이동하는 경로 사이클을 표현한 것입니다.

이 격자에는 길이가 16인 사이클 1개가 있으며, 다른 사이클은 존재하지 않습니다.

격자의 정보를 나타내는 1차원 문자열 배열 grid가 매개변수로 주어집니다. 주어진 격자를 통해 만들어지는 빛의 경로 사이클의 모든 길이들을 배열에 담아 오름차순으로 정렬하여 return 하도록 solution 함수를 완성해주세요.

제한사항

• 1 ≤ grid의 길이 ≤ 500
• 1 ≤ grid의 각 문자열의 길이 ≤ 500
• grid의 모든 문자열의 길이는 서로 같습니다.
• grid의 모든 문자열은 'L', 'R', 'S'로 이루어져 있습니다.

입출력 예

grid    result
["SL","LR"]    [16]
["S"]    [1,1,1,1]
["R","R"]    [4,4]

문제 풀이

네 방향의 사이클을 전부 판별하기 위해, 각 좌표의 네 방향을 방문했는지 상태를 들고 있는 visitDirGrid를 만들고, 한 사이클을 DFS로 돌았따.

좌표가 넘어갈땐 % 처리를 해주고, 방향을 회전할때는 순서대로 dx & dy를 지정해야 편하다

맞은 코드

import sys
sys.setrecursionlimit(10**6)

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

def DFS(x, y, dir, cnt, grid):
    global ans
    ans = cnt

    nx = (dx[dir] + x) % m
    ny = (dy[dir] + y) % n

    if grid[ny][nx] == 'L':
        ndir = (dir+1) % 4
    elif grid[ny][nx] == 'R':
        ndir = (dir-1) % 4
    else:
        ndir = dir

    if not visitDirGrid[ny][nx][ndir]:
        visitDirGrid[ny][nx][ndir] = True
        DFS(nx, ny, ndir, cnt+1, grid)

def solution(grid):
    global sum, n, m, visitDirGrid, ans
    answer = []
    n = len(grid)
    m = len(grid[0])
    visitDirGrid = [[[False] * 4 for i in range(m)] for i in range(n)]
    for i in range(n):
        for j in range(m):
            for dir in range(4):
                if not visitDirGrid[i][j][dir]:
                    ans = 0
                    visitDirGrid[i][j][dir] = True
                    DFS(j,i,dir,1,grid)
                    answer.append(ans)
    answer.sort()
    return answer

공유된 자원을 여러 프로세스(스레드)가 동시에 접근할때, 접근하는 순서에 따라서 결과가 달라질 수 있는 상태를 의미한다.

Critical Section (임계 구역)

코드 내에서 위의 Race Condition이 발생할 수 있는 영역을 Critical Section 이라고 한다.

이 문제(Critical Section)를 해결하기 위해서는 다음 조건 모두를 만족해야한다.

i) Mutual Exclusion (상호 배제)

어떤 한 프로세스가 공유된 자원을 접근해 사용중일 경우, 다른 프로세스는 이 자원에 접근해서는 안된다.

ii) Progress (진행)

Critical Section에 접근해있는 프로세스가 없는 경우(Mutual Exclusion에 해당하지 않는 경우)에 해당 섹션에 접근하려는 프로세스가 생기면 그 프로세스는 자원에 접근할 수 있어야 한다. (선택이 연기될 수 없으며, 진입 요청한 프로세스들로만 순서가 결정되어야 한다)

iii) Bounded Waiting (한정 대기)

한 프로세스가 Critical Section에 접근하고자 요청을 한 후 그 요청이 수락될 떄까지 다른 프로세스가 이 임계구역에 접근할 수 있는 횟수가 제한되어야함.

ex) 프로세스 A가 C자원을 사용중이다가, B가 요청을 하고 대기하고 있는데 또 A가 C자원을 요청해서 계속 자원을 붙잡으려고 하는 경우 B는 영원히 자원에 접근할 수 없는 상태가 될 수 있음

Synchronization Algorithms

Mutex (Mutual Exclusion)

Lock, Unlock을 Atomic한 객체로 두어서 자원을 점유하고있는지에 대한 상태를 가지고 있고, 점유하고있는 경우 접근을 제한한다.

그림과 마찬가지로 락이 걸려있는 상태이면 while에 의해서 무한 대기하고, 그게 아닌 경우 락을 잠그게끔 되어있다.

하지만 그림과 같은 무한대기는 CPU의 자원을 낭비하고 그로 인한 지속적인 Context Switching이 발생하기에 유용하지는 않은 방법이다.

Semaphores (세마포어)

Counter형태의 변수 S로 동시에 접근 가능한 프로세스를 제안하는 방식으로, Mutex방식과의 차이는 여러 프로세스가 동시에 대기하고 그 수를 관리할 수 있다는 점이다.

물론 Mutex와 같이 이 무한대기 방법은 CPU의 자원을 낭비하기에,

다음과 같이 스레드/프로세스 자체를 블로킹시켜서 대기하게끔 하고 그 후 접근 가능한 시점에서 깨워주는 방식으로 주로 사용된다.

Mutex와 다르게, 동기화를 위해 wait와 signal이라는 2개의 Atomic 동작을 이용하여, 락을 걸지 않은 쓰레드도 signal을 보내 락을 해제할 수 있다는 차이점이 있다.

Reference

https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/OS#%ED%94%84%EB%A1%9C%EC%84%B8%EC%8A%A4-%EB%8F%99%EA%B8%B0%ED%99%94 https://mangkyu.tistory.com/104

https://school.programmers.co.kr/learn/courses/30/lessons/77885?language=python3

문제 설명

양의 정수 x에 대한 함수 f(x)를 다음과 같이 정의합니다.

• x보다 크고 x와 비트가 1~2개 다른 수들 중에서 제일 작은 수

예를 들어,

• f(2) = 3 입니다. 다음 표와 같이 2보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 3이기 때문입니다.

  수    비트    다른 비트의 개수
  2    000...0010    
  3    000...0011    1

• f(7) = 11 입니다. 다음 표와 같이 7보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 11이기 때문입니다.

  수    비트    다른 비트의 개수
  7    000...0111    
  8    000...1000    4
  9    000...1001    3
  10    000...1010    3
  11    000...1011    2

  정수들이 담긴 배열 numbers가 매개변수로 주어집니다. numbers의 모든 수들에 대하여 각 수의 f 값을 배열에 차례대로 담아 return 하도록 solution 함수를 완성해주세요.

제한사항 1 ≤ numbers의 길이 ≤ 100,000 0 ≤ numbers의 모든 수 ≤ 1015 입출력 예

numbers    result
[2,7]    [3,11]

문제 풀이

1차 시도

def solution(numbers):
    answer = []
    for number in numbers:
        numTwoBit = bin(number)[2:]
        temp = number + 1
        while True:
            tempTwoBit = bin(temp)[2:]
            sum = 0
            if len(tempTwoBit) != len(numTwoBit):
                numTwoBit = '0' + numTwoBit

            for i in range(len(numTwoBit)):
                if numTwoBit[i] != tempTwoBit[i]:
                    sum += 1
                if sum > 2:
                    break
            else:
                answer.append(temp)
                break
            temp += 1
    return answer

맘편하게 브루트 포스로 풀었다가 시간초과 당했다 !

생각해보니까 홀짝으로 나눠 생각할 수 있었다

• 짝수면 끝 비트가 0이니 단순 +1을 해준다

• 홀수라면 끝 비트가 1이니 오른쪽에서 부터 0을 찾아서 1로 바꾸고, 그 바로 뒤는 0으로 바꿔주면, 최소 수가 되는 것을 알수 있다

  맞은 코드

  def solution(numbers):
    answer = []
    for number in numbers:
        if number % 2 == 0:
            answer.append(number+1)
        else:
            numTwoBit = '0' + bin(number)[2:]
            idx = numTwoBit.rfind('0')
            st = ""
            for i in range(len(numTwoBit)):
                if i == idx:
                    st += "1"
                elif i == idx+1:
                    st += "0"
                else:
                    st += numTwoBit[i]
            ans = int(st,2)
            answer.append(ans)
  
    return answer

11886번 - 요세푸스 문제 0

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

n, k = map(int,input().split())
arr = []
for i in range(n):
  arr.append(i+1)

now = 0
print("<", end="")
while arr:
  now += k - 1
  now %= len(arr)
  temp = arr.pop(now)
  if not arr:
    print(str(temp) + ">")
  else:
    print(str(temp) + ", ", end="")

1009번 - 분산 처리

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

t = int(input())
for _ in range(t):
  a, b = map(int,input().split())
  arr = []
  temp = a % 10
  arr.append(temp)
  while True:
    temp *= a
    if temp % 10 in arr:
      break
    else:
      temp = temp % 10
      arr.append(temp)
  ans = arr[(b-1) % len(arr)]
  if ans == 0:
    print(10)
  else:
    print(ans)

주로 멀티 스레드, I/O 등에서 사용되는 개념이며, 함수의 리턴 시점 및 제어권이 관심사다.

→ 어떠한 작업이 진행중일때 다른 작업을 동시에 진행할 수 있냐 ?

Blocking

• 제어권이 호출된 함수에게 넘어가서 호출된 함수 내에서 작업이 모두 끝난 후 호출한 함수에게 다시 제어권이 넘어온다.
• 작업이 완료된 후에야 새로운 작업을 수행할 수 있다.
• ex. Spring Boot는 Block I/O + 멀티 쓰레드

Non-Blocking

• 제어권이 계속 호출한 함수에 있기 때문에 작업의 완료여부와 관계없이 새로운 작업을 수행할 수 있다.
• ex. Node.js는 Non-Block I/O + 싱글 쓰레드

Synchronous / Asynchronous

주로 어플리케이션에서 자주 다뤄지는 개념이며, 다음 작업이 요청되는 시간이 관심사다.

→ 프로세스 간 작업의 흐름이 순차적이냐 ?

Synchronous(동기)

• 현재 작업의 응답이 끝남과 동시에 다음 작업이 요청된다.
• 함수를 호출하는 곳에서 호출되는 함수가 결과를 반환할 때까지 기다린다.
• 그렇기 때문에 작업 완료 여부를 계속해서 확인한다.

Asynchronous(비동기)

• 현재 작업의 응답이 끝나지 않은 상태에서도 다음 작업이 요청된다.
• 함수를 호출하는 곳에서 결과를 기다리지 않고, 다른 함수(callback)에서 결과를 처리한다.
• 그렇기 때문에 작업 완료 여부를 계속해서 확인하지 않는다.

Blocking vs Synchronous ??

그래서 뭐가 다른거야???

상위 프로세스 boss 함수와 하위 프로세스 employee 함수로 예를 들어 보자.

Synchronous(동기) + Blocking

function employee () {
  for (let i = 1; i < 101; i++) {
    console.log(`직원: 인형 눈알 붙히기 ${i}번 수행`);
  }
}

function boss () {
  console.log('사장: 출근');
  employee();
  console.log('사장: 퇴근');
}

boss();

사장: 출근
직원: 인형 눈알 붙히기 1번 수행
직원: 인형 눈알 붙히기 2번 수행
...
직원: 인형 눈알 붙히기 100번 수행
사장: 퇴근

• 동기 방식이기 때문에 작업의 흐름이 순차적으로 진행되는 것이 보장된다.
• 블로킹 방식이기 때문에 어떠한 작업이 진행중일때는 다른 작업을 동시에 진행할 수 없다.

Synchronous(동기) + Non-Blocking

function* employee () {
  for (let i = 1; i < 101; i++) {
    console.log(`직원: 인형 눈알 붙히기 ${i}번 수행`);
    yield;
  }
  return;
}

function boss () {
  console.log('사장: 출근');

  const generator = employee();
  let result = {};

  while (!result.done) {
    result = generator.next();
    console.log(`사장: 유튜브 시청...`);
  }

  console.log('사장: 퇴근');
}

boss();

사장: 출근
직원: 인형 깔알 붙히기 1번 수행
사장: 유튜브 시청...
직원: 인형 눈알 붙히기 2번 수행
사장: 유튜브 시청...
...
직원: 인형 눈알 붙히기 100번 수행
사장: 유튜브 시청...
사장: 퇴근

JavaScript의 제너레이터를 사용하여, 작업의 순서를 지키면서도 상위 프로세스(boss)가 다른 작업을 하도록 만들었다.

• 동기 방식이기 때문에 작업의 흐름이 순차적으로 진행되는 것이 보장된다.
• 논블로킹 방식이기 때문에 어떠한 작업이 진행중이어도 다른 작업을 수행할 수 있다.

Asynchronous(비동기) + Non-Blocking

function employee (maxDollCount = 1, callback) {
  let dollCount = 0;
  const interval = setInterval(() => {
    if (dollCount > maxDollCount) {
      callback();
      clearInterval(interval);
    }
    dollCount++;
    console.log(`직원: 인형 눈알 붙히기 ${dollCount}번 수행`);
  }, 10);
}

function boss () {
  console.log('사장: 출근');
  employee(100, () => console.log('직원: 눈알 결산 보고'));
  console.log('사장: 퇴근');
}

boss();

사장: 출근
사장: 퇴근
직원: 인형 눈알 붙히기 1번 수행
직원: 인형 눈알 붙히기 2번 수행
...
직원: 인형 눈알 붙히기 100번 수행
직원: 눈알 결산 보고

사장은 직원이 일이 끝나기도 전에 퇴근해버렸다. 그 후 직원의 일이 끝나고, 사장에게 보고했다.

• 비동기 방식이기 때문에 작업의 흐름이 순차적으로 진행되는 것을 보장하지 않는다.

  → 상위 프로세스(boss)는 하위 프로세스(employee)의 작업이 언제 끝나는지 관심 없음

• 논블로킹 방식이기 때문에 어떠한 작업이 진행중이어도 다른 작업을 수행할 수 있다.

비동기 & 논블로킹 방식은 여러 개의 작업을 동시에 처리할 수 있는 부분에서 효율적이라고 할 수 있지만, 너무 복잡하게 얽힌 비동기 처리 때문에 개발자가 어플리케이션의 흐름을 읽기 어려워지는 등의 문제가 있을 수 있다. JavaScript에서 Promise나 async/await와 같은 문법을 사용하는 이유도 이런 비동기 처리의 흐름을 좀 더 명확하게 인지하고자 하는 노력인 것이다.

Asynchronous(비동기) + Blocking

일반적으로 어플리케이션 레이어에서 자주 사용되지 않기도 하고, 평소에 접하기 힘든 개념이라고 한다.

이 방식은 블록킹 방식으로 진행되기 때문에 개발자에게도 직관적으로 다가오고, 비동기 방식이기 때문에 여러 개의 I/O를 동시에 감시하며 처리할 수 있다. 하지만 성능이 그렇게 좋은 편은 아니므로 IBM에서는 높은 성능이 필요한 어플리케이션에서는 되도록 쓰지 말라고 한다.

Blocking-Async는 별다른 장점이 없어서 일부러 사용할 필요는 없지만,

NonBlocking-Async 방식을 쓰는데 그 과정 중에 하나라도 Blocking으로 동작하는 놈이 포함되어 있다면 의도하지 않게 Blocking-Async로 동작할 수 있다.

Reference

https://cotak.tistory.com/136

https://evan-moon.github.io/2019/09/19/sync-async-blocking-non-blocking/#동기-방식--논블록킹-방식

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

문제 설명

N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다.

아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.

아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.

아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다.

더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다. 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다. 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다. 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다. 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다. 아기 상어의 이동은 1초 걸리고, 물고기를 먹는데 걸리는 시간은 없다고 가정한다. 즉, 아기 상어가 먹을 수 있는 물고기가 있는 칸으로 이동했다면, 이동과 동시에 물고기를 먹는다. 물고기를 먹으면, 그 칸은 빈 칸이 된다.

아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다. 예를 들어, 크기가 2인 아기 상어는 물고기를 2마리 먹으면 크기가 3이 된다.

공간의 상태가 주어졌을 때, 아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구하는 프로그램을 작성하시오.

입력 첫째 줄에 공간의 크기 N(2 ≤ N ≤ 20)이 주어진다.

둘째 줄부터 N개의 줄에 공간의 상태가 주어진다. 공간의 상태는 0, 1, 2, 3, 4, 5, 6, 9로 이루어져 있고, 아래와 같은 의미를 가진다.

0: 빈 칸 1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기 9: 아기 상어의 위치 아기 상어는 공간에 한 마리 있다.

출력 첫째 줄에 아기 상어가 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간을 출력한다.

문제 풀이

1차시도

from collections import deque

n = int(input())
graph = []
sharkPower = 2
nowEat = 0
nowSharkX, nowSharkY = 0, 0
ans = 0

# 위, 왼쪽 순서
dx = [0, -1, 1, 0]
dy = [-1, 0, 0, 1]

for i in range(n):
  temp = list(map(int,input().split()))
  graph.append(temp)
  for j, elem in enumerate(temp):
    if elem == 9:
      nowSharkX, nowSharkY = j, i

def BFS():
  global nowEat, nowSharkX, nowSharkY
  q = deque()
  q.append((nowSharkX,nowSharkY,0))
  visit = [[False] * n for _ in range(n)]
  visit[nowSharkY][nowSharkX] = True
  graph[nowSharkY][nowSharkX] = 0
  while q:
    nowX, nowY, time = q.popleft()
    for i in range(4):
      nx = dx[i] + nowX
      ny = dy[i] + nowY
      if nx >= 0 and ny >= 0 and nx < n and ny < n:
        if not visit[ny][nx]:
          if graph[ny][nx] == 0 or graph[ny][nx] == sharkPower:
            q.append((nx,ny,time+1))
            visit[ny][nx] = True
          elif graph[ny][nx] < sharkPower:
            graph[ny][nx] = 9
            nowSharkX, nowSharkY = nx, ny
            nowEat += 1
            return time+1
  return -1

while True:
  for i in range(n):
    for j in range(n):
      print(graph[i][j], end=" ")
    print("")
  #print(sharkPower)
  print(ans)
  print("")
  if sharkPower == nowEat:
    sharkPower += 1
    nowEat = 0
  ret = BFS()
  if ret == -1:
    break
  else:
    ans += ret

print(ans)

맞왜틀.... 하다가 보니까, (0,2)에서 (0,4)로 가지 못하고, (1,1)로 가버렸다! 단순 위,왼,오른,아래 순서로만 bfs했을때, (0,4)에 도달하기전에 (1,1)로 먼저 도달해버리는 문제였다.

즉, 최단 거리 큐에서 한번 더 위/왼쪽 방향의 비교가 필요했다.

bfs 이해가 모자랐다,,(dx,dy로 위/아래 순서를 정했을때 무조건 최단거리가 될거라 생각)

맞왜틀? print 찍어서 잘 트래킹 해보자

맞은 코드

from collections import deque

n = int(input())
graph = []
sharkPower = 2
nowEat = 0
nowSharkX, nowSharkY = 0, 0
ans = 0

# 위, 왼쪽 순서
dx = [0, -1, 1, 0]
dy = [-1, 0, 0, 1]

for i in range(n):
  temp = list(map(int,input().split()))
  graph.append(temp)
  for j, elem in enumerate(temp):
    if elem == 9:
      nowSharkX, nowSharkY = j, i

def BFS():
  global nowEat, nowSharkX, nowSharkY
  q = deque()
  q.append((nowSharkX,nowSharkY,0))
  visit = [[False] * n for _ in range(n)]
  visit[nowSharkY][nowSharkX] = True
  graph[nowSharkY][nowSharkX] = 0
  temp = []
  eatFlag = 0
  while q:
    nowX, nowY, time = q.popleft()
    for i in range(4):
      nx = dx[i] + nowX
      ny = dy[i] + nowY
      if nx >= 0 and ny >= 0 and nx < n and ny < n:
        if not visit[ny][nx]:
          if graph[ny][nx] == 0 or graph[ny][nx] == sharkPower:
            q.append((nx,ny,time+1))
            visit[ny][nx] = True
          elif graph[ny][nx] < sharkPower:
            eatFlag = 1
            temp.append((nx,ny,time+1))

  if not eatFlag:
    return (-1,-1,-1)
  else:
    #print(temp)
    temp.sort(key=lambda x:(x[2],x[1],x[0]))
    #print(temp)
    return (temp[0])

while True:
  if sharkPower == nowEat:
    sharkPower += 1
    nowEat = 0
  ret = BFS()
  nowSharkX, nowSharkY, cnt = ret[0], ret[1], ret[2]
  if cnt == -1:
    break
  else:
    ans += cnt
    nowEat += 1
    graph[nowSharkY][nowSharkX] = 9

print(ans)

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

문제 설명

N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다.

오늘부터 인구 이동이 시작되는 날이다.

인구 이동은 하루 동안 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.

국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루 동안 연다. 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다. 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다. 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다. 연합을 해체하고, 모든 국경선을 닫는다. 각 나라의 인구수가 주어졌을 때, 인구 이동이 며칠 동안 발생하는지 구하는 프로그램을 작성하시오.

입력 첫째 줄에 N, L, R이 주어진다. (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100)

둘째 줄부터 N개의 줄에 각 나라의 인구수가 주어진다. r행 c열에 주어지는 정수는 A[r][c]의 값이다. (0 ≤ A[r][c] ≤ 100)

인구 이동이 발생하는 일수가 2,000번 보다 작거나 같은 입력만 주어진다.

출력 인구 이동이 며칠 동안 발생하는지 첫째 줄에 출력한다.

문제 풀이

1차 시도

n, l, r = map(int, input().split())
graph = []

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

for _ in range(n):
  graph.append(list(map(int, input().split())))

def DFS(x, y, visit, group):
  for i in range(4):
    newX = x + dx[i]
    newY = y + dy[i]
    if newX >= 0 and newY >= 0 and newX < n and newY < n:
      if not visit[newY][newX] and abs(graph[newY][newX] - graph[y][x]) >= l and abs(graph[newY][newX] - graph[y][x]) <= r :
        group.append((newX, newY))
        visit[newY][newX] = True
        DFS(newX, newY, visit, group)

ans = 0

while True:
  visit = [[False] * n for _ in range(n)]
  groups = []
  for i in range(n):
    for j in range(n):
      if not visit[i][j]:
        group = []
        group.append((j, i))
        visit[i][j] = True
        DFS(j, i, visit, group)
        groups.append(group)
  #print(groups)

  if len(groups) == n ** 2:
    break

  ans += 1

  for g in groups:
    sum = 0
    cnt = 0
    for x, y in g:
      sum += graph[y][x]
      cnt += 1
    movePeople = sum // cnt
    for x, y in g:
      graph[y][x] = movePeople

  #print(graph)
  #break

print(ans)

전체 그래프를 훑으며 연합을 구성하고, 인구이동을 시켜줬다.

recursion error가 떠버렸다... 근데 그래프를 훑을때 왜 dfs를 썼지? 재귀에러면 그냥 bfs를 쓰면 되지 않을까?

맞은 코드

from collections import deque

n, l, r = map(int, input().split())
graph = []

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

for _ in range(n):
  graph.append(list(map(int, input().split())))

def BFS(x, y, visit, group):
  q = deque()
  q.append((x, y))
  while q:
    nowX, nowY = q.popleft()
    for i in range(4):
      newX = nowX + dx[i]
      newY = nowY + dy[i]
      if newX >= 0 and newY >= 0 and newX < n and newY < n:
        if not visit[newY][newX] and abs(graph[newY][newX] - graph[nowY][nowX]) >= l and abs(graph[newY][newX] - graph[nowY][nowX]) <= r:
          group.append((newX, newY))
          visit[newY][newX] = True
          q.append((newX, newY))

ans = 0

while True:
  visit = [[False] * n for _ in range(n)]
  groups = []
  for i in range(n):
    for j in range(n):
      if not visit[i][j]:
        group = []
        group.append((j, i))
        visit[i][j] = True
        BFS(j, i, visit, group)
        groups.append(group)

  if len(groups) == n ** 2:
    break

  ans += 1

  for g in groups:
    sum = 0
    cnt = 0
    for x, y in g:
      sum += graph[y][x]
      cnt += 1
    movePeople = sum // cnt
    for x, y in g:
      graph[y][x] = movePeople

print(ans)

웬만하면 bfs로 짜는게 안전할 것 같다,,

3-Way Handshake는 TCP 네트워크의 연결을 설정, 4-Way Handshake는 TCP 네트워크 연결을 해제하는 과정이다.

• 포트(PORT) 상태 정보

  • CLOESD: 포트가 닫힌 상태
  • LISTEN: 포트가 열린 상태로 연결 요청 대기 중
  • ESTABLISHED: 포트 연결 상태

• 플래그 정보

  • SYN(Synchronize Sequence Number)

    • 연결 요청. 세션을 설정하는데 사용되며, 초기에 Sequence Number를 랜덤으로 설정하여 전송한다.

      → 랜덤으로 설정하는 이유: Connection을 맺을 때 사용하는 포트(Port)는 유한 범위 내에서 사용하고 시간이 지남에 따라 재사용된다. 따라서 두 통신 호스트가 과거에 사용된 포트 번호 쌍을 사용하는 가능성이 존재한다. 서버 측에서는 패킷의 SYN을 보고 패킷을 구분하게 되는데 난수가 아닌 순차적인 Number가 전송된다면 이전의 Connection으로부터 오는 패킷으로 인식할 수 있다. 이런 문제가 발생할 가능성을 줄이기 위해서 난수로 ISN을 설정한다.

  • ACK(Acknowledgment)

    • 응답 확인. 패킷을 받았다는 것을 의미한다.

  • FIN(Finish)

    • 연결 해제. 세션 연결을 종료시킬때 사용되며, 더 이상 전송할 데이터가 없음을 의미한다.

TCP 3-Way Handshake

• TCP 통신을 이용하여 데이터를 전송하기 위해 네트워크 연결을 설정하는 과정
• 양쪽 모두 데이터를 전송할 준비가 되었다는 것을 보장하고, 실제로 데이터 전달이 시작하기 전에 한 쪽에서 다른 쪽이 준비되었다는 것을 알 수 있도록 한다.
• 즉, TCP/IP 프로토콜을 이용해서 통신을 하는 응용 프로그램이 데이터를 전송하기 전에 먼저 정확한 전송(신뢰성)을 보장하기 위해 상대방 컴퓨터와 사전에 세션을 수립하는 과정을 의미한다.

작동 방식

• Client와 Server는 서로 연결 요청을 먼저 할 수 있기 때문에, 연결 요청을 먼저 시도한 쪽을 Client(Host P), 연결 요청을 받은 수신자를 Server(Host Q)라고 가정함

(출처 : https://velog.io/@averycode/네트워크-TCPUDP와-3-Way-Handshake4-Way-Handshake)

• STEP 1 (SYN)
  • 클라이언트는 서버와 연결하기 위해 SYN(x)을 보냄 (seq : x)
  • 포트 상태
    • Client: CLOSED → SYN_SENT
    • Server: LISTEN → SYN_RCV
• STEP 2 (SYN + ACK)
  • 서버는 클라이언트에게 SYN를 받았다는 신호(연결 요청 수락)인 ACK(x+1)와 SYN(y) 패킷을 보냄 (seq : y, ack : x+1)
  • 포트 상태
    • Client: SYN_SENT → ESTABLISHED
    • Server: SYN_RCV
• STEP 3 (ACK)
  • 서버는 ACK(y+1)을 보내 연결을 맺음
  • 포트 상태
    • Client: ESTABLISHED
    • Server: SYN_RCV → ESTABLISHED

TCP 4-Way Handshake

• 맺어진 TCP 네트워크 연결을 해제하는 과정

작동 방식

(출처 : https://velog.io/@averycode/네트워크-TCPUDP와-3-Way-Handshake4-Way-Handshake)

• STEP 1 (FIN)

  • 클라이언트가 close()를 호출하여 연결을 끊는다는 신호인 FIN을 보냄
  • 포트 상태
    • Client: ESTABLISHED → FIN_WAIT_1
    • Server: ESTABLISHED → CLOSE_WAIT

• STEP 2 (ACK)

  • 서버가 확인했다는 신호인 ACK를 보내고, 남은 데이터가 있다면 마저 전송을 마친 후에 close()를 호출함
  • 포트 상태
    • Client: FIN_WAIT_1 → FIN_WAIT_2
    • Server: CLOSE_WAIT

• STEP 3 (FIN)

  • 서버가 남은 데이터를 모두 보냈다면, 서버도 연결을 합의하에 종료한다는 신호로 FIN을 보냄

  • 클라이언트의 TIME_WAIT 상태는 의도치 않은 에러로 연결이 데드락으로 빠지는 것을 방지

    → 종료가 지연되다가 타임이 초과되면 CLOSED 로 들어감

  • 포트 상태

    • Client: FIN_WAIT_2 → TIME_WAIT
    • Server: CLOSE_WAIT → LAST_ACK

• STEP 4(ACK)

  • 클라이언트가 확인했다는 신호인 ACK를 보내고, 서버는 ACK를 받고 소켓을 닫음
  • 포트 상태
    • Client: TIME_WAIT → CLOSED
    • Server: LAST_ACK → CLOSED

Reference

https://velog.io/@averycode/네트워크-TCPUDP와-3-Way-Handshake4-Way-Handshake

https://asfirstalways.tistory.com/356

모든 인터넷상의 페이지는 서버를 가지고 있는데, 그 서버는 각자 IP주소를 가지게 된다.

이때 항상 IP주소를 외우고 다닐수는 없기에, 도메인 이름을 통해서 인터넷 페이지를 접속할 수 있게 해주는데 이 도메인 이름을 IP주소로 변환시켜주는 서버로서 이때 행해지는 요청을 “쿼리"라고 한다.

DNS 라운드로빈

DNS 라운드로빈은 위 개념에서 도메인이름-IP주소가 1:1 매칭되지 않고, 실제 IP주소 여러개를 등록해 DNS 쿼리가 올때마다 그 주소를 한개씩 돌아가면서 혹은 랜덤으로 응답해주는 방식이다.

이론적으로는 다수의 사용자가 분산된 서버들의 여러 아이피로 나눠지게 되면서 서버의 부하가 분산될 수 있는 방식이다.

그러나 현실은 그렇지 않았습니다

DNS는 캐싱 주기 TTL(Time To Live)이 존재한다. 즉, 개인의 클라이언트는 DNS를 캐싱해서 들고있고 그 TTL동안은 도메인이름-IP 매핑 정보를 들고있게 된다. 게다가 클라이언트만 캐싱을 하는게 아니라 ISP(Internet Service Provider)역시 DNS 쿼리 정보를 캐싱해서 들고있게 된다. DNS구조상 DNS의 원본 네임서버까지 도달하지 않더라도 그 경로상 어딘가에서 결과를 찾으면(recursively) 돌려받게 된다.

게다가 DNS 라운드로빈은 서버의 Health Check등을 하게끔 설계되어있지 않기에, 그 서버가 살아있든 죽어있든 그냥 반환을 하게 된다. 이 단점을 극복하고자 AWS의 경우 Route53에서 자체적으로 Health Check 를 지원하는 형태로 서비스를 제공하고 있다고 한다...

그럼 어떻게 써야할까?

무지성 TTL낮추기

일단 무지성으로 TTL을 낮게 잡아서(약 30초대) 무조건 DNS에서 쿼리를 긁어서 접속하게끔 만들면 어느정도 위 혜택을 볼 수 있다. 물론 DNS도 UDP를 사용하는 엄연한 Application Layer의 패킷이기에 쿼리 시간이 어느정도 필요하고, 원본 네임서버가 아니라 캐싱된 ISP의 네임서버에서 결과를 찾을 경우 위 단락의 Health Check 기능등도 무용지물이기에 TTL에 대해서도 적절한 트레이드오프가 필요하다.

GSLB(Global Server Load Balancing)

애초에 실시간 분산은 LB가 맡게 하고 GSLB(Global Server Load Balancing)을 통해 DNS 라운드로빈은 LB의 아이피를 응답해주는 방식이라고 한다. HA(High Availability) 목적도 만족해준다고 한다.

Reference

https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/Network

https://ckddn9496.tistory.com/33

TCP와 UDP는 전송계층(L4)에 해당하는 프로토콜로서, L3의 IP Packet의 페이로드 부분에 들어있던 패킷이다. 포트를 기준으로 통신하며 클라이언트는 dynamic port range인 49152~65535를 사용한다. TCP는 UDP와 같은 포트로 listen할 수 있다.

TCP(Transmission Control Protocol)

• Connection Oriented(연결 지향) 서비스로 가상 회선 방식을 사용한다. (논리적 연결지향으로 물리적 연결지향은 애초에 L3의 IP 프로토콜이 Connectionless인 시점에서 파괴되었다..)
• 연결은 3-way handshaking, 연결종료는 4-way handshaking을 사용한다.
• Congestion control(혼잡 제어)와 Flow Control(흐름 제어)를 지원한다.
  • 혼잡 제어: 네트워크 내의 패킷 수를 조절하여 네트워크의 오버플로우를 방지하는 기능
  • 흐름 제어: 송신 측과 수신 측의 TCP 버퍼 크기 차이로 인해 생기는 데이터 처리 속도 차이를 해결하기 위하여, 송 수신 측 사이의 패킷 수를 제어하는 기능
• 신뢰성을 보장하는 프로토콜이다.
• UDP보다 일반적으로 속도가 느리다
• 서버와 1:1로 통신한다

UDP(User Datagram Protocol)

• Connectionless(연결 안지향) 서비스로 데이터그램 방식을 사용한다.
• 상호간 정보를 보낸다, 정보를 받는다, 정보를 받았다 와 같은 의사소통을 하지 않는다
• 패킷 헤더에서 CheckSum 필드로 최소한의 오류는 검출할 수 있다
• 신뢰성을 보장하지 않는 프로토콜이다
• 전송 순서를 보장하지 않는 프로토콜이다
• TCP보다 일반적으로 속도가 빠르다
• 서버와 1:1, 1:N, N:M 으로 통신한다

언제 무엇을 사용하는가?

어지간한 모든 인터넷을 기반으로 통신하는 서비스나 프로그램은 TCP를 사용한다. TCP를 쓸것인가 UDP를 쓸것인가를 결정하는 주요 분기는 “데이터가 속도만 빠르면 손실되어도 상관없는가?”이기에, 이에 해당하는 항목이 그리 많지 않다. 이에 부합하는 대표적인 예로 동영상 스트리밍(중간에 몇픽셀 혹은 프레임이 손실나더라도 보는데 지장이 있지는 않기에), [CS] DNS란? 에 언급되는 DNS 쿼리 패킷 등이 이에 해당한다.

Reference

https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/Network

IoC(Inversion of Control)란 제어의 "역전"으로, 프로그램의 제어 흐름을 직접 제어하는 것이 아니라 외부에서 관리하는 것이다.

외부(스프링 빈 !)에서 주입된(DI !) 객체들을 관리함으로써 응집도를 높이고 결합도를 낮추는 객체지향의 원칙을 지킬 수 있게 된다.

스프링 빈?

Spring IoC 컨테이너가 관리하는 자바 객체를 Bean 이라고 한다. 객체들을 빈에 등록하면 빈이 객체들을 관리해준다.

빈에 등록?

• 빈 설정파일에 직접 빈을 등록

• @Configuration를 붙인 자바 설정파일에서 @Bean을 이용하여 직접 빈을 정의하여 등록한다.

• Component Scanning

• @ComponentScan 이 포함되어있는 애노테이션(ex. @Controller, @Service, ...)을 사용하여 빈에 등록한다.

DI ?

DI(Dependency Injection)란 외부에서 의존성을 주입받는 것을 의미한다. 의존성 주입에는 여러 방법이 있는데,

• 필드 주입
  • 외부 의존성 주입을 받지 않고 인스턴스를 생성하여 Bean에 등록.
  • 추상체가 아닌 구현체를 직접 생성하기 때문에 변화에 민감해짐
• Setter 주입
  • 인스턴스 생성 시 set()을 돌려주지 않으면 null값을 가져 exception이 터질 수 있다. 런타임시에 문제 해결 불가능...
• 생성자 주입
  • 추천! 외부로 부터 주입 받기 때문에 변화에 능동적으로 대처할 수 있고, 구현체에 의존하지 않고 사용할 수 있는 장점이 있다.
  • 또한, final로 생성된 불변객체를 사용함으로서, 인스턴스의 복제, 비교가 쉬워지며, 한번 생성한 인스턴스에 대한 변경을 금지시킴으로서 안전한 객체사용이 가능해짐!

DIP 란?

DIP(Dependency Inversion Principle)란 의존 역전 원칙으로, 상위 레벨의 모듈이 절대 하위 레벨 모듈에 의존하지 않으며, 둘 다 추상화에 의존해야 한다는 원칙이다.

DI 기법으로 추상화에 의존하도록 하여, DIP를 만족함으로써 클래스 간 결합도를 낮출 수 있다.

Reference

https://www.youtube.com/watch?v=8lp_nHicYd4

https://velog.io/@dong_geon_kim/JAVA-4-DIP%EC%99%80-DI-%EC%9D%B4%ED%95%B4%ED%95%98%EA%B8%B0

클라이언트에서 서버로 리소스를 요청하기 위해 사용되는 메서드 입니다.

전송해야할 데이터를 쿼리 스트링을 URL 끝 부분에 넣어 전송합니다.

특징

1. 불필요한 요청을 제한하기 위해 요청이 캐시될 수 있습니다.
2. 파라미터에 내용이 노출되기 때문에 민감한 데이터를 다룰때는 GET 요청을 사용해서는 안됩니다.
3. 브라우저 기록에 남습니다.
4. 북마크에 추가할 수 있습니다.
5. 성공시, 200 return
6. 데이터 길이에 대한 제한이 있습니다.
7. idempotent 합니다.

POST 이란 ?

리소스를 생성/업데이트 하기 위해 서버에 데이터를 보내는데 사용되는 메서드 입니다.

전송해야할 데이터를 HTTP 메세지의 Body에 담아서 전송합니다.

특징

1. 캐시되지 않습니다.
2. 브라우저 기록에 안남습니다.
3. 데이터 길이에 대한 제한이 없습니다.
4. 리소스 생성 성공시, 201 return
5. idempotent 하지 않습니다.

idempotent ?

멱등성이라고 하는데, 연산을 여러번 적용하더라도 결과가 달라지지 않는 성질을 의미합니다.

• GET은 같은 요청에 대해 같은 결과를 매번 던져주고,

• PUT은 동일한 데이터를 계속 덮어쓰기하는 결과이기 때문에 멱등합니다.

• DELETE의 경우 코드에 따라 에러를 출력할 수도 있겠지만, 데이터의 관점에서 봤을 때 삭제되었다는 사실이 변하지는 않습니다.

• 반면, POST는 같은 요청이더라도 던져주는 결과가 매번 다를 수 있습니다.

• 추가로, 데이터를 일부만 수정하는 PATCH의 경우도 멱등성이 보장되지 않을 수 있습니다. (운이 좋으면 결과가 동일할 수도 있음)

Reference

https://github.com/JaeYeopHan/Interview_Question_for_Beginner

https://velog.io/@bae12/HTTP-%EB%A9%94%EC%86%8C%EB%93%9C%EC%9D%98-%EB%A9%B1%EB%93%B1Idempotent%EB%9E%80

HTTP 란 서버/클라이언트 모델을 따라 데이터를 주고 받기 위한 프로토콜이다.

애플리케이션 레벨의 프로토콜로 TCP/IP 위에서 작동한다. HTTP는 상태를 가지고 있지 않는 Stateless 프로토콜이며 Method, Path, Version, Headers, Body 등으로 구성된다.

• 암호화되지않은 평문 데이터를 전송하는 프토토콜이어서 보안상 문제가 있다.
• 80번 포트로 통신 한다.

TCP/IP: 인터넷 프로토콜인 IP와 전송 조절 프로토콜인 TCP로 이루어져있다.

HTTPS

HTTP에 데이터 암호화가 추가된 프로토콜이다.

• 443 포트로 통신 한다.

암호화 방식

대칭키 암호화

클라이언트와 서버가 동일한 키를 사용해 암호화/복호화를 진행함. 키가 노출되면 매우 위험하지만 연산 속도가 빠르다.

비대칭키 암호화

1개의 쌍으로 구성된 공개키 - 개인키를 암호화/복호화 하는데 사용함. 키가 노출되어도 비교적 안전하지만, 연산 속도가 느리다.

• 공개키: 모두에게 공개하는 키
  • 공개키로 암호화를 하면 개인키로만 복호화할 수 있다.
    • 개인키는 나만 가지고 있으므로 나만 볼 수 있다.

• 개인키: 나만 가지고 알고 있어야 하는 키
  • 개인키로 암호화를 하면 공개키로만 복호화할 수 있다.
    • 공개키는 모두에게 공개되어 있으므로, 내가 인증한 정보임을 알려 신뢰성을 보장할 수 있다.

HTTPS 동작 과정

Hand-Shaking 과정을 통해서 서버와 클라이언트간 세션키를 교환하여, 신뢰성을 확보한다.

1. 클라이언트가 서버로 최초 연결 시도
2. 서버는 인증서를 클라이언트에게 넘김
3. 클라이언트는 인증서의 유효성을 검사하고, 세션키를 발급
4. 클라이언트는 세션키를 보관하며 서버의 인증서로 세션키를 암호화하여 서버로 전송
5. 서버는 개인키로 암호화된 세션키를 복호화하여 세션키를 얻음
6. 클라이언트와 서버는 동일한 세션키를 공유, 데이터를 전달할 때 세션키로 암호화/복호화를 진행

** Hand Shaking 흐름**

** Hand Shaking 과정**

Reference

https://github.com/JaeYeopHan/Interview_Question_for_Beginner

https://stackoverflow.com/questions/188266/how-are-ssl-certificates-verified#:~:text=Your web browser downloads the,key of the web server.&text=It uses this public key,address of the web server

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

문제 설명

사진이 많으니 위 링크 참조 !

입력 첫째 줄에 사무실의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 8)

둘째 줄부터 N개의 줄에는 사무실 각 칸의 정보가 주어진다. 0은 빈 칸, 6은 벽, 1~5는 CCTV를 나타내고, 문제에서 설명한 CCTV의 종류이다.

CCTV의 최대 개수는 8개를 넘지 않는다.

출력 첫째 줄에 사각 지대의 최소 크기를 출력한다.

1차 시도

import copy

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

cctv = [
  [-1],
  [[0], [1], [2], [3]],
  [[0,2], [1,3]],
  [[0,1], [1,2], [2,3], [3,0]],
  [[0,1,2], [1,2,3], [2,3,0]],
  [[0,1,2,3]]
]

graph = []
cctvPoint = []
ans = 100
n, m = map(int, input().split())

for _ in range(n):
  graph.append(list(map(int, input().split())))

for i in range(n):
  for j in range(m):
    if graph[i][j] != 0 and graph[i][j] != 6:
      cctvPoint.append((i, j, graph[i][j]))

def DFS(dir, nowGraph, nowY, nowX):
  nx = dx[dir] + nowX
  ny = dy[dir] + nowY

  if nx >= 0 and ny >= 0 and nx < m and ny < n:
    if nowGraph[ny][nx] == 0:
      nowGraph[ny][nx] = '#'
      DFS(dir, nowGraph, ny, nx)
    elif nowGraph[ny][nx] != '#' and nowGraph[ny][nx] != 6:
      DFS(dir, nowGraph, ny, nx)

def sol(cctvLeft, nowGraph):
  global ans
  if not cctvLeft:

    for i in range(n):
      print(nowGraph[i])

    sum = 0
    for i in range(n):
      for j in range(m):
        if nowGraph[i][j] == 0:
          sum += 1
    ans = min(ans, sum)
    print(sum)
  else:
    cctvNowY, cctvNowX, cctvNowNum = cctvLeft.pop()
    for dirs in cctv[cctvNowNum]:
      nextGraph = copy.deepcopy(nowGraph)  # 그래프 유지 주의!
      for dir in dirs:
        DFS(dir, nextGraph, cctvNowY, cctvNowX)
        sol(cctvLeft, nextGraph)

sol(cctvPoint, graph)

print(ans)

6 6
1 0 0 0 0 0
0 1 0 0 0 0
0 0 1 0 0 0
0 0 0 1 0 0
0 0 0 0 1 0
0 0 0 0 0 1
[1, '#', '#', '#', '#', '#']
[0, 1, '#', '#', '#', '#']
[0, 0, 1, '#', '#', '#']
[0, 0, 0, 1, '#', '#']
[0, 0, 0, 0, 1, '#']
[0, 0, 0, 0, 0, 1]
15
[1, 0, 0, 0, 0, 0]
['#', 1, '#', '#', '#', '#']
['#', 0, 1, '#', '#', '#']
['#', 0, 0, 1, '#', '#']
['#', 0, 0, 0, 1, '#']
['#', 0, 0, 0, 0, 1]
15
[1, 0, 0, 0, 0, 0]
[0, 1, '#', '#', '#', '#']
[0, 0, 1, '#', '#', '#']
[0, 0, 0, 1, '#', '#']
[0, 0, 0, 0, 1, '#']
[0, 0, 0, 0, 0, 1]
20
[1, 0, 0, 0, 0, 0]
[0, 1, '#', '#', '#', '#']
[0, 0, 1, '#', '#', '#']
[0, 0, 0, 1, '#', '#']
[0, 0, 0, 0, 1, '#']
[0, 0, 0, 0, 0, 1]
20
[1, 0, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0]
[0, '#', 1, '#', '#', '#']
[0, '#', 0, 1, '#', '#']
[0, '#', 0, 0, 1, '#']
[0, '#', 0, 0, 0, 1]
20
[1, 0, 0, 0, 0, 0]
['#', 1, 0, 0, 0, 0]
[0, 0, 1, '#', '#', '#']
[0, 0, 0, 1, '#', '#']
[0, 0, 0, 0, 1, '#']
[0, 0, 0, 0, 0, 1]
23
[1, '#', 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0]
[0, 0, 1, '#', '#', '#']
[0, 0, 0, 1, '#', '#']
[0, 0, 0, 0, 1, '#']
[0, 0, 0, 0, 0, 1]
23
[1, 0, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0]
[0, 0, 1, 0, 0, 0]
[0, 0, '#', 1, '#', '#']
[0, 0, '#', 0, 1, '#']
[0, 0, '#', 0, 0, 1]
24
[1, 0, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0]
['#', '#', 1, 0, 0, 0]
[0, 0, 0, 1, '#', '#']
[0, 0, 0, 0, 1, '#']
[0, 0, 0, 0, 0, 1]
25
[1, 0, '#', 0, 0, 0]
[0, 1, '#', 0, 0, 0]
[0, 0, 1, 0, 0, 0]
[0, 0, 0, 1, '#', '#']
[0, 0, 0, 0, 1, '#']
[0, 0, 0, 0, 0, 1]
25
[1, 0, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0]
[0, 0, 1, 0, 0, 0]
[0, 0, 0, 1, 0, 0]
[0, 0, 0, '#', 1, '#']
[0, 0, 0, '#', 0, 1]
27
[1, 0, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0]
[0, 0, 1, 0, 0, 0]
['#', '#', '#', 1, 0, 0]
[0, 0, 0, 0, 1, '#']
[0, 0, 0, 0, 0, 1]
26
[1, 0, 0, '#', 0, 0]
[0, 1, 0, '#', 0, 0]
[0, 0, 1, '#', 0, 0]
[0, 0, 0, 1, 0, 0]
[0, 0, 0, 0, 1, '#']
[0, 0, 0, 0, 0, 1]
26
[1, 0, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0]
[0, 0, 1, 0, 0, 0]
[0, 0, 0, 1, 0, 0]
[0, 0, 0, 0, 1, 0]
[0, 0, 0, 0, '#', 1]
29
[1, 0, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0]
[0, 0, 1, 0, 0, 0]
[0, 0, 0, 1, 0, 0]
['#', '#', '#', '#', 1, 0]
[0, 0, 0, 0, 0, 1]
26
[1, 0, 0, 0, '#', 0]
[0, 1, 0, 0, '#', 0]
[0, 0, 1, 0, '#', 0]
[0, 0, 0, 1, '#', 0]
[0, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 0, 1]
26
[1, 0, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0]
[0, 0, 1, 0, 0, 0]
[0, 0, 0, 1, 0, 0]
[0, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 0, 1]
30
[1, 0, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0]
[0, 0, 1, 0, 0, 0]
[0, 0, 0, 1, 0, 0]
[0, 0, 0, 0, 1, 0]
['#', '#', '#', '#', '#', 1]
25
[1, 0, 0, 0, 0, '#']
[0, 1, 0, 0, 0, '#']
[0, 0, 1, 0, 0, '#']
[0, 0, 0, 1, 0, '#']
[0, 0, 0, 0, 1, '#']
[0, 0, 0, 0, 0, 1]
25
15

• 백트래킹에서 마지막 원소가 끝났을때, 다시 append를 안해줘서 위와 같은 오류가 났다.
• 위 오류를 고치고 모든 예시가 통과했는데 틀렸댄다,, 이럴때는 특수 케이스는 다 맞은것 같으니, 편안한 마음으로 문제와 코드를 유심히 보자.. 자세히 보니 cctv4번에서 [3,0,1]을 추가안했었다!

  맞은 코드

  import copy
  import sys
  

#sys.setrecursionlimit(10**9)

dx = [1, 0, -1, 0] dy = [0, 1, 0, -1]

cctv = [ [-1], [[0], [1], [2], [3]], [[0,2], [1,3]], [[0,1], [1,2], [2,3], [3,0]], [[0,1,2], [1,2,3], [2,3,0], [3,0,1]], [[0,1,2,3]] ]

graph = [] cctvPoint = [] ans = 100 n, m = map(int, input().split())

for _ in range(n): graph.append(list(map(int, input().split())))

for i in range(n): for j in range(m): if graph[i][j] != 0 and graph[i][j] != 6: cctvPoint.append((i, j, graph[i][j]))

def DFS(dir, nowGraph, nowY, nowX): nx = dx[dir] + nowX ny = dy[dir] + nowY

if nx >= 0 and ny >= 0 and nx < m and ny < n: if nowGraph[ny][nx] == 0: nowGraph[ny][nx] = '#' DFS(dir, nowGraph, ny, nx) elif nowGraph[ny][nx] != 6: DFS(dir, nowGraph, ny, nx)

def sol(cctvLeft, nowGraph): global ans if not cctvLeft: ''' for i in range(n): print(nowGraph[i]) ''' sum = 0 for i in range(n): for j in range(m): if nowGraph[i][j] == 0: sum += 1 ans = min(ans, sum) #print(sum) else: cctvNowY, cctvNowX, cctvNowNum = cctvLeft.pop() for dirs in cctv[cctvNowNum]: #print(dirs) nextGraph = copy.deepcopy(nowGraph) # 그래프 유지 주의 for dir in dirs: DFS(dir, nextGraph, cctvNowY, cctvNowX) sol(cctvLeft, nextGraph) cctvLeft.append((cctvNowY, cctvNowX, cctvNowNum))

sol(cctvPoint, graph)

print(ans) ```

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

문제 설명

총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴가 1번, 그 오른쪽은 2번, 그 오른쪽은 3번, 가장 오른쪽 톱니바퀴는 4번이다.

이때, 톱니바퀴를 총 K번 회전시키려고 한다. 톱니바퀴의 회전은 한 칸을 기준으로 한다. 회전은 시계 방향과 반시계 방향이 있다.

톱니바퀴를 회전시키려면, 회전시킬 톱니바퀴와 회전시킬 방향을 결정해야 한다. 톱니바퀴가 회전할 때, 서로 맞닿은 극에 따라서 옆에 있는 톱니바퀴를 회전시킬 수도 있고, 회전시키지 않을 수도 있다. 톱니바퀴 A를 회전할 때, 그 옆에 있는 톱니바퀴 B와 서로 맞닿은 톱니의 극이 다르다면, B는 A가 회전한 방향과 반대방향으로 회전하게 된다. 예를 들어, 아래와 같은 경우를 살펴보자.

사진이 많으므로 링크 참고 !

입력 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 시계방향 순서대로 주어진다. N극은 0, S극은 1로 나타나있다.

다섯째 줄에는 회전 횟수 K(1 ≤ K ≤ 100)가 주어진다. 다음 K개 줄에는 회전시킨 방법이 순서대로 주어진다. 각 방법은 두 개의 정수로 이루어져 있고, 첫 번째 정수는 회전시킨 톱니바퀴의 번호, 두 번째 정수는 방향이다. 방향이 1인 경우는 시계 방향이고, -1인 경우는 반시계 방향이다.

출력 총 K번 회전시킨 이후에 네 톱니바퀴의 점수의 합을 출력한다. 점수란 다음과 같이 계산한다.

1번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 1점 2번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 2점 3번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 4점 4번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 8점

문제 풀이

주어진 시뮬레이션대로 구현하면 되는 문제다.

• 처음에 톱니바퀴가 리스트인줄 알고 deque 등을 이용해서 풀었는데, 문자열이었다.. 더 간단
• 양 쪽 톱니바퀴가 굴러가는 것을 결정할 때, 현재 톱니바퀴를 굴리기 전에 결정해야한다. 그래서 실제 굴리는 기능과 옆 톱니바퀴를 결정하는 기능을 나눴따.
• -> 시뮬레이션, 구현 문제는 모듈화를 잘하자 !*
• 톱니바퀴가 4개밖에 없으니까, 분기를 결정하는 방향을 직접 설정해서 moveDir로 부여했다.

맞은 코드

import copy

graph = []

for _ in range(4):
  graph.append(input())

def rotateSelf(num, dir):
  global graph
  tempGraph = copy.deepcopy(graph[num])
  graph[num] = ""
  if dir == -1: # 123456789
    graph[num] = tempGraph[1:8]
    graph[num] += tempGraph[0]

  else:  # 70123456
    graph[num] = ""
    graph[num] += tempGraph[7]
    for elem in tempGraph[0:7]:
      graph[num] += elem


def rotate(num, dir, moveDir):
  if moveDir == 1 and num < 3:
    if graph[num][2] != graph[num+1][6]:
      rotate(num+1, -1 * dir, 1)
  elif moveDir == -1 and num > 0:
    if graph[num][6] != graph[num-1][2]:
      rotate(num-1, -1 * dir, -1)
  elif moveDir == 0 and (num == 1 or num == 2):
    if graph[num][6] != graph[num-1][2]:
      rotate(num-1, -1 * dir, -1)
    if graph[num][2] != graph[num+1][6]:
      rotate(num+1, -1 * dir, 1)

  rotateSelf(num, dir)

k = int(input())
for _ in range(k): 
  # 방향이 1인 경우는 시계 -> 방향이고, -1인 경우는 반시계 <- 방향이다.
  wheelNum, wheelDir = map(int, input().split())
  if wheelNum == 1:
    moveDir = 1
  elif wheelNum == 4:
    moveDir = -1
  else:  # 0은 양방향
    moveDir = 0
  rotate(wheelNum-1, wheelDir, moveDir)
  #print(graph)

ans = 0
for idx, wheel in enumerate(graph):
  ans += (2**idx) * int(wheel[0])
print(ans)

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

문제 설명

크기가 N×N인 지도가 있다. 지도의 각 칸에는 그 곳의 높이가 적혀져 있다.

오늘은 이 지도에서 지나갈 수 있는 길이 몇 개 있는지 알아보려고 한다. 길이란 한 행 또는 한 열 전부를 나타내며, 한쪽 끝에서 다른쪽 끝까지 지나가는 것이다.

다음과 같은 N=6인 경우 지도를 살펴보자.

이때, 길은 총 2N개가 있으며, 아래와 같다.

길을 지나갈 수 있으려면 길에 속한 모든 칸의 높이가 모두 같아야 한다. 또는, 경사로를 놓아서 지나갈 수 있는 길을 만들 수 있다. 경사로는 높이가 항상 1이며, 길이는 L이다. 또, 개수는 매우 많아 부족할 일이 없다. 경사로는 낮은 칸과 높은 칸을 연결하며, 아래와 같은 조건을 만족해야한다.

경사로는 낮은 칸에 놓으며, L개의 연속된 칸에 경사로의 바닥이 모두 접해야 한다. 낮은 칸과 높은 칸의 높이 차이는 1이어야 한다. 경사로를 놓을 낮은 칸의 높이는 모두 같아야 하고, L개의 칸이 연속되어 있어야 한다. 아래와 같은 경우에는 경사로를 놓을 수 없다.

경사로를 놓은 곳에 또 경사로를 놓는 경우 낮은 칸과 높은 칸의 높이 차이가 1이 아닌 경우 낮은 지점의 칸의 높이가 모두 같지 않거나, L개가 연속되지 않은 경우 경사로를 놓다가 범위를 벗어나는 경우 L = 2인 경우에 경사로를 놓을 수 있는 경우를 그림으로 나타내면 아래와 같다.

경사로를 놓을 수 없는 경우는 아래와 같다.

위의 그림의 가장 왼쪽부터 1번, 2번, 3번, 4번 예제라고 했을 때, 1번은 높이 차이가 1이 아니라서, 2번은 경사로를 바닥과 접하게 놓지 않아서, 3번은 겹쳐서 놓아서, 4번은 기울이게 놓아서 불가능한 경우이다.

가장 위에 주어진 그림 예의 경우에 지나갈 수 있는 길은 파란색으로, 지나갈 수 없는 길은 빨간색으로 표시되어 있으며, 아래와 같다. 경사로의 길이 L = 2이다.

지도가 주어졌을 때, 지나갈 수 있는 길의 개수를 구하는 프로그램을 작성하시오.

입력 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다.

출력 첫째 줄에 지나갈 수 있는 길의 개수를 출력한다.

문제 풀이

가로줄들은 그냥 순서대로 넣으면 되고, 세로줄은 행렬 한 바퀴돌려서 넣으면, 결론적으론 각각 한 줄에 대해서 시뮬레이션 문제라고 생각했다. 차근차근 경우를 잘 따져보며 풀자,,

처음에는 분기를 절댓값으로 했다가, 앞 뒤 비교할때 뭐가 더 크냐에 따라 다르다는 것을 인지하고 이또한 분기했다. 뒤가 더 작을 경우에서 lenConnection이라는 변수를 썼는데, 그냥 continuousBlock으로 깔끔히 관리할 수 있을것 같다.

앞뒤 비교해가는 문제에서는 범위의 맨 앞이나 맨 뒤가 포함되는지 꼭 생각!

맞은 코드

n, l = map(int, input().split())
graph = []

for _ in range(n):
  graph.append(list(map(int, input().split())))

def rotate_matrix(matrix):
    row = len(matrix)
    column = len(matrix[0])
    result=[[0] * row for _ in range(column)]
    for i in range(row):
        for j in range(column):
            result[j][row - i - 1] = matrix[i][j]
    return result

rotateGraph = rotate_matrix(graph)
ans = 0

def checkPossible(line):
  checkConnection = 0
  lenConnection = 1
  continuousBlock = 1
  for block in range(len(line)-1):
    if checkConnection:    # 앞보다 뒤가 더 작을 경우
      if lenConnection == l:
        checkConnection = 0
        continuousBlock = 0
        lenConnection = 1
      elif line[block+1] != line[block]:
        return 0
      else:
        lenConnection += 1

    if abs(line[block+1] - line[block]) > 1:
      return 0
    elif line[block+1] == line[block]:
      continuousBlock += 1
    elif line[block+1] - line[block] == 1:
      if continuousBlock >= l:
        continuousBlock = 1
        continue
      else:
        return 0
    elif line[block] - line[block+1] == 1:    # 앞보다 뒤가 더 작을 경우
      checkConnection = 1
      continuousBlock = 1
      continue

  if lenConnection == l:
    checkConnection = 0

  if checkConnection:
    return 0

  #print(line)
  return 1


for i in range(n):
  ans += checkPossible(graph[i])
  ans += checkPossible(rotateGraph[i])

print(ans)