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

문제풀이 kick

[기존 이분탐색] arr에서 value 찾기 [문제] arr에 '쌍이 되는' target 찾기

코드

import sys

n=int(input())
li=list(map(int,input().split()))
li.sort()

def find_pair_value(left, right, value):
    optimalPairValue=0
    optimalPairTotal=sys.maxsize

    while left<=right:
        mid=(left+right)//2
        sum=value+li[mid]

        # 최적값 갱신 
        if abs(sum)<optimalPairTotal:
            optimalPairValue=li[mid]
            optimalPairTotal=abs(sum)

        if sum<0:
            left=mid+1
        elif sum>0:
            right=mid-1
        else:
            return li[mid]
            # 찾으면 그냥 반환 
    return optimalPairValue

ans1,ans2=0,0
ans_total=sys.maxsize

for i in range(0,n-1):
    # 리스트는 정렬되어 있음.
    # i>j 일때,arr[j]는 arr[j]보다 작은 값이기 때문에 더해서 0을 만들 수 있는 최적의 해가 아님. 따라서 i+1 부터 탐색.
    pair_value=find_pair_value(i+1, n-1, li[i])
    total=abs(li[i]+pair_value)
    # 정답 갱신 
    if total<ans_total:
        ans_total=total
        ans1, ans2= li[i], pair_value
print(ans1, ans2)

이분탐색 문제인건 알겠음. 구간 내에서 target 값 찾는거니깐.

여기서 수학적 사고가 필요함.

x + y + z = k k가 집합에 포함된 원소인지 판별해야 함.

ex) 2 + 3 + 5 = 10 2 + 3 = 10 - 5

x + y = k - z 가 성립함. 당연한 거임.

서로 같거나 다른 숫자 2개를 더한 배열을 선언함. 이게 x + y 가 가질 수 있는 값들임.

# x,y가 가질 수 있는 값

for i in range(n):
    for j in range(j, n):
    # 1. x + y값이 중복되지 않게 0부터 설정하지 않음.
    # 2. x, y 는 서로 같은 값을 가질 수 있으니깐 j부터로 선언함.
    sum.append(arr[i] + arr[j])

> sum은 x+y가 가질 수 있는값.
> 다음으로 해야될 일은 ? 
    x+y가 가질수 있는 값 리스트 중에서, k-z 가 있는지 판별.

k-z의 값은

for i in range(n):  # i는 k를 따른다. 
    for j in range(n):    # j는 z를 따른다.
        if binary_search(arr[i] - arr[j]):
            # 값 갱신 

수학적 사고를 할 수 있느냐가 관건인 문제. k도 집합에 포함된 값임을 인지해서 x + y = k - z / 이분탐색을 활용할 수 있어야 한다.

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

설명

동굴의 길이는 N미터, 높이 H미터 석순 > 종유석 > 석순 > 정유석 순서대로 입력을 받는다. 개똥벌레는 구간을 날라다니면서, 석순과 정유석을 파괴한다. 개똥벌레가 파괴하는 장애물의 최소개수와, 그러한 구간의 개수를 구한다.

이분탐색

시간복잡도 = O(logN)

이분탐색은 !정렬!되어 있어야 한다.

upper_bound, lower_bound = 같은 값일 때 어떻게 처리할지를 추가한다.

upper_bound = x초과의 값이 처음으로 나타나는 위치 lower_bound = x이상의 값이 처음으로 나타나는 위치

문제풀이

구간은 1부터 H까지의 값을 가집니다.

구간이 1일때 파괴하는 석순과, 종유석의 개수를 구해봅시다. 석순의 개수 : 높이가 0보다 큰 석순을 모두 파괴합니다. 종유석의 개수 : 높이가 3보다 큰 종유석을 모두 파괴합니다.

구간이 2일때 파괴하는 석순과, 종유석의 개수를 구해봅시다. 석순의 개수 : 높이가 1보다 큰 석순을 모두 파괴합니다. 종유석의 개수 : 높이가 2보다 큰 종유석을 모두 파괴합니다.

특정 구간일 때 파괴할 수 있는 석순과 종유석의 개수를 구해보면서, 결국 구간이 h일때 파괴할 수 있는 석순/종유석의 개수를 일반화 할 수 있다.

구간이 h일때, 파괴하는 석순 개수 = 높이가 (h-1) 보다 큰 석순의 개수 파괴하는 종유석 개수 = 높이가 (H-h) 보다 큰 종유석의 개수

코드

import sys

N, H = map(int,input().split())

down_arr , up_arr = [], []

for i in range(N):
    if i%2 == 0:
        down_arr.append(int(input())
        up_arr.append(int(input())

# 이분탐색은 정렬 되어 있어야 한다!
down_arr.sort()
up_arr.sort()

def upper_bound(arr, target)
    left, right = 0, len(arr)-1

    while left <= right :
        mid = (left+right)//2

        # 초과인 값 찾기
        if target>=arr[mid]:
            left = mid + 1  # 범위 좁히기
        else:
            right = mid - 1

    # left와 right이 역전
    # target 초과인 개수 구하기 
    return len(arr) - (right + 1)
    # return len(arr) - left

cnt = 0
ans = sys.maxsize()

# 구간 탐색
for h in range(1, H+1):    
    석순 = upper_bound(down_arr, h-1)
    종류석 = upper_bound(up_arr, H-h)

    sum = 석순 + 종류석

    if sum < ans :
        cnt = 1 
        ans = sum

    elif sum == ans:
        cnt += 1

 print(ans, cnt)

참고

https://blog.naver.com/PostView.nhn?blogId=crm06217&logNo=222023706440&categoryNo=23&parentCategoryNo=0&viewDate=&currentPage=1&postListTopCurrentPage=1&from=postView

Multiplexing

여러 소켓들로부터 데이터를 받아, header(source port + dest port) +data 형식으로 segment를 만든다. 이 header의 정보는 demultiplexing 할 때 사용된다.

Demultiplexing

전달받은 segment들을 알맞은 소켓에 전달한다. 이때 segment의 헤더 정보를 가지고 어떤 소켓에 전달할지 판단한다. host는 ip 주소와 포트넘버로 어떤 소켓에 segment를 전달할지 판단한다.

UDP는 demultiplexing을 어떻게 사용할까?

UDP는 dest IP와 dest port만 사용해서 어떤 소켓에 올릴지 demultiplexing 한다. 따라서 소켓은 아무한테나 올 수 있다. disconnection-oriented

TCP는 demultiplexing을 어떻게 사용할까?

TCP는 dest IP, dest port, source IP, source port 이 4가지 정보를 모두 사용해서 demultiplexing하기 때문에, 다 다른 소켓을 가지며 사용자만을 위한 고유하고 특정한 소켓을 가질 수 있다. 'CONNECTION-ORIENTED' 단점) 자원 많이 소모

정리

여러 소켓에 나온 데이터를 전송할 때는 Multiplexing, 받은 패킷을 적절한 소켓으로 보내줄 때는 Demultiplexing을 사용한다.

IP 주소는 인터넷을 이용할 때 사용하는 주소 시스템은 주소를 숫자로 구분하는게 편하지만, 사람은 주소를 이름으로 구분하는 것이 더 편함. 따라서 IP주소 외 호스트명을 지정. 예를 들어, 호스트명이 www.naver.com인 시스템의 IP주소는 111.123.45.6이다.

인터넷에서 사용하는 호스트명은 '호스트명+도메인명' 형태로 구성된다. www.naver.com의 경우 www는 호스트명, naver.com은 도메인명이다.호스트명과 도메인명을 관리하는 시스템을 DNS라 한다.

포트번호

IP주소는 데이터가 전송될 목적지 호스트를 알려주는 역할을 함. 그런데 목적지 호스트에는 여러 기능을 수행하는 서비스 프로세스들이 동시에 동작하고 있을 수 있다. 따라서 전송되어 오는 데이터를 어느 서비스 프로세스에 전달할 것인지 구분해야 한다. 인터넷에서도 IP 주소 외에 서비스를 구분하는 다른 정보가 필요하다. 이때 사용하는 것이 포트번호이다.

프로세스란?

실행 중에 있는 프로그램을 의미한다. 하드디스크에 있는 프로그램을 실행하면, 실행을 위해 메모리 할당이 이루어지고, 할당된 메모리 공간으로 바이너리 코드가 올라가게된다. 이 순간부터 프로세스라 불린다.

프로세스 내부에는 최소 하나의 스레드를 가진다.

소켓과 포트번호의 차이

• 소켓은 특정 포트에서 데이터를 송수신하는 인터페이스, 포트는 특정 프로세스에 할당된 숫자 값이다.

• 소켓은 특정 포트를 통해 데이터를 주고 받는 인터페이스 역할, 포트는 특정 프로세스를 식별하는데 도움을 준다.

• 소켓 정보에는 네트워크 주소(IP주소)와 포트번호 포함. 이것들을 통해 소켓 개설 가능

• 소켓은 다른 컴퓨터간 프로세스간 통신을 도와주는 인터페이스

응용계층(Application Layer)

endsystem에서 존재

응용계층 구조

client-server 구조 : 서버와 클라이언트 간 통신 ex) 구글 서버에 클라이언트가 데이터를 요청하는 방식으로 검색 Peer to peer 구조 : 호스트끼리 직접 통신

응용계층 프로토콜

클라이언트 속 애플리케이션과 서버 측 애플리케이션과 통신하려면 응용계층의 프로토콜을 사용해야 한다.

HTTP

• HypterText를 전송하는 프로토콜

• 웹의 애플리케이션 계층 프로토콜

• 클라이언트와 서버 프로그램으로 구현된다

• 서로 다른 종단 시스템에서 수행되는 클라이언트, 서버 프로그램은 서로 HTTP 메소드(Http request, response)를 교환하여 통신한다.

• tcp를 기반으로 통신한다. (tcp를 사용한다)

  • http2는 TCP 방식으로 HTTP 메시지를 주고 받는다. 쉽게 말하면 메시지 형식에 대해 http가 룰을 제시하고, TCP방식으로 메시지를 전달하고 있는 것이다. http3는 속도를 위해 UDP를 사용한다고 한다.

• HTTP는 상태가 없다. 직전에 같은 IP주소에서 똑같은 주소로 요청을 보냈든지, 상관없이 다음 요청은 이에 대한 내용을 전혀 모른다. 요청이나 응답의 히스토리를 HTTP가 관리하지 않지만, 브라우저나 서버는 여러 가지 방식으로 상태를 저장한다. 대표적인 예시로 브라우저의 쿠키, 서버의 세션이 있다.

인터넷 구성요소

network edge : hosts

network core : routers, network of networks

access networks, physical media : communication links(무선-wifi,LTE)

📍network edge

end systems(종단 시스템, hosts: 네트워크에 연결된 컴퓨터), client/server, peer-peer

인터넷에서 데이터를 전송하는 방법 2가지

전송계층에서 사용하는 프로토콜 데이터를 보내기 위한 프로토콜

1. TCP

• connection-oriented service, 연결 지향 방식으로 데이터를 보낼 때 논리적 경로를 지정
• 신뢰성 있고, 순서 있는 데이터 스트림 전달
• 흐름 제어: 송신측과 수신측의 데이터 속도 처리를 해결하기 위한 방법으로, 수신측의 데이터 속도를 강제로 줄이는 방법이다.
• 혼잡 제어: 네트워크가 혼잡할 때, 송신측의 데이터를 보내는 속도를 낮추는 방법이다.

HTTP(Web), SMTP(email), FTP(file transfer)에서 사용

2. UDP

• connectionless service, 비연결 지향으로 데이터 전송을 위해 할당하는 논리적 경로를 지정하지 X
  • 각각의 패킷은 다른 경로로 이동하여 독립적 관계 가짐, 데이터를 서로 다른 경로로 독립적으로 처리
• 비연결형
• 흐름제어, 혼잡제어 X
• 신뢰성 없는 데이터 전달

스트리밍 미디어, 음성전화(오디오 패킷 몇개 유실되더라도 영향 X)

프로토콜(Protocol)

컴퓨터간 통신을 위해 정의한 규칙

📍network core

네트워크 시스템의 중앙에 위치하여, 데이터를 전송하는 핵심적 역할 네트워크 코어의 구조는 "라우터들이 그물망처럼 얽혀있는 형태"

네트워크 상에서 데이터가 전송되는 방식

1. circuit switching

데이터를 전송하기 위한 경로를 미리 예약하는 방식 통신을 위한 연결을 하고, 전송지-수신지까지 사용되는 경로를 독점적으로 사용해, 다른 사람이 끼어들 수 없음 ex) 전화

2. packet-switching

데이터를 패킷 단위로 쪼개 데이터를 전송하는 방식 패킷의 header에는 출발지, 목적지 ip주소, 패킷번호 등의 식별정보가 있고, payload에는 실제 데이터가 있다. 핵심은 header이다. 헤더의 정보를 이용해 목적지까지 순서대로 패킷이 도달될 수 있다. 그리고 이 패킷의 구조를 윌는 프로토콜이라고 한다.

이 패킷의 정보를 이용해 송신측은 네트워크에 정보를 뿌린다. 그러면 각자 링크를 타고, 스위치를 타고, 라우터를 타서 최종 목적지까지 방향을 잃지 않고 도착한다. 이 과정에서 라우터 또한 중요한 역할을 한다. 패킷이 수신된 링크를 구별하고, 송신할 링크를 찾는, 경로를 탐색하고 패킷을 저장하고 송신하는 역할을 라우터가 한다. 라우팅 알고리즘을 이용해 경로를 지정해, 중간의 라우터들을 거처 최종 목적지가지 도착한다. 이런 과정에서 패킷은 다음 라우터로 이동하기 위해 큐에서 대기를 하는데, 이때 수용할 수 있는 큐의 범위를 넘어가면 손실이 발생한다.

장단점

패킷 스위칭은 더 많은 사용자가 사용할 수 있다. 만약 n명의 사용자가 있고, 라우터가 1개 있을 때, n명의 사용자가 동시에 접속 하지만 않는다면, 사용자가 사용하는 네트워크 시간은 분산되어, 네트워크를 제약없이 사용할 수 있다.

packet-switching 단점

네트워크 상에서 데이터를 packet단위로 쪼개 라우터를 거쳐 수신지로 전될되는 packet-switching은 지연이 발생할 수 있다. 라우터에서 패킷이 도착하는 링크의 속도가 수신하는 링크의 속도보다 빠르면, 패킷은 라우터의 "큐" 공간에 대기한다. 따라서 먼저 온 패킷이 송신되고, 나중에 온 패킷은 대기해야 되는데, 이때 delay가 발생한다. 라우터에서 발생하는 delay를 4가지로 정리할 수 있다.

1. nodal processing

패킷의 헤더를 열어 패킷을 검사하고, 패킷을 보낼 위치를 결정하는데 걸리는 시간이다. 요즘 라우터의 성능이 좋아 nodal processing 시간이 짧아졌다. 개선 -> 라우터 성능이 좋은 것을 사용한다.

2. queueing delay

큐에서 패킷이 대기상태로 쌓여 나가는데 까지 걸리는 시간 개선 -> 사람들이 몰리는 것을 조절할 수 없다. 사람들이 몰려 queue의 허용량을 넘어선다면 패킷 유실이 발생한다. TCP에서는 신뢰성 있는 연결을 지향하기 때문에, 패킷 유실이 발생하면 client단에서 유실된 패킷을 재전송한다. 라우터가 재전송하는게 아니다.

3. transmission delay

패킷을 송신하기 위해, 모든 bit를 output link로 전송하는데 걸리는 시간 패킷의 비트수와, 링크의 전송률에 의해 결정된다. 개선 -> 링크의 bandwidth 통로를 높여 전송률을 높인다.

4. propagation delay

마지막 비트가 올라온 순간부터 다음 라우터까지 도달하는데 걸리는 시간을 의미한다. 빛의 속도와 같거나 작다.

위 4개의 delay를 합친 시간이, 노드 상에서의 delay가 된다.

추상과 구현

OSI 7 Layers(추상) ex) transport 계층 (추상) -> TCP/IP (구현)

OSI 7 Layers란?

컴퓨터(개방형 체계: 다른 것과 통신하려는 체계)가 인터넷(상호연결_다른 것과 연결돼 있는 것에 또 연결)을 통해 통신하는 과정을 7단계로 나눈 것

[물리(L1), 데이터링크(L2), 네트워크(L3), 전송(L4), 세션(L5), 표현(L6), 응용(L7)] 계층

💸Socket이란?

TCP를 유저모드 어플리케이션이 접근할 수 있도록 파일 형식으로 추상화한 인터페이스 이미지 별표 100개, TCP/IP공부해라

각 계층 중에 식별자가 있다.

• Access 계층 : MAC 주소 (HW주소)
• Network 계층 : IP 주소
• 전송 계층 (TCP) : Port 번호

[포트번호, IP주소, MAC 주소]무엇에 대한 식별자인가?

1) MAC Address : Network Interface Card(LAN카드_무선/유선)에 대한 식별자

• = 하드웨어 주소
• ** MAC 주소 변경 가능? Yes**

2) IP 주소(Ipv4, Ipv6) : Host에 대한 식별자

• Host란? 인터넷(네트워크)에 연결된 컴퓨터
• 하나의 컴퓨터의 IP주소는 몇개? N개 가능 NIC1개에 여러개 바인딩 가능 NIC <-> IP 1 NIC <-> IP 2
• 즉, 컴퓨터 1개에 여러개 IP주소 가질 수 있다. *

3) Port 번호:

* 여러 형태로 식별 대상자가 달라진다

• SW개발/관리(user mode) -> Process 식별자
• 네트워크 관리 -> 서비스 식별자
• HW 관점 -> 인터페이스 번호

Host, Switch, Network

Host = computer + network

• 네트워크에 연결된 컴퓨터
• 1) network 이용하는 주체로서 host = ⭐️end-point = 단말기
  • 역할에 따라 나눔: Peer, server, client
• 2) network 자체를 이루는 host(컴퓨터) = switch router, 방화벽
  • IP 주소 가지고 스위치 한다 -> L3 스위치
  • L3 스위치 중 가장 대표적인 것 -> 라우터

Network = Internet

구성 요소 중대한 2가지

• router
• DNS
• 인터넷은 라우터랑, DNS의 집합체이다. *

오랜만에 네트워크 공부하려니 머리가 아프다.. 아무래도 기본 이론부터 차근차근 공부해야 될 듯 싶다

https://mamu2830.blogspot.com/2020/06/osi-7.html

1. OSI 7계층이란

컴퓨터가 네트워크를 통해 통신하는 과정을 7단계로 나눈 것

2. 프로토콜이란

공식적인 상황에서 사용되는 규칙

컴퓨터 공학도에서의 프로토콜이란

"다른 기계들과 통신을 하기 위해 지켜야 할 규칙"

• 통신은 전기적 신호를 일치시켜 정보를 교환하는 행위 이기 때문에 규칙(프로토콜)을 지켜야 한다.
• 인터넷을 통한 통신은 수 많은 기술들이 복합적으로 사용해 가능한 것이기 때문에 osi1~7까지 프로토콜이 정의되어 있다.
• "규칙"이라 해석할 경우 이해가 안되는 경우가 종종 있기 때문에, "기술"로 정의하고 이해하자
• HTTP(HyperText Transport Protocol)라고 네트워크 공부하면서 많이 들어보았을 텐데, 이는 "_HTTP 문서를 전송할 때 지겨야할 규칙_을 말한다.". 즉 _HTML 문서 전송 기술_이다.

3. 물리계층이란?

신호와 0과 1로 이루어진 데이터를 다루는 구간이다.

물리계층에서 데이터링크로 데이터를 전송할 때, 메인보드에 달린 랜카드에서 컴퓨터의 0과 1로 이루어진 데이터를, 전기적 신호를 변환해주는 랜카드와 연결된 랜 선으로 전송한다.

NIC(Network Interface Card)는 랜카드다. 네트워크 분야에서 나오는 Interface 용어는 데이터 신호가 흐르는 통로를 말한다. NIC은 "네트워크 데이터 신호가 흐르는 통로 카드"를 말한다.

4. 데이터링크 계층

1계층인 물리적계층을 지나서, _각 전선_들이 서로 연결될 때 사용되는 기술을 말한다. _서로 다른 신호_들이 연결되는 계층. "데이터들이 연결된다"라고 해서 데이터링크 계층이다. 데이터 링크 계층에는 _어떻게 다른 컴퓨터_들에서 오는 데이터를 혼동없이 원활히 처리해 다른 컴퓨터로 보내냐에 대한 프로토콜들이 있다. 대표적인 것으로 이더넷(Ethernet) 이 있고, 그 외에 FDDI, ATM, 토큰링 등이 있다. 그리고 _같은 네트워크에서 통신이 가능한 매개체들을 구분하고, 접근 및 사용_하기 위해 사용되는, 절대 겹치지 않는 주소인 MAC (Media Access Contrl)Address가 있다.

_📍이해 안가는 내용 위에서 말했다시피 통신이 가능하게 해주는 매개체를 구분하기 위한 것이 "MAC주소"로, "컴퓨터"인 경우 "랜 카드"가 0과1 데이터를 신호로 바꿔 통신이 되게 해주는 매개체죠?

그래서 랜카드에 "MAC주소"가 있습니다.📍_

그리고 이런 2계층 프로토콜과 MAC 주소를 이용해 같은 네트워크에 속한 매개체들의 원활한 통신을 가능하게 해주는 장비가 2계층 [L2]스위치이다.

기본적으로 "스위치"란, "트래픽을 적절히 분배해, 원활한 통신이 가능하게 해주는 장비"이다.

https://www.acmicpc.net/problem/15970 직선 위에 위치를 나타내는 0, 1, 2, ...와 같은 음수가 아닌 정수들이 일정한 간격으로 오른쪽 방향으로 놓여 있다. 이러한 위치들 중 N개의 위치에 하나씩 점들이 주어진다(<그림 1>). 주어진 점들의 위치는 모두 다르다. 두 점 사이의 거리는 두 점의 위치를 나타내는 수들의 차이이다. <그림 1>에서는 4개의 점이 주어지고 점 a와 b의 거리는 3이다.

각 점은 N개의 색깔 중 하나를 가진다. 편의상, 색깔은 1부터 N까지의 수로 표시한다.

각 점 p에 대해서, p에서 시작하는 직선 화살표를 이용해서 다른 점 q에 연결하려고 한다. 여기서, 점 q는 p와 같은 색깔의 점들 중 p와 거리가 가장 가까운 점이어야 한다. 만약 가장 가까운 점이 두 개 이상이면 아무거나 하나를 선택한다.

모든 점에 대해서 같은 색깔을 가진 다른 점이 항상 존재한다. 따라서 각 점 p에서 시작하여 위 조건을 만족하는 q로 가는 하나의 화살표를 항상 그릴 수 있다.

예를 들어, 점들을 순서쌍 (위치, 색깔) 로 표시할 때, a = (0,1), b = (1, 2), c = (3, 1), d = (4, 2), e = (5, 1)라고 하자.

아래 <그림 2>에서 이 점들을 표시한다. 여기서 흰색은 1, 검은색은 2에 해당된다.

위의 조건으로 화살표를 그리면, 아래 <그림 3>과 같이 점 a의 화살표는 c로 연결된다. 점 b와 d의 화살표는 각각 d와 b로 연결된다. 또한 점 c와 e의 화살표는 각각 e와 c로 연결된다. 따라서 모든 화살표들의 길이 합은 3 + 3 + 2 + 3 + 2 = 13이다.

점들의 위치와 색깔이 주어질 때, 모든 점에서 시작하는 화살표들의 길이 합을 출력하는 프로그램을 작성하시오.

입력

표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 점들의 개수를 나타내는 정수 N이 주어 진다. 다음 N개의 줄 각각에는 점의 좌표와 색깔을 나타내는 두 정수 x와 y가 주어진다.

출력

표준 출력으로 모든 점에서 시작하는 화살표들의 길이 합을 출력한다.

제한

모든 서브태스크에서 점들의 위치 x와 색깔 y는 각각 0 ≤ x ≤ 10^5, 1 ≤ y ≤ N를 만족한다.

문제 접근

주의

1) AttributeError: 'list' object attribute 'append' is read-only arr.append = x -> arr.append(x)

2) TypeError: list indices must be integers or slices, not list 2차원 리스트 순회

for color in arr:
    print(arr[color])

->

for color in range(n+1):
    arr[color].sort()

코드

import sys
n=int(sys.stdin.readline())
arr = [[] for _ in range(n+1)]
for _ in range(n):
    coord, color = map(int, sys.stdin.readline().split())
    arr[color].append(coord)

def left(idx, color):
    if idx==0:
        return 100000
    else:
        return arr[color][idx]-arr[color][idx-1]
def right(idx, color):
    if idx==len(arr[color])-1:
        return 100000
    else:
        return arr[color][idx+1]-arr[color][idx]

sum=0
for color in range(n+1):
    arr[color].sort()
    size=len(arr[color])
    for i in range(size):
        val = min(left(i, color), right(i,color))
        sum+=val

print(sum)

난이도 2

구분: 정렬

문제

P[0], P[1], ...., P[N-1]은 0부터 N-1까지(포함)의 수를 한 번씩 포함하고 있는 수열이다. 수열 P를 길이가 N인 배열 A에 적용하면 길이가 N인 배열 B가 된다. 적용하는 방법은 B[P[i]] = A[i]이다.

배열 A가 주어졌을 때, 수열 P를 적용한 결과가 비내림차순이 되는 수열을 찾는 프로그램을 작성하시오. 비내림차순이란, 각각의 원소가 바로 앞에 있는 원소보다 크거나 같을 경우를 말한다. 만약 그러한 수열이 여러개라면 사전순으로 앞서는 것을 출력한다.

입력

첫째 줄에 배열 A의 크기 N이 주어진다. 둘째 줄에는 배열 A의 원소가 0번부터 차례대로 주어진다. N은 50보다 작거나 같은 자연수이고, 배열의 원소는 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 비내림차순으로 만드는 수열 P를 출력한다.

예제 입력

3
2 3 1

예제 출력

1 2 0

문제 링크

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

문제 접근

• P배열은 0~n-1 의 값을 원소로 하나씩 가진다

• P 배열 -> A 배열-> B 배열

• B 배열은 비내림차순 (b1 <= b2 <= b3 ...) => A배열 정렬, sort()함수 이용

• B[P[i]] = A[i]를 예제 배열에 하나씩 적용하여 패턴 파악

  • P의 i번째 요소 값 => B가 A[i]을 원소로 가지는 인덱스 값

코드 1

import sys
n = int(sys.stdin.readline())
arr_a = list(map(int, sys.stdin.readline().split())
arr_b = sorted(arr_a)    # b배열은 비내림차순
arr_p = [0]*n
for i in range(n):
    p[i] = arr_b.index(arr_a[i])
for i in range(n):
    sys.stdout.write(str(p[i]) + ' ')

오류

문제 조건 중,

만약 그러한 수열이 여러개라면 사전순으로 앞서는 것을 출력한다

🛠 중복처리 p[x] = y 에서 y의 값이 같을 때 예외처리 안함! ✔️ index()함수는 가장 먼저 있는 원소의 인덱스 값 출력

해결 방법

• 중복되는 값은? b배열에 원소가 중복될 때, index값도 여러개
• arr_b 배열에 방문처리 하기
• arr_b[] = -1
• arr_b는 0~n-1 수를 하나씩 가짐
• 제거만 생각하고 변경을 생각하지 못했다

코드 2

import sys
n = int(sys.stdin.readline())
arr_a = list(map(int, sys.stdin.readline().split())
arr_b = sorted(arr_a)    # b배열은 비내림차순
arr_p = [0]*n
for i in range(n):
    index = arr_b.index(arr_a[i])
    p[i] = index
    arr_b[index] = -1    # 방문처리


for i in range(n):
    sys.stdout.write(str(p[i]) + ' ')

✔️ 조건1 : 정렬 조건이 필요하다

자료들이 주어졌을 때, 뭐가 앞에 와야되는지

✔️ 조건2 : 시간 복잡도는 약 O(NlogN)이다

N개의 원소를 정렬하는 것은 O(NlogN)만큼의 시간 복잡도를 갖는다.

✔️ 조건3 : In-place / Stable 여부를 알아야 한다.

1. 정렬 알고리즘이 In-place(제자리)한가?

• 정렬 하는 과정에서 N에 비해 충분히 무시할 만한 개수의 메모리만큼만 추가적으로 사용하는가?
• ex) 정렬 해야하는 원소 개수: 10만개, 필요한 메모리 10개 => In-place(메모리 무시할만한 크기)
• 정렬 해야하는 원소 개수: 10만개, 필요한 메모리 10만개 => not In-place(메모리 무시 크기 무시 X)

2. 정렬 알고리즘이 Stable(안정)한가?

• 동등한 위상의 원소들의 순서 관계가 보존되는가?
• ex) A배열은 5원소 2개(5-1, 5-2) 가지고 있음 => 정렬 후에도 5-1이 5-2보다 먼저 정렬되어야 함.

📍 정렬 특성

• 같은 정보들은 인접해 있을 것이다.
• 각 원소마다, 가장 가까운 원소는 자신의 양 옆 중에 있다.

📍 PYTHON 정렬 함수 & lambda

- sort()

< list >.sort(key = <function>, reverse = <bool>)

• 원본 자체를 수정하며, 반환값 없음
• sort함수는 inplace함수로 아무것도 리턴하지 않고, 기존 리스트 자체에서 정렬이 이루어짐

  - sorted()

  sorted( <list> , key = <function> , reverse = <bool>

• iterable 자료형에 대해 정렬 가능
• list 자료형으로 return
• 기존의 리스트는 건드리지 않고, 정렬된 새로운 리스트를 반환함 => 정렬 결과를 다른 변수에 따로 받고 싶은 경우 유용하게 쓰임

이처럼 lambda 함수를 이용하면 특정한 기준으로 정렬하는 대부분의 문제를 해결할 수 있다는 점을 기억하자!

✔️ 2중 리스트에서의 다중조건 정렬

• key 값으로 정렬
• key = lambda x : x[0] => 0번째 원소를 기준으로 오름차순 정렬
• key = lambda x : -x[0] => 0번째 원소를 기준으로 내림차순 정렬

✔️ key가 여러개 일 때?

• key = lambda x: (x[0] , x[2])
• x[0]을 우선순위로 정렬 후, x[0]이 같으면 x[2]를 기준으로 다시 정렬!

📍 BOJ 10825 - 국영수

난이도 1

문제

도현이네 반 학생 N명의 이름과 국어, 영어, 수학 점수가 주어진다. 이때, 다음과 같은 조건으로 학생의 성적을 정렬하는 프로그램을 작성하시오.

국어 점수가 감소하는 순서로 국어 점수가 같으면 영어 점수가 증가하는 순서로 국어 점수와 영어 점수가 같으면 수학 점수가 감소하는 순서로 모든 점수가 같으면 이름이 사전 순으로 증가하는 순서로 (단, 아스키 코드에서 대문자는 소문자보다 작으므로 사전순으로 앞에 온다.)

입력

첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. 이름은 알파벳 대소문자로 이루어진 문자열이고, 길이는 10자리를 넘지 않는다.

출력

문제에 나와있는 정렬 기준으로 정렬한 후 첫째 줄부터 N개의 줄에 걸쳐 각 학생의 이름을 출력한다.

🛠 문제 파악하기 - 정답의 최대치

형 결정 (입력 조건) 1 <= 모든점수 <= 100 => Integer 사용해도 충분하다!

🛠 시간, 공간 복잡도 계산하기

정렬만 하면 되니깐 O(NlogN)

• NlogN <= 100,000 * log100,000 = 1,600,000
• 즉 1초안에 충분히 가능한 연산이다!

🛠 리스트의 원소들을 정렬할 때는 람다(lambda) 함수 이용하기

• 이 문제는 정렬 문제를 공부하는데 필수로 풀어야 할 문제이다.

• 문제의 조건을 살펴보면 N이 최대 100,000이고 시간제한이 1초이다. 이는 O(N^2)로 풀지 말고 다른 방법으로 풀라는 뜻이다.
• 파이썬 정렬 라이브러리는 O(NlogN) 시간복잡도를 가지므로 시간 초과가 나지 않고 문제를 풀 수 있다.
• 따라서 정렬 라이브러리인 sort()함수를 이용하여 lambda 함수로 해결한다.
• lambda 함수의 기본 형식은 list.sort(key=lambda x:(정렬대상)) or
• sorted(list, key=lambda x:(정렬 대상))이다.

코드1

import sys
n = int(sys.stdin.readline())
array = [list(map(str, sys.stdin.readline().split(' '))) for _ in range(n)]
sorted_array = sorted(array, key = lambda x: (-int(x[1]), int(x[2]), -int(x[3]), x[0]))

for arr in sorted_array:
    sys.stdout.write(arr[0])
    sys.stdout.write('\n')

✨ 코드2 (클래스-구조체)

import sys

class Elem:
    def __init__(self, name, korean, english, math):
        self.name = name
        self.korean = korean
        self.english = english
        self.math = math

n = int(sys.stdin.readline())
a = []

for i in range(n):
    inp = sys.stdin.readline().split()
    inp[1:] = map(int, inp[1:])        # 이름 inp[0] 빼고 int형으로 변환 
    a.append(Elem(*inp))

a.sort(key = lambda x: (-x.korean, x.english, -x.math, x.name))

names = [elem.name for elem in a]
for name in names:
    print(name)

참고 https://velog.io/@yeseolee/Python-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%9E%85%EB%A0%A5-%EC%A0%95%EB%A6%ACsys.stdin.readline https://velog.io/@hyejin_nk/파이썬-sorted-정렬-조건-다중-조건 https://data-flower.tistory.com/89

1. (1) N개 중 중복을 허용하여 (A)M개를 순서있게 나열하기
2. (1) N개 중 중복을 허용하여 (B)M개를 고르기
3. (2) N개 중 중복 없이 (A)M개를 순서있게 나열하기
4. (2) N개 중 중복 없이 (B)M개를 고르기

1. N개중 중복을 허용하여 M개를 순서 있게 나열하기

BOJ 15651 - N과 M (3)

def dfs(cnt):
    if cnt == m:
    # 수열 완성
    for i in arr:
        sys.stdout.write(str(i) + ' ')
     sys.stdout.write('\n')
    else:
        for i in range(1, n+1):
            arr[cnt]=i
            dfs(cnt+1)
            arr[cnt]=0
 dfs(0)

2. N개중 중복을 허용하여 M개를 고르기

BOJ 15652 - N과 M(4)

def dfs(cnt):
    if cnt == m:
        for i in arr:
            sys.stdout.write(str(i) + ' ')
        sys.stdout.write('\n')
    else:
        start = 1 if cnt==0 else arr[cnt-1]
        for i in range(start , n+1):
            arr[cnt]=i
            dfs(cnt+1)
            arr[cnt]=0

3. N개중 중복없이 M개를 순서있게 나열하기

BOJ 15649 - N과 M(1)

def dfs(cnt):
    if cnt == m:
        #수열 완성
        for i in arr:
            sys.stdout.write(str(i)+' ')
        sys.stdout.write('\n')
    else:
        for i in range(1, n+1):
            if i in arr:
                continue
            arr[cnt]=i
            dfs(cnt+1)
            arr[cnt]=0

4. N개중 중복없이 M개를 고르기

BOJ 15650 - N과 M (2)

def dfs(cnt):
    if cnt==m:
        for i in arr:
            sys.stdout.write(str(i) + ' )
        sys.stdout.write('\n')
    else:
        start=0 if cnt==0 else start=arr[cnt-1]+1
        for i in range(start, n+1):
            arr[cnt]=i
            dfs[cnt+1]
            arr[cnt]=0

완전 탐색 문제를 접근할 때는

• 고를 수 있는 값의 종류 파악하기
• 중복을 허용하는지
• 순서가 중요한지

• 문제를 해결하기 위해 확인해야 하는 모든 경우를 전부 탐색하는 방법
• 그 중에서도 백트래킹을 통해야 하는 상황을 해결하기
• 모든 코테 문제에서 기본적으로 접근해 봐야 한다. 많은 연습 필요
• 부분점수를 얻기 좋다
• 전부 탐색하기에 시간 복잡도가 일반적으로 높다

완전 탐색 알고리즘 종류

단순 Brute-Force

• 단순히 반복문(for)과 조건문(if)으로 모든 경우(case)를 만들어 답을 구하는 방법
• 이 방법만을 사용하는 문제는 거의 나오지 않음

비트마스크(Bitmask)

• 나올 수 있는 모든 경우의 수가 각각의 원소를 포함하거나, 포함하지 않는 두가지 선택으로 구성되는 경우 유용하게 사용
• ex) '원소가 n개인 집합의 모든 부분 집합'을 구한다면, 각 원소가 포함되는 경우와, 포함되지 않는 경우를 0과 1로 구분함

재귀함수

• 비트마스크와 마찬가지로 각 원소가 두가지 선택지를 가질 때 유용하게 사용
• 포함이 되면 해당 원소를 넣어 함수를 호출하고, 포함되지 않으면 그 상태에서 함수를 호출하는 등의 식
• ex) 위 부분집합 문제를 예로, 만들고자 하는 부분집합을 S'라고 할 때, S' = { } 부터 시작해서 각 원소에 대해서 해당 원소가 포함이 되면 S'에 넣고 재귀 함수를 돌려주고, 포함이 되지 않으면 S'를 그대로 재귀 함수에 넣어주는 방식이다.
• ex) 피보나치 수열
• 시간복잡도 O(N)

여기서 중요한 점! (1) 재귀를 탈출하기 위한 탈출 조건이 필요! (2) 현재 함수의 상태를 저장하는 Parameter 필요!

• cnt 통해 몇 개를 선택했는지 전달.이것이 없다면 현재 함수의 상태를 저장할 수 없어 재귀 탈출 조건을 만들 수 없게 되거나 잘못된 결과 출력! (3) Return문 신경 쓸 것!
• 재귀를 통해 이후의 연산 결과를 반환 후 이전 결과에 추가 연산을 수행하는 경우도 있을 수 있다

순열

• 오나전 탐색의 대표적인 유형
• 순열은 서로 다른 N개의 원소를 일렬로 나열하는 경우의 수를 말함
• 순열의 경우의 수는 N!으로 완전 탐색을 이용하기 위해서는 N이 한자리 수는 되어야 함.
• 순서가 중요함! 만약, 수열에서 숫자 [1, 2, 3]이 있다면, 이것을 [1, 2, 3]으로 보는 순서와 [3, 2, 1]로 보는 순서가 차이가 있음이 중요한 경우를 의미한다.
• 순열에 원소를 하나씩 채워가는 방식
• 재귀 함수 이용
• 시간복잡도 O(N!)

너비 우선 탐색(BFS), 깊이 우선 탐색(DFS)

• 약간의 난이도 있는 문제, 완전 탐색 + BFS/DFS 문제 많이 나옴
• 너비 우선 탐색(Breadth-First Search, BFS)는 하나의 요소를 방문하고, 그 요소에 인접한 모든 요소를 우선 방문하는 방식
• 깊이 우선 탐색(Depth-First Search, DFS)는 트리의 한 노드와 다른 레벨의 자식 노드를 따라가는 방햑으로 탐색하는 방식
• 길 찾기 등에 주로 쓰이는 알고리즘 : 단순 길찾기에는 BFS/DFS만 써도 무방하지만, 장애물이 존재하는 등 추가적 연산이 필요할 때 완전탐색과 병용하기도 함
• ex) 지구 상에 존재하는 모든 친구 관계를 그래프로 표현하고, A와 B사이에 존재하는 경로 찾을 때
• DFS : 모든 친구 관계를 다 살펴야 한다.
• BFS : A와 가까운 관계부터 탐색한다

추천 문제

★ BOJ 14502 연구소 ★ BOJ 9663 N-Queen ★ BOJ 15686 치킨 배달 ★ BOJ 1062 가르침 ★ BOJ 10819 차이를 최대로 ★ 2309번: 일곱 난쟁이 ★ 2231번: 분해합 ★ 3085번: 사탕 게임 ★ 10448번: 유레카 이론 ★ 2503번: 숫자 야구 ★ 1018번: 체스판 다시 칠하기 ★ 1182번: 부분집합의 합 (★)

참고

https://rebro.kr/59 https://hongjw1938.tistory.com/88 https://hongjw1938.tistory.com/78

백트랙킹

문제

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

출력

첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

예제 입력

5 0 -7 -3 -2 5 8

예제 출력

1

접근방법

이 문제는 부분수열의 모든 경우의 수는 이진트리로 나타낼 수 있음을 알아야 풀 수 있는 문제다. 처음에 어떻게 접근해야 할지 전혀 감이 안왔는데, 원소가 포함되는 경우와 포함되지 않는 경우를 이진트리로 모든 경우의 수를 탐색할 수 있음을 배웠다.

코드

import sys
n,s = map(int, sys.stdin.readline().split(' '))
arr = list(map(int, sys.stdin.readline().split(' ')))
ans = 0

def dfs(cnt, value):
    global ans
    if cnt==n:
        if value==s:
            ans+=1
    else:
        #include
        dfs(cnt+1, value+arr[cnt])
        #not include
        dfs(cnt+1, value)

dfs(0, 0)
print(ans)

실패

크기가 양수인 부분수열 을 고려하지 않은 코드다. 만약 s가 0일 때, 모든 원소를 포함하지 않았다면, 합은 0이 되고, ans을 1 증가시킨다. 이 경우에는 위의 조건, 즉 크기가 양수인 부분수열이 아니기 때문에 정답에서 배제시켜야 한다.

성공 코드

import sys
n,s = map(int, sys.stdin.readline().split(' '))
arr = list(map(int, sys.stdin.readline().split(' ')))
ans = 0

def dfs(cnt, value):
    global ans
    if cnt==n:
        if value==s:
            ans+=1
    else:
        #include
        dfs(cnt+1, value+arr[cnt])
        #not include
        dfs(cnt+1, value)

dfs(0, 0)
if s==0:
    ans-=1
print(ans)

이진트리로 모든 원소를 탐색할 수 있음을 알고 있어야 하고, 예외조건까지 생각할 수 있어야 되는 까다로운 문제이다. 하지만 접근 방법을 힌트로 코드를 짜보니 아예 절망편은 아니였다!

• 백트랙킹은 알고리즘 기법 중 하나로, 재귀적으로 문제를 하나씩 풀어가되, 현재 재귀를 통해 확인중인 노드(상태)가 제한 조건에 위배되는지(유망하지 않은지) 판단하고, 그러한 경우에는 해당 노드(상태)를 제외하고 다음 단계로 나아가는 방식이다.

  여기서 중요한 점은 특정 노드(상태)를 제외한다는 것이다!

• 백트랙킹은 현재 상태(노드)에서 다음 상태(노드)로 나아갈 수 있는 모든 경우를 찾되, 그 중 유망하지 않다면 현재에서 더 이상 나아가지 않고 이전의 상태(노드)로 돌아가 다음 상태(노드)를 검사한다.

• 백트랙킹을 사용하는 알고리즘 중 하나는 대표적으로 DFS가 있다. DFS는 재귀를 통해 가능한 경로 중 유망한 경로만 찾아서 탐색한 뒤 다시 돌아와 그 중 가장 최적의 경로를 반환한다.

• 백트랙킹을 사용해 해결할 수 있는 문제는 의사 결정, 최적화, 열거하기 등이 있다.

• 사실 백트랙킹은 사용 가능한 경우가 많지만 시간 복잡도가 보통 Exponential(지수, 2^n 꼴)이며, 대부분 Dynamic Programming, 그리디 알고리즘 등으로 더 빠르게 해결할 수 있다.

• 하지만 일부 문제들은 여전히 백트랙킹으로만 해결이 가능한 문제도 있다..!

백트랙킹 사용 예

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

문제 정의

• 각 행당 하나의 퀸이 놓인다.
• 다음 행에 놓일 퀸의 위치는 백트랙킹 방법을 이용한다.

  첫번째 행에 퀸을 놓는다. 두번째 줄에 되는 칸이 있으면, 세번째 줄로 내려간다. 세번째 줄에 되는 칸이 없으면, 다시 두번째 줄로 올라간다.

• 이때, 이전 행에 놓인 퀸들과 같은 열에 놓여있는지와 같은 대각선상에 위치하는지 체크해야한다.
• 여기서 같은 대각선상 이란 (1)왼쪽아래에서 오른쪽 위로의 방향, (2)왼쪽위에서 오른쪽 아래로의 방향을 말한다.
• row == n 은 각 행당 퀸이 모두 놓인 경우이므로, sum+=1을 해준다.
• 처음에 2차원 배열을 이용했지만,
• arr 배열에서의 인덱스를 행과 대응, 인덱스를 값에 대응하면 1차원 배열으로도 풀 수 있다!
• ex) arr[3]=2 : 3번째행의 2열에 퀸이 놓여있다.

  • 백트래킹은 재귀함수를 사용한다.
  • 함수를 이용하자!

위 사진에서는 3번째 열에서 어떠한 곳에서든 퀸을 배치할 수 없다! 그러니 백트랙킹으로 2번째 열로 돌아가 다시 다른 행에 배치한다.

코드1

import sys
n = int(sys.stdin.readline())
arr=[0 for _ in range(n)]
sum=0

def check(r1, c1, r2, c2):
    if c1==c2:
        return True        # 같은 열
    if r1-c1=r2-c2:
        return True     # (1)번 대각선
    if r1+c1=r2+c2:
        return True        # (2)번 대각선
    return False

def dfs(row):
    if row==n:
        global sum
        sum+=1
    else:
        for cand in range(n):    # row행에 퀸이 놓일 열을 순차적으로 탐색
            possible=True
            for i in range(row):    # row이전 행들에 놓인 퀸에 대해서 열, 대각선 체크
                if check(row, cand, i, arr[i]):
                    possible=False
                    break
            if possible:
                arr[row]=cand
                dfs(row+1)
                arr[row]=0
 dfs(0)
 print(sum)

코드2

import sys
n = int(sys.stdin.readline())
arr = [0 for _ in range(n)]
sum = 0

def check(row):
    for i in range(row):
        if arr[row]==arr[i] or abs(arr[row]-arr[i])==abs(row-i):    # 같은 열, 대각선 (1), 대각선 (2) 이면,
            return False
    return True

def dfs(row):
    if row == n:
        global sum
        sum+=1
    else:
        for cand in range(n):    # row행에 퀸이 놓일 열을 순차적으로 탐색
            arr[row]=cand    #행 값 고정
            if check(row):
                dfs(row+1)

코드1,2 모두 python3으로 제출하면 시간초과 발생,, pypy3로 제출해야 함.

다른 백트랙킹 문제

The knight's tour problem (https://www.geeksforgeeks.org/the-knights-tour-problem/) Rat in a Maze (https://www.geeksforgeeks.org/rat-in-a-maze/) Subset Sum(https://www.geeksforgeeks.org/subset-sum-problem/) m Coloring Problem(https://www.geeksforgeeks.org/m-coloring-problem/)

DFS와 백트랙킹(Backtracking)의 차이

• DFS는 기본적으로 그래프 형태 자료구조에서 모든 정점을 탐색할 수 있는 알고리즘 중 하나이다.
• 깊이를 우선으로 탐색하기에 재귀 또는 스택을 이용한다.
• 재귀를 이용해 탐색을 수행한다는 부분에서 완전탐색 알고리즘에서의 재귀/백트랙킹과 유사한 측면이 보여 혼란이 올 수도 있다.
• 그런데, 재귀라는 것은 말 그래도 스스로의 함수를 호출하는 방식을 의미하는 것이므로 DFS가 재귀를 이용해 탐색을 수행하는 것으로 하나의 방식이라 이해하면 된다.
• 또한 백트랙킹은 재귀를 통해 알고리즘을 풀어 가는기법 중 하나로 가지치기를 통해 탐색을 시도하다가 유망하지 않으면 추가 탐색을 하지 않고 다른 해를 찾는 방법이다.
• DFS는 기본적으로 모든 노드를 탐색하는 것이 목적이지만 상황에 따라서 백트랙킹 기법을 혼용하여 불필요한 탐색을 그만두는 것이 가능하다!

즉, DFS와 백트랙킹은 유사한 부분이 있으며 기본적으로 사용 목적이 다르지만 두 기법을 혼용하여 사용하는 것이 가능하다! 완전히 다른 개념이 아니라 재귀 호출을 통한 기법 중 하나이기 때문이다.

참고

https://sso-feeling.tistory.com/415 https://hongjw1938.tistory.com/88

엔티티 매니저 팩토리

// 데이터베이스를 하나만 사용하는 애플리케이션은 일반적으로 EntityManagerFactory를 하나만 생성
EntityManagerFactory emf = Persistence.createManagerFactory("jpabook");

• 엔티티 매니저 팩토리는 엔티티 매니저를 만드는 공장인데 비용이 아주 많이 든다.
• 따라서 한 개만 만들고 애플리케이션 전체에서 공유하도록 설계되어 있다.
• 여러 스레드가 동시에 접근해도 안전하다
• META-INT/persistence.xml에 있는 정보를 바탕으로 EntityManagerFactory 생성

엔티티 매니저

//공장에서 엔티티 매니저 생성, 비용이 거의 안 든다.
EntityManager em = emf.createEntityManager();

• 여러 스레드가 동시 접근하면 동시성 문제가 발생하므로 스레드 간 공유 X

• 하나의 EntityManagerFactory에서 다수의 엔티티 매니저 생성
• EntituManager1은 아직 데이터베이스의 커넥션 사용 X -> 엔티티 매니저는 데이터베이스 연결이 꼭 필요한 시점까지 커넥션 얻지 않는다.

📌 영속성 컨텍스트란?

• '엔티티를 영구 저장하는 환경'
• 엔티티 매니저로 엔티티를 저장하거나 조회하면 엔티티 매니저는 영속성 컨텍스트에 엔티티를 보관하고 관리

참고) 여러 엔티티 매니저가 같은 영속성 컨텍스트에 접근할 수도 있다.

📌 엔티티의 생명주기

• 비영속(new/transient): 영속성 컨텍스트와 전혀 관계가 없는 상태
• 영속(managed): 영속성 컨텍스트에 저장된 상태
• 준영속(detached): 영속성 컨텍스트에 저장되었다가 분리된 상태
• 삭제(removed): 삭제된 상태

📌 영속성 컨텍스트의 특징

• 영속성 컨텍스트와 식별자 값

  • 영속성 컨텍스트는 엔티티의 식별자 값(@Id로 테이블의 기본 키와 매핑한 값)으로 구분
  • 영속성 상태의 엔티티는 식별자 값 반드시 존재해야 함

• 영속성 컨텍스트와 데이터베이스 저장

  • 트랜잭션 커밋하는 순간 영속성 컨텍스트의 변경 내용이 데이터베이스에 반영(플러시)

• 장점

  • 1차 캐시
  • 동일성 보장
  • 트랜잭션을 지원하는 쓰기 지연
  • 변경 감지
  • 지연 로딩

엔티티 조회

• 영속성 컨텍스트는 내부에 캐시 존재, 이것을 1차 개시라 함.
• 영속성 상태의 엔티티는 모두 이곳에 저장
• 1차 캐시의 키는 식별자 값(데이터베이스의 기본 키와 매핑)
• 따라서 영속성 컨텍스트에 데이터를 저장하고 조회하는 모든 기준은 데이터베이스 기본 키 값

  Member member = new Member();
  member.setId("member1");
  member.setUserName("회원1");
  

//엔티티를 영속 em.persist(member);

Membe member = em.find(Member.class, "member1");

em.find()를 호출하면 먼저 1차 캐시에서 엔티티 조회, 1차 캐시에 없으면 데이터베이스에서 조회

### 1차 캐시에서 조회
![](https://media.vlpt.us/images/uuuuu_j_/post/79ed5e09-75b4-42c9-a3e4-335121be1cee/IMG_54ED56F08F54-1.jpeg)
em.find()를 호출하면 우선 1차 캐시에서 식별자 값으로 엔티티를 찾는다. 만약 찾는 엔티티가 있으면 데이터베이스를 조회하지 않고 메모리에 있는 1차 캐시에서 엔티티를 조회한다.

### 데이터베이스에서 조회

만약 em.find()를 호출했는데 엔티티가 1차 캐시에 없으면 엔티티 매니저는 데이터베이스를 조회해서 엔티티를 생성하고 1차 캐시에 저장. 영속 상태의 엔티티를 반환한다. 
![](https://media.vlpt.us/images/uuuuu_j_/post/c11331c7-e6c1-4861-af36-fbc7b1f1c945/IMG_8F7359F5D8C1-1.jpeg)
1. em.find(Member.class, "member2") 실행
2. member2가 1차 캐시에 없으므로 데이터베이스에서 조회
3. 조회한 데이터로 member2 엔티티를 생성해서 1차 캐시에 저장(영속 상태)
4. 조회한 엔티티를 반환

member1, member2를 조회하면 메모리에 있는 1차 캐시에서 바로 불러온다. 따라서 성능상 이점을 누릴 수 있다. 

### 영속 엔티티의 동일성 보장

Member a = em.find(Member.class, "member1"); Member b = em.find(Member.class, "member1");

같은 식별자 값으로 엔티티를 조회했다. 영속성 컨텍스트는 **1차 캐시**에 있는 **같은 엔티티 인스턴스**를 반환해서 a==b의 결과는 참이다. 따라서 영속성 컨텍스트는 성능성 이점과 엔티티의 동일성을 보장한다. 

### 트랜잭션을 지원하는 쓰기 지연
#### 엔티티 등록

엔티티 매니저는 트랜잭션을 커밋하기 직전까디 내부 쿼리 저장소에 SQL을 모아두고, 트랜잭션 커밋 시(플러시) 모아둔 쿼리를 데이터베이스에 보낸다.
![](https://media.vlpt.us/images/uuuuu_j_/post/cc098f45-63a3-426f-94b1-65cddb2958fa/IMG_ACBB6EDFCDF9-1.jpeg)
회원A를 영속화했다. 영속성 컨텍스트는 1차 캐시에 엔티티를 저장하면서 동시에 쿼리를 만들고 쓰기 지연 SQL 저장소에 보관한다. 

### 변경 감지
JPA는 엔티티를 어떻게 수정할까?
👉 JPA로 엔티티를 수정할 땐 단순히 엔티티를 조회하고 데이터만 변경하면 된다. 
👉 엔티티의 변경사항을 데이터베이스에 자동으로 반영하는 기능을 변경 감지라 한다.
![](https://media.vlpt.us/images/uuuuu_j_/post/00f266af-3a80-46a7-b356-91d22013b72f/IMG_1681F9793370-1.jpeg)
1. 트랜잭션을 커밋하면 flush()가 호출된다.
2. 엔티티의 스냅샷과 비교해서 변경된 엔티티를 찾는다,
3. 변경된 엔티티가 있으면 수정 SQL문 생성해서 쓰기 지연 SQL 저장소에 저장한다.
4. 쓰기 지연 저장소의 SQL을 데이터베이스에 보낸다.
5. 데이터베이스 트랜잭션을 커밋한다.
+JPA는 엔티티를 영속성 컨텍스트에 보관할 때 최초 상태를 복사해서 저장해 두는데, 이것을 **스냅샷**이라 한다.

# 📌 플러시
#### 플러시란?
영속성 컨텍스트의 변경 내용을 데이터베이스에 동기화하는 것

#### 플러시가 실행하면 구체적으로 다음과 같은 일이 일어난다.
1. 변경 감지가 동작한다. 
(영속성 컨텍스트에 있는 모든 엔티티가 스냅샵과 비교해서 수정된 엔티티를 찾는다. 수정된 엔티티는 수정 쿼리를 만들어 쓰기 지연 SQL 저장소에 등록한다.)
2. 쓰기 지연 SQL 저장소의 쿼리를 데이터베이스에 전송한다.

### 영속성 컨텍스트를 플러시 하는 방법

1. em.flush() 직접 호출

2. 트랜잭션 커밋 시 플러시가 자동 호출된다.

3. JPQL 쿼리 실행 시 플러시가 자동 호출된다.


# 📌 준영속
- 영속 상태의 엔티티가 영속성 컨텍스트에서 분리된 것
- 영속성 컨텍스트가 제공하는 기능 사용 X(영속성 컨텍스트가 관리X)

### 영속 상태의 엔티티를 준영속 상태로 만드는 방법
1. em.detach(entity): 특정 엔티티만 준영속 상태로 전환한다.
![](https://media.vlpt.us/images/uuuuu_j_/post/3cc66277-d4f0-4617-ba44-5bb4792e6f16/IMG_E255567CFEB9-1.jpeg)
![](https://media.vlpt.us/images/uuuuu_j_/post/a7d0ce59-8179-45cc-8759-049deb8eafa9/IMG_EFC1F017B766-1.jpeg)
- 1차 캐시부터 쓰기 지연 SQL 저장소까지 해당 엔티티와 관련된 모든 정보가 제거된다. 
- 데이터베이스에 반영 X
2. em.clear()
![](https://media.vlpt.us/images/uuuuu_j_/post/81f6a2e2-4861-49f0-9095-f40eac794477/IMG_9CC26D0A7931-1.jpeg)
![](https://media.vlpt.us/images/uuuuu_j_/post/d288412d-8429-4c73-a63e-d6365f5f4038/IMG_9F55B509A555-1.jpeg)
- 영속성 컨텍스트를 완전히 초기화
- 해당 영속성 컨텍스트의 모든 엔티티 준영속 상태 됨
- 준영속 상태이므로 변경 감지 동작 X,데이터베이스에 반영 X

3. em.close()
![](https://media.vlpt.us/images/uuuuu_j_/post/d712d78a-dc4e-45a0-a9e3-12b3e38cd0fb/IMG_A23083679091-1.jpeg)
![](https://media.vlpt.us/images/uuuuu_j_/post/220aeabe-f0f1-4204-ab52-a067b63d4dc5/IMG_8FD349B8BBDD-1.jpeg)
- 영속성 컨텍스트를 종료
- 해당 영속성 컨텍스트기 관리하던 영속 상태의 엔티티가 모두 준영속 상태 됨

### 준영속 상태의 특징
1. 영속성 컨텍스트가 관리하지 않으므로 1차 캐시, 쓰기 지연, 변경 감지, 지연로딩 동작 X
2. 준영속 상태는 이미 한번 영속상태였으므로 반드시 식별자 값 가짐


### 병합: merge()
- 준영속 상태의 엔티티를 다시 영속 상태로 변경(새로운 영속 상태의 엔티티 반환)함
![](https://media.vlpt.us/images/uuuuu_j_/post/20621c69-81d7-4960-b783-dd51d8793b06/IMG_96B6FDAFF2FD-1.jpeg)
1. merge()를 실행
2. 파라미터로 넘어온 준영속 엔티티의 식별자 값으로 **1차 캐시**에서 엔티티 조회
2-1. 1차 캐시에 엔티티가 없으면 데이터베이스에서 엔티티 조회후 1차 캐시에 저장
3. 조회한 영속 엔티티(mergeMember)에 member엔티티 값을 채움
(이때 merberMember의 이름이 "회원명 변경"으로 바뀐다.)
4. memberMember를 반환


<br></br>
![](https://images.velog.io/images/uuuuu_j_/post/a9d9c8e1-038a-4c1e-b778-d11dda2fa8b3/%EC%8A%A4%ED%81%AC%EB%A6%B0%EC%83%B7%202022-01-06%20%EC%98%A4%ED%9B%84%2011.24.36.png)


> 이 글은 김영한님의 자바 ORM 표준 JPA 프로그래밍 책을 참고하였습니다.

1. 무한 반복, 지루한 코드

JPA를 사용하지 않고,SQL과 JDBC를 사용해서 회원 객체를 생성하고, 회원을 찾는 코드는 다음과 같다.

public class Member{
    private String memberId;
    private String name;
}

public class MemberDAO {
    public Member find(String memberId){...}
}

MemberDAO의 find() 메소드 작성해보자.

1. 회원 조회용 SQL을 실행한다. SELECT MEMBER_ID, NAME FROM MEMBER M WHERE MEMBER_ID = ?

2. JDBC API를 사용해서 SQL을 실행한다. ResultSet rs = stmt.executeQuery(sql);

3. 조회 결과를 Member 객체로 매핑한다

   String memberId = rs.getString("MEMBER_ID");
   String name = rs.getString("NAME");
   

Member member = new Member(); member.setMemberId(memberId); member.setName(name);

회원 조회하는 기능을 만들었다. 
등록, 수정, 삭제하는 기능도 SQL을 작성하고, JDBC API를 사용하는 비슷한 일을 반복해야 할 것이다. 
데이터베이스는 객체 구조와는 다른 **데이터 중심의 구조**를 가지므로 **객체를 데이터베이스에 직접 저장하거나 조회할 수 없다**. 
따라서 개발자가 객체 지향 애플리케이션과 데이터베이스 중간에서 SQL과 JDBC를 사용해서 변환 작업(객체 -> 데이터 구조)을 직접 해주어야 한다. 이 작업을 JPA가 대신 해줘서 개발자는 객체지향 개발에 더 집중할 수 있다.  

## 2. SQL에 의존적인 개발의 문제점
### 🔎 1) 등록 코드 변경
위에 작성한 Member 필드에 연락처 컬럼을 추가하면, insert, select, update, delete SQL 쿼리도 맞춰서 다 수정해야 하는 불편함이 있다. 

public class Member{ private String memberId; private String name; private String tel; //연락처 컬럼 추가 }

String sql = "SELECT MEMBER_ID, NAME, TEL FROM MEMBER WHERE MEMBER_ID = ?";

Member 클래스에 연락처 컬럼을 추가해서 SELECT 쿼리도 그에 맞게 수정한다. 

String tel = rs.getString("TEL"); member.setTel(tel)

Member 객체를 매핑할 때도 그에 맞게 수정해야 하는 불편함이 있습니다. 

### 🔎 2) 연관된 객체
회원은 어떤 한 팀에 필수로 소속되어야 한다는 요구사항이 추가되었다.

class Member{ private String memberId; private String name; private String tel; private Team team; //추가

//Team 객체 반환 
public Team getTeam(){
    return team;
}

}

//추가된 팀 class Team{ private String teamName; }

**member.getTeam();** 을 실행하면 값이 항상 null이다.
MemberDAO 클래스를 열어서 Member를 조회하는 find() 메소드를 보니 위에 작성한 **회원만 조회**하는 "SELECT MEMBER_ID, NAME, TEL FROM MEMBER M WHERE MEMBER_ID = ?" SQL을 그대로 유지했다.
**회원과 연관된 팀을 함께 조회**하는 findWithTeam()메소드에 다음과 같은 sql문을 추가하자.

public class MemberDAO { public Member find(String memberId){...} public Member findWithTeam(String memberId){...} }

<회원 + 팀 조회 : Member, Team 조인>

SELECT M.MEMBER_ID, M.NAME, M.TEL, M.TEAM_ID, T.TEAM_NAME FROM MEMBER M JOIN TEAM T ON M.TEAM_ID = T.TEAM_ID

결국 MemberDAO 클래스를 열어서 SQL을 확인하고 나서야 null 값이 나오는 원인을 알 수 있었고, 
회원 조회 코드를 MemberDAO.find()에서 MemberDAO.findWithTeam()으로 변경해서 문제를 해결해야 한다.

정리:
Member 객체가 연관된 Team 객체를 사용할 수 있을지는 사용하는 **SQL**에 달려있다. 
데이터 접근 계층을 사용해서 SQL을 숨겨도 어쩔 수 없이 **DAO를 열어서 어떤 SQL이 실행되는지 확인해야 한다**는 문제가 있다. = 엔티티를 신뢰할 수 없다

## 3. 정리
- 진정한 의미의 계층 분할이 어렵다.
- 엔티티를 신뢰할 수 없다.
- SQL에 의존적인 개발을 피하기 어렵다.

## 4. JPA와 문제 해결
JPA를 사용하면 객체를 데이터베이스에 저장하고 관리할 때, 개발자가 직접 SQL을 작성하는 것이 아니라 JPA가 제공하는 API를 사용하면 된다. 그러면 JPA가 개발자 대신에 적절한 SQL을 생성해서 데이터베이스에 전달한다.

jpa.persist(member); //저장 -> .persist() jpa.find(Member.class, "helloId"); //조회 -> find()

Member member = jpa.find(Member.class, memberId); member.setName("변경"); //수정

Member member = jpa.find(Member.class, memberId); Team team = member.getTeam(); //연관된 객체 조회 , sql문 확인 필요 X

수정 기능-> 객체를 조회해서 값을 변경하면 트랜잭션 커밋할 때 update SQL이 데이터베이스에 전달됨. **변경 감지(Dirty Checking)**




# 📌 패러다임의 불일치
## 1. 상속
![](https://images.velog.io/images/uuuuu_j_/post/495fd105-d452-4ba9-ab8f-5be48b60a586/IMG_1643.jpg)
![](https://images.velog.io/images/uuuuu_j_/post/b29dbf85-994e-4336-a401-6ff80f3c29da/IMG_1644.jpg)
Album 객체를 저장하려면 이 객체를 분해해서 다음 두 SQL을 만들어야 한다.

INSERT INTO ITEM... INSERT INTO ALBUM...

JDBC API를 사용해서 이 코드를 완성하려면 부모 객체에서 부모 데이터만 꺼내서 ITEM용 INSERT SQL을 작성하고, 자식 객체에서 자식 데이터만 꺼내서 ALBUM용 INSERT SQL을 작성해야 하는데, 작성해야 할 코드량이 만만치 않다. 
조회할 때도 ITEM과 ALBUM 테이블을 조인해서 조회한 수 ALBUM 객체를 생성해야 한다.
이런 과정이 모두 패러다임 불일치를 해결하려고 소모하는 비용이다.

## 2. JPA와 상속
JPA는 상속과 관련된 패러다임의 불일치 문제를 개발자 대신 해결해준다.
**저장**
![](https://images.velog.io/images/uuuuu_j_/post/05ca4d79-d1d7-40d2-aa59-9c06be7cafca/%EC%8A%A4%ED%81%AC%EB%A6%B0%EC%83%B7%202022-03-18%20%EC%98%A4%ED%9B%84%2010.15.13.png)

**조회**
![](https://images.velog.io/images/uuuuu_j_/post/9b23541c-7226-4ee4-ae5a-962b0d35e38a/%EC%8A%A4%ED%81%AC%EB%A6%B0%EC%83%B7%202022-03-18%20%EC%98%A4%ED%9B%84%2010.16.46.png)

## 3. 연관관계
객체는 참조를 사용해서 다른 객체와 연관관계를 가지고 조회한다.
반면에 테이블은 외래 키를 사용해서 다른 테이블과 연관관계를 가지고, 조인을 사용해서 조회한다.
객체는 참조가 있는 방향으로만 조회 가능하다. member.getTeam()은 가능하지만 반대 방향인 team.getMember()은 불가능하다.
반면에 테이블은 외래 키 하나도 MEMBER JOIN TEAM, TEAM JOIN MEMBER이 가능하다.

class Member {

String id;
Team team;
String username;

}

class Team{

long id;
String name;

}

JPA는 team의 참조를 외래 키로 변환해서 적절한 INSERT SQL을 데이터베이스에 전달한다. 객체를 조회할 때 외래 키를 참조로 변환하는 일도 JPA가 처리해준다.

member.setTeam(team) //회원과 팀 연관관계 설정 jpa.persist(member) //회원과 연관관계 함께 저장

Member member = jpa.find(Member.class, memberId); Team team = member.getTeam();

## 4. 객체 그래프 탐색
객체는 자유롭게 객체 그래프를 탐색할 수 있어야 한다. 하지만 처음 실행하는 SQL에 따라 탐색 범위가 결정된다.
예를 들어, MemberDAO에서 member객체를 조회할 때 아래의 SQL을 실행하면 member.getTeam()은 성공하지만, member.getOrder()을 null을 반환한다.
![](https://images.velog.io/images/uuuuu_j_/post/86e5a9fe-5b9d-4bd3-b986-9d4a0e89eead/IMG_8679DFC32D9A-1.jpeg)
즉, SQL을 직접 다루면 처음 실행하는 SQL에 따라 객체 그래프를 어디까지 탐색할 수 있는지 정해진다.
![](https://images.velog.io/images/uuuuu_j_/post/974649a5-804b-4540-8b16-979d5b71b5c7/%EC%8A%A4%ED%81%AC%EB%A6%B0%EC%83%B7%202022-03-18%20%EC%98%A4%ED%9B%84%2010.29.42.png)
MemberService는 memberDAO를 통해 member객체를 조회했지만, 이 객체와 연관된 Team, Order, Delivery 방향으로 객체 그래프를 탐색할 수 있는지는 이 코드만 보고 전혀 예측할 수 없다! 결국 DAO 코드를 열어서 SQL를 직접 해결해야 한다.

## 5. JPA와 객체 그래프 탐색
그렇다면 JPA는 이 문제를 어떻게 해결할까?
JPA는 연관된 객체를 사용하는 시점에 적절한 SELECT SQL을 실행한다. 따라서 JPA를 사용하면 객체 그래프를 마음껏 탐색할 수 있다.**(지연로딩)**
![](https://images.velog.io/images/uuuuu_j_/post/dd64ac72-b54b-48ab-858b-3ea8ef14aaa4/IMG_4F1B9DC96A50-1.jpeg)

## 6. 비교
![](https://images.velog.io/images/uuuuu_j_/post/e67d4732-7b00-41b7-932c-d9744de8cb70/IMG_B9BC9A25CD53-1.jpeg)
member1, 2는 같은 데이터베이스 로우에서 조회했지만, 객체 측면에서 볼 때 둘은 다른 인스턴스이다.

## 7. JPA와 비교
![](https://images.velog.io/images/uuuuu_j_/post/eb61b636-a1c1-4c17-b7d3-4e158c8b7f5e/IMG_DBD17723EF6D-1.jpeg)
JPA는 같은 트랜잭션일 때 같은 객체가 조회되는 것을 보장한다. 

# 📌 JPA란 무엇인가?
JPA는 자바 진영의 ORM 기술 표준으로 애플리케이션과 jdbc 사이에서 동작한다.
![](https://images.velog.io/images/uuuuu_j_/post/ec1ab705-6abd-4b19-8b2b-c42bfaa3957a/IMG_C2A32AEB02B0-1.jpeg)
![](https://images.velog.io/images/uuuuu_j_/post/7d237a8f-5ff4-44dd-824c-66d5bc282b70/IMG_3F47C165FE3D-1.jpeg)
JPA를 사용해서 객체를 저장하는 코드는 다음과 같다.

jpa.persist(member);

조회할 때도 JPA를 통해 객체를 직접 조회하면 된다.
![](https://images.velog.io/images/uuuuu_j_/post/e81f4918-0aa6-40d1-863a-02ca996d478e/IMG_CDEF8B125EE9-1.jpeg)
JPA를 사용해서 객체를 조회하는 코드는 다음과 같다.

Member member = jpa.find(memberId);

``` ORM 프레임워크는 단순히 SQL을 개발자 대신 생성해서 데이터베이스에 전달해주는 것뿐만 아니라 패러다임 불일치 문제들도 해결한다. 따라서 객체 측면에서 정교한 객체 모델링이 가능하고, 관계형 데이터베이스는 데이터베이스에 맞도록 모델링하면 된다. 그리고 둘을 어떻게 매핑해야 하는지 매핑방법만 알려주면 된다. 즉 개발자는 객체지향 애플리케이션 개발에 더 집중할 수 있다!

이 글은 김영한님의 자바 ORM 표준 JPA 프로그래밍 책을 참고하였습니다.

print(a,b,c, sep=', ') 
    #출력 : a, b, c
print(a, end=' ')
print(b, end=' ')
print(c) #줄바꿈
    #출력 : a, b, c

2. 입력

a, b = input().split()

☀️ a, b는 문자형

a, b = map(int, input().split()

☀️ a, b는 정수형

3. 연산자

🌳 // : 몫 🌳 % : 나머지

if x>0 and x<10:
==
if 0<x<10:    #파이썬만 가능!

4. 반복문

for i in range(10,0,-1):
    print(i)
#10부터 1까지 1씩 줄임

5. 문자열

🌳 .upper() : 대문자로 반환, 기존 문자열 변하지 X 🌳 .lower() : 소문자로 반환, 기존 문자열 변하지 X 🌳 .find('a') : 문자 a에 해당하는 인덱스 반환 🌳 .count('a) : 문자 a의 등장 횟수 반환 🌳 인덱싱 : ‼️문자열 인덱싱 가능‼️ 🌳 슬라이싱 : [:2] 인덱스 0부터 1까지 뽑음 🌳 len() : 공백 포함해서 문자 개수 반환 🌳 ord('a') : ASCII 코드 반환 👉🏻 AZ : 6590 🌳 chr(65) : ASCII 번호에 해당하는 문자 출력 👉🏻 A 출력

tmp = 'AZ'
for x in tmp:
    print(x, end=' ')
#출력 : A Z

6. 리스트와 내장함수

🌳 리스트 선언

a = []
b = list()
b = list(range(1,11))

🌳 리스트 추가 🌱 .append() 🌱 .insert(3, 7) : 인덱스를 지정해서 저장(인덱스 3에 7 추가)

🌳 리스트 삭제 🌱 .pop() 🌱 .pop(2) : 인덱스 2에 해당하는 값 삭제 🌱 .remove(4) : 숫자 4 찾아서 제거

🌳 .index(5) : 숫자 5의 인덱스 값 반환 🌳 .sum(), max(), min() -> min(3,7) : 인자값 3, 7 중 최소값 반환

🌳 .sort() : 오름차순 🌳 .sort(reverse = True) : 내림차순 🌳 .clear() : 리스트 전체 삭제 🌳 슬라이싱 : a[ : 3] 0부터 2번까지 반환 🌳 .len() : 리스트 길이 반환 🌳 .enumerate() : 인덱스와 값을 튜플로 반환 -> 튜플은 인덱스 사용 가능‼️

a = [10,20,30,40]
for x in a.enumerate():    
    print(x[0], x[1])

x : (0,10), (1,20), (2,30), (3,40)
#출력 : 
0, 10
1, 20
2, 30
3, 40

7. 2차원 리스트 선언

a = [ [0]*3 for _ in range(3)]

[ [0, 0, 0], [0, 0, 0], [0, 0, 0]]

8. 람다함수(익명함수)

plus_two = lambda x: x+2
print(plus_two(1)) # 출력값 :3

☀️ lambda 매개변수 : 리턴값

a= [1, 2, 3]
print(list(map(lambda x : x+1, a)))
# 출력 : [2,3,4]

☀️ map(함수명, 자료형)

📌1. 비즈니스 요구사항과 설계

회원

• 회원은 일반과 VIP 등급으로 나뉜다.
• 회원 데이터는 자체 DB를 구출할 수 있고, 외부 시스템과 연동할 수 있다. → 미확정

주문과 할인 정책

• 회원 등급에 따라 할인 정책을 적용한다.
• 할인정책 : 모든 VIP는 1000원을 할인해주는 고정 금액 할인을 적용한다. → 변경 가능

정리 : 회원 데이터, 할인 정책은 아직 명확히 정해지지 않았다. 그렇다고 정책이 결정될 때 까지 개발을 기다릴 수 없다‼️ 이때 구현과 역할을 분리해서 이 문제를 해결할 수 있다. 즉, 인터페이스를 만들고 구현체를 언제든지 갈아끼울 수 있도록 설계하는 것이다.

📌2. 구현과 역할의 분리

• 회원 데이터는 자체 DB를 구축할 수 있고, 외부 시스템과 연동할 수 있다. → 미확정

  🌈 MemberRepository 인터페이스를 만들고 MemoryMemberRepository와 DbMemberRepository를 구현체로 설계한다!

• 할인 정책은 변경 가능성이 높다. 회사의 기본 할인 정책을 아직 정하지 않았다. → 미확정 🌈 Discount 인터페이스를 만들고 FixDiscountPolicy와 RateDiscountPolicy를 구현체로 설계한다!

🔎 코드

🌈 Grade

public enum Grade {
    BASIC,
    VIP 
}

🌈 Member

public class Member {

    private Long id;
    private String name;
    private Grade grade;

    public Member(Long id, String name, Grade grade) {
        this.id = id;
        this.name = name;
        this.grade = grade;
    }

    public Long getId() {
        return id;
    }

    public void setId(Long id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Grade getGrade() {
        return grade;
    }

    public void setGrade(Grade grade) {
        this.grade = grade;
    }
}

🌈 MemberRepository

public interface MemberRepository {

    void save(Member member);

    Member findById(Long memberId);
}

🌈 MemoryMemberRepository

public class MemoryMemberRepository implements MemberRepository{

    private static Map<Long, Member> store = new HashMap<>();

    @Override
    public void save(Member member) {
        store.put(member.getId(), member);
    }

    @Override
    public Member findById(Long memberId) {
        return store.get(memberId);
    }
}

🌈 MemberService

public interface MemberService {

    void join(Member member);

    Member findMember(Long memberId);
}

🌈 MemberServiceImpl

public class MemberServiceImpl implements MemberService {

      private final MemberRepository memberRepository = new MemoryMemberRepository();

      public void join(Member member) {
          memberRepository.save(member);
    }

      public Member findMember(Long memberId) {
          return memberRepository.findById(memberId);
    } 
}

🌈 DiscountPolicy

public interface DiscountPolicy {

    //할인된 가격 반환
    int discount(Member member, int price);
}

🌈 FixDiscountPolicy

public class FixDiscountPolicy implements DiscountPolicy {

    private int discountFixAmount = 1000; //1000원 할인

    @Override
    public int discount(Member member, int price) {
          if (member.getGrade() == Grade.VIP) {
              return discountFixAmount;
          } else {
              return 0;
        } 
   }
}

🌈 Order

public class Order {

    private Long memberId;
    private String itemName;
    private int itemPrice;
    private int discountPrice;

    public int calculatePrice() {
        return itemPrice - discountPrice;
    }

    //생성자
    public Order(Long memberId, String itemName, int itemPrice, int discountPrice) {
        this.memberId = memberId;
        this.itemName = itemName;
        this.itemPrice = itemPrice;
        this.discountPrice = discountPrice;
    }

    //게터, 세터
    public Long getMemberId() {
        return memberId;
    }

    public void setMemberId(Long memberId) {
        this.memberId = memberId;
    }

    public String getItemName() {
        return itemName;
    }

    public void setItemName(String itemName) {
        this.itemName = itemName;
    }

    public int getItemPrice() {
        return itemPrice;
    }

    public void setItemPrice(int itemPrice) {
        this.itemPrice = itemPrice;
    }

    public int getDiscountPrice() {
        return discountPrice;
    }

    public void setDiscountPrice(int discountPrice) {
        this.discountPrice = discountPrice;
    }

    @Override
    public String toString() {
        return "Order{" +
                "memberId=" + memberId +
                ", itemName='" + itemName + '\'' +
                ", itemPrice=" + itemPrice +
                ", discountPrice=" + discountPrice +
                '}';
    }
}

🌈 OrderService

public interface OrderService {
      Order createOrder(Long memberId, String itemName, int itemPrice);
}

🌈 OrderServiceImpl

public class OrderServiceImpl implements OrderService {

      private final MemberRepository memberRepository = new MemoryMemberRepository();

      private final DiscountPolicy discountPolicy = new FixDiscountPolicy();

      @Override
        public Order createOrder(Long memberId, String itemName, int itemPrice){

        Member member = memberRepository.findById(memberId);

        int discountPrice = discountPolicy.discount(member, itemPrice);

        return new Order(memberId, itemName, itemPrice, discountPrice);
      }
}

📌3. 새로운 할인 정책 개발

악덕의 기획자가 기존의 할인정책(FixDiscountPolicy)을 변경하고 싶다고 한다‼️ 우리는 객체지향 설계 원칙을 잘 준수했기 때문에 DiscountPolicy 인터페이스를 구현한 RateDiscountPolicy로 갈아 끼우면 된다.

🌈 RateDiscountPolicy

public class RateDiscountPolicy implements DiscountPolicy{

    private int discountPercent = 10;

    //할인된 가격 반환
    @Override
    public int discount(Member member, int price) {
        if(member.getGrade() == Grade.VIP) {
            return price*discountPercent/100;
        } else {
            return 0;
        }
    }
}

📌4. 새로운 할인 정책 적용과 문제점

할인 정책을 변경하려면 클라이언트인 OrderServiceImpl 코드를 고쳐야 한다.

public class OrderServiceImpl implements OrderService {
  //    private final DiscountPolicy discountPolicy = new FixDiscountPolicy();
      private final DiscountPolicy discountPolicy = new RateDiscountPolicy();
  }

🔎 문제점 발견

• 우리는 역할과 구현을 충실하게 분리했다. OK

• 다형성도 활용하고, 인터페이스와 구현 객체를 분리했다. OK

• OCP, DIP 같은 객체지향 설계 원칙을 충실히 준수했다. → 그렇게 보이지만 사실은 아니다‼️

• DIP: 주문서비스 클라이언트( OrderServiceImpl )는 DiscountPolicy 인터페이스에 의존하면서 DIP를 지킨 것 같은데?

  → 추상(인터페이스) 뿐만 아니라 구체(구현) 클래스에도 의존하고있다‼️ → 추상(인터페이스) 의존: DiscountPolicy → 구체(구현) 클래스: FixDiscountPolicy , RateDiscountPolicy

  🔎 지금까지 단순히 DiscountPolicy 인터페이스만 의존한다고 생각했다. 잘보면 클라이언트인 OrderServiceImpl 이 DiscountPolicy 인터페이스 뿐 만 아니라 FixDiscountPolicy 인 구체 클래스도 함께 의존하고 있다. 실제 코 드를 보면 의존하고 있다! DIP 위반

  • OCP: 변경하지 않고 확장할 수 있다고 했는데! → 지금 코드는 기능을 확장해서 변경하면, 클라이언트 코드에 영향을 준다! 따라서 OCP를 위반한다‼️

    

🔎 문제 해결

• 클라이언트 코드인 OrderServiceImpl 은 DiscountPolicy 의 인터페이스 뿐만 아니라 구체 클래스도 함께 의존한다.
• 그래서 구체 클래스를 변경할 때 클라이언트 코드도 함께 변경해야 한다.
• DIP 위반 → 추상에만 의존하도록 변경(인터페이스에만 의존)
• DIP를 위반하지 않도록 인터페이스에만 의존하도록 의존관계를 변경하면 된다.

→ 인터페이스에만 의존하도록 설계와 코드를 변경했다. → 그런데 구현체가 없는데 어떻게 코드를 실행할 수 있을까? → 실제 실행을 해보면 NPE(null pointer exception)가 발생한다.

🔎 최종 해결방안

이 문제를 해결하려면 누군가가 클라이언트인 OrderServiceImpl 에 DiscountPolicy 의 구현 객체를 대신 생성하고 주입해주어야 한다. → 뒤에 나올 AppConfig 클래스, 스프링 컨테이너의 역할‼️

📌5. AppConfig 등장

애플리케이션의 전체 동작 방식을 구성하기 위해, 구현 객체를 생성하고, 연결하는 책임을 가지는 설정 클래스를 만든다.

public class AppConfig {

      public MemberService memberService() {
          return new MemberServiceImpl(new MemoryMemberRepository());
        }

    public OrderService orderService() {
          return new OrderServiceImpl(new MemoryMemberRepository(),new FixDiscountPolicy());
         } 

    ...
}

⭐️ 구현 객체를 생성한다

• MemberServiceImpl
• MemoryMemberRepository
• OrderServiceImpl
• FixDiscountPolicy

⭐️ 생성한 구현 객체 인스턴스의 참조를 생성자를 통해서 주입한다.

• MemberServiceImpl가 MemoryMemberRepository를 주입
• OrderServiceImpl가 MemoryMemberRepository, FixDiscountPolicy를 주입

🌈 MemberServiceImpl 클래스의 생성자 주입

public class MemberServiceImpl implements MemberService {

        private final MemberRepository memberRepository;

                //생성자 주입 
        public MemberServiceImpl(MemberRepository memberRepository) {
            this.memberRepository = memberRepository;
}

생성자를 주입하므로서 MemberServiceImpl는 MemoryMemberRepository에 의존하지 않고, 인터페이스 MemberRepository에만 의존하므로 DIP 원칙을 준수한다!

즉, MemberServiceImpl의 생성자를 통해서 어떤 구현 객체를 주입할지는 오직 외부( AppConfig )에서 결정된다. MemberServiceImpl 은 이제부터 의존관계에 대한 고민은 외부에 맡기고 실행에만 집중하면 된다.

⭐️ 객체의 생성과 연결은 AppConfig 가 담당한다. ⭐️ DIP 완성: MemberServiceImpl 은 MemberRepository 인 추상에만 의존하면 된다. 이제 구체 클래스를 몰라도 된다. ⭐️ 관심사의 분리: 객체를 생성하고 연결하는 역할과 실행하는 역할이 명확히 분리되었다.

🌈 OrderServiceImpl의 생성자 주입

public class OrderServiceImpl implements OrderService {

      private final MemberRepository memberRepository;
      private final DiscountPolicy discountPolicy;

      public OrderServiceImpl(MemberRepository memberRepository, DiscountPolicy
  discountPolicy) {
          this.memberRepository = memberRepository;
          this.discountPolicy = discountPolicy;
      }

    ...
}

설계 변경으로 OrderServiceImpl 은 FixDiscountPolicy 를 의존하지 않는다! 단지 DiscountPolicy 인터페이스만 의존한다. OrderServiceImpl 입장에서 생성자를 통해 어떤 구현 객체가 들어올지(주입될지)는 알 수 없다. OrderServiceImpl 의 생성자를 통해서 어떤 구현 객체을 주입할지는 오직 외부( AppConfig )에서 결정한다. OrderServiceImpl 은 이제부터 실행에만 집중하면 된다.

🌈 테스트 코드

class OrderServiceTest {

      MemberService memberService;
      OrderService orderService;

      @BeforeEach
      public void beforeEach() {
          AppConfig appConfig = new AppConfig();
          memberService = appConfig.memberService();
          orderService = appConfig.orderService();
    } 
}

FetchType=LAZY 지연로딩을 사용하면 프록시 객체만 가져오기 때문에 객체를 serializer 할 때 오류가 발생한다.

📌 해결 방법

1. application 파일에 spring.jackson.serialization.fail-on-empty-beans=false 추가

1번 방법은 오류를 발생시키지 않게 할 뿐, 오류가 발생하는 근본적인 원인은 해결하지 못한다.

2. 따라서 오류가 나는 필드에 @JsonIgnore 설정하거나
3. FetchType = EAGER로 변경한다.

📌 원문

As it is correctly suggested in previous answers, lazy loading means that when you fetch your object from the database, the nested objects are not fetched (and may be fetched later when required).

Now Jackson tries to serialize the nested object (== make JSON out of it), but fails as it finds JavassistLazyInitializer instead of normal object. This is the error you see. Now, how to solve it?

As suggested by CP510 previously, one option is to suppress the error by this line of configuration:

spring.jackson.serialization.fail-on-empty-beans=false

But this is dealing with the symptoms, not the cause. To solve it elegantly, you need to decide whether you need this object in JSON or not?

1. Should you need the object in JSON, remove the FetchType.LAZYoption from the field that causes it (it might also be a field in some nested object, not only in the root entity you are fetching).

2. If do not need the object in JSON, annotate the getter of this field (or the field itself, if you do not need to accept incoming values either) with @JsonIgnore, for example:

   // this field will not be serialized to/from JSON @JsonIgnore private NestedType secret;

Should you have more complex needs (e.g. different rules for different REST controllers using the same entity), you can use jackson views or filtering or for very simple use case, fetch nested objects separately.